iteración a través de un impulso :: dynamic_bitset

Question

Tengo una boost dynamic_bitset que yo estoy tratando de extraer los bits fijados a partir de:

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

Mi primera idea era hacer un simple 'volcar' bucle a través de cada índice y preguntar si que se estableció:

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

Pero entonces vi dos métodos interesantes, find_first() y find_next() que pensé con certeza estaban destinados para este fin:

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

Realicé algunas pruebas y parece que el segundo método es más eficiente, pero esto me preocupa que podría haber otra forma "más correcta" de realizar esta iteración. No pude encontrar ningún ejemplo o nota en la documentación que indique la forma correcta de iterar sobre los bits establecidos.

Entonces, ¿está utilizando find_first() y find_next() la mejor manera de iterar sobre dynamic_bitset, o hay otra manera?

Answer 1

find_first y find_next son la manera más rápida. La razón es que estos pueden omitir un bloque completo (de dynamic_bitset::bits_per_block bits, probablemente 32 o 64) si ninguno de ellos está configurado.

Tenga en cuenta que dynamic_bitsetdoes not have iterators, por lo que se comportará un poco un-C++ 'ish no importa qué.

Answer 2

Depende de su definición de más correcto. Un método correcto probablemente debe arrojar resultados correctos en todas las entradas válidas y ser lo suficientemente rápido.

find_first y find_next están ahí para que puedan optimizarse para escanear bloques enteros de bits en una comparación. Si un bloque es, digamos, un largo sin signo de 64 bits, una comparación de bloque analiza 64 bits a la vez, donde un bucle directo como el que publicaría haría 64 iteraciones para eso.