(C++23) flat_map: シンプルだが効率的なコンテナ

■ これ書いている人

• C/C++での組込み一筋17年のexpert…だったのに、いきなり専門外の部署に飛ばされ、業務が振らず窓際族な（元）技術者
• 私生活では、OpenCV CommunityでPull Request発行しまくっているヘンな人

■ TL;DR

• C++23でサポートしているstd::flat_mapは、std::mapよりもメモリ効率も処理効率も高い連想配列です！
• メリット：KeyやValueが連続配置されており、キャッシュ効率が高いです！また、末尾追加は早いです！
• デメリット：途中要素への挿入や削除にはmapよりもコストがかかります！激遅！
• （個人的感想）組み込み分野だと、とっても素敵やん・・・

■ はじめに

C++には、たくさんのコンテナがありますね。

• 固定長配列ならstd::array、可変長配列ならstd::vector
• 連想配列ならキー重複無しのstd::mapや、重複ありのstd::multimap

std::mapであれば、データの挿入や削除、検索も早いだろう。ただ、赤黒木で実装すると、どうしてもメモリ効率やキャッシュ効率がいまいち…

boost::flat_mapを使えば、メモリ効率やキャッシュ効率が良くなるけど、そのためだけにboost導入するのはちょっとねえ…。色々悩ましいですね？

そこで今回ご紹介するのは、C++23からサポートされたstd::flat_mapでございます。

■ flat_mapとは何者か

一言でいうと、基本的にはstd::mapよりもメモリ効率・実行効率の高いコンテナですね！

std::map と違ってノードベースの実装ではなく、メモリ連続性のある平坦 (flat) な配列で扱われる。

"3 Motivation and Scope"で、このように記載されている

(和訳) C++ユーザーの間では、mapのよりメモリ効率および実行効率の高い表現に対する強い要望が、これまで長らく存在してきました。この要望がSG14メンバー間の議論を促し、論文1
、多数の記事や講演、そしてBoostによる実装であるboost::container::flat_map2
が誕生しました。C++でゲーム、組み込みソフトウェア、システムソフトウェアを開発するほぼすべての人が、Boostの実装、あるいは独自に開発した実装を使用しています。

ポイントになるのは、ここ。

(和訳) この論文の以前の改訂版では、その理由を示すベンチマーク結果が出ています。その結果、キーと値を別々のコンテナに格納した場合（少なくともキーと値の型が小さい場合）、フラットマップに要素を挿入する際の線形実行コストの約半分が回収されることが明らかになったことに注意してください。

「キーと値を別のコンテナに格納する事で、キーで探索する場合に値はキャッシュを汚染しないので、その分早く処理できる」ってことですかね。

flat_map

	idx = 0	1	2	3	4	5
std::vector<K>	1	2	5	9	11	15
std::vector<V>	1	4	25	81	121	225

flattenだけど、KeyとValueを同じメモリ空間上に配置している場合はこんな感じ。これを見ると違いが分かりやすい・・・かも？

	idx = 0	1	2	3	4	5
std::vector<pair<K,V> >	1,1	2,4	5,25	9,81	11,121,	15,225

▢ flat_mapの強み

Keyの要素を探索する場合、Keyに対する二分探索が利用できる。

例えば、11を探す場合…

Left index	Right index	Mid index	Mid Value
0	5	(0+5)/2 = 2.5 = 3	9
3	5	(3+5)/2 = 4	11

Keyは連続しているメモリ上に乗っているので、キャッシュ効率も高い。
そしてValueは全く別のメモリにあるので、Keyに対してValueが非常に大きなデータであっても、キャッシュが汚染されない、ってことですね。

▢ flat_mapの弱点

ここでKey=3,Value=9を追加しようかな・・・とした場合、vectorに対する挿入であり、計算量がO(N)になってしまう。

挿入位置を決定したら、そこから後ろを全部１つシフト

	idx = 0	1	▢	3	4	5	6
std::vector<K>	1	2	▢	5	9	11	15
std::vector<V>	1	4	▢	25	81	121	225

挿入位置に要素を入れる

	idx = 0	1	2	3	4	5	6
std::vector<K>	1	2	3	5	9	11	15
std::vector<V>	1	4	9	25	81	121	225

ということで、こりゃおそい・・・

▢ 実行結果

ふるーいPC(i7-4790K)上のubuntu 25.10で。

a.out : main.cpp
        g++ -O2 -std=c++23 main.cpp -o a.out

=== ソート済み順挿入 ===
map (sorted): 20.6444 ms
flat_map (sorted): 10.3034 ms

=== ランダム順挿入 ===
map (random): 34.6067 ms
flat_map (random): 5398.01 ms

想定通りに早いけど、遅い！！って感じになりましたね。

■ libc++の実装を確認してみる(Option)

この、_KeyContainerと_MappedContainerなんかがclass templateになって…

で、key_container_typeやmapped_container_typeとしてusingして使いまわせるようになり！

container構造体の中に、並んでいる！！まさしく想定したとおりになっていますね！

■ まとめ（再掲）

• C++23でサポートしているstd::flat_mapは、std::mapよりもメモリ効率も処理効率も高い連想配列です！
• メリット：KeyやValueが連続配置されており、キャッシュ効率が高いです！また、末尾追加は早いです！
• デメリット：途中要素への挿入や削除にはmapよりもコストがかかります！激遅！
• （個人的感想）組み込み分野だと、とっても素敵やん・・・

■ サンプルコード

メインのコンテンツが性能で、具体的な性能を自分環境でも試してもらうためのサンプルコードなのですがレギュレーション違反？ということでdetailsにしておきます。

サンプルコード

#include <iostream>
#include <map>
#include <flat_map>
#include <chrono>
#include <random>
#include <vector>

int main() {
    const int N = 100'000;
    auto start = std::chrono::high_resolution_clock::now();
    auto end = std::chrono::high_resolution_clock::now();

    // --- 1. ソート済み順で逐次挿入 ---
    std::cout << "=== ソート済み順挿入 ===\n";
    start = std::chrono::high_resolution_clock::now();
    std::map<int, std::string> m1;
    for (int i = 0; i < N; ++i) m1[i] = "x";
    end = std::chrono::high_resolution_clock::now();
    std::cout << "map (sorted): " << std::chrono::duration<double, std::milli>(end-start).count() << " ms\n";

    start = std::chrono::high_resolution_clock::now();
    std::flat_map<int, std::string> fm1;
    for (int i = 0; i < N; ++i) fm1[i] = "x";
    end = std::chrono::high_resolution_clock::now();
    std::cout << "flat_map (sorted): " << std::chrono::duration<double, std::milli>(end-start).count() << " ms\n";

    // --- 2. ランダム順で逐次挿入 ---
    std::cout << "\n=== ランダム順挿入 ===\n";
    std::vector<int> keys(N);
    std::iota(keys.begin(), keys.end(), 0);
    std::mt19937 g(42);
    std::shuffle(keys.begin(), keys.end(), g);

    start = std::chrono::high_resolution_clock::now();
    std::map<int, std::string> m2;
    for (int k : keys) m2[k] = "x";
    end = std::chrono::high_resolution_clock::now();
    std::cout << "map (random): " << std::chrono::duration<double, std::milli>(end-start).count() << " ms\n";

    start = std::chrono::high_resolution_clock::now();
    std::flat_map<int, std::string> fm2;
    for (int k : keys) fm2[k] = "x";
    end = std::chrono::high_resolution_clock::now();
    std::cout << "flat_map (random): " << std::chrono::duration<double, std::milli>(end-start).count() << " ms\n";
}