füge vs emplace vs operator [] in die c ++ - Map ein

Ich verwende zum ersten Mal Karten und habe festgestellt, dass es viele Möglichkeiten gibt, ein Element einzufügen. Sie können emplace(), operator[]oder insert(), plus Varianten wie value_typeoder verwenden make_pair. Obwohl es viele Informationen zu allen gibt und Fragen zu bestimmten Fällen, kann ich das Gesamtbild immer noch nicht verstehen. Meine beiden Fragen sind also:

1. Was ist der Vorteil eines jeden von ihnen gegenüber dem anderen?

2. Gab es eine Notwendigkeit, dem Standard Emplace hinzuzufügen? Gibt es etwas, was ohne es vorher nicht möglich war?

Im speziellen Fall einer Karte waren die alten Optionen nur zwei: operator[]und insert(verschiedene Geschmacksrichtungen von insert). Also werde ich anfangen, diese zu erklären.

Das operator[]ist ein Find-or-Add- Operator. Es wird versucht, ein Element mit dem angegebenen Schlüssel in der Karte zu finden. Wenn es vorhanden ist, wird ein Verweis auf den gespeicherten Wert zurückgegeben. Ist dies nicht der Fall, wird ein neues Element erstellt, das mit der Standardinitialisierung eingefügt wurde, und es wird ein Verweis darauf zurückgegeben.

Die insertFunktion (in der Einzelelement-Variante) nimmt ein value_type( std::pair<const Key,Value>), verwendet den Schlüssel ( Element first) und versucht, ihn einzufügen. Da std::mapDuplikate nicht zulässig sind, wenn ein Element vorhanden ist, wird nichts eingefügt.

Der erste Unterschied zwischen beiden besteht darin, dass operator[]ein standardmäßig initialisierter Wert erstellt werden muss. Daher ist er für Werttypen, die nicht standardmäßig initialisiert werden können, unbrauchbar. Der zweite Unterschied zwischen den beiden besteht darin, was passiert, wenn bereits ein Element mit dem angegebenen Schlüssel vorhanden ist. Die insertFunktion ändert nicht den Status der Karte, sondern gibt stattdessen einen Iterator an das Element zurück (und einen falseHinweis darauf, dass es nicht eingefügt wurde).

// assume m is std::map<int,int> already has an element with key 5 and value 0
m[5] = 10;                      // postcondition: m[5] == 10
m.insert(std::make_pair(5,15)); // m[5] is still 10

Im Falle des insertArguments handelt es sich um ein Objekt von value_type, das auf verschiedene Arten erstellt werden kann. Sie können es direkt mit dem entsprechenden Typ value_typeerstellen oder jedes Objekt übergeben, aus dem das erstellt werden kann. Hier std::make_pairkommt es ins Spiel, da es die einfache Erstellung von std::pairObjekten ermöglicht, obwohl es wahrscheinlich nicht das ist, was Sie wollen ...

Der Nettoeffekt der folgenden Aufrufe ist ähnlich :

K t; V u;
std::map<K,V> m;           // std::map<K,V>::value_type is std::pair<const K,V>

m.insert( std::pair<const K,V>(t,u) );      // 1
m.insert( std::map<K,V>::value_type(t,u) ); // 2
m.insert( std::make_pair(t,u) );            // 3

Aber die sind nicht wirklich gleich ... [1] und [2] sind tatsächlich gleichwertig. In beiden Fällen erstellt der Code ein temporäres Objekt desselben Typs ( std::pair<const K,V>) und übergibt es an die insertFunktion. Die insertFunktion erstellt den entsprechenden Knoten im binären Suchbaum und kopiert dann den value_typeTeil aus dem Argument auf den Knoten. Der Vorteil der Verwendung value_typeist, dass Sie value_typeimmer übereinstimmen value_type und den Typ der std::pairArgumente nicht falsch eingeben können !

Der Unterschied liegt in [3]. Die Funktion std::make_pairist eine Vorlagenfunktion, die eine erstellt std::pair. Die Unterschrift lautet:

