unordered_map에서 찾기의 성능

Question

나는 이것이 아마 어리석은 질문이지만, 나는이 정보를 쉽게 찾을 수 없다는 것을 알고 싶었다.

정렬되지 않은 맵에서 find()의 성능 특성은 무엇입니까? 정상적인 조회만큼 빠르거나 거의 빠릅니다.

e.e.

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

대 Rows::NameRowMap는 INT에 문자열 인덱스를 매핑 정렬되지 않은지도입니다

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

.

내 경우에는 열쇠가 손에 먼저 존재하는지 확실하지 않으므로 첫 번째 해결책은 내게 안전하다고 생각되지만 실존을 보장 할 수 있다면 두 번째 경우가 빠릅니다 (추가 검사를 무시 함). 내가하고있는거야?) 그렇다면 왜? 문제가 해결되면 1.46 부스트 구현을 사용하고 있습니다.

Answer 1

find 및 operator[]은 정렬되지 않은 컨테이너에서 O (1) 평균, O (n) 최악의 경우입니다. 이는 해시 함수의 품질에 따라 다릅니다.

Answer 2

operator[]은 find과 insert을 내부적으로 사용합니다. 예를 들어, IIRC는 Miscrosoft의 std::map 구현의 경우입니다.

편집 : 내가 말하고자하는 것은 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)); 
    } 
}