通过移动高效地将元组插入容器

Question

我是 move 语义初学者。是这个代码吗：

template <typename... Args>
void foo(const Args & ... args){
    map<tuple<Args...>, int> cache;
    auto result = cache.emplace(move(make_tuple(args ...)),1);
    //...
    }

效率高于：

template <typename... Args>
void foo(const Args & ... args){
    map<tuple<Args...>, int> cache;
    tuple<Args...> t(args...);
    auto result = cache.insert(make_pair(t,1));
    //...
    }

特别是如果 args 包含一些大对象？

同样的问题，但有 std::vector（所以不需要 make_pair 或 make_tuple）

Answer 1

template <typename... Args>
void foo(const Args & ... args){
    map<tuple<Args...>, int> cache;
    auto result = cache.emplace(move(make_tuple(args ...)),1);
    //...
}

此代码应该更快。 emplace进行就地构建（完美转发）。这应该保证最少数量的构建和复制。但是，如果您对它们进行基准测试也不会有害。

一般情况下，尽可能使用 emplace。它应该总是一个更好的选择。

Answer 2

第一个：

auto result = cache.emplace(move(make_tuple(args ...)),1);

对

auto result = cache.emplace(make_tuple(args ...),1);

没有区别。 make_tuple(args...) 是临时的，因此作为右值引用传递。此举不会增加任何东西。

不同的是

tuple<Args...> t(args...);
auto result = cache.emplace(t, 1);

现在 emplace() 接收左值引用，因此使用 std::pair 的复制构造函数而不是移动构造函数。

无论如何，如果 args... 中有大量数据，那么您的问题无论如何都出在其他地方。所有 args 当前都作为左值引用传递。

您想要做的是：

template <typename... Args>
void foo(Args && ... args){
    map<tuple<Args...>, int> cache;
    auto result = cache.emplace(make_tuple(forward<Args>(args)...)),1);
    //...
}

如果您将右值引用传递给 foo()，则 forward<Args>(args)... 会将其作为右值引用转发，从而导致移动而不是复制。如果您使用左值引用调用 foo()，它将作为左值转发。

Answer 3

因为这是为了记忆，所以这两个选项都不是一个好主意。

对于唯一键容器，emplace 和 insert（当 insert 传递给 value_type 时除外 - 即 pair<const Key, Value>）可能无条件先分配内存并构造键值对，如果键已经存在，则销毁键值对并释放内存；如果您的密钥已经存在，这显然是昂贵的。（他们需要这样做，因为在一般情况下，您必须先构造密钥，然后才能检查它是否存在，并且必须直接在其最终位置构造密钥。）

但是，您还想避免不必要地复制密钥，因此插入 value_type 是不好的 - 其中的 Key 是 const 限定的，因此不能从中移动。

最后，您还希望避免额外的查找。不像内存分配那么昂贵，但仍然可以节省它。

因此，我们需要先查找key，如果key不在map中才调用emplace。在 C++11 中，只允许同构查找，所以你必须复制一份 args....

map<tuple<Args...>, int> cache;
auto key = std::make_tuple(args...);
auto it = cache.lower_bound(key); // *it is the first element whose key is
                                  // not less than 'key'
if(it != cache.end() && it->first == key) {
    // key already in the map, do what you have to do
}
else {
    // add new entry, using 'it' as hint and moving 'key' into container.
    cache.emplace_hint(it, std::move(key), /* value */);
}

在 C++14 中，您可以进行异构查找，这意味着您可以保存副本以备不时之需：

map<tuple<Args...>, int, less<>> cache; // "diamond functor" enables hetergeneous lookup
auto key = std::tie(args...); // this is a tuple<const Args&...> - a tuple of references!
auto it = cache.lower_bound(key); // *it is the first element whose key is
                                  // not less than 'key'
if(it != cache.end() && it->first == key) {
    // key already in the map, do what you have to do
}
else {
    // add new entry, copying args...
    cache.emplace_hint(it, key, /* value */);
}

通过移动高效地将元组插入容器

Efficiently instert tuple into container through move

c++

move-semantics

c++11

emplace