Boost.Intrusive
×
Boost.MultiIn dex
k.inaba (稲葉一浩)

http://www.kmonos.net/
Boost.勉強会 Dec 12, 2009

2/68

k.inaba といいます
こんなことやってます↓3/68

今日お話したい内容「僕はデータ構造が 好きです」

Boostの すごい データ構造
その１

Boost.MultiIndex

5/68

日本語で言うとMulti：複数のIndex：索引

6/68

お題：今日の発表リスト#include <list>
struct Presen {string twitterID; // ﾂｲｯﾀｰID
string hatenaID; // はてなID
string title;// 発表題目};
std::list<Presen> timeTable;

7/68

お題：今日の発表リスト作ろう#include <boost/assign.hpp>
timeTable += Presen(“cpp_akira”,“faith_and_brave”,“Boostライブラリ一週の旅”
);

8/68

お題：今日の発表リスト作ろう
timeTable += Presen(“kinaba”,“cafelier”,“Boost.MultiIntrusivedex”
);

9/68

お題：今日の発表リスト作ろう
timeTable += Presen(“melponn”,“melpon”,“Boost.Coroutine”);
・・・以下略・・・

10/68

作ったデータを使おう！
• ○○さんの発表タイトルってなんだったっけ？
twid_to_title(
timeTable,“DecimalBloat”) ==“Boost.Preprocessor”

11/68

こうだ！
#include <boost/foreach.hpp>
string twid_to_title(tt, id){BOOST_FOREACH(Presen& p, tt)
if( p.twitterID == id )return p.title;
throw std::out_of_range(id);}12/68

こうだ！
#include <boost/foreach.hpp>
string twid_to_title(tt, id){
BOOST_FOREACH(Presen& p, tt)
if( p.twitterID == id )return p.title;
throw std::out_of_range(id);}Boost
勉強会
発表者

13/68

未来予測

14/68

発表者

300億人にスケールするには？

15/68データ構造を変えれば•std::set なら、検索が速い！
struct ByTwID{ bool operator()(略) { 略 } };// std::list<Presen>
std::set<Presen,ByTwID>
timeTable;

16/68

1億倍速い！
string twid_to_title(tt, id){auto it =tt.find(Presen(twid,“”,“”));if( it != tt.end() )return it->title;
throw std::out_of_range(twid);}

17/68

1億倍速い！
string twid_to_title(tt, id){
auto it =tt.find(Presen(twid,“”,“”));if( it != tt.end() )return it->title;
throw std::out_of_range(twid);}

18/68

なんで不合格？ (1)• Twitter ID じゃなくて
はてな ID でも検索したい！
hatenaid_to_title(timeTable,“xyuyux”)== “Boost.Asio”

19/68

なんで不合格？ (2)• 発表の順番も知りたい！
BOOST_FOREACH(Presen& p, timTbl)
cout << p.title << endl;// setだとIDの順に並んでしまう// - Boost.SmartPtr:shared_ptr+weak_ptr// - Boost.Preposessor// - Boost.ライブラリ一週の旅 …

20/68

ここまでの要望をまとめる
Twitter ID で高速検索できて
はてな ID で高速検索できて表に入れた順番も覚えとけ！

21/68

そんなBoost.MultiIndex
あなたに22/68

こうだ！
入れる物はPresentypedef
multi_index_container<Presen,.twitterID でindexed_by<
検索したいordered_unique<member<Presen,string,&Presen::twitterID>>,ordered_unique<member<Presen,string,&Presen::hatenaID>>,.hatenaID でsequenced<>
検索したい>
入れた順も> MyTimeTable;

覚えといて！

23/68

mi<Presen,index<Tw,Ht,seq>>// get<0>//
twitterIDで//高速検索
timeTable.get<0>().find(“wraith13”);

24/68

mi<Presen,index<Tw,Ht,seq>>
timeTable.get<1>().find(“Cryolite”);// get<1>//
はてなIDで//高速検索

25/68

mi<Presen,index<Tw,Ht,seq>>// get<2>

入れた順

BOOST_FOREACH(const Presen& p,timeTable.get<2>())
cout << p.title << endl;

26/68

ＦＡＱ

よくある質問27/68ＦＡＱ

3つデータ構造作るのと何が違うの？

28/68

つまり、これとの違いは？
struct MyTimeTable {set<Presen, ByTwID>
tt1;
set<Presen, ByHatenaID> tt2;
list<Presen>
tt3;
void add(const Presen& p){ tt1.insert(p);tt2.insert(p);tt3.push_back(p); }};29/68

つまり、これとの違いは？
struct MyTimeTable {set<Presen, ByTwID>
tt1;
set<Presen, ByHatenaID> tt2;
list<Presen>
tt3;
void add(const Presen& p){ tt1.insert(p);tt2.insert(p);tt3.push_back(p); }};30/68

インデックスの更新「@kinaba です。用事入ったので発表キャンセル！」
tt1.erase(Presen(“kinaba”,“”,“”));tt2.erase(…略…);
tt3.erase(…略…);遅い！

31/68

インデックスの更新

MultiIndex ならtt.get<0>().erase(“kinaba”);

１行 ＆ 一瞬32/68

用意されてるインデックス
挿入

削除

機能

O(1)

set, multiset:
指定キーで検索O(1)unordered_set 等:
指定キーでハッシュ検索

O(1)

O(1)

list:
入れた順を覚える

O(1)O(後続要素数)

vector:
ランダムアクセス

ordered_unique O(log N)
ordered_non_uniquehashed_uniquehashed_non_uniquesequenced

random_accessO(1)33/68MultiIndexの便利な所まとめ• 色んなインデックスを付けられる
tt.get<0>().erase(“uskz”);
BOOST_FOREACH(p, tt.get<2>()) { … }• 整数 0, 1, 2, … でなく、タグも付けられます
struct oreore {}; // てきとうな型
multi_index_container<T,indexed_by<…, sequenced<tag<oreore>> > tt;
tt.get<oreore>();34/68MultiIndexの便利な所まとめ• 実はむしろ普通のコンテナより便利– find(key), modify(…)

set_tt.find(Presen(“uskz”,“”,“”));vsmi_tt.find(“uskz”);

Boostの すごい データ構造
その２

Boost.Intrusive
こちらｽﾈｰｸ Boostへの侵入に成功した＿＿＿＿／ ／ ／|＿|￣￣￣￣| |＿＿／ |＿＿＿＿|／ ／￣￣ |し | ￣￣し⌒Ｊ

36/68

日本語で言うとintrusive= 侵入的37/68

普通のデータ構造• 構造の管理用メンバは、外struct Presen {string twitterID;string hatenaID;
string title;};struct _List_node {_List_node* prev;_List_node* next;
Presendata;};

std::list<Presen> lst;

38/68

侵入的データ構造• 管理用メンバが、侵入
struct Presen {list_member_hook<> hook;＿＿＿＿string twitterID;／ ／ ／|＿|￣￣￣￣| |＿＿／ |＿＿＿＿|／ ／string hatenaID;￣￣ |し | ￣￣し⌒Ｊstring title;};
intrusive::list<Presen,…> lst;

39/68

メリット＆デメリット• デメリット[Bad]– データ定義がコンテナに依存しちゃう– hook を自分で置く手間がかかる• メリット[Good]– コピー不可オブジェクトも入れられる– 複数のコンテナに同時に入れられる• 実は MultiIndex 的なことができる40/68

メリット＆デメリット

今日は
細かい話はスキップ• デメリット[Bad]– データ定義がコンテナに依存しちゃう– hook を自分で置く手間がかかる• メリット[Good]– コピー不可オブジェクトも入れられる– 複数のコンテナに同時に入れられる• 実は MultiIndex 的なことができる

41/68データ構造マニア的

Boost.Intrusiveの、特徴

異様に set の種類が多い
STL

MultiIndex

vectordequeslist
list
set

random_accessunordered_set

sequenced
orderedhashedIntrusive

slist
list
set
unordered_set
avl_setsplay_set
sg_settreap_set

42/68

43/68

マニア心をくすぐるset•set
挿入:速い 検索:遅い•avl_set 挿入:遅い 検索:速い•sg_set 実行時↑ﾊﾞﾗﾝｽ切替•splay_set よく使う要素:速い•treap_set 優先度つけられる

Boostの すごい データ構造その３

まぜてみよう！
こちらｽﾈｰｸMultiIndexへの侵入に成功した＿＿＿＿／ ／ ／|＿|￣￣￣￣| |＿＿／ |＿＿＿＿|／ ／￣￣ |し | ￣￣し⌒Ｊ

45/68

すごいところ•MultiIndex は–入れるデータに手を加えずに複数のインデックス張れて凄い•Intrusive は–sg_set とか splay_set とか色々あってすごい46/68

あわせると…？
もっとすごい！

47/68というわけで目標•Intrusive を使ってMultiIndex 用インデックスavl<>
sg<>を実装します

splay<>
treap<>

48/68

インデックスの作り方調べ中…
将来やりたいなーと思ってる事• User-defined indices
ユーザもインデックスを定義できるようにする– The mechanisms by which Boost.MultiIndexorchestrates the operations of the indices held bya multi_index_container are simple enough to makethem worth documenting so that the (bold) user canwrite implementations for her own indices.

もしかして： 今はまだできない49/68

インデックスの作り方調べ中…

整理はされてる！
将来やりたいなーと思ってる事（ドキュメントないけど！）• User-defined indices
ユーザもインデックスを定義できるようにする– The mechanisms by which Boost.MultiIndexorchestrates the operations of the indices held bya multi_index_container are simple enough to makethem worth documenting so that the (bold) user canwrite implementations for her own indices.

もしかして： 今はまだできない50/68というわけで• この後の発表内容は– 私がソースから勝手に解釈した方法– 色々間違ってるかも– 将来的に色々変わるかも51/68１

そもそも複数のインデックスの実体は？

52/68class
index_node_base{ T value; }mi<T,index<Tw,Ht,Seq>>のﾉｰﾄﾞ• こんなノードクラス
class node_type {node_type*twL,*twR;
redblack twC;
node_type*htL,*htR;
redblack htC;
正確には
node_type *prev;
継承でnode_type *next;
Tvalue;}class {
seqnode* next;
seqnode* prev; }class {
htnode *L, *R;
redblack C; }class node_type {node_type *L,*R;
redblack C; }

53/68２

俺々ノードの実装

54/68intrusive::sg_set の場合• 親ｸﾗｽを外から指定可にする
template<typename Super>
struct my_node : public Super{
sg_set_member_hook<> hook_;};あとは好きなように実装

コンストラクタ
呼ばれないので注意55/68

３

次にインデックス本体の実体

class (順番保存用) : …
{ push_back,begin,end, … }protected
class (はてなID検索用) : …
{ find,erase,begin,end, … }protected

56/68

これも継承
protected
class index_base{…}class (TWitterID検索用):…
{ find,erase,begin,end, … }publicclass multi_index_container : … {public:}twIndex& get<0>() { return *this; }htIndex& get<1>() { return *this; }seqIndex& get<2>() { return *this; }57/68４

俺々インデックスの実装

58/68intrusive::sg_set の場合• 親ｸﾗｽを外から指定可にする
template<class Meta, class Tag>
struct my_index: protected Meta::type{ // ここで必須typedefを大量定義// ここで必須メソッドを実装する

sg_set<my_node<…>> impl_;};
あとは好きなように実装

59/68５

次にコンテナ的メソッドの実装

60/68例

pop_back(最後の要素を消す)

61/68class my_index : … {いろいろなインデックス
void pop_back() {{ my_node* p = 気合い;
final_erase_(p); }class index_base {void erase_(my_node* p)final_erase_(p){{ impl_.erase(気合(p));((mi*)this)->erase_(p);super::erase_(p); }}}}いろいろなインデックス

class multi_index_container : …
{ void erase_(node* p){super::erase_(p);} }62/68実装に使えるメソッド•
•
•
•
•
•
•
•
••
•
•
•

bool
final_empty_()size_t final_size_()size_t final_max_size_()pair<fnode*,bool> final_insert_(value)pair<fnode*,bool> final_insert_(value, fnode*)
void final_erase_(fnode*)
void final_delete_node_(fnode*)
void final_delete_all_nodes_()void final_clear_()void final_swap_(final&)bool final_replace_(value, fnode*)bool final_modify_(MODIFIER mod, fnode*)bool final_modify_(MODIFIER mod, ROLLBACK back, fnode*)63/68

実装しないといけないメソッド• void copy_(const self&,const copy_map_type&)• node* insert_(value, node*)• node* insert_(value, node* position, node*)• void erase_(node*)• void delete_node_(node*)• void delete_all_nodes_()• void clear_()• void swap_()• bool replace_(value, node*)• bool modify_(node*)• bool modify_rollback_(node*)

64/68

６

最後にIndexSpecifier65/68IndexSpecifierって何？
multi_index_container<Presen,indexed_by<ここに並べるもの>>66/68IndexSpecifierって何？
multi_index_container<Presen,indexed_by<use_my_index<>>indexed_by<ここに並べるもの>> template<typename Tag=tag<>>struct use_my_index {template<typename Super>
struct node_class{ typedef my_node<Super> type; };template<typename Meta>
struct index_class{ typedef my_index<Meta,Tag> type; }};67/68７

完成！

68/68Thank You for Listening!
＿＿＿＿／ ／ ／|＿|￣￣￣￣| |＿＿／ |＿＿＿＿|／ ／￣￣ |し | ￣￣し⌒Ｊ

http://github.com/kinaba/mint