STL bitset :: count()方法的性能如何？

Question

我四处搜索,找不到bitset :: count()的性能时间规范.有人知道它是什么(O(n)或更好)以及在哪里找到它？

编辑按STL我只参考标准模板库.

Answer 1

我在我的电脑上读到了这个文件(C:\ cygwin\lib\gcc\i686-pc-cygwin\3.4.4\include\c ++\bitset).
看到这些

/// Returns the number of bits which are set.
size_t
count() const { return this->_M_do_count(); }      

size_t
_M_do_count() const
{
  size_t __result = 0;
  for (size_t __i = 0; __i < _Nw; __i++)
  __result += __builtin_popcountl(_M_w[__i]);
  return __result;
}

顺便说一下,这是指定_Nw的地方:

  template<size_t _Nw>
    struct _Base_bitset

因此它在gcc实现中是O(n).我们得出结论,规范并不要求它比O(n)更好.在他们正确的思想中没有人会以比这更糟的方式实施它.然后我们可以安全地假设它最坏的是O(n).可能更好,但你永远不能指望它.