読者です 読者をやめる 読者になる 読者になる

ゆとりーなの日記

日記的な事を書いて行くと思はれる

mapの要素operator[]は更新のとき、insertは要素の追加の時に使うのがいい

C++のmapについてのめも - ichirin2501's diaryに便乗です。簡単に言うとEffective STLにこの辺の話が詳しく載っているのでそれの宣伝です。

Effective STL―STLを効果的に使いこなす50の鉄則
Effective STL―STLを効果的に使いこなす50の鉄則スコット メイヤーズ Scott Meyers

ピアソンエデュケーション 2002-01
売り上げランキング : 71311


Amazonで詳しく見る
by G-Tools
C++関連のEffectiveシリーズはMoreを除き翻訳はいい感じなので、STLの教科書的な位置づけでこの本もあると便利です。「俺はSTLなぞ使わん。Range派だ!」って人も多分アルゴリズムイテレータの組を置き換えて読めばいいだけなので少し落ち着きましょう。
で、本題ですが、mapのoperator はmapにキーがあるかどうかを調べて、あればそのキーに対応するオブジェクトの参照を返して、なければデフォルトコンストラクタでオブジェクトを作ってそれの参照を返すという挙動になります。
operator
ではこのキーがなければデフォルトコンストラクタでオブジェクトを作るってのが場合に因ってはネックになります。これを使って要素を追加しようとすると、クラスでいうといわば初期化子を使わずにコンストラクタの中身でオブジェクトを初期化している感じに近いことが起きる感じですかね。
一方で、更新のときはoperator []の方が効率がよくなります。構文的にもinsertを使えば

foo_map.insert(std::make_pair(hoge, huga)).first->second = hage;

と書かなければならず気持ち悪いですし、何よりもpairを作るのが無駄なんですね。
最後に、insertには挿入位置のヒントがあれば(正しければ)挿入が定数時間になるという仕様があるらしいです。他の部分は以前に読んだときに何となく覚えていたのですが、この部分は何故か頭に残っていませんでした。
詰まりこの様に書けば、

const auto lb = foo_map.lower_bound(hoge);
foo_map.insert(lb, std::make_pair(hoge, hage));

単純にこれよりも

foo_map.insert(std::make_pair(hoge, hage));

効率がいいということらしいです。まぁヒントが正しくなければ意味ないみたいですが。
Effective STLが出た当時と比べると、C++0x時代ではautoが使えるようになるので色々な意味で恵まれた環境になってきてることが実感できますね。
せっかくなのでVC++2010でも簡単な時間計測をしてみます。先ずは追加。

#include <iostream>
#include <map>
#include <boost/progress.hpp>
#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/irange.hpp>

int main() {
  std::map<int, int> map1;
  std::map<int, int> map2;
  std::map<int, int> map3;
  {
    const boost::progress_timer timer;
    boost::for_each(boost::irange(0, 1000000), [&map1](const int i) {
      map1[i] = i;
    });
  }
  {
    const boost::progress_timer timer;
    boost::for_each(boost::irange(0, 1000000), [&map2](const int i) {
      map2.insert(std::make_pair(i, i));
    });
  }
  {
    const boost::progress_timer timer;
    boost::for_each(boost::irange(0, 1000000), [&map3](const int i) {
      const auto it = map3.lower_bound(i);
      map3.insert(it, std::make_pair(i, i));
    });
  }
  return 0;
}

リリースビルドで試したらどれも0.28sと全然差が出ませんでした。恐るべし最適化。
続いて更新。

#include <iostream>
#include <map>
#include <boost/progress.hpp>
#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/irange.hpp>

int main() {
  std::map<int, int> map;
  {
    boost::for_each(boost::irange(0, 1000000), [&map](const int i) {
      map[i] = 0;
    });
  }
  {
    const boost::progress_timer timer;
    boost::for_each(boost::irange(0, 1000000), [&map](const int i) {
      map[i] = i;
    });
  }
  {
    const boost::progress_timer timer;
    boost::for_each(boost::irange(0, 1000000), [&map](const int i) {
      map.insert(std::make_pair(i, i)).first->second = i;
    });
  }
  return 0;
}

こちらだと前者は0.13s、後者は0.18sとoperator []の方が速くなりました。
追記:
元記事の時間計測コードの趣旨を読み違えてたみたいなので追加。

#include <iostream>
#include <map>
#include <boost/progress.hpp>
#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/irange.hpp>

int main() {
  std::map<int, int> map1;
  std::map<int, int> map2;
  {
    boost::for_each(boost::irange(0, 1000000, 2), [&map1, &map2](const int i) {
      map1[i] = i;
      map2[i] = i;
    });
  }
  {
    const boost::progress_timer timer;
    boost::for_each(boost::irange(0, 1000000), [&map1](const int i) {
      map1.insert(std::make_pair(i, i));
    });
  }
  {
    std::map<int, int>::iterator it;
    const boost::progress_timer timer;
    boost::for_each(boost::irange(0, 1000000), [&map2, &it](const int i) {
      it = map2.lower_bound(i);
      map2.insert(it, std::make_pair(i, i));
    });
  }
  return 0;
}

これで大丈夫ですかね。lower_boundなしが0.18sでありが0.30sという結果になってしまいましたが。map使いまわし疑惑を受けて二つ用意しましたが結果はあまり変らず。因みに元記事はg++使用だと勝手に思ったので手元のg++4.5.1でも試してみたところ0.77s、0.72sとlower_boundありの方が若干速くなりましたが、-O3付けたらどっちも0.24sになりました。
更に追記:
このままだとlower_boundさんが残念な扱いをされかねないのでもう一つ簡単な測定を。

#include <iostream>
#include <map>
#include <boost/progress.hpp>
#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/irange.hpp>

int hoge(std::map<int, int> &map, const int i) {
  if (map.count(i)) {
    return map[i];
  } else {
    const int temp = i * 2;
    map.insert(std::make_pair(i, temp));
    return temp;
  }
}

int hage(std::map<int, int> &map, const int i) {
  const auto it = map.lower_bound(i);
  if (it != map.end() && !(map.key_comp()(i, it->first))) {
    return it->second;
  } else {
    const int temp = i * 2;
    map.insert(it, std::make_pair(i, temp));
    return temp;
  }
}

int main() {
  std::map<int, int> map1;
  std::map<int, int> map2;
  {
    boost::for_each(boost::irange(0, 1000000, 2), [&map1, &map2](const int i) {
      map1[i] = i;
      map2[i] = i;
    });
  }
  {
    const boost::progress_timer timer;
    boost::for_each(boost::irange(0, 1000000), [&map1](const int i) {
      hoge(map1, i);
    });
  }
  {
    const boost::progress_timer timer;
    boost::for_each(boost::irange(0, 1000000), [&map2](const int i) {
      hage(map2, i);
    });
  }
  return 0;
}

キーが関連付ける値が既にあればそれを、なければ新しく挿入したものを返すみたいな関数です。前者は単純にcountでキーがあるか調べてあればそれの関連する値、なければキーと値を挿入して挿入した値を返しています。元の記事でもありますがこれには無駄な探索が含まれています。そういうときにlower_boundを使うと無駄な探索が減って幸せになれるんです。多分。この例では前者はVC++2010リリースが0.36s、g++4.5.1-O3で0.32s、後者はVC++2010リリースが0.20s、g++4.5.1-O3で0.23sとlower_boundの有意義っぷりが発揮されてます。