10

stackOverflow std::map insert または std::map find?で次の質問に出くわしました 。

find() の使用が lower_bound() + key_comp() よりも劣っていると見なされるのはなぜですか?

次のマップがあるとします

map<int, int> myMap;
myMap[1]=1; 
myMap[2]=3;
myMap[3]=5;
int key = xxx; //some value of interest.
int value = yyy;

提案された答えは使用することです

map<int, int>::iterator itr = myMap.lower_bound(key);
if (itr != myMap.end() && !(myMap.key_comp()(key, itr->first)))
{
    //key found. 
    // do processing for itr->second
    // 
}else {
    //insert into the end position 
    myMap.insert (itr, map<int, int>::value_type(key, value));
}

なぜそれは次よりも優れているのですか？

map<int, int>::iterator itr = myMap.find(key);
if (itr != myMap.end())
{
    //key found. 
    // do processing for itr->second
    // 
}else {
    //insert into the end position 
    myMap.insert (itr, map<int, int>::value_type(key, value));
}
4

1 に答える 1

13

2 番目のケースでは、値を挿入する必要がある場合、反復子は常に であることに注意してくださいmyMap.end()。これは、挿入操作のパフォーマンスを向上させるのに役立ちません (もちろん、新しい要素が最後に挿入される場合を除きます)。コンテナーは、新しいノードを挿入する正しい位置を見つける必要があります。これは通常、O(log N) です。

を使用すると、新しい要素を挿入するコンテナの最適なヒントがすでに見つかりました。これは、最初の手法が提供する最適化の機会ですlower_bound()。これにより、O(1) に近いパフォーマンスが得られる可能性があります。追加のキー比較がありますが、それは O(1) でもあります (コンテナーの観点から)。

最初のfind()との両方lower_boundが O(log N) であるため、最初の手法では O(log N) に加えて 2 つの O(1) 演算が行われ、2 番目の手法では 2 つの O(log N) 演算が行われます。

于 2013-11-01T08:42:32.337 に答える