Efficacement instert tuple dans le récipient par mouvement

Question

Je suis un move sémantique débutant. Est-ce code:

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

Plus efficace que:

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)); 
    //... 
    } 

Surtout si args contient certains gros objet?

Même question mais avec std::vector (donc pas besoin de make_pair ou make_tuple)

Answer 1

Depuis c'est pour memoization, aucune des deux options est une bonne idée.

Pour des récipients uniques de clé, emplace et insert (sauf quand insert est passé un value_type - qui est, pair<const Key, Value>) peut inconditionnellement allouer de la mémoire et construire la paire clé-valeur, et ensuite détruire le couple et désallouer la mémoire si la clé existe déjà; ceci est évidemment coûteux si votre clé existe déjà. (Ils doivent le faire car dans le cas général, vous devez construire la clé avant de pouvoir vérifier si elle existe et la clé doit être construite directement à son emplacement final.Cependant, vous voulez également éviter de copier inutilement la clé, donc insérer un value_type n'est pas bon - le Key est qualifié de constable et ne peut donc pas être déplacé à partir de value_type.

Enfin, vous souhaiterez également éviter les recherches supplémentaires. Pas aussi coûteux qu'une allocation de mémoire, mais toujours bon pour l'enregistrer.

Ainsi, nous devons d'abord rechercher la clé, et appeler seulement emplace si la clé n'est pas dans la carte. En C++ 11, seule la recherche homogène est autorisée, vous devez donc faire une copie de 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 */); 
} 

En C++ 14, vous pouvez le faire recherche hétérogène, ce qui signifie que vous pouvez enregistrer la copie lorsque vous avez réellement besoin:

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); 
    //... 
} 

Ce code devrait être plus rapide. emplace effectuer la construction sur place (transmission parfaite). Cela devrait garantir un nombre minimum de constructions et de copies. Cependant, cela ne nuira pas si vous les comparez.

En général, utilisez emplace lorsque cela est possible. Cela devrait toujours être une meilleure option.

Answer 3

Première:

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

vs

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

ne fait pas de différence. make_tuple(args...) est un temporaire et donc transmis comme référence de référence. Le mouvement n'ajoute rien.

Quelque chose de différent serait

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

maintenant emplace() reçoit une référence lvalue en utilisant ainsi le constructeur de copie de std :: pair au lieu du constructeur de déplacement.

Dans tous les cas, si des données volumineuses se trouvent dans l'un des args..., votre problème se situe quelque part ailleurs. Tous les args sont actuellement transmis en tant que références lvalue.

Qu'est-ce que vous voulez faire est:

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

Si vous passez une référence à foo() rvalue, puis forward<Args>(args)... avant elle comme référence rvalue entraînant ainsi un mouvement au lieu d'une copie. Si vous appelez foo() avec une référence lvalue, il sera renvoyé en tant que lvalue.