Optimized C++ ―最適化、高速化のためのプログラミングテクニック

228

10 章　データ構造を最適化する

10.6.1

　

std::map

での挿入削除

ベクトルから

10

万個のランダムな要素を

std::map

にイテレータで挿入するには

33.8

ミリ秒か

かった。

マップへの挿入は、マップの内部木を走査して挿入点を探し出す必要があるので、通常

O(log

2

n)

になる。このコストの高さから、

std::map

には、どの点で挿入するのがより効率的かの

ヒントを示すもう

1

つのイテレータを取る

insert()

が別途用意されている。ヒントが最適なら、

挿入コストはならし

O(1)

になる。

挿入点のヒントには良いことと悪いこととがある。良いのは、ヒント付き挿入が通常の挿入より

コストが低いことだ。悪いことは、挿入ヒントの最適値が

C++11

で変更になったことだ。

C++11

以前は、挿入ヒントの最適値は、新要素の前の位置、すなわち、要素が整列順で挿入されるなら、

前の挿入の位置だった。

C++11

以降では、最適挿入ヒントは新要素の後の位置、すなわち、要素

が整列順で挿入されるなら、位置のヒントは

end()

であるべきだ。前に挿入された要素を最適位置

にするために、プログラムは整列済み入力を例

10-2

に示すように逆順でイテレーションすべきだ。

例

10-2

 

C++11

スタイルのヒントを使った整列済みベクトルからの挿入

ContainerT test_container;

std::vector<kvstruct> sorted_vector;

...

std::stable_sort(sorted_vector.begin(), ...