ブーストを反復:: dynamic_bitset

Question

は、私は、設定されたビットを抽出しようとしていますboost dynamic_bitsetを持っているから：

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

場合は私の最初の考えは、各インデックスを通じて、単純な「ダンプ」ループを行うと尋ねることでした

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

をしかし、私は、私は確かに考えて2つの興味深い方法、find_first()とfind_next()は、この目的のために意味された見ました：それが設定された

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

いくつかのテストを実行しましたが、2番目の方法が効率的だと思われますが、これはこの繰り返しを実行する別の「より正確な」方法がある可能性があります。ドキュメンテーション内で、セットビットを反復する正しい方法を示す例や注釈を見つけることができませんでした。

したがって、find_first()とfind_next()を使用してdynamic_bitsetを繰り返し処理する最善の方法、または別の方法がありますか？

Answer 1

find_firstおよびfind_nextが最も速い方法です。その理由は、ブロックが1つも設定されていない場合は、ブロック全体（dynamic_bitset::bits_per_blockビット、おそらくは32または64）をスキップできます。

注：dynamic_bitsetdoes not have iteratorsだから、それは少しun-C++の 'ish何があっても動作します。

Answer 2

の定義によりより正確です。。正しい方法は、おそらくすべての有効な入力に対して正しい結果をもたらし、十分に速くなければなりません。

find_firstおよびfind_nextがあるので、1つの比較でビットブロック全体をスキャンするように最適化することができます。ブロックが64ビットの符号なしロングの場合、1ブロックの比較で64ビットが一度に解析され、投稿されたような単純なループで64回繰り返されます。