O Boostマルチインデックスコンテナ

multi_index_containerのようなすばらしいBoostモジュールを紹介したり、思い出させたいと思います。 リスト、ベクター、マップなどのデータを保存およびアクセスするために、標準のSTLクラスを知っており、集中的に使用していますか？ それらについてはすでに多くのことが言われており、アプリケーションのすべての機能が調査されています。



クラスが複数のキーまたはそれらの組み合わせを使用してオブジェクトを保存およびアクセスする必要がある場合、事態は複雑になります。 通常、2つのマップまたはハッシュを作成することから始まり、その数が増えるとすべてがより複雑になり、これらのハッシュを同期、挿入、削除、および名前変更するためのコードのより複雑なセクションがあり、この操作またはその操作のコストを理解することは非常に困難になります。 そしてもちろん、そのような自転車の作成は、多くのバグ、最適化の必要性などにつながります。



もちろん、私たちの前にすべてがすでに発明されており、Boostライブラリにはすでにこれらの問題を解決するためのモジュールがあります-boost :: multi_index。 大きな利点は速度であり、multi_indexは非常に高速です。 ただし、このモジュールのドキュメントは理解するのが難しく、初心者はこのモジュールをバイパスしようとします。 そしてもちろん、multi_index_containerを使用する際のエラーに関するコンパイラメッセージについて個別に言うことができます-誰もがテンプレートに関する長いメッセージを理解できるわけではありません。



このギャップを埋めて、この強力なツールのホットスタートと使用の簡単な例を示します。 例ではQtと一緒に少し使用します。 （独自のテンプレートシステムを備えたQtでは、multi_indexに匹敵するプリミティブが見落とされることがよくあります）





フィールドを持つ小さな構造があるとしましょう：

struct Rec { QString name, phone, addr; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

multi_indexは、キーにタグ/（ドック内のタグ）を使用する非常に便利な機会を提供します。

それらがコードに沿わないようにRecで直接定義します：

 struct Rec { QString name, phone, addr; struct ByName {}; struct ByPhone {}; struct ByAddr {}; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次の配列を作成できます。

 typedef boost::multi_index_container<Rec, indexed_by< ordered_unique< tag<Rec::ByName>, member<Rec,QString,&Rec::name> >, ordered_non_unique< tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone> >, ordered_non_unique< tag<Rec::ByAddr>, member<Rec,QString,&Rec::addr> > > > Store;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

記録は名前（名前）で一意であるが、住所や電話で一意ではないことを受け入れます。 名前の一意性は、同じ名前の2つのレコードを配列に追加できないという事実にもあります。

