24項 効率を重視するときは、map::operator[]とmap::insertの選択に注意しよう

Effective STL

効率を重視するときは、map::operatorとmap::insertの選択に注意しよう



map::operatorは、mapにキーが有るかどうか調べ、あれば値を更新し、なければ要素を追加します。

class Widget{
public:
	Widget();
	Widget(double weight);
	Widget &operator=(double weight);
};

...

map<int Widget> m;
m[1] = 1.50;

キーが無く要素を追加する時、"m[1] = 1.50"は下の振る舞いになります。

typedef map<int, Widget> IntWidgetMap;
pair<IntWidgetMap::iterator, bool> result = 
　　　　m.insert(IntWidgetMap::value_type(1, Widget())); // Widgetのデフォルトコンストラクタを呼び出し、
　　　　　　　　　　　　　　　　　　　　　　　　　       //一時的なオブジェクトを作成

result.first->second = 1.50; //result.firstはIntWidgetMap::iterator 値はinsertされた場所
　　　　　　　　　　　　　   //result.first->secondで insertされたIntWidgetMap::value_typeのsecondの一時的なオブジェクト
			     //それに1.50を代入

この振る舞いには無駄が多いです。
pairのコンストラクタが"pair():first(), second(){}"なのでデフォルトコンストラクタで一時オブジェクトを作る必要がありますし、最後の代入も無駄です。

この無駄なコストを避けるには、単純にinsertを呼び出します。

m.insert(IntWidgetMap::value_type(1, 1.50);

こうすれば、一時的なオブジェクトの作成と代入演算子の呼び出しが避けられます。



キーが有り、値を更新するときは、map::operator[]のほうが高速になります。
insertで値を更新するときは、下のようなコードになります。

m.insert(IntWidgetMap::value_type(k, v).first->second = v; //kの値をvにする

map::operatorが値を更新するときは、その値を書き換えるだけですが、insertを使うとpairの一時的なオブジェクトを作成する必要があります。



効率を重視するとき、要素を追加するにはinsertを、要素を更新するときにはmap::operatorを使う必要があります。
これを簡単に行うには、下のような関数を定義します。

template<typename MapType,
         typename KeyArgType,
         typename ValueArgType>

typename MapType::iterator
efficientAddOrUpdate(MapType &m,
                     const KeyArgType &k,
                     const ValueArgType &v)
{
　　　　typename MapType::iterator lb =
　　　　　　　　m.lower_bound(k);　　　　//kの場所を探索

　　　　if(lb != m.end() &&
　　　　　　　　!(m.key_comp()(k, lb->first))) { //更新
　　　　　　　　lb->second = v;
　　　　　　　　return lb;
　　　　}
　　　　else {　　　　　　　　　　　　　　　　　 //追加
　　　　　　　　typedef typename MapType::value_type MVT;
　　　　　　　　return m.insert(lb, MVT(k,v));
　　　　}
}

...

map<int Widget> m;
efficientAddOrUpdate(m, 10, 1.5);