insert vs emplace vs opérateur dans la carte c ++

J’utilise les cartes pour la première fois et j’ai réalisé qu’il y a plusieurs façons d’insérer un élément. Vous pouvez utiliser emplace() , operator[] ou insert() , ainsi que des variantes comme using value_type ou make_pair . Bien qu’il y ait beaucoup d’informations sur chacun d’eux et des questions sur des cas particuliers, je ne comprends toujours pas la situation dans son ensemble. Donc, mes deux questions sont:

  1. Quel est l’avantage de chacun d’eux par rapport aux autres?

  2. Y a-t-il eu besoin d’append emplace à la norme? Y a-t-il quelque chose qui n’était pas possible avant sans ça?

Related of "insert vs emplace vs opérateur dans la carte c ++"

Dans le cas particulier d’une carte, les anciennes options n’étaient que deux: operator[] et insert (différentes saveurs d’ insert ). Je vais donc commencer à les expliquer.

L’ operator[] est un operator[] find-or-add . Il essaiera de trouver un élément avec la clé donnée dans la carte, et s’il existe, il renverra une référence à la valeur stockée. Si ce n’est pas le cas, il créera un nouvel élément inséré avec une initialisation par défaut et y renverra une référence.

La fonction d’ insert (dans la version à élément unique) prend un type value_type ( std::pair ), utilise la clé ( first membre) et tente de l’insérer. Comme std::map n’autorise pas les doublons s’il existe un élément existant, il ne va rien insérer.

La première différence entre les deux est que l’ operator[] doit être capable de construire une valeur initialisée par défaut, et donc inutilisable pour les types de valeur qui ne peuvent pas être initialisés par défaut. La deuxième différence entre les deux est ce qui se passe quand il y a déjà un élément avec la clé donnée. La fonction d’ insert ne modifie pas l’état de la carte, mais renvoie plutôt un iterator à l’élément (et une false indiquant qu’il n’a pas été inséré).

 // assume m is std::map 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 

Dans le cas de insert l’argument est un object de value_type , qui peut être créé de différentes manières. Vous pouvez le construire directement avec le type approprié ou passer tout object à partir duquel le value_type peut être construit, c’est-à-dire où std::make_pair entre en jeu, car il permet la création simple d’objects std::pair , bien que ce ne soit probablement pas ce que tu veux…

L’effet net des appels suivants est similaire :

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

Mais ce ne sont pas vraiment les mêmes … [1] et [2] sont en réalité équivalents. Dans les deux cas, le code crée un object temporaire du même type ( std::pair ) et le transmet à la fonction insert . La fonction d’ insert créera le nœud approprié dans l’arborescence de recherche binary, puis copiera la partie value_type de l’argument dans le nœud. L’avantage d’utiliser value_type est que, bien, value_type correspond toujours à value_type , vous ne pouvez pas définir le type des arguments std::pair !

La différence est dans [3]. La fonction std::make_pair est une fonction de modèle qui créera une std::pair . La signature est:

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

