c++ - unordered_map : why range operation are inefficient, 是这种情况吗？

Question

我得到了 this example关于在 C++ 中实现通用内存。然而，正如有人在此评论中指出的那样，原始代码进行了 2 次查找，而下面的代码只进行了一次查找。

template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)> memoize(std::function<ReturnType (Args...)> func)
{
    std::map<std::tuple<Args...>, ReturnType> cache;
    return ([=](Args... args) mutable  {
            std::tuple<Args...> t(args...);
auto range = cache.equal_range(t);
if (range.first != range.second) return (*range.first).second;
return (*cache.insert(range.first, func(args...))).second;

    });
}

有人注意到使用 unordered_map 可能会有更好的性能。但是我有read那:

they are generally less efficient for range iteration through a subset of their elements. I don't understand why the range operation are less efficient, and if the case above is one of these cases (since we use range)?

Answer 1

as someone made notice in this comment, the original code makes 2 lookups, while the code below makes only one

好的，所以您正在尝试使用提示的 insert 以避免对插入点进行冗余的对数复杂度搜索。您仍然有与另一个问题相同的错误，您的代码可能如下所示:

cache.insert(range.first, std::make_pair(t, func(args...)));
//           ^hint        ^value_type

(这是链接文档中的重载 #4)。

您完全可以不进行第一次查找:insert如果键存在，则简单地将迭代器返回到现有元素，因此您可以使用乐观插入来编写它 - 这是否更好取决于默认构造的成本，然后分配您的 ReturnType:

auto result = cache.insert(make_pair(t, ReturnType{}));
if (result.second) {
    // insertion succeeded so the value wasn't cached already
    result.first->second = func(args...);
}
return result.first->second;

... using unordered_map would have probably better performance ...

std::map查找/插入具有对数复杂度的刻度，以及 std::unordered_map以恒定的复杂性扩展。实际上哪个更好取决于您有多少条目，以及其他因素，您需要分析才能确定。

... [unordered_map is] less efficient for range iteration ...

嗯，如果你避免equal_range，你根本不需要范围迭代.

查看您实际使用的操作，并了解哪种数据结构最适合。对于简单的查找和插入，这是您真正需要的，unordered_map可能没问题。 std::map如果您关心键的相对顺序(而您并不关心)，那就更好了。

两种结构对key也有不同的要求:map需要排序( operator< 或自定义比较器)，而 unordered_map需要一个明确定义的散列函数和 operator==或自定义谓词。

首先，我不确定std::hash支持std::tuple ，因此您可能需要提供自定义哈希器才能使用 unordered_map .