値の参照という点に着目してソート済み vector、map、unordered map で簡単なベンチマークをとってみた。最初に要素は登録されていて、後は参照のみが発生するケースを想定し、1048576 = 2^20 回の参照にかかる時間を測定(5回平均)。キー、値とも int (32bit)でハッシュ関数はデフォルト、コンパイラは gcc 4.3.4 on Cygwin で最適化は -O2、CPU は C2D T7600 (2.33GHz) である。コンテナ中の要素数と、キーに対応する要素がコンテナ中にある確率(ヒット率)を変化させている。コードは末尾。コードの汚さとか非効率性は目をつぶって欲しい。

ヒット率 1.0 Google Chart グラフ

要素数        100   1000  10000 10000
sorted vector 0.134 0.213 0.303 0.390
map           0.156 0.240 0.397 0.841
unordered map 0.047 0.038 0.032 0.050

ヒット率 0.8 Google Chart グラフ

要素数        100   1000  10000 100000
sorted vector 0.153 0.222 0.309 0.425
map           0.166 0.237 0.437 0.866
unordered map 0.066 0.047 0.050 0.069

ヒット率 0.5 Google Chart グラフ

要素数        100   1000  10000 100000
sorted vector 0.157 0.219 0.281 0.531
map           0.203 0.266 0.390 0.937
unordered map 0.093 0.108 0.078 0.094

普通こういうのは考察つけてなんぼだとは思うのだが自分に言えることは少ない。とりあえずほぼ一貫して unordered map、ソート済み vector、map の順に速い。ただし百万回で一秒レベルなので用途によっては別選択肢もありか。計算量通り unordered map がほとんど要素数の影響を受けていない点が見て取れる。vector の挙動も割ときれいである。一方で map が要素数増加に従って跳ね上がってる理由はよく分からない。これだと n^0.2 くらい？

#include <iostream>
#include <tr1/unordered_map>
#include <map>
#include <vector>
#include <algorithm>
#include <utility>

#include <cmath>

#include <boost/timer.hpp>

using namespace std;
using namespace std::tr1;
using namespace boost;

typedef int Key;
typedef int Value;
typedef pair<Key, Value> Elem;

struct Less
{
    bool operator()(const Elem &p1, const Elem &p2) const {
        return p1.first < p2.first;
    }
};

struct VectorInit
{
    void operator()(vector<Elem> &v) {
        sort(v.begin(), v.end(), Less());
    }
};

struct Vector
{
    int hit;
    Vector() : hit(0) {}
    typedef vector<Elem> Container;
    typedef Container::iterator Iterator;
    void operator()(Container &c, const Value &v) {
        Iterator p = lower_bound(c.begin(), c.end(), make_pair(v, 0), Less());
        if(p != c.end() && p->first == v) ++hit;
    }
};

struct Null
{
    template<typename T>
    void operator()(T &t) {}
};

struct Map
{
    int hit;
    Map() : hit(0) {}
    typedef map<Key, Value> Container;
    typedef Container::iterator Iterator;
    void operator()(Container &c, const Value &v) {
        Iterator p = c.find(v);
        if(p != c.end()) ++ hit;
    }
};

struct UnorderedMap
{
    int hit;
    UnorderedMap() : hit(0) {}
    typedef unordered_map<Key, Value> Container;
    typedef Container::iterator Iterator;
    void operator()(Container &c, const Value &v) {
        Iterator p = c.find(v);
        if(p != c.end()) ++ hit;
    }
};

struct MakePair
{
    int n;
    MakePair() : n(0) {}
    Elem operator()() { return make_pair(n++, Value()); }
};

class Benchmark
{
    int num;
    vector<Elem> v;
    static const int tries = 1024*1024;
public:
    Benchmark(int num_, double hit_rate) : num(num_), v(num_ / hit_rate)
    {
        generate_n(v.begin(), v.size(), MakePair());
        random_shuffle(v.begin(), v.end());
    }
    template<typename C, typename F1, typename F2>
    void run(C &c, F1 init, F2 process)
    {
        double result = 0.0;
        for(int i=0;i<5;++i) {
            c.clear();
            copy(v.begin(), v.begin() + num, inserter(c, c.end()));
            init(c);
            random_shuffle(v.begin(), v.end());
            timer t;
            for(int i=0;i<tries;++i) { process(c, v[i%v.size()].first); }
            result += t.elapsed();
        }
        cout << process.hit / 5 << ':' << result / 5 << endl;
    }
};

int main(void)
{
    srand(clock());

    vector<Elem> v;
    map<int, int> m;
    unordered_map<int, int> u;

    struct { int num; double rate; } param[] = {
        { 100, 1.0 },
        { 100, 0.8 },
        { 100, 0.5 },
        { 1000, 1.0 },
        { 1000, 0.8 },
        { 1000, 0.5 },
        { 10000, 1.0 },
        { 10000, 0.8 },
        { 10000, 0.5 },
        { 100000, 1.0 },
        { 100000, 0.8 },
        { 100000, 0.5 },

        { 0, 0 }
    };

    for(int i = 0; param[i].num; ++i) {
        Benchmark bench(param[i].num, param[i].rate);
        cout << '[' << param[i].num << ':' << param[i].rate << ']' << endl;
        bench.run(v, VectorInit(), Vector());
        bench.run(m, Null(), Map());
        bench.run(u, Null(), UnorderedMap());
    }
    return 0;
}