Эффективно вставлять кортеж в контейнер через перемещение

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

Поскольку это для заметок, ни одна из них не является хорошей идеей.

Для получения уникальных ключей контейнеров, emplace и insert (кроме случаев, когда insert передается value_type - то есть, pair<const Key, Value>) может безусловно выделить память и построить пару ключ-значение, а затем уничтожить пару и освободить память, если ключ уже существует; это очевидно дорого, если ваш ключ уже существует. (Им нужно сделать это, потому что в общем случае вам нужно построить ключ, прежде чем вы сможете проверить, существует ли он, и ключ должен быть сконструирован непосредственно в конечном месте.)

Тем не менее, вы также хотите избежать ненужного копирования ключа, поэтому вставка value_type не подходит - Key в нем есть константа и поэтому не может быть перемещен.

Наконец, вы также захотите избежать дополнительных поисков. Не так дорого, как выделение памяти, но все же полезно его сохранить.

Таким образом, нам нужно сначала найти ключ и только позвонить 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 */); 
} 

Answer 2

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 3

Первое:

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

против

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

не делает разницы. make_tuple(args...) является временным и поэтому передается как ссылка rvalue. Этот шаг ничего не добавляет.

Что-то другое было бы

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

Теперь emplace() получает Lvalue ссылки, таким образом, используя конструктор копирования из станда :: пар вместо конструктора перемещения.

В любом случае, если большие данные находятся в любом из args..., ваша проблема находится где-то в другом месте. Все args в настоящее время передаются как ссылки lvalue.

Что вы хотите сделать, это:

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

Если вы передаете ссылку на RValue foo(), а затем отправляет его forward<Args>(args)... как при этом ссылка Rvalue что приводит в движение, а не копии. Если вы вызываете foo() с ссылкой на lvalue, он будет перенаправлен как lvalue.