template <typename T, typename U>
std::pair<T,U> make_pair(T const & t, U const & u );

Ich habe die Vorlagenargumente absichtlich nicht angegeben std::make_pair, da dies die übliche Verwendung ist. Und die Implikation ist, dass die Vorlagenargumente aus dem Aufruf abgeleitet werden, in diesem Fall zu sein T==K,U==V, so dass der Aufruf von a std::make_pairzurückgibt std::pair<K,V>(beachten Sie das Fehlen const). Die Signatur erfordert, value_typedass sie nahe ist, aber nicht mit dem vom Aufruf an zurückgegebenen Wert übereinstimmt std::make_pair. Da es nah genug ist, wird eine temporäre Datei des richtigen Typs erstellt und durch Kopieren initialisiert. Dies wird wiederum auf den Knoten kopiert, wodurch insgesamt zwei Kopien erstellt werden.

Dies kann durch Angabe der Vorlagenargumente behoben werden:

m.insert( std::make_pair<const K,V>(t,u) );  // 4

Dies ist jedoch immer noch fehleranfällig, genauso wie die explizite Eingabe des Typs in case [1].

Bis zu diesem Punkt haben wir verschiedene Arten des Aufrufs insert, die die Erstellung des value_typeexternen Objekts und die Kopie dieses Objekts in den Container erfordern . Alternativ können Sie verwenden, operator[]wenn der Typ standardmäßig konstruierbar und zuweisbar ist (absichtlich nur in fokussiert m[k]=v) und die Standardinitialisierung eines Objekts und die Kopie des Werts in dieses Objekt erforderlich sind .

In C ++ 11 gibt es mit variablen Vorlagen und perfekter Weiterleitung eine neue Möglichkeit, Elemente durch Einfügen (Erstellen an Ort und Stelle) in einen Container einzufügen . Die emplaceFunktionen in den verschiedenen Containern machen im Grunde dasselbe: Anstatt eine Quelle zum Kopieren in den Container zu erhalten, übernimmt die Funktion die Parameter, die an den Konstruktor des im Container gespeicherten Objekts weitergeleitet werden.

m.emplace(t,u);               // 5

In [5] wird das std::pair<const K, V>nicht erstellt und übergeben emplace, sondern es werden Verweise auf das Objekt tund uübergeben, emplacedie sie an den Konstruktor des value_typeUnterobjekts innerhalb der Datenstruktur weiterleiten . In diesem Fall werden überhaupt keine Kopien von erstellt std::pair<const K,V>, was emplacegegenüber den C ++ 03-Alternativen von Vorteil ist . Wie im Fall insertwird der Wert in der Karte nicht überschrieben.

Eine interessante Frage, über die ich nicht nachgedacht hatte, ist, wie emplacesie tatsächlich für eine Karte implementiert werden kann, und das ist im allgemeinen Fall kein einfaches Problem.

Einfügen: Nutzt die rWert-Referenz, um die tatsächlich erstellten Objekte zu verwenden. Dies bedeutet, dass kein Konstruktor zum Kopieren oder Verschieben aufgerufen wird, was für GROSSE Objekte gut ist! O (log (N)) Zeit.

Einfügen: Enthält Überladungen für Standard-L-Wert-Referenz und R-Wert-Referenz sowie Iteratoren für Listen der einzufügenden Elemente und "Hinweise" auf die Position, zu der ein Element gehört. Die Verwendung eines "Hinweis" -Iterators kann dazu führen, dass die Zeit, die für das Einfügen benötigt wird, auf die Contant-Zeit reduziert wird, andernfalls ist es die Zeit O (log (N)).

Operator []: Überprüft, ob das Objekt vorhanden ist, und ändert in diesem Fall den Verweis auf dieses Objekt, verwendet andernfalls den angegebenen Schlüssel und Wert, um make_pair für die beiden Objekte aufzurufen, und führt dann die gleiche Arbeit wie die Einfügefunktion aus. Dies ist die Zeit O (log (N)).

