Effizient Tuple in Container durch Verschieben

Question

Ich bin ein move Semantik Anfänger. Ist dieser Code:

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

Effizienter als:

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

Vor allem, wenn args einige große Objekt enthält?

Gleiche Frage aber mit std::vector (so dass keine Notwendigkeit für make_pair oder make_tuple)

Answer 1

Da dies für Memoisierung ist, ist keine der beiden Optionen eine gute Idee.

Für einzigartige Schlüssel Container, emplace und insert (außer wenn insert geben wird eine value_type - das heißt, pair<const Key, Value>) Speicher bedingungslos zuteilen kann und konstruieren den Schlüssel-Wert-Paar erste und dann das Paar zerstören und freigeben, den Speicher, wenn der Schlüssel existiert bereits; Das ist natürlich teuer, wenn Ihr Schlüssel bereits existiert. (Sie müssen dies tun, weil Sie im Allgemeinen den Schlüssel erstellen müssen, bevor Sie überprüfen können, ob er existiert, und der Schlüssel muss direkt an seinem endgültigen Ort erstellt werden.)

Sie wollen aber auch vermeiden, unnötigerweise den Schlüssel zu kopieren, also ist das Einfügen eines value_type nicht gut - das Key dort ist const-qualifiziert und kann daher nicht verschoben werden.

Schließlich möchten Sie auch zusätzliche Lookups vermeiden. Nicht so teuer wie eine Speicherzuweisung, aber immer noch gut, um sie zu speichern.

Daher müssen wir den Schlüssel zuerst suchen und nur emplace aufrufen, wenn der Schlüssel nicht in der Karte ist. In C++ 11 ist nur eine homogene Suche zulässig, daher müssen Sie eine Kopie von args... erstellen.

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

In C++ 14, können Sie heterogenen Lookup tun, was bedeutet, dass Sie die Kopie, wenn Sie es wirklich brauchen sparen können:

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

Dieser Code schneller sein sollte. emplace führen Sie In-Place-Konstruktion durch (perfekte Weiterleitung). Dies sollte eine minimale Anzahl von Konstruktionen und Kopien garantieren. Es würde jedoch nicht schaden, wenn Sie sie benchmarken.

Im Allgemeinen verwenden Sie emplace wenn möglich. Es sollte immer eine bessere Option sein.

Answer 3

Erstens:

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

vs

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

keinen Unterschied machen. make_tuple(args...) ist eine temporäre und daher als Rvalue Verweis übergeben. Die Bewegung fügt nichts hinzu.

Etwas anderes wäre

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

Jetzt emplace() somit eine L-Wert Referenz erhält den Kopierkonstruktor von std :: pair statt den Umzug Konstruktor.

In jedem Fall, wenn große Daten in einem der args... Ihr Problem liegt irgendwo sonst. Alle args werden derzeit als Lvalue-Referenzen übergeben.

Was Sie wollen, würden zu tun ist:

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

Wenn Sie einen rvalue Bezug auf foo() passieren, dann forward<Args>(args)... leitet sie als rvalue Referenz somit in einer Bewegung statt einer Kopie zur Folge hat. Wenn Sie foo() mit einem Lvalue-Verweis aufrufen, wird es als Lvalue weitergeleitet.