用提示有效替代 std：：map：：insert_or

问：

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

我希望这个替代品同样有效，并且不要求映射类型是 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::mapstd::map::insert_or_assignhint

C++ 字典 C++-标准库

// 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_emplacestd::map::insert_or_assign

编辑：删除了尝试检查密钥是否已存在的慢速迭代器算术愚蠢。hint

编辑 2：现在被视为一个突变迭代器，以避免昂贵的 O（N）转换，如果它以其他方式作为 .这允许我手动检查提示，并在提示成功时执行 O（1）插入或赋值。hintconst_iterator

用提示有效替代 std：：map：：insert_or_assign

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

评论

评论