std::map::insert_or_assign 的有效替代与提示

Question

我正在尝试为不支持 C++17 的构建环境编写采用 hint 参数的 std::map::insert_or_assign 替代品。

我希望这个替代品同样高效，并且不需要映射类型是 DefaultConstructible。后一个要求排除了map[key] = value.

我想到了这个：

template <class M, class K, class T>
typename M::iterator insert_or_assign(M& map, typename M::const_iterator hint,
                                      K&& key, T&& value)
{
    using std::forward;
    auto old_size = map.size();
    auto iter = map.emplace_hint(hint, forward<K>(key), forward<T>(value));

    // If the map didn't grow, the key already already existed and we can directly
    // assign its associated value.
    if (map.size() == old_size)
        iter->second = std::forward<T>(value);
    return iter;
}

但是，我不知道我是否可以相信 std::map 在密钥已经存在的情况下不会移动赋值两次。这样安全吗？如果不是，是否有一种安全的方法可以有效地实现 std::map::insert_or_assign 的替代 hint 参数？

Answer 1

根据 NathanOliver 的评论，他引用了 std::map::emplace 的 cppreference documentation:

The element may be constructed even if there already is an element with the key in the container, in which case the newly constructed element will be destroyed immediately.

如果我们假设同样适用于 std::map::emplace_hint，那么我在问题中提出的解决方案中的值可能会过早移开。

我想出了另一个解决方案（未测试），它只有 forward 值一次。我承认它不漂亮。 :-)

// Take 'hint' as a mutating iterator to avoid an O(N) conversion.
template <class M, class K, class T>
typename M::iterator insert_or_assign(M& map, typename M::iterator hint,
                                      K&& key, T&& value)
{
    using std::forward;

#ifdef __cpp_lib_map_try_emplace
    return map.insert_or_assign(hint, forward<K>(key), forward<T>(value);
#else
    // Check if the given key goes between `hint` and the entry just before
    // hint. If not, check if the given key matches the entry just before hint.
    if (hint != map.begin())
    {
        auto previous = hint;
        --previous; // O(1)
        auto comp = map.key_comp();
        if (comp(previous->first, key)) // key follows previous
        {
            if (comp(key, hint->first)) // key precedes hint
            {
                // Should be O(1)
                return map.emplace_hint(hint, forward<K>(key),
                                        forward<T>(value));
            }

        }
        else if (!comp(key, previous->first)) // key equals previous
        {
            previous->second = forward<T>(value); // O(1)
            return previous;
        }
    }

    // If this is reached, then the hint has failed.
    // Check if key already exists. If so, assign its associated value.
    // If not, emplace the new key-value pair.
    auto iter = map.find(key); // O(log(N))
    if (iter != map.end())
        iter->second = forward<T>(value);
    else
        iter = map.emplace(forward<K>(key), forward<T>(value)); // O(log(N))
    return iter;
#endif
}

我希望其他人能提出更好的解决方案！

请注意，我检查 __cpp_lib_map_try_emplace feature test macro 以测试 std::map::insert_or_assign 是否受支持，然后再求助于这个丑陋的混乱。

编辑：删除了尝试检查键是否已存在于 hint.

时缓慢的迭代器算术愚蠢行为

编辑 2：hint 现在被视为变异迭代器，以避免在以其他方式作为 [=18= 传递时进行昂贵的 O(N) 转换].这允许我手动检查提示并在提示成功时执行 O(1) 插入或赋值。

std::map::insert_or_assign 的有效替代与提示

Efficient substitute for std::map::insert_or_assign with hint

c++

dictionary

c++-standard-library