make_pair: Macht kaum mehr als ein Paar.

Es bestand keine "Notwendigkeit", dem Standard Emplace hinzuzufügen. In c ++ 11 wurde meiner Meinung nach der Referenztyp && hinzugefügt. Dies beseitigte die Notwendigkeit einer Verschiebungssemantik und ermöglichte die Optimierung einer bestimmten Art der Speicherverwaltung. Insbesondere die rWertreferenz. Der überladene Einfügeoperator (value_type &&) nutzt die In_place-Semantik nicht aus und ist daher viel weniger effizient. Es bietet zwar die Möglichkeit, mit Wertreferenzen umzugehen, ignoriert jedoch deren Hauptzweck, nämlich die Konstruktion von Objekten.

Neben den Optimierungsmöglichkeiten und der einfacheren Syntax besteht ein wichtiger Unterschied zwischen Einfügen und Einfügen darin, dass letzteres explizite Konvertierungen ermöglicht. (Dies gilt für die gesamte Standardbibliothek, nicht nur für Karten.)

Hier ist ein Beispiel, um zu demonstrieren:

#include <vector>

struct foo
{
    explicit foo(int);
};

int main()
{
    std::vector<foo> v;

    v.emplace(v.end(), 10);      // Works
    //v.insert(v.end(), 10);     // Error, not explicit
    v.insert(v.end(), foo(10));  // Also works
}

Dies ist zwar ein sehr spezifisches Detail, aber wenn Sie mit Ketten benutzerdefinierter Conversions arbeiten, sollten Sie dies berücksichtigen.

Der folgende Code kann Ihnen helfen, die "Gesamtidee" zu verstehen, wie sich diese insert()unterscheidet emplace():

#include <iostream>
#include <unordered_map>
#include <utility>

//Foo simply outputs what constructor is called with what value.
struct Foo {
  static int foo_counter; //Track how many Foo objects have been created.
  int val; //This Foo object was the val-th Foo object to be created.

  Foo() { val = foo_counter++;
    std::cout << "Foo() with val:                " << val << '\n';
  }
  Foo(int value) : val(value) { foo_counter++;
    std::cout << "Foo(int) with val:             " << val << '\n';
  }
  Foo(Foo& f2) { val = foo_counter++;
    std::cout << "Foo(Foo &) with val:           " << val
              << " \tcreated from:      \t" << f2.val << '\n';
  }
  Foo(const Foo& f2) { val = foo_counter++;
    std::cout << "Foo(const Foo &) with val:     " << val
              << " \tcreated from:      \t" << f2.val << '\n';
  }
  Foo(Foo&& f2) { val = foo_counter++;
    std::cout << "Foo(Foo&&) moving:             " << f2.val
              << " \tand changing it to:\t" << val << '\n';
  }
  ~Foo() { std::cout << "~Foo() destroying:             " << val << '\n'; }

  Foo& operator=(const Foo& rhs) {
    std::cout << "Foo& operator=(const Foo& rhs) with rhs.val: " << rhs.val
              << " \tcalled with lhs.val = \t" << val
              << " \tChanging lhs.val to: \t" << rhs.val << '\n';
    val = rhs.val;
    return *this;
  }

  bool operator==(const Foo &rhs) const { return val == rhs.val; }
  bool operator<(const Foo &rhs)  const { return val < rhs.val;  }
};

int Foo::foo_counter = 0;

//Create a hash function for Foo in order to use Foo with unordered_map
namespace std {
   template<> struct hash<Foo> {
       std::size_t operator()(const Foo &f) const {
           return std::hash<int>{}(f.val);
       }
   };
}

