Recommended
More Related Content
What's hot
What's hot (20)
Viewers also liked
Viewers also liked (20)
Similar to クソザコ鳥頭が非順序連想コンテナに入門してみた
Similar to クソザコ鳥頭が非順序連想コンテナに入門してみた (20)
Recently uploaded
Recently uploaded (9)
クソザコ鳥頭が非順序連想コンテナに入門してみた
- 2. で、お前だれよ？ 2
- 3. で、お前だれよ？ ■名前 ⇒刈谷 満（鳥頭かりやマン） ■職業 ⇒働かないタイプの社畜（老い先短い） ■普段使用してる言語 ⇒ ExcelHogan（好きとは言ってない） ■好きな言語 ⇒ C++、Perl5（できるとは言ってない） 3
- 5. 何でクソザコが発表してんの？ ※ 意味 てめぇ、ありがたくも cpprefjp 編集させて やってるんだから Boost.勉強会で発表ぐ らいしろやゴルァ！ せっかく cpprefjp で unordered やったんだから、 Boost.勉強会で発表でも どうですか？※ 5
- 7. 非順序連想コンテナとは？ • 今すぐ使用すべき 連想界のスーパーコンテナ • 速い（検索が） • 小さい（メモリ使用量が） • 長い（名前が） ※連想コンテナ比 ※ ※ ※ 7
- 9. 非順序連想コンテナって どんな構造？ 非順序連想コンテナ鉄の掟 1. 非順序連想コンテナの要素は「bucket」に 分けて入れられる。 2. 同じハッシュコードのキーは同じ「bucket」 に現れる。 3. 要素が追加されると「bucket」の数は自動 で増えるので、「bucket」あたりの平均要 素数は限度以下に保たれる。 from C++規格書勝手訳 9
- 11. bucket？ bucket 【可算名詞】 バケツ; 手おけ; つるべ. from 研究社 新英和中辞典 11
- 14. 非順序連想コンテナって どんな構造？ バケツが何個かあって… bucket_count() = 3, size() = 0 (empty()) ０ １ ２ 14
- 16. 非順序連想コンテナって どんな構造？ ハッシュ値に従って選ばれた バケツに入れる！ size() = 1 ０ １ ２ この場合、 ハッシュ値「55」を バケツ数「3」で割った 余り「1」に 16
- 19. 非順序連想コンテナって どんな構造？ 同じバケツに入れるのです！ size() = 3 ０ １ ２ ハッシュ値「20」を バケツ数「3」で割った 余り「2」に 19
- 20. 非順序連想コンテナって どんな構造？ ちなみに、バケツ要素数を得る bucket_size() ってのがあって ０ １ ２ ０ １ ２ 20
- 21. 非順序連想コンテナって どんな構造？ バケツ内だけのイテレータも取れる ０ １ ２ 最初は begin(2), cbegin(2) 最後は end(2), cend(2) 例によって最後の 要素の一つ先 でもぶっちゃけ 使い道が わからん… 21
- 26. 非順序連想コンテナって どんな構造？ バケツあたりの平均要素数は、 要素数４／バケツ数３＝１．３３３３… size() / bucket_count() これは load_factor() で得られる。 ０ １ ２ 26
- 28. 非順序連想コンテナって どんな構造？ バケツが自動で増える！（リハッシュと言う） bucket_count() = 4 （普通はバケツ数もっと増えます…） ０ １ ２ ３ リハッシュで バケツが別れた リハッシュされたら バケツが分かれた 仲良しハッシュ値が 同じなのでリハッシュ されてもバケツが 一緒なのです！ 28
- 30. 非順序連想コンテナって どんな構造？ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ これ を こう するのは結構大変なので、あらかじめ バケツ数を増やしておくこともできる。 ０ １ ２ ０ １ ２ ３ 30
- 31. 非順序連想コンテナって どんな構造？ n 個以上バケツを確保しておく。 rehash(n) リハッシュされずに n 個の要素が 格納できるだけのバケツを確保しておく。 reserve(n) 31
- 32. 非順序連想コンテナって どんな構造？ n 個以上バケツを確保しておく。 rehash(n) リハッシュされずに n 個の要素が 格納できるだけのバケツを確保しておく。 reserve(n) が！ 32
- 33. 非順序連想コンテナって どんな構造？ ちょっと規格に問題があって、 reserve(n) だと n 個の要素が格納できない… （LWG Issue 2156） n を 1 つ増やしておくと良さそう… cpprefjp の unordered_*::reserve にも書いてあるので見てみてください… http://cpprefjp.github.io/reference/unordered_set/unordered_set/reserve.html 33
- 34. 非順序連想コンテナって どんな構造？ あと、max_load_factor() も デフォルトの1.0 以外を指定できる！ max_load_factor(float) でも、必ず指定した値になるとは限らないし、 特に要素格納してから設定するといろいろ トラブるもとになるから、気をつけよう！ cpprefjp の unordered_*::max_load_factor にも書いてあるので見てみてください… http://cpprefjp.github.io/reference/unordered_map/unordered_multimap/max_load_factor.html 34
- 46. で、実際のところ 実装はどうなってんの？ じゃあこんな感じ？ from CodeZine のJavaセキュアコーディング入門 各バケツの最後の 要素は次のバケツの 最初の要素を指す libstdc++ 4.6.x までは この時点でもうダメっぽい… 頼むよ GCC… 46
- 49. で、実際のところ 実装はどうなってんの？ 例えばこの状態で… from CodeZine のJavaセキュアコーディング入門 これを… こうしなきゃ ならない… このバケツに 追加すると… 49
- 55. で、実際のところ 実装はどうなってんの？ たとえば erase(const key_type&) from CodeZine のJavaセキュアコーディング入門 ココをキー指定で 削除したいときは… キーから ハッシュ値を計算して ここからたどって… 55
- 56. で、実際のところ 実装はどうなってんの？ たとえば erase(const key_type&) from CodeZine のJavaセキュアコーディング入門 一つ前のポインタを 修正しなきゃならないけど… 要素を削除して… どうやって 逆向きに たどるねん… 56
- 68. で、実際のところ 実装はどうなってんの？ こんな感じ？ from CodeZine のJavaセキュアコーディング入門 ダミー バケツ配列 へのポインタ バケツ数 要素数 最大負荷率 ハッシュ関数 オブジェクト キー比較関数 オブジェクト アロケータ オブジェクト 実際のところ、これら３つは 大抵状態を持たないので、 空基底最適化によって サイズを0にしている実装もある （EBO：Empty Base Optimization） 68
- 71. で、実際のところ 実装はどうなってんの？ 対象 libc++ 3.0～3.8(Clang) libstdc++ 4.6.4～6.0.0(GCC) boost.unordered 1.47～1.59 いずれも、long とポインタが64bitのケース （LP64モデル） 71
- 73. で、実際のところ 実装はどうなってんの？ 基本 ハッシュや キー比較に 8バイト アロケータに 8バイト 全部に 8バイト (計24バイト) libc++ 3.0～3.8 40 48(+8) 56(+16) 72(+32) libstdc++ 4.6.4 56 72(+16) 64(+8) 88(+32) libstdc++ 4.7.0～4.7.4 64 72(+8) 64(+0) 80(+16) libstdc++ 4.8.0～4.9.0 48 56(+8) 56(+8) 72(+24) libstdc++ 4.9.1～6.0 56 64(+8) 64(+8) 80(+24) boost 1.47 56 80(+24) 72(+16) 104(+48) boost 1.48～1.51 40 72(+32) 56(+16) 96(+48) boost 1.52～1.59 48 72(+24) 64(+16) 96(+40) 結果、こうなりました。 73
- 74. で、実際のところ 実装はどうなってんの？ 基本 ハッシュや キー比較に 8バイト アロケータに 8バイト 全部に 8バイト (計24バイト) libc++ 3.0～3.8 40 48(+8) 56(+16) 72(+32) libc++ 3.0～3.8 EBOも効いててだいたい順当。 ただし、アロケータは、バケツ配列用と ノード用の2つ持ってる。 （両方はいらないと思うんだけど…） 74
- 75. で、実際のところ 実装はどうなってんの？ libc++ 3.0～3.8 こんな イメージ です (カッコ内はバイト数) バケツ配列へのポインタ(8) バケツ配列用アロケータ(0, 8) バケツ数(8) ノード用アロケータ(0, 8) ダミーノード(8) ハッシュ関数オブジェクト(0, 8) 要素数(8) キー比較関数オブジェクト(0, 8) 最大負荷率(4) ココでEBO ココでEBO ココでEBO ココでEBO 75
- 76. で、実際のところ 実装はどうなってんの？ 基本 ハッシュや キー比較に 8バイト アロケータに 8バイト 全部に 8バイト (計24バイト) libstdc++ 4.9.1～6.0 56 64(+8) 64(+8) 80(+24) libstdc++ 4.9.1～6.0 EBOは効いてるけど、基本がデカい。 1. floatの計算を極力避けるため、次にリ ハッシュが起きる要素数を持ってる。 2. バケツ数が0になるのを避けるため、要素 数1のバケツ配列を持ってる。 76
- 77. で、実際のところ 実装はどうなってんの？ libstdc++ 4.9.1～6.0 こんな イメージ です (カッコ内はバイト数) ハッシュ関数オブジェクト(0, 8) キー比較関数オブジェクト(0, 8) アロケータオブジェクト(0, 8) バケツ配列へのポインタ(8) バケツ数(8) ダミーノード(8) 要素数(8) 最大負荷率(4) 次にリハッシュされる要素数(8) 1要素のバケツ配列(8) ココと 自クラスと でEBO 77
- 79. で、実際のところ 実装はどうなってんの？ 基本 ハッシュや キー比較に 8バイト アロケータに 8バイト 全部に 8バイト (計24バイト) boost 1.52～1.59 48 72(+24) 64(+16) 96(+40) boost.unordered 各関数オブジェクトがデカい。 1. ハッシュとキー比較を2セットと、使ってる側フラ グを持ってる。（強い例外保証のためらしい…） 2. アロケータも、バケツ配列用とノード用の2つ 持ってる。（両方は(ry） 3. 次にリハッシュが起きる要素数を持ってる。 79
- 80. で、実際のところ 実装はどうなってんの？ boost 1.52～1.59 こんな イメージ です (カッコ内はバイト数) どっちの関数使ってるフラグ(1) ハッシュ関数1(0, 8)、キー比較関数1(0, 8) ハッシュ関数2(0, 8)、キー比較関数2(0, 8) バケツ配列用アロケータ(0, 8) ノード用アロケータ(0, 8) バケツ数(8) 要素数(8) 最大負荷率(4) 次にリハッシュされる要素数(8) バケツ配列へのポインタ(8) ココでEBO ココでEBO ココでEBO それぞれは 両方0でも 0にはならない あれ？ ダミーノード が無い… 80
- 81. で、実際のところ 実装はどうなってんの？ boost 1.52～1.59 こんな イメージ です (カッコ内はバイト数) どっちの関数使ってるフラグ(1) ハッシュ関数1(0, 8)、キー比較関数1(0, 8) ハッシュ関数2(0, 8)、キー比較関数2(0, 8) バケツ配列用アロケータ(0, 8) ノード用アロケータ(0, 8) バケツ数(8) 要素数(8) 最大負荷率(4) 次にリハッシュされる要素数(8) バケツ配列へのポインタ(8) ココでEBO ココでEBO ココでEBO それぞれは 両方0でも 0にはならない あれ？ ダミーノード が無い… バケツ配列の 最後の要素を ダミーノードとして 使ってるっぽい… 81
- 83. で、実際のところ 実装はどうなってんの？ ノードサイズ libc++ 3.0～3.8 24 libstdc++ 4.6.4～6.0 16 boost 1.47 16 boost 1.48～1.59 24 結果、こうなりました。 あれ？ 要素（int）と ポインタと… あと何？ ハッシュ値 でした… 83
- 84. で、実際のところ 実装はどうなってんの？ つまり、 1. libc++ と boost 1.48以降はハッシュ値は 一度計算するとノードに保存しとく。 2. libstdc++ と boost 1.47 は毎回計算する。 と、思ったら、libstdc++ 4.8.0 以降については、 マニュアルに記載がありました！ 84
- 85. で、実際のところ 実装はどうなってんの？ libstdc++ 4.8.0 以降では、以下のいずれか が満たされれば、ハッシュ値がノードに保存 される。 1. ハッシュ関数の operator() が noexcept じゃない。 2. std::__is_fast_hash<hasher> が std::false_type を 継承している。 （デフォルトは std::true_typeを継承） https://gcc.gnu.org/onlinedocs/gcc-4.8.0/libstdc++/manual/manual/unordered_associative.html 85
- 86. で、実際のところ 実装はどうなってんの？ ちなみに、GCC 4.6.x と 4.7.x については、 制御する方法は無いっぽい… もしあったら教えてください。 内部実装を直接使えば制御できるっぽいけど… 86
- 91. 中身はだいたい分かった。 で、使い方は？ あと、連想コンテナには無い メンバ関数もいくつかあるけど、 （バケツ系とか）、 あんまり使う気がしない… せいぜい、rehash と reserve ですかね… （最初の方で説明した奴） 91
- 92. 中身はだいたい分かった。 で、使い方は？ 連想コンテナ • 双方向イテレータ • 昇順にならんでる • 変更操作でイテ レータが無効にな らない 非順序連想コンテナ • 前方向イテレータ • 順序って何？ • 変更操作でイテ レータが無効にな るかも(リハッシュ) イテレータにはこんな違いが… 92
- 93. 中身はだいたい分かった。 で、使い方は？ あ！ C++14 で連想コンテナに追加された、 異種混合比較※は、 非順序連想コンテナには 無いです！（残念！） ハッシュ値が必要だから仕方ないね… ※ string がキーのコンテナを検索する時に、const char* 渡したりする奴 http://faithandbrave.hateblo.jp/entry/20131121/1385013127 93
- 94. 中身はだいたい分かった。 で、使い方は？ 要素追加時にも ちょっとした違いが… insert(const_iterator it, ...); emplace_hint(const_iterator it, ...); ⇓ it は意味なし！ 94
- 95. 中身はだいたい分かった。 で、使い方は？ 要素追加時にも ちょっとした違いが… insert(const_iterator it, ...); emplace_hint(const_iterator it, ...); ⇓ it は意味なし！ どっちにしろ、 ハッシュ値からたどる 必要があるので… 95
- 96. 中身はだいたい分かった。 で、使い方は？ 最後に、 せっかく要素追加が出てきたので、 insert と emplace の使い分けを。 （連想コンテナと一緒だけど…） 96
- 97. 中身はだいたい分かった。 で、使い方は？ emplace すごいよね！ コンテナ内に直接構築できるし！ じゃあ下の例だったらどれ使う？ 1. c[key] = value; 2. c.insert(make_pair(key, value)); 3. c.emplace(key, value); 97
- 98. 中身はだいたい分かった。 で、使い方は？ 1. c[key] = value; ① keyが既にコンテナにある時は、 値が value で上書かれる。 ② key がまだコンテナに無い時は、 デフォルト値で新規ノード作っちゃう。 98
- 99. 中身はだいたい分かった。 で、使い方は？ 1. c[key] = value; ① keyが既にコンテナにある時は、 値が value で上書かれる。 ② key がまだコンテナに無い時は、 デフォルト値で新規ノード作っちゃう。 新規ノード作る時に、 まずデフォルトコンストラクタで value の型の要素を構築してから value を代入することになる ⇓ 型によっては効率悪い そんなん百も 承知ですよね… 99
- 100. 中身はだいたい分かった。 で、使い方は？ 2. c.insert(make_pair(key, value)); ① key が既にコンテナにある時は、 値は上書かれない。 ② key がまだコンテナに無い時だけ、 ノードが新規に作られる。 何を当たり前の ことを… 100
- 101. 中身はだいたい分かった。 で、使い方は？ 3. c.emplace(key, value); ① key が既にコンテナにある時は、 値は上書かれない。（insert と一緒） ② key の有無に関わらず、 ノードが新規に作られるかも… 101
- 102. 中身はだいたい分かった。 で、使い方は？ 3. c.emplace(key, value); ① key が既にコンテナにある時は、 値は上書かれない。（insert と一緒） ② key の有無に関わらず、 ノードが新規に作られる、かも… えっ！？ 102
- 106. 中身はだいたい分かった。 で、使い方は？ ちなみに、unordered_multimap とかは 必ず追加だから平気な模様。 あと、boost.unordered は、 emplace の最初の引数の型が key の型と一致する場合には、 ノード構築前に 重複チェックしてくれる模様。 106
Editor's Notes
- 自主クソザコ枠
- 某主催者に誘われたから
- メンバ関数 バケツ数：bucket_count() 要素数：size()
- 最大消費量
- 最大消費量
- 最大消費量
- 最新版を基準に時折過去のバージョンも…
- 実際、1件ずつ insert して言った後、イテレータで全要素を出力すると、追加した逆順で出力される
- libstdc++ のコメントに、vector と forward_list をくっつけた物って書いてあった…
- 規格によれば、要素数は計算量が定数時間じゃなきゃダメ
- 違うのもいるけど…
- 各実装の最新版について、ちょっと説明
- libstdc++ と同じ理由だと思うが、次にリハッシュが起きる要素数を持ってる。
- int は 4 バイトだけど、ポインタが 8 バイトなので、アラインメントの関係で16バイトになる。
- 内部実装の__unordered_set とかを使えば可能っぽい… 試してない…
- これだけじゃあんまりなので…
- よく見る（？）、各メンバに std::hash を適用した結果を xor するのはダメらしい…
- バケツ系とか、使い道がわからない… 逆に連想コンテナにはある、一部のメンバ関数は無い lower_bound、upper_bound とか…
- 男は後ろを振り向かない
- アキラさんのブログに記事があるよ！
- EMC++ にも、ちまつと触れられてる…