Je n’ai intentionnellement pas fourni les arguments du modèle à std::make_pair , car c’est l’usage commun. Et l’implication est que les arguments du modèle sont déduits de l’appel, dans ce cas être T==K,U==V , donc l’appel à std::make_pair renverra un std::pair ( notez le const manquant. La signature requirejs value_type qui est proche mais pas la valeur renvoyée par l’appel à std::make_pair . Comme il est assez proche, il va créer un temporaire du type correct et le copier pour l’initialiser. Cela sera à son tour copié sur le nœud, créant un total de deux copies.

Cela peut être corrigé en fournissant les arguments du modèle:

 m.insert( std::make_pair(t,u) ); // 4 

Mais cette erreur est toujours sujette à erreur de la même manière que le fait de taper explicitement le type dans le cas [1].

Jusqu’à ce point, nous avons différentes façons d’appeler insert qui nécessitent la création du type value_type externe et la copie de cet object dans le conteneur. Alternativement, vous pouvez utiliser operator[] si le type est constructible et assignable par défaut (focalisation intentionnelle uniquement dans m[k]=v ), et nécessite l’initialisation par défaut d’un object et la copie de la valeur dans cet object.

En C ++ 11, avec les modèles variadiques et le transfert parfait, il existe une nouvelle façon d’append des éléments dans un conteneur en les mettant en place (création en place). Les fonctions emplace dans les différents conteneurs font essentiellement la même chose: au lieu d’obtenir une source à copier dans le conteneur, la fonction prend les parameters qui seront transmis au constructeur de l’object stocké dans le conteneur.

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

Dans [5], le std::pair n’est pas créé et passé à emplace , mais plutôt des références à l’object t et u sont transmises à emplace qui les transmet au constructeur du sous-object value_type dans les données. structure. Dans ce cas, aucune copie du std::pair n’est effectuée, ce qui constitue un avantage par rapport aux alternatives C ++ 03. Comme dans le cas de l’ insert il ne remplacera pas la valeur de la carte.


Une question intéressante à laquelle je n’ai pas pensé est de savoir comment emplace peut réellement être implémenté pour une carte, et ce n’est pas un problème simple dans le cas général.

Emplace: profite de la référence rvalue pour utiliser les objects que vous avez déjà créés. Cela signifie qu’aucun constructeur de copie ou de déplacement n’est appelé, bon pour les GRANDS objects! O (log (N)) temps.

Insert: contient des surcharges pour la référence lvalue standard et la référence rvalue, ainsi que des iterators pour des listes d’éléments à insérer et des “indications” sur la position d’un élément. L’utilisation d’un iterator “hint” peut amener le temps d’insertion à la durée constante, sinon c’est le temps O (log (N)).

Opérateur []: vérifie si l’object existe et, si c’est le cas, modifie la référence à cet object, utilise la clé et la valeur fournies pour appeler make_pair sur les deux objects, puis effectue le même travail que la fonction d’insertion. C’est le temps O (log (N)).

make_pair: Fait un peu plus que faire une paire.

Il n’y avait pas de “besoin” pour append emplace à la norme. En c ++ 11, je crois que le type de référence && a été ajouté. Cela a éliminé la nécessité de la sémantique de déplacement et permis une optimisation de certains types de gestion de la mémoire. En particulier, la référence rvalue. L’opérateur insert (value_type &&) surchargé ne tire pas parti de la sémantique in_place et est donc beaucoup moins efficace. Bien qu’il offre la possibilité de traiter des références de valeur, il ignore leur objective principal, à savoir la construction d’objects.

Outre les possibilités d’optimisation et la syntaxe plus simple, une distinction importante entre l’insertion et la mise en place est que cette dernière permet des conversions explicites . (Ceci est dans toute la bibliothèque standard, pas seulement pour les cartes.)

Voici un exemple pour démontrer:

 #include  struct foo { explicit foo(int); }; int main() { std::vector v; v.emplace(v.end(), 10); // Works //v.insert(v.end(), 10); // Error, not explicit v.insert(v.end(), foo(10)); // Also works } 

C’est un détail très précis, mais lorsque vous traitez des chaînes de conversions définies par l’utilisateur, cela vaut la peine de garder cela à l’esprit.

Le code suivant peut vous aider à comprendre la “grande idée” de la différence entre insert() emplace() :

 #include  #include  #include  struct Foo { static int foo_counter; int val; 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 { std::size_t operator()(const Foo &f) const { return std::hash{}(f.val); } }; } int main() { std::unordered_map umap; Foo foo0, foo1, foo2, foo3; int d; std::cout < < "\numap.insert(std::pair(foo0, d))\n"; umap.insert(std::pair(foo0, d)); //equiv. to: umap.insert(std::make_pair(foo0, d)); std::cout < < "\numap.insert(std::move(std::pair(foo1, d)))\n"; umap.insert(std::move(std::pair(foo1, d))); //equiv. to: umap.insert(std::make_pair(foo1, d)); std::cout < < "\nstd::pair pair(foo2, d)\n"; std::pair 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(); } 

Le résultat que j'ai eu était:

 Foo() with val: 0 Foo() with val: 1 Foo() with val: 2 Foo() with val: 3 umap.insert(std::pair(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(foo1, d))) Foo(Foo &) with val: 6 created from: 1 Foo(Foo&&) moving: 6 and changing it to: 7 ~Foo() destroying: 6 std::pair 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 

Remarquerez que:

  1. unordered_map stocke toujours en interne les objects Foo (et non, disons, Foo * s) en tant que clés, qui sont toutes détruites lorsque le unordered_map est détruit. Ici, les clés internes de unordered_map étaient foos 13, 11, 5, 10, 7 et 9.

    • Donc, techniquement, notre unordered_map stocke réellement les objects std::pair , qui stockent à leur tour les objects Foo . Mais pour comprendre la "grande image" de la différence entre emplace() insert() (voir encadré ci-dessous), imaginez temporairement que cet object std::pair soit entièrement passif. Une fois que vous avez compris cette "idée d'ensemble", il est important de sauvegarder et de comprendre comment l'utilisation de cet object intermédiaire std::pair par unordered_map introduit des aspects techniques subtils, mais importants.
  2. Insérez chacun des foo0 , foo1 et foo2 requirejs 2 appels à l'un des constructeurs de copier / déplacer de Foo et 2 appels au destructeur de Foo (comme je le décris maintenant):

    une. L'insertion de chacun des foo0 et foo1 créé un object temporaire (respectivement foo4 et foo6 ) dont le destructeur a été immédiatement appelé après la fin de l'insertion. De plus, les destructeurs internes de la unordered_map (qui sont des foos 5 et 7) ont également leurs destructeurs appelés lorsque la unordered_map a été détruite.

    b. Pour insérer foo2 , nous avons d'abord créé une paire non temporaire ( foo8 ), qui a appelé le constructeur de copie de Foo , puis l'a insérée, ce qui a amené unordered_map à appeler le constructeur pour créer une copie interne ( foo9 ). Comme pour foos 0 et 1, le résultat final était deux appels de destructeurs pour cette insertion, la seule différence étant que le destructeur de foo8 n'était appelé que lorsque nous avions atteint la fin de main() .

  3. La mise en foo3 foo3 foo3 donné lieu qu'à 1 appel constructeur de copie / déplacement (création de foo10 interne) et à 1 seul appel au destructeur de Foo . (Je reviendrai plus tard).

  4. Pour foo11 , nous avons passé directement le nombre entier 11 afin que unordered_map appelle le constructeur Foo(int) . Contrairement à (3), nous n'avions même pas besoin d'un object foo pré-existant pour le faire.

Cela montre quelle est la différence principale entre les éléments insert() et emplace() :

Alors qu'utiliser insert() requirejs presque toujours la construction ou l'existence d'un object Foo dans main() scope de main() , suivie d'une copie ou d'un déplacement, si vous utilisez emplace() tout appel à un constructeur est entièrement interne. (c'est-à-dire dans la scope de la définition de la méthode emplace() ). Les arguments de la clé que vous transmettez à emplace() sont directement transmis à un appel de constructeur Foo dans unordered_map (détails supplémentaires facultatifs: où cet object nouvellement construit est immédiatement incorporé dans l'une des variables membres de unordered_map de sorte qu'aucun destructeur est appelée lorsque l'exécution quitte emplace() et qu'aucun constructeur de déplacement ou de copie n'est appelé).

Note: La raison du presque dans presque toujours est expliqué dans I) ci-dessous.

  1. suite: La raison pour laquelle l'appel de umap.emplace(foo3, d) appelé constructeur de copie non-const de Foo est la suivante: Puisque nous utilisons emplace() , le compilateur sait que foo3 (un object non-const Foo ) est censé être un argument pour un constructeur de Foo . Dans ce cas, le constructeur Foo le plus approprié est la construction de copie non-const Foo(Foo& f2) . C'est pourquoi umap.emplace(foo3, d) appelé un constructeur de copie alors que umap.emplace(11, d) ne l'a pas fait.