int main()
{
    std::unordered_map<Foo, int> umap;  
    Foo foo0, foo1, foo2, foo3;
    int d;

    //Print the statement to be executed and then execute it.

    std::cout << "\numap.insert(std::pair<Foo, int>(foo0, d))\n";
    umap.insert(std::pair<Foo, int>(foo0, d));
    //Side note: equiv. to: umap.insert(std::make_pair(foo0, d));

    std::cout << "\numap.insert(std::move(std::pair<Foo, int>(foo1, d)))\n";
    umap.insert(std::move(std::pair<Foo, int>(foo1, d)));
    //Side note: equiv. to: umap.insert(std::make_pair(foo1, d));

    std::cout << "\nstd::pair<Foo, int> pair(foo2, d)\n";
    std::pair<Foo, int> pair(foo2, d);

    std::cout << "\numap.insert(pair)\n";
    umap.insert(pair);

    std::cout << "\numap.emplace(foo3, d)\n";
    umap.emplace(foo3, d);

    std::cout << "\numap.emplace(11, d)\n";
    umap.emplace(11, d);

    std::cout << "\numap.insert({12, d})\n";
    umap.insert({12, d});

    std::cout.flush();
}

Die Ausgabe, die ich bekam, war:

Foo() with val:                0
Foo() with val:                1
Foo() with val:                2
Foo() with val:                3

umap.insert(std::pair<Foo, int>(foo0, d))
Foo(Foo &) with val:           4    created from:       0
Foo(Foo&&) moving:             4    and changing it to: 5
~Foo() destroying:             4

umap.insert(std::move(std::pair<Foo, int>(foo1, d)))
Foo(Foo &) with val:           6    created from:       1
Foo(Foo&&) moving:             6    and changing it to: 7
~Foo() destroying:             6

std::pair<Foo, int> pair(foo2, d)
Foo(Foo &) with val:           8    created from:       2

umap.insert(pair)
Foo(const Foo &) with val:     9    created from:       8

umap.emplace(foo3, d)
Foo(Foo &) with val:           10   created from:       3

umap.emplace(11, d)
Foo(int) with val:             11

umap.insert({12, d})
Foo(int) with val:             12
Foo(const Foo &) with val:     13   created from:       12
~Foo() destroying:             12

~Foo() destroying:             8
~Foo() destroying:             3
~Foo() destroying:             2
~Foo() destroying:             1
~Foo() destroying:             0
~Foo() destroying:             13
~Foo() destroying:             11
~Foo() destroying:             5
~Foo() destroying:             10
~Foo() destroying:             7
~Foo() destroying:             9

Beachte das:

1. Ein unordered_mapspeichert FooObjekte immer intern (und nicht etwa Foo *s) als Schlüssel, die alle zerstört werden, wenn das unordered_mapzerstört wird. Hier waren die unordered_mapinternen Schlüssel des Foos 13, 11, 5, 10, 7 und 9.

   • Technisch gesehen unordered_mapspeichert unser std::pair<const Foo, int>Objekt tatsächlich Objekte, die wiederum die FooObjekte speichern . Um jedoch die "Gesamtidee" zu verstehen, wie emplace()unterschiedlich sie ist insert()(siehe hervorgehobenes Kästchen unten), ist es in Ordnung, sich dieses Objekt vorübergehendstd::pair als vollständig passiv vorzustellen . Sobald Sie diese verstehen „big picture Idee“ , ist es wichtig, dann zu sichern und zu verstehen , wie die Verwendung dieses Vermittler std::pairObjekt durch unordered_mapeinleiten subtil, aber wichtig, technische.

2. Einfügen von foo0, foo1und foo2erforderte 2 Aufrufe an einen der FooKopier- / Verschiebungskonstruktoren und 2 Aufrufe an Fooden Destruktor (wie ich jetzt beschreibe):

   ein. Einsetzen jedes von foo0und foo1eine temporäre Objekt erzeugt ( foo4und foo6sind) , deren destructor sofort wurde dann aufgerufen , nachdem das Einsetzen abgeschlossen. Darüber hinaus wurden die Destruktoren der internen Foos der unordered_map ( Foos 5 und 7) aufgerufen, als die unordered_map zerstört wurde.

   b. Zum Einfügen foo2haben wir stattdessen zunächst explizit ein nicht temporäres Paarobjekt (aufgerufen pair) erstellt, das Fooden Kopierkonstruktor von foo2( aufgerufen foo8als internes Mitglied von pair) aufgerufen hat . Wir haben dann insert()dieses Paar bearbeitet, was dazu führte, unordered_mapdass der Kopierkonstruktor erneut (on foo8) aufgerufen wurde, um eine eigene interne Kopie ( foo9) zu erstellen . Wie bei foos 0 und 1 war das Endergebnis zwei Destruktoraufrufe für diese Einfügung, mit dem einzigen Unterschied, dass foo8der Destruktor nur aufgerufen wurde, wenn wir das Ende von erreicht hatten, main()anstatt unmittelbar nach insert()Beendigung aufgerufen zu werden .

