std :: map insert（）ヒント位置：C++ 98とC++の違い11

Question

cplusplus' entry on map::insert()「関数が挿入時間を最適化するヒントとして追加できる場所については、positionが先行するの要素を指します。「C++ 98の場合は、C++の場合には最適化が行われます」positionが要素を指している場合の場合が挿入されます。それは最後になるだろう）」

これは、私が働いているレガシーコードに豊富で、Scott Meyerの "Effective STL"の項目24の後にモデル化されたコードスニペットのパフォーマンスが、 C++ 11準拠のコンパイラ？

auto pLoc = someMap.lower_bound(someKey); 
if(pLoc != someMap.end() && !(someMap.key_comp()(someKey, pLoc->first))) 
    return pLoc->second; 
else 
    auto newValue = expensiveCalculation(); 
    someMap.insert(pLoc, make_pair(someKey, newValue)); // using the lower bound as hint 
    return newValue; 

C++ 11でこのパターンを改善するにはどうすればよいでしょうか？

Answer 1

C++ 98の仕様は、標準の欠陥です。 LWG issue 233およびN1780の説明を参照してください。

lower_boundは、指定されたキー以上のキーで最初の要素に反復子を返します。一方、upper_boundは、指定されたキーより大きなキーを持つ最初の要素に反復子を返します。それはマップにあった場合後の鍵となる要素にイテレータ - コンテナ内の指定されたキーへのキー相当がない場合、lower_boundとupper_bound同じものを返します。

だから、他の言葉では、あなたの現在のコードは、すでにC++ 11の仕様で正常に動作し、実際にはC++ 98の欠陥仕様の下に間違っているだろう。

Answer 2

はい、それが複雑に影響します。正しいヒントを与えると、insert()は一定の複雑さを償却しますが、ヒントを与えたり間違えたりすると、マップが最初から位置を検索して対数の複雑さを与えます。基本的には、地図の大きさに関係なく、一定の時間内に挿入が行われるようにするヒントがあります。悪いヒントでは、大きな地図では挿入が遅くなります。

解決策は、明らかにlower_boundの代わりにupper_boundでヒントを検索することです。

Answer 3

は、私は次のように正しいC++ 11スタイルのヒント挿入があるかもしれない思っています：幻想的な非互換性をだ

iterator it = table.upper_bound(key); //upper_bound returns an iterator pointing to the first element that is greater than key 
if (it == table.begin() || (--it)->first < key) { 
    // key not found path 
    table.insert(it, make_pair(key, value)); 
} 
else { 
    // key found path 
    it->second = value; 
}