趣味でc++の言語仕様のワーキンググループの解説記事を読んでたら、flat_mapっていうデータ構造を見つけて、これ使うとbook周りでもう少し効率的にできそうなので考察。

・Nをbookに登録されている局面数とします。1000万くらい
・1局面を記録するのに必要なメモリ(盤面の状態、評価値、book(完)の数など)をxとする。

今の方式だと、bookをstd::unordered_map（いわゆるハッシュ付き連想配列）で管理していて、
book読み込み:  O(1)×N局面=kN (kは定数)
1局面参照:  O(1)=k'  (k'は定数)
総メモリ:  (x+m)×N  (mはunordered_map特有のポインタなどのオーバーヘッド)

問題点は、
・xが小さいのでmの影響が無視できない（メモリを無駄に使っている）
・メモリがキャッシュに乗ってないので検索や登録が遅い(kやk'が大きい)
・【不具合？】メモリが断片化して巨大なので、しばらく放置しているとWindowsが勝手にRAMをディスクに移動してしまってswapになってしまい極端にパフォーマンスが落ちるケースがある

で、flat_mapを使った場合は、（※実際はまだflat_mapがないのでvectorに突っ込んでソートする）
book読み込み:  O(1)×N局面+ソート=k''N+NlogN  （k''はkより小さいと思う）
1局面参照:  O(logN)
総メモリ:  xN
となる。※bookは一度読み込んだら変更されないので、flat_mapの要件は満たしている。

差分は、
・vectorだと確かにメモリは局所化はするので省メモリになる
・が、メモリがキャッシュに乗るほど小さくはないので本当にパフォーマンス改善するの？
キャッシュのページングの仕様（基本情報でよく聞かれるやつ）にもよるのか？
・上記【不具合？】は改善する？
・O(1)からO(logN)に格下げされた部分は遅くならない？そもそも係数が違うのでむしろ速くなる？

正直、実装しないと分からないので、とりあえず切り替えられるように作ってみて良かったら採用しようと思います。

結論：こんなの書いてる暇あったら実装しろ

おしまい。