平らな地図、もといflat_map
この記事は C++ Advent Calendar 2021 の8日目です。
ブログもAdvent Calendarも、ものすごく久しぶりになってしまいました。あの頃カラオケで規格書を開いて語り合っていた面子も見なくなり、最近の新しい仕様はよくわからないです。歳をとったものです。
(Unordered) Associative Containers
言語によって連想配列、マップ、ハッシュなどと呼ばれていますが、C++標準ライブラリでは std::(unordered_)map が用意されています（細かいバリエーションの話なのでmultiやらsetやらは省略します）。これは内部的には赤黒木であったり、ハッシュのリストに更に線形コンテナが生えていたりと、端的に言ってメモリ上のあっちこっちに要素が配置されたりします。
参考
www.slideshare.net
また、イテレータの走査というところに注目すると、std::mapは要素が順番に並んでいることが保証されています*1が、std::unordered_mapではそのようなことはありません。更にメモリ上でどのように配置されているかは（アロケータを自分で用意するなら別ですが）わからないので、なんにも考えないで走査するとものすごいコストを払うことになる場合があります。そもそもmapを走査するなよ（真顔）。
www.slideshare.net
flat map
古くから人々はソート済みで一意な要素列を手に入れるためにstd::mapを使っていますが（使うなよ）、本質的にやっていることは std::stable_sort して std::unique するだけのことのはずです。そうじゃなくてちゃんとmapとして使いたいけど、パフォーマンス上の理由で間接参照をできるだけ減らしたいパターンがあったりします。
例えばとても小さい要素をkey-valueとするようなmapの場合、適当な要素のlookupのためにpage cacheやTLB、LL/2/1Cをものすごく汚す場合あって悲しくなってしまいます。つまり、ちょっとしたコンテナを頻繁にlookupする場合において、できるだけキャッシュにヒットしたり、read-ahead cacheのprefetchを抑えたりしたいときには、隣接要素は近い場所にあったほうが有利になるわけです。
これは std::map や std::unordered_map の構造では抑制するのが難しいアクセスパターンになります。そういった場合には線形コンテナ上に二分探索木を構築することで効率的なlookupを実現するようにします。これを一般にflat_mapといいます。
flat_mapは構築や挿入削除よりも参照の比が大きい場合（特に最初に1回だけ構築してあとは参照だけのようなパターン）には効果的ですが、挿入削除等のほうが支配的になる場合には、線形コンテナの再配置のコストの方が支配的になるので逆にパフォーマンスが低下するという特徴があります（ただ、１ページに全部が収まるとかだと割と速い気もするしちゃんと計測はしてください）。
手で書くには
flat_mapは今の所標準で提供されていないので、手で実装するには std::vector や std::deque 上に std::stable_sort や std::unique、std::lower_boundといったアルゴリズムを駆使してソート済みコンテナを構築します。
作った
でもアルゴリズムを駆使したソート済みコンテナは単純に読みづらくて他の人に理解してもらうのは大変です。なので書きました。
flat_mapの主な実装方法には2つあって、 std::vector<std::pair<Key, Value>> 的なものと、std::pair<std::vector<Key>, std::vector<Value>>的なものです。私が実装したものは前者で、これが一番楽なのでそうしています。拡張すると後者の実装もできなくはないのですが、C++標準が要求するIterator Requirementsを満たさなくなるので、標準アルゴリズムに適用できなくてあんまり嬉しくなかったので諦めました*2。
C++17のstd::mapのインターフェイスを備えていて、単純に置き換えて動作するはずです。
パフォーマンス
実際のところ、あんまりパフォーマンス測定はしていないので微妙ですが、とりあえずわかっていることとしてはmergeはだいぶパフォーマンスが悪いです。だれか虐めてくれると嬉しいです。
マージやソートを一回でまとめてやるアルゴリズムを考えて実装してみたけど、どうにもなんにも考えないでソートしたほうが早くなったというのもありだいぶ辛いです。まぁちゃんとしたベンチマークケース考えるわけではないので一般化すると実は良かったりするのか？C++なんもわからん。 github.com
その他の実装
flat_mapは古くから知られているコンテナなので、何も私が初めて実装したわけではなく、有名所の実装がいくつかあります。
とはいえこれらのライブラリはそもそもがでかいのであんまり使いたくないというのもあります。
また、標準にも提案がされているようですが、これは前述の2通りある実装のうち、後者のようで、やっぱりコンテナ要求を満たせなくてうまくいっていないようです？（最近の標準周りよくわかってないので、実は解決されてるかもしれないです）。
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0429r0.pdfwww.open-std.org
まとめ
*1:仕様が直接順番に並べるとは書いていなかったはずですが、各要件を整理していくと順番に並べる以外の方法が無くなります。 [追記]ピンポイントな要件が書いてある部分を指摘してもらいました。
Associative Container のイテレータの走査において要素が順番に並んでいることはこの辺りに書いてありませんか？https://t.co/clb2zLlTuY
— 夜糸 (@yaito3014) 2021年12月8日
