STL bitset::count() 方法的性能如何? [英] What is the performance of STL bitset::count() method?

问题描述

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

I searched around and could not find the performance time specifications for bitset::count(). Does anybody know what it is (O(n) or better) and where to find it?

编辑 STL 我只指标准模板库.

EDIT By STL I refer only to the Standard Template Library.

推荐答案

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

I read this file (C:\cygwin\lib\gcc\i686-pc-cygwin\3.4.4\include\c++\bitset) on my computer.
See these

/// 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 的地方:

BTW, this is where _Nw is specified:

  template<size_t _Nw>
    struct _Base_bitset

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

Thus it's O(n) in gcc implementation. We conclude the specification doesn't require it better than O(n). And nobody in their right mind will implement it in a way worse than that. We can then safely assume that it's at worst O(n). Possibly better but you can never count on that.

这篇关于STL bitset::count() 方法的性能如何?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！