在 unordered_map 中查找的性能

Question

我知道这可能是一个愚蠢的问题，但我想确定一下，但我无法轻易找到这些信息。

find() 在无序映射中的性能特征是什么？它与普通查找一样快/几乎一样快吗？

即

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

vs.

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

其中 Rows::NameRowMap 是将字符串索引映射到 int 的无序映射。

就我而言，我不确定密钥是否会事先存在，因此第一个解决方案对我来说似乎更安全，但如果我可以保证存在，那么第二种情况会更快（忽略我正在做的额外检查） ？如果是这样，为什么？如果重要的话，我正在使用 1.46 boost 实现

Answer 1

无序容器上的 find 和 operator[] 平均为 O(1)，最坏情况为 O(n) - 这取决于哈希函数的质量。

Answer 2

operator[] 很可能在内部使用 find 和 insert 。例如，IIRC Miscrosoft 的 std::map 实现就是这种情况。

编辑：
我想说的是operator[]并不神奇，它仍然需要先进行查找。从我在 Boost 1.46.0 中看到的情况来看，find 和所说的运算符都在内部使用 find_iterator 。

通常最好使用 find 进行查找，因为您的代码将更加可重用和健壮（例如，您永远不会意外插入某些内容），尤其是在某种通用代码中。

Answer 3

它们具有相同的摊余复杂度 O(1)，但当未找到值时，运算符也会创建一个新元素。如果找到该值，则性能差异应该很小。我的 boost 有点旧 - 版本 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));
    }
}