 { Store store; Rec r1 = { "Basilio Pupkinio", "022", "Neron st" }; qDebug() << "ok1" << store.insert(r1).second; // ok1 true qDebug() << "ok2" << store.insert(r1).second; // ok2 false }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

私にとって、配列自体が重複の出現を許可しないことは重要な利便性であり、それにアクセスするとき、私はアプリオリに内容の正確さに頼ることができます。



名前でエントリを検索します。

 { QString find_id = "Basilio Pupkinio"; typedef Store::index<Rec::ByName>::type List; const List & ls = store.get<Rec::ByName>(); List::const_iterator it = ls.find(find_id); if ( it != ls.end() ) { qDebug() << (*it).addr; // "Neron st" } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

電話番号022のレコードが複数ある場合

 { Store store; Rec r1 = { "Basilio Pupkinio", "022", "Pushkina st" }; Rec r2 = { "Vasya Pupkin", "022", "Around st" }; store.insert(r1) store.insert(r2) }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、電話022ですべてのレコードを検索します

 { QString find_phone = "022"; Store::index<Rec::ByPhone>::type::iterator it0, it1; tie(it0,it1) = store.get<Rec::ByPhone>().equal_range(find_phone); while(it0 != it1) { qDebug() << (*it0).name; ++it0; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

電話と住所の組み合わせによる検索に興味がある場合はどうなりますか？

このブロックを使用して、配列に複合インデックスを追加できます。

  ordered_non_unique< tag<Rec::ByKey>, composite_key< Rec, member<Rec,QString,&Rec::phone>, member<Rec,QString,&Rec::addr> > >,
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

（さらに、ラベルstruct ByKey {}を追加することを忘れないでください。）

 { Rec r1 = { "Basilio Pupkinio", "022", "Pushkina st" }; Rec r2 = { "Vasya Pupkin", "022", "Around st" }; Rec r3 = { "Vasilisa Pupkina", "022", "Around st" }; store.insert(r1); store.insert(r2); store.insert(r3); { QString find_phone = "022"; QString find_addr = "Around st"; Store::index<Rec::ByKey>::type::iterator it0, it1; tie(it0,it1) = store.get<Rec::ByKey>().equal_range(make_tuple(find_phone, find_addr)); while(it0 != it1) { qDebug() << (*it0).name; ++it0; } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

繰り返しますが、複合キーの場合、ordered_non_uniqueとordered_uniqueの両方を使用できることを理解しています。

このように、許可されたキーの内容とその組み合わせにいくつかの追加条件を課すことは非常に便利です。配列自体は「間違った」オブジェクトを追加することを許可しません。

配列にベクトルとして同時にアクセスできるようにする場合は、random_accessを簡単に追加できます。

 typedef boost::multi_index_container<Rec, indexed_by< random_access<>, ordered_unique< tag<Rec::ByName>, member<Rec,QString,&Rec::name> >, ordered_non_unique< tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone> > > > Store;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

その後、ストア[0]など、push_back（）としてアクセスできます。

O（1）キーですばやくアクセスするために配列をハッシュとして使用したいが、挿入/削除によりO（log（n））よりも遅い場合、ordered_unique / ordered_non_uniueの代わりにhashed_unique / hashed_non_uniqueを使用できます：

 typedef boost::multi_index_container<Rec, indexed_by< hashed_non_unique< tag<Rec::ByName>, member<Rec,QString,&Rec::name> >, ordered_non_unique< tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone> > > > Store; std::size_t hash_value(QString x) { return qHash(x); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

また、複合キーにhashed_uniqie / hashed_non_uniqueを使用することもできます。



レコードの変更について。

オブジェクトのフィールドは配列のインデックスと同期する必要があるため、オブジェクトのフィールドのみを変更することはできません。 いずれかのエントリの電話を変更する必要があるとします。 キーをオブジェクトと同期するには、ファンクターを介してこの変更を行う必要があります。

 struct Rec { QString name, phone, addr; struct ByName {}; struct ByPhone {}; struct ByAddr {}; struct PhoneChange : public std::unary_function<Rec,void> { QString p; PhoneChange(const QString &_p) : p(_p) {} void operator()(Rec & r) { r.phone = p; } }; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

名前で配列を検索し、名前でイテレータを取得し、project（）を使用して電話でイテレータに変換し、ファンクタを使用してオブジェクトと配列を変更します。

 { Store store; Rec r1 = { "Basilio Pupkinio", "021", "Around st" }; Rec r2 = { "Vasya Pupkin", "022", "Around st" }; Rec r3 = { "Vasilisa Pupkina", "022", "Around st" }; store.insert(r1); store.insert(r2); store.insert(r3); QString find_id = "Basilio Pupkinio"; typedef Store::index<Rec::ByName>::type NList; typedef Store::index<Rec::ByPhone>::type PList; NList & ns = store.get<Rec::ByName>(); PList & ps = store.get<Rec::ByPhone>(); NList::const_iterator nit = ns.find(find_id); if ( nit != ns.end() ) { PList::const_iterator pit = store.project<Rec::ByPhone>(nit); ps.modify(pit, Rec::PhoneChange("022")); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

インデックスの使用はフィールドに限定されません。たとえば、クラスメソッドを使用することもできます。

 struct Rec { QString n, phone, addr; QString name() const { return n; } struct ByName {}; struct ByPhone {}; }; typedef boost::multi_index_container<Rec, indexed_by< hashed_unique< tag<Rec::ByName>, const_mem_fun<Rec,QString,&Rec::name> >, ordered_non_unique< tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone> > > > Store;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ポインターの使用についても言及する必要があります。

 struct Rec { QString n, phone, addr; QString name() const { return n; } struct ByName {}; struct ByPhone {}; }; typedef boost::shared_ptr<Rec> Rec_ptr; typedef boost::multi_index_container<Rec_ptr, indexed_by< hashed_non_unique< tag<Rec::ByName>, const_mem_fun<Rec,QString,&Rec::name> >, ordered_non_unique< tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone> >, hashed_non_unique< tag<Rec::ByKey>, composite_key< Rec, member<Rec,QString,&Rec::phone>, member<Rec,QString,&Rec::addr> > >, ordered_non_unique< tag<Rec::ByAddr>, member<Rec,QString,&Rec::addr> > > > Store;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

残りのロジックはほぼ同じままです（代わりに->のみ。数箇所）。

 { QString find_phone = "022"; Store::index<Rec::ByPhone>::type::iterator it0, it1; tie(it0,it1) = store.get<Rec::ByPhone>().equal_range(find_phone); while(it0 != it1) { qDebug() << (*it0)->name(); ++it0; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

さらに、たとえばブロックを追加する価値があります

  ordered_unique< tag<Rec::ByPtr>, const_mem_fun<Rec_ptr,Rec *,&Rec_ptr::get> >,
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

重複するポインターの追加を除外します。



その結果、アクセスが非常に効率的で相互接続されたデータ構造を構築することができます。たとえば、スマートポインタによって、各操作で1つまたは別のデータにアクセスするコストを非常に簡単に予測できます。 ある意味では、multi_index_containerは、事前定義されたキーを使用してアクセスするための非常に高速なメモリ内データベーステーブルと考えることができます。



簡単な例で、この素晴らしいツールを使用して「ホットスタート」の機会を提供したいと考えています。元のドキュメントを調査し、multi_indexを使用してテンプレートに関するコンパイラエラーを解析しようとすると、初心者に大きな失望を引き起こし、別のことをしようとするためです。 いつものように判明しました。