結論

unordered_map の方が速いこともあるし、 map の方が速いこともある。

やったこととやってないこと

やったこと

C++11 で、std::map<std::string, int> と std::unordered_map<std::string, int> の emplace をたくさん呼んで、その部分の時間を測定するコードを書いた。
キーはランダムな文字列。長さはコマンドライン引数で指定
emplace する要素の数は、コマンドライン引数で指定
上記コードからできたバイナリをたくさん呼んで csv化するスクリプトを ruby で書いた。
上記コードで出来上がった csv をグラフにするスクリプトを R で書いた。
全部実行した。

やってないこと

emplace 以外の操作の時間を測ること
<std::string, int> 以外のテンプレートパラメータについての調査
ランダムな文字列以外のキーについての調査
ランダムな順序以外での挿入

実験に使ったソースコード

まずは C++11 のコード。

c++11

// clang++ -std=c++11 -O2 bench.cpp -o bench
# include <iostream>
# include <chrono>
# include <map>
# include <unordered_map>
# include <string>
# include <vector>
# include <cstdlib>
# include <random>

char randchar()
{
  static std::mt19937_64 rng(0xbeef);
  std::uniform_int_distribution<> dist(1, 255);
  return static_cast<char>(dist(rng));
}

std::vector<std::string>
prepare(int len, int count)
{
  std::vector<std::string> r;
  r.reserve(count);
  for (int vi = 0; vi < count; ++vi)
  {
    std::string s;
    s.reserve(len);
    for (int si = 0; si < len; ++si)
    {
      s += randchar();
    }
    r.push_back(std::move(s));
  }
  return r;
}

template <typename map_t>
void run(int len, int count)
{
  using mapped_type = typename map_t::mapped_type;
  std::vector<std::string> srces = prepare(len, count);
  auto start = std::chrono::high_resolution_clock::now();
  map_t map;
  for (auto &&s : srces)
  {
    map.emplace(std::move(s), mapped_type());
  }
  auto end = std::chrono::high_resolution_clock::now();
  std::cout
      << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() * 1e-3
      << "ms"
      << std::endl;
}

int main(int argc, char const *argv[])
{
  char type = *argv[1];
  int len = std::atoi(argv[2]);
  int count = std::atoi(argv[3]);
  switch (type)
  {
  case 'm':
    run<std::map<std::string, int>>(len, count);
    break;
  case 'u':
    run<std::unordered_map<std::string, int>>(len, count);
    break;
  default:
    std::cout << "unexpected type" << std::endl;
  }
}

上記のソースをコンパイルした結果を、ruby で走らせる：

ruby2.5

require "csv"

def run( t, len, count )
  r = %x( ./bench #{t} #{len} #{count} ).gsub( /ms\s*/, "" )
  [t, len, count, r]
end

N=16

def out(csv,data)
  csv << %w( len count u m )
  data[0].zip(data[1]).each do |a,b|
    csv << [ a[1], a[2], a[3], b[3] ]
  end
end

CSV.open( "len.csv", "w" ) do |csv|
  data = %w( u m ).map do |t|
    N.downto(6).map do |e|
      p e
      run(t, (10**(e/3.0)).round, 1000) # 平準化のために走らせる
      run(t, (10**(e/3.0)).round, 1000)
    end
  end
  out(csv,data)
end

CSV.open( "count.csv", "w" ) do |csv|
  data = %w( u m ).map do |t|
    N.downto(6).map do |e|
      p e
      run(t, 10, (10**(e/3.0)).round) # 平準化のために走らせる
      run(t, 10, (10**(e/3.0)).round)
    end
  end
  out(csv,data)
end

そして出来上がった CSV を R でグラフにする

R

pdf("len.pdf", width=8, height=5) # 8×5 inch
dt<-read.csv("len.csv")
plot(
  dt$len,dt$m,
  col="red",
  type="o",
  pch=20,
  log="xy",
  xlab="string length",ylab="time(ms)",
  ylim=c(0.1,30))
lines(dt$len,dt$u,col="blue",type="o",pch=20,xlab="foo",ylab="hoge")
legend("bottomright", legend=c("map", "unorderd_map"),pch=20,col=c("red","blue"),lwd=1,lty=1)
dev.off()

pdf("count.pdf", width=8, height=5) # 8×5 inch
dt<-read.csv("count.csv")
plot(
  dt$count,dt$m,
  col="red",
  type="o",
  pch=20,
  xlab="item count",ylab="time(ms)",
  log="xy",
  ylim=c(0.01,200))
lines(dt$count,dt$u,col="blue",type="o",pch=20,xlab="foo",ylab="hoge")
legend("bottomright", legend=c("map", "unorderd_map"),pch=20,col=c("red","blue"),lwd=1,lty=1)
dev.off()

測定結果

結果その1 - 文字列長を変えて、要素数固定

キーになる文字列の長さを変えて測定。要素数は 1000 で固定。

両対数グラフ注意。

今回の実験ではランダムな文字列を使っている。
map の場合は比較ができればよい。比較の場合最初の数文字を見ればいいだけなので、文字数が多くなっても比較に要する時間は変わらない。
したがって、mapの方は文字列長の影響を受けない。
※ グラフがデコボコしていて気持ち悪けど、気にしないことにした。

一方unorderd_mapの場合、Hash値を計算するために文字列を最後まで舐める必要がある（と思われる）。そのため、文字列が長くなると遅くなる。

予想通りの結果だった。

結果その2 - 要素数を変えて、文字列長固定

キーになる文字列は 10文字固定。要素数を変えて測定。

両対数グラフ注意。

unordered_map の方が速いものの、その差は1〜1.8倍程度。要素数が多くなっても差が開くことはなかった。
差が開くと予想していたので、予想は外れた。

まとめ

文字列が長い要素がたくさんある（そして、最初の数文字を見れば比較が終わる事が多い）場合は、map の方が速くなりがち。
それ以外の場合は、unordered_map の方が速くなりがち。
今回の実験は、ランダムなキーをランダムな順序で挿入している。それ以外のパターンについては今回の実験からはわからない。