What is the effectiveness of the STL bitset :: count () method?

Question

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

EDIT STL I refer only to the standard template library.

Answer 1

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; } 

By the way, _Nw is indicated here:

  template<size_t _Nw> struct _Base_bitset 

So O (n) in the gcc implementation. We conclude that the specification does not require it better than O (n). And no one in their right mind will realize it in much worse than that. Then we can safely assume that it is in the worst case O (n). Perhaps better, but you can never count on it.

Answer 2

I can't be sure what you really mean by "STL" here because of the prevailing abuse of the term in the C ++ community.

• The C ++ (2003) standard does not give any permissions for the performance of std::bitset::count() (or, in fact, any members of std::bitset , as far as I can see).

• I cannot find any links offering a mandate to execute STL bitset::count() .

I think that any reasonable implementation will provide this in a constant (or in the worst case) time. However, this is just a feeling. Check yours to find out what you actually get.

Answer 3

"The SGI reference implementation is performed in linear time with respect to the number of bytes needed to store the bits. It does this by creating a static array of 256 integers. The value stored in the i-th index in the array is the number of bits set to I."

http://www.cplusplus.com/forum/general/12486/

Answer 4

I'm not sure that you will find a specification for this, since STL usually does not require a certain level of performance. I saw tips that it is "fast", about 1 cycle per bit in a given size. Of course, you can read your implementation code to find out what to expect.