scorrendo un boost :: dynamic_bitset

Question

Ho un boost dynamic_bitset che sto cercando di estrarre i bit impostati da:

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

Il mio primo pensiero è stato quello di fare un semplice 'discarica' loop attraverso ogni indice e chiedere se è stato impostato:

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

ma poi ho visto due metodi interessanti, find_first() e find_next() che ho pensato di sicuro sono stati pensati per questo scopo:

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

Ho eseguito alcuni test e sembra che il secondo metodo sia più efficiente, ma questo mi preoccupa che potrebbe esserci un altro modo "più corretto" per eseguire questa iterazione. Non ero in grado di trovare alcun esempio o note nella documentazione che indica il modo corretto di scorrere i bit impostati.

Quindi, sta usando find_first() e find_next() il modo migliore per scorrere su un dynamic_bitset, o c'è un altro modo?

Answer 1

find_first e find_next sono il modo più veloce. Il motivo è che questi possono saltare un intero blocco (di dynamic_bitset::bits_per_block bit, probabilmente 32 o 64) se nessuno di essi è impostato.

Si noti che dynamic_bitsetdoes not have iterators, quindi si comporterà un po 'un-C++' ish non importa quale.

Answer 2

A seconda della definizione di più corretta. Un metodo corretto probabilmente deve fornire risultati corretti su tutti gli input validi ed essere abbastanza veloce.

find_first e find_next ci sono in modo che possano essere ottimizzati per scansionare interi blocchi di bit in un confronto. Se un blocco è, per esempio, un unsigned long di 64 bit, un confronto a blocchi analizza 64 bit in una volta, in cui un ciclo diretto come quello che hai postato farebbe 64 iterazioni per quello.