1

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

find() 在无序映射中的性能特点是什么？它是否与正常查找一样快/几乎一样快？

IE

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];

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

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

4

3 回答 3

4

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

编辑：我想说的是这operator[]并不神奇，它仍然需要先进行查找。从我在 Boost 1.46.0 中看到的find和所说的操作员在find_iterator内部使用。

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

于 2011-08-11T00:35:18.427 回答
3

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

于 2011-08-11T00:30:10.860 回答
1

它们具有相同的 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));
    }
}
于 2011-08-11T00:51:12.027 回答