unordered_mapでの検索のパフォーマンス

Question

これはおそらく愚かな質問ですが、私は確かめたいと思っていました。

順序付けられていないマップでのfind（）のパフォーマンス特性は何ですか？それは通常のルックアップと同じくらい速く/ほとんど速いですか？

I.e. Rows::NameRowMapはint型に文字列インデックスをマッピング順不同マップです

std::string defaultrow = sprite.attribute("defaultrow").value(); 
auto rclassIt = Rows::NameRowMap.find(defaultrow); 
if (rclassIt != Rows::NameRowMap.end()) 
    defRow = rclassIt->second; 

対

std::string defaultrow = sprite.attribute("defaultrow").value(); 
defRow = Rows::NameRowMap[defaultrow]; 

。

私の場合、鍵が手前に存在するかどうかはわからないので、最初の解決策は私にとっては安全だと思われますが、存在を保証できれば、2番目の場合が速くなりますやってる？）もしそうなら、なぜですか？問題があれば、私は1.46のブーストの実装を使用しています。

Answer 1

findとoperator[]は、順序付けられていないコンテナには、O（1）平均、O（n）最悪の場合です - あなたのハッシュ関数の品質によって異なります。

Answer 2

operator[]はfindとinsertを内部的に使用している可能性があります。たとえば、Miscrosoftのstd::map実装の場合のIIRCです。

編集： 私が言っていることは、operator[]が魔法ではないということです。それでも、それでも検索が必要です。私がブースト1.46.0で見るものから、findと上記演算子の両方は内部でfind_iteratorを使用します。

通常、特定の種類の汎用コードでは、コードの再利用性と堅牢性（誤って何かを挿入しないなど）があるため、検索にfindを使用する方がよいでしょう。

Answer 3

これらは同じ償却複雑度O（1）を持ちますが、演算子は値が見つからない場合にも新しい要素を作成します。値が見つかった場合、パフォーマンスの差は軽微でなければなりません。私の後押しは少し古い - バージョン1.41ですが、うまくいけばそれは問題ではありません。コードは次のとおりです。

// find 
// 
// strong exception safety, no side effects 
template <class H, class P, class A, class G, class K> 
BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::iterator_base 
hash_table<H, P, A, G, K>::find(key_type const& k) const 
{ 
    if(!this->size_) return this->end(); 

    bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); 
    node_ptr it = find_iterator(bucket, k); 

    if (BOOST_UNORDERED_BORLAND_BOOL(it)) 
     return iterator_base(bucket, it); 
    else 
     return this->end(); 
} 

// if hash function throws, basic exception safety 
// strong otherwise 
template <class H, class P, class A, class K> 
    BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::value_type& 
hash_unique_table<H, P, A, K>::operator[](key_type const& k) 
{ 
    typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type; 

    std::size_t hash_value = this->hash_function()(k); 
    bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value); 

    if(!this->buckets_) { 
     node_constructor a(*this); 
     a.construct_pair(k, (mapped_type*) 0); 
     return *this->emplace_empty_impl_with_node(a, 1); 
    } 

    node_ptr pos = this->find_iterator(bucket, k); 

    if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { 
     return node::get_value(pos); 
    } 
    else { 
     // Side effects only in this block. 

     // Create the node before rehashing in case it throws an 
     // exception (need strong safety in such a case). 
     node_constructor a(*this); 
     a.construct_pair(k, (mapped_type*) 0); 

     // reserve has basic exception safety if the hash function 
     // throws, strong otherwise. 
     if(this->reserve_for_insert(this->size_ + 1)) 
      bucket = this->bucket_ptr_from_hash(hash_value); 

     // Nothing after this point can throw. 

     return node::get_value(add_node(a, bucket)); 
    } 
}