boost/multi_index - siki@wiki - atwiki（アットウィキ）

boost > multi_index

※このページに書かれている内容は http://www.boost.org/doc/libs/1_38_0/libs/multi_index/doc/index.html を参考にしていますが、推測も多く含まれています。

概要

下図が示す通りです。詳細な説明は Boost.org にあります。
画像はBoost.orgより。

名前空間

multi_index関連のものは基本的に名前空間boost::multi_index内で定義されている。
コンテナであるmulti_index_containerは名前空間boostでusingされているので、
boost::multi_index_containerでアクセスできる。

ヘッダ

コンテナ
<boost/multi_index_container.hpp>	multi_index_containerを使用する
インデックス
<boost/multi_index/ordered_index.hpp>	setやmapのように整列されたインデックスを使用する。 ordered_unique, ordered_non_unique
<boost/multi_index/hashed_index.hpp>	ハッシュをキーに持つインデックスを使用する。 hashed_unique, hashed_non_unique
<boost/multi_index/sequenced_index.hpp>	listのような順番にアクセスするインデックスを使用する。 sequenced
<boost/multi_index/random_access_index.hpp>	vectorのようなランダムアクセスが可能なインデックスを使用する。 random_access
ソート方法
<boost/multi_index/key_extractors.hpp>	以下のヘッダ全てをインクルードする
<boost/multi_index/identity.hpp>	要素のクラス(インスタンス)同士を比較する場合に必要
<boost/multi_index/member>	要素のフィールドを比較する場合に必要
<boost/multi_index/mem_fun.hpp>	要素のメンバ関数で比較する場合に必要
<boost/multi_index/global_fun.hpp>	グローバルな関数で比較する場合に必要
<boost/multi_index/composite_key.hpp>	複数の条件で比較する( 参考 )場合に必要

コンテナ (multi_index_container)

デフォルトではstd::setのような振舞いになる。
indexed_by<>の中に使用したいインデックスを追加することで、
内部に複数のコンテナを保持しているかのように振舞うことができる。

template<
    typename Value,
    typename IndexSpecifierList=indexed_by<ordered_unique<identity<Value> > >,
    typename Allocator=std::allocator<Value> >
class multi_index_container;

インデックス

使用する側から見れば、multi_index_containerが内部に持つコンテナのようなもの。
実際は複数のコンテナを保持している訳ではない。
おそらく現在のところ、用意されているのは

ordered_unique
ordered_non_unique
hashed_unique
hashed_non_unique
sequenced
random_access

の6つ。
indexed_by<>の中に並べることで使用可能になる。

type		specifier
key-based	ordered	ordered_unique
		ordered_non_unique
	hashed	hashed_unique
		hashed_non_unique
non key-based		sequenced
		random_access

ordered_unique, ordered_non_unique

キーの値を基に自動的にソートされるインデックス。
ordered_uniqueは重複を許さない。
ordered_non_uniqueは重複を許す。

template<
    typename KeyFromValue,
    typename Compare=std::less<KeyFromValue::result_type>
>
struct (ordered_unique | ordered_non_unique);
 
template<
    typename TagList,
    typename KeyFromValue,
    typename Compare=std::less<KeyFromValue::result_type>
>
struct (ordered_unique | ordered_non_unique);

hashed_unique, hashed_non_unique

キーから作られるハッシュで管理するインデックス。いわゆる連想配列。当然、要素の順番は不定。

template<
    typename KeyFromValue,
    typename Hash=boost::hash<KeyFromValue::result_type>,
    typename Pred=std::equal_to<KeyFromValue::result_type>
>
struct (hashed_unique | hashed_non_unique);
 
template<
    typename TagList,
    typename KeyFromValue,
    typename Hash=boost::hash<KeyFromValue::result_type>,
    typename Pred=std::equal_to<KeyFromValue::result_type>
>
struct (hashed_unique | hashed_non_unique);

-	-	テンプレート引数	制限
-	-	Value
-	-	Allocator
-	-	TagList
-	-	KeyFromValue
-	-	Hash
-	-	Pred
-	可視性	ベースクラス	機能

