mapよりもunordered_mapを使おう

unorderedとは

要するにハッシュです。検索が早くなるので基本的にはunordered_mapを使いましょう。
mapはorderedつまり常にソートされた状態で保持されますが、これが有効に働くことは連想配列的な使い方ではまず無いでしょう。

でもkeyに複雑な値が来る場合は辛い

unordered_mapではkey値からハッシュ値が計算できないと機能しません。
その為、key値に複雑な型が来る場合はハッシュの計算仕方を教えてあげなければいけません。

#include<iostream>
#include<unordered_map>
#include<functional>

namespace torini{
    struct Key{
        int value = 0;
        
        // keyは等号を処理できなければ同じか判断できません
        bool operator==(const Key& other) const{
            return value == other.value;
        }
    };
    struct Hash{
        std::size_t operator()(const Key& key) const{
            // ここに良い感じのハッシュ関数を書きましょう
            return 0;
        }
    };
    using Map = std::unordered_map<Key, int, Hash>;
}

int main(){
    torini::Map map;
    // map.insert(std::make_pair(torini::Key(), 1));よりもオススメ
    map.emplace(torini::Key(), 1);

    // 1が出力される
    std::cout << map.find(torini::Key())->second;
}

妥協策

定義されてあるようなプリミティブな型はunordered_mapを使い、他はmapを使う。 mapで速度的な負担が計測されたらHashを書く。で良いんじゃないですかね！