3. Das Einfügen foo3führte zu nur einem Aufruf des Kopier- / Verschiebungskonstruktors ( foo10intern im unordered_map) erstellt und nur zu einem Aufruf des FooDestruktors. (Ich werde später darauf zurückkommen).

4. Für foo11kamen wir direkt die ganze Zahl 11 , emplace(11, d)so dass unordered_mapder Anruf würde Foo(int)Konstruktor während der Ausführung innerhalb seiner ist emplace()Methode. Anders als in (2) und (3) brauchten wir dazu nicht einmal ein vorbestehendes fooObjekt. Beachten Sie, dass nur 1 Aufruf eines FooKonstruktors aufgetreten ist (der erstellt wurde foo11).

5. Wir haben dann die ganze Zahl 12 direkt an übergeben insert({12, d}). Anders als bei emplace(11, d)(dieser Rückruf führte nur zu einem Aufruf eines FooKonstruktors) führte dieser Aufruf zu insert({12, d})zwei Aufrufen des FooKonstruktors (Erstellen foo12und foo13).

Dies zeigt, was der Hauptunterschied zwischen insert()und emplace()ist:

Während die Verwendung insert() fast immer die Konstruktion oder Existenz eines FooObjekts im main()Gültigkeitsbereich erfordert (gefolgt von einer Kopie oder Verschiebung), erfolgt bei Verwendung emplace()jeder Aufruf eines FooKonstruktors vollständig intern im unordered_map(dh innerhalb des Gültigkeitsbereichs der emplace()Methodendefinition). Die Argumente für den Schlüssel, an den Sie übergeben, emplace()werden direkt an einen FooKonstruktoraufruf innerhalb unordered_map::emplace()der Definition weitergeleitet (optionale zusätzliche Details: Dieses neu erstellte Objekt wird sofort in eine der unordered_mapMitgliedsvariablen integriert, sodass kein Destruktor aufgerufen wird, wenn Ausführungsblätter emplace()und keine Verschiebungs- oder Kopierkonstruktoren werden aufgerufen).

Hinweis: Der Grund für das " fast " in " fast immer " oben wird in I) unten erläutert.

3. Fortsetzung: Der Grund , warum calling umap.emplace(foo3, d)genannt Foo‚s nicht konstanten Copykonstruktor ist folgende: Da wir verwenden emplace(), der Compiler, der weiß foo3(eine nicht-const Foogemeint Objekt) ein Argument zu einem gewissen sein FooKonstruktor. In diesem Fall ist der am besten geeignete FooKonstruktor der nicht konstante Kopierkonstruktor Foo(Foo& f2). Aus diesem Grund wurde umap.emplace(foo3, d)ein Kopierkonstruktor aufgerufen, obwohl umap.emplace(11, d)dies nicht der Fall war.

Epilog:

I. Beachten Sie, dass eine Überlastung von insert()tatsächlich entspricht emplace() . Wie auf dieser Seite cppreference.com beschrieben , entspricht die Überladung template<class P> std::pair<iterator, bool> insert(P&& value)( dh die Überladung (2) insert()auf dieser Seite cppreference.com) emplace(std::forward<P>(value)).

II. Wohin von hier aus?