Épilogue:

I. Notez qu'une surcharge d' insert() est en réalité équivalente à emplace() . Comme décrit dans cette page cppreference.com , le template std::pair insert(P&& value) surcharge template std::pair insert(P&& value) (qui est la surcharge (2) de insert() sur cette page cppreference.com) est équivalent mettre en place emplace(std::forward

(value))

.

II. Où aller en partant d'ici?

une. Jouez avec le code source ci-dessus et étudiez la documentation pour insert() (par exemple ici ) et emplace() (par exemple ici ) qui se trouve en ligne. Si vous utilisez un IDE tel que eclipse ou NetBeans, vous pouvez facilement demander à votre EDI de vous indiquer quelle surcharge de insert() ou emplace() est appelée (en cas d'éclipse, gardez le curseur de la souris sur l'appel de la fonction). une seconde). Voici un code supplémentaire à essayer:

 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({" < < Foo::foo_counter << ", d}))\n"; umap.insert(std::pair({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::foo_counter << ", d}))\n"; umap.insert(std::pair({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 to the call above // being the additional { }. std::cout < < "\numap.insert({std::pair({" < < Foo::foo_counter << ", d})})\n"; umap.insert({std::pair({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>({{Foo::foo_counter, d}})); //The call below works fine, but the commented out line above gives a // comstackr error. It's instructive to find out why. The two cals // differ by a "const". std::cout < < "\numap.insert(std::initializer_list>({{" < < Foo::foo_counter << ", d}}))\n"; umap.insert(std::initializer_list>({{Foo::foo_counter, d}})); 

Vous verrez bientôt que la surcharge du constructeur std::pair (voir référence ) finit par être utilisée par unordered_map peut avoir un effet important sur le nombre d'objects copiés, déplacés, créés et / ou détruits et quand cela se produit.

b. Voyez ce qui se passe lorsque vous utilisez une autre classe de conteneur (par exemple std::set ou std::unordered_multiset ) au lieu de std::unordered_map .

c. Utilisez maintenant un object Goo (juste une copie renommée de Foo ) au lieu d'un int comme type d'intervalle dans un unordered_map (utilisez unordered_map au lieu de unordered_map ) et voyez combien de constructeurs Goo sont appelés. (Spoiler: il y a un effet mais ce n'est pas très dramatique.)