Какова производительность метода 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

Таким образом, это O (n) в реализации gcc. Мы заключаем, что спецификация не требует этого лучше, чем O (n). И никто в здравом уме не сделает это хуже, чем это. Затем можно смело предположить, что в худшем случае O (n). Возможно, лучше, но вы никогда не можете рассчитывать на это.

Answer 2

Я не могу быть уверен, что вы на самом деле имеете в виду под "STL", из-за преобладающего неправильного использования этого термина в сообществе C ++.

• Стандарт C ++ (2003) не дает никаких полномочий для выполнения std::bitset::count() (или, на самом деле, любых членов std::bitset, насколько я вижу).

• Я могуЯ не нахожу никаких ссылок, предлагающих мандат на выполнение STL bitset::count().

Я думаю, что любая нормальная реализация обеспечит это в постоянное (или в худшем случае линейное) время.Тем не менее, это просто чувство.Проверьте свой, чтобы узнать, что вы на самом деле получите.

Answer 3

Я не уверен, что вы найдете спецификацию для этого, поскольку STL обычно не требует определенного уровня производительности.Я видел намеки, что это «быстро», около 1 цикла на бит в размере набора.Конечно, вы можете прочитать код вашей конкретной реализации, чтобы узнать, чего ожидать.

Answer 4

"Эталонная реализация SGI выполняется за линейное время по отношению к количеству байтов, необходимых для хранения битов. Это достигается путем создания статического массива из 256 целых чисел. Значение, хранящееся в i-м индексе в массиве, представляет собойколичество битов, установленных в значении i. "

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