Итерация через boost :: dynamic_bitset

Question

У меня есть boost dynamic_bitset , из которого я пытаюсь извлечь установленные биты:

boost::dynamic_bitset<unsigned long> myBitset(1000);

Моей первой мыслью было сделать простой цикл «dump» для каждого индекса и спросить, установлен ли он:

for(size_t index = 0 ; index < 1000 ; ++index)
{
   if(myBitset.test(index))
   {
      /* do something */
   }
}

Но потом я увидел два интересных метода, find_first() и find_next(), которые, как я думал, наверняка предназначены для этой цели:

size_t index = myBitset.find_first();
while(index != boost::dynamic_bitset::npos)
{
        /* do something */
        index = myBitset.find_next(index);
}

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

Итак, использование find_first() и find_next() лучший способ перебрать dynamic_bitset, или есть другой способ?

Answer 1

find_first и find_next - самый быстрый способ. Причина в том, что они могут пропускать весь блок (из dynamic_bitset::bits_per_block битов, возможно, 32 или 64), если ни один из них не установлен.

Обратите внимание, что dynamic_bitset не имеет итераторов , поэтому он будет вести себя немного не на C ++, несмотря ни на что

Answer 2

Зависит от вашего определения правильнее .Правильный метод, вероятно, должен давать правильные результаты на всех допустимых входах и быть достаточно быстрым.

find_first и find_next существуют для того, чтобы их можно было оптимизировать для сканирования целых блоков битов в одном сравнении.Если, скажем, блок имеет длину 64 бита без знака, то при сравнении одного блока анализируется 64 бита за раз, где простой цикл, как вы выложили, будет выполнять для этого 64 итерации.