ein. Spielen Sie mit dem obigen Quellcode und der Studiendokumentation für insert()(z. B. hier ) und emplace()(z. B. hier ), die online verfügbar sind. Wenn Sie eine IDE wie Eclipse oder NetBeans verwenden, können Sie sich von Ihrer IDE leicht mitteilen lassen, welche Überlastung von insert()oder emplace()aufgerufen wird (halten Sie in Eclipse den Mauszeiger für eine Sekunde ruhig über dem Funktionsaufruf). Hier ist noch ein Code zum Ausprobieren:

std::cout << "\numap.insert({{" << Foo::foo_counter << ", d}})\n";
umap.insert({{Foo::foo_counter, d}});
//but umap.emplace({{Foo::foo_counter, d}}); results in a compile error!

std::cout << "\numap.insert(std::pair<const Foo, int>({" << Foo::foo_counter << ", d}))\n";
umap.insert(std::pair<const Foo, int>({Foo::foo_counter, d}));
//The above uses Foo(int) and then Foo(const Foo &), as expected. but the
// below call uses Foo(int) and the move constructor Foo(Foo&&). 
//Do you see why?
std::cout << "\numap.insert(std::pair<Foo, int>({" << Foo::foo_counter << ", d}))\n";
umap.insert(std::pair<Foo, int>({Foo::foo_counter, d}));
//Not only that, but even more interesting is how the call below uses all 
// three of Foo(int) and the Foo(Foo&&) move and Foo(const Foo &) copy 
// constructors, despite the below call's only difference from the call above 
// being the additional { }.
std::cout << "\numap.insert({std::pair<Foo, int>({" << Foo::foo_counter << ", d})})\n";
umap.insert({std::pair<Foo, int>({Foo::foo_counter, d})});


//Pay close attention to the subtle difference in the effects of the next 
// two calls.
int cur_foo_counter = Foo::foo_counter;
std::cout << "\numap.insert({{cur_foo_counter, d}, {cur_foo_counter+1, d}}) where " 
  << "cur_foo_counter = " << cur_foo_counter << "\n";
umap.insert({{cur_foo_counter, d}, {cur_foo_counter+1, d}});

std::cout << "\numap.insert({{Foo::foo_counter, d}, {Foo::foo_counter+1, d}}) where "
  << "Foo::foo_counter = " << Foo::foo_counter << "\n";
umap.insert({{Foo::foo_counter, d}, {Foo::foo_counter+1, d}});


//umap.insert(std::initializer_list<std::pair<Foo, int>>({{Foo::foo_counter, d}}));
//The call below works fine, but the commented out line above gives a 
// compiler error. It's instructive to find out why. The two calls
// differ by a "const".
std::cout << "\numap.insert(std::initializer_list<std::pair<const Foo, int>>({{" << Foo::foo_counter << ", d}}))\n";
umap.insert(std::initializer_list<std::pair<const Foo, int>>({{Foo::foo_counter, d}}));

Sie werden bald feststellen, dass die Überlastung des std::pairKonstruktors (siehe Referenz ), die letztendlich verwendet wird unordered_map, einen wichtigen Einfluss darauf haben kann, wie viele Objekte kopiert, verschoben, erstellt und / oder zerstört werden und wann dies alles auftritt.

b. Sehen Sie, was passiert, wenn Sie eine andere Containerklasse (z. B. std::setoder std::unordered_multiset) anstelle von verwenden std::unordered_map.

c. Verwenden Sie nun ein GooObjekt (nur eine umbenannte Kopie von Foo) anstelle eines intals Bereichstyp in einem unordered_map(dh verwenden Sie unordered_map<Foo, Goo>anstelle von unordered_map<Foo, int>) und sehen Sie, wie viele und welche GooKonstruktoren aufgerufen werden. (Spoiler: Es gibt einen Effekt, aber er ist nicht sehr dramatisch.)

In Bezug auf Funktionalität oder Ausgabe sind beide gleich.

Für beide großen Speicher ist object emplace speicheroptimiert, wobei keine Kopierkonstruktoren verwendet werden

Für eine einfache detaillierte Erklärung https://medium.com/@sandywits/all-about-emplace-in-c-71fd15e06e44