-	可視性	型名	元の型名
-	public	key_type	KeyFromValue::result_type
-	public	value_type	Value
-	public	key_from_value	KeyFromValue
-	public	hasher	Hash
-	public	key_equal	Pred
-	public	ctor_args	tuple<size_type,key_from_value,hasher,key_equal>
-	public	allocator_type	Allocator
-	public	pointer	Allocator::pointer
-	public	const_pointer	Allocator::const_pointer
-	public	reference	Allocator::reference
-	public	const_reference	Allocator::const_reference
-	public	size_type	implementation defined
-	public	difference_type	implementation defined
-	public	iterator	implementation defined
-	public	const_iterator	implementation defined
-	public	local_iterator	implementation defined
-	public	const_local_iterator	implementation defined
静的／仮想	可視性	関数	機能
-	public	operator=()
-	public	get_allocator() const
-	public	empty() const
-	public	size() const
-	public	max_size() const
-	public	begin()
-	public	begin() const
-	public	end()
-	public	end() const
-	public	cbegin() const
-	public	cend() const
-	public	iterator_to()
-	public	iterator_to() const
-	public	insert()	modifiers:
-	public	erase()
-	public	replace()
-	public	modify()
-	public	modify_key()
-	public	clear()
-	public	swap()
-	public	key_extractor() const	observers:
-	public	hash_function() const
-	public	key_eq() const
-	public	find() const	lookup:
-	public	count() const
-	public	equal_range() const
-	public	bucket_count() const	bucket interface:
-	public	max_bucket_count() const
-	public	bucket_size() const
-	public	bucket() const
-	public	load_factor() const	hash policy:
-	public	max_load_factor() const
-	public	rehash(size_type n)

静的	可視性	フィールド	用途

クラス	可視性		機能

sequenced

std::listのように順番を保つインデックス。ソートの必要がある場合は手動で行う。

template<typename TagList=tag<> >
struct sequenced;

random_access

std::vectorのようにランダムアクセスが可能なインデックス。

template<typename TagList=tag<> >
struct random_access;

Key Extractors

キーを持つインデックス (ordered_unique, ordered_non_unique, hashed_unique, hashed_non_unique)
について、キーの指定方法を指定する。

基本的な指定方法は以下の6つ。

identity
member
const_mem_fun
mem_fun
global_fun
composite_key

identity

template<typename T> struct identity;

member, member_offset

template<class Class,typename Type,Type Class::*PtrToMember>
struct member;
 
template<class Class,typename Type,std::size_t OffsetOfMember>
struct member_offset;
 
#define BOOST_MULTI_INDEX_MEMBER(Class,Type,MemberName) implementation defined

const_mem_fun, mem_fun, const_mem_fun_explicit, mem_fun_explicit

template<class Class,typename Type,Type (Class::*PtrToMemberFunction)() const>
struct const_mem_fun;
 
template<class Class, typename Type, Type (Class::*PtrToMemberFunction)()>
struct mem_fun;
 
template<
    class Class, typename Type,
    typename PtrToMemberFunctionType, PtrToMemberFunctionType PtrToMemberFunction
>
struct const_mem_fun_explicit;
 
template<
  class Class,typename Type,
  typename PtrToMemberFunctionType,PtrToMemberFunctionType PtrToMemberFunction
>
struct mem_fun_explicit;
 
#define BOOST_MULTI_INDEX_CONST_MEM_FUN(Class, Type, MemberFunName) \
implementation defined
#define BOOST_MULTI_INDEX_MEM_FUN(Class, Type, MemberFunName) \
implementation defined

global_fun

template<class Value,typename Type,Type (*PtrToFunction)(Value)>
struct global_fun;

composite_key

template<typename Value,typename KeyFromValue0,...,typename KeyFromValuen>
struct composite_key;
 
template<typename CompositeKey>
struct composite_key_result;

その他

indexed_by

multi_index_containerが持つデータ群にアクセスする複数のインデックス(インターフェース)を持たせるために使用する。

multi_index_container<
    要素の型,
    indexed_by<
        0番目のインデックス, // 例えばsequenced<>
        1番目のインデックス, // 例えばordered_unique<...>
        ...
    >
>

tag

インデックスに任意の型のタグを設定する。
multi_index_containerはget<>()メソッドを使ってインデックスを取得できる。

typedef multi_index_container<
    要素の型,
    indexed_by<
        sequenced<>,           // 0番目のインデックス
        ordered_unique<...> // 1番目のインデックス
        ...
    >
>   Container;
 
Container container;
...
Container::nth_index<0>::type& index0 = container.get<0>();
Container::nth_index<1>::type& index1 = container.get<1>();
...

上記の例では0番目のインデックスと1番目のインデックスを取得している。
Container::nth_index<0>::type& がインデックスの型。
これはタグ付けすると以下のようになる。

typedef multi_index_container<
    要素の型,
    indexed_by<
        sequenced<tag<型A> >,            // 0番目のインデックス
        ordered_unique<tag<型B>, ...> // 1番目のインデックス
        ...
    >
>   Container;
 
Container container;
...
Container::index<型A>::type& index0 = container.get<型A>();
Container::index<型B>::type& index1 = container.get<型B>();
...

この場合、Container::index<型A>::type& がインデックスの型。
タグは型名にのみ意味を持つので、空の構造体などでもよい。

[09/02/26 21:58][履歴][編集]

タグ：

「multi_index」をウィキ内検索

最終更新：2009年02月26日 21:58

添付ファイル

multi_index_cont_example.png

siki@wiki

仕様

ドキュメント

トピック

その他

最近変更されたページ

更新履歴