3

問題：

人々はこれについて不平を言っています: STL マップでは、[] よりも map::insert を使用する方が良いですか?

アクセス時

std::map<Key, ExpensiveDefaultConstructorValue> data;
data[key1] // <-- Calls default constructor each time it is called, 
           // even when the element is there

実装はシンプルで洗練されていますが、完全に非効率的です (unordered_map から引用)。

_Tp& operator[](const key_type& __key)
   { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }

明白な解決策

_Tp& operator[](const key_type& __key)
   { return _M_ht.find_or_insert_default(key_type(__key)).second; }

find_or_insert_default必要な場合にのみ呼び出す場所_Tp()(つまり、要素が存在しない場合)

なぜだめですか？

この悲観的なアプローチによって、新しい要素が必要であることに気付く前に新しい要素を構築することによって引き起こされる可能性のある他の問題はありますか?

これは標準ライブラリであり、最適化するために多大な努力を払う必要があります。この単純なアプローチを使用しないのはなぜですか?

4

1 に答える 1

5

std::map少なくともg++ 4.5以降では、このような問題は発生していません。

// stripped comments and requirements
mapped_type&
operator[](const key_type& __k)
{    
    iterator __i = lower_bound(__k);

    if (__i == end() || key_comp()(__k, (*__i).first))
        __i = insert(__i, value_type(__k, mapped_type()));
    return (*__i).second;
}

あなたが投稿したスニペットは からstd::mapではなく、ライブラリへのhash_mapGCC拡張機能である からのものです。

00052 /** @file backward/hash_map
00053  *  This file is a GNU extension to the Standard C++ Library (possibly
00054  *  containing extensions from the HP/SGI STL subset).
00055  */

これは拡張機能であるため、メンテナーは複雑さ/パフォーマンスのルールに従う義務はありません (提案された関数がより高速になる場合でも)。要素が存在する場合、コンストラクターを使用しないhash_mapの実装に置き換えられていることに注意してください。std::unordered_map

于 2013-10-26T07:41:14.460 に答える