Insertar vs Emplace vs operador [] en el mapa de C ++

Estoy usando mapas por primera vez y me di cuenta de que hay muchas formas de insertar un elemento. Puede usar emplace(), operator[]o insert(), más variantes como usar value_typeo make_pair. Si bien hay mucha información sobre todos ellos y preguntas sobre casos particulares, todavía no puedo entender el panorama general. Entonces, mis dos preguntas son:

1. ¿Cuál es la ventaja de cada uno de ellos sobre los demás?

2. ¿Hubo alguna necesidad de agregar un lugar al estándar? ¿Hay algo que antes no fuera posible sin él?

En el caso particular de un mapa, las opciones anteriores eran solo dos: operator[]y insert(diferentes sabores de insert). Entonces comenzaré a explicar eso.

El operator[]es un operador de buscar o agregar . Intentará encontrar un elemento con la clave dada dentro del mapa y, si existe, devolverá una referencia al valor almacenado. Si no lo hace, creará un nuevo elemento insertado en su lugar con una inicialización predeterminada y le devolverá una referencia.

La insertfunción (en el sabor del elemento único) toma un value_type( std::pair<const Key,Value>), usa la clave ( firstmiembro) e intenta insertarlo. Debido a std::mapque no permite duplicados si hay un elemento existente, no insertará nada.

La primera diferencia entre los dos es que operator[]tiene que ser capaz de construir un defecto inicializado valor , y es así inutilizable para los tipos de valor que no puede ser predeterminado inicializado. La segunda diferencia entre los dos es lo que sucede cuando ya hay un elemento con la clave dada. La insertfunción no modificará el estado del mapa, sino que devolverá un iterador al elemento (y una falseindicación de que no se insertó).

// 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

En el caso del insertargumento es un objeto de value_type, que se puede crear de diferentes maneras. Puede construirlo directamente con el tipo apropiado o pasar cualquier objeto a partir del cual value_typese pueda construir, que es donde std::make_pairentra en juego, ya que permite la creación simple de std::pairobjetos, aunque probablemente no sea lo que desea ...

El efecto neto de las siguientes llamadas es similar :

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

Pero en realidad no son lo mismo ... [1] y [2] son ​​en realidad equivalentes. En ambos casos, el código crea un objeto temporal del mismo tipo ( std::pair<const K,V>) y lo pasa a la insertfunción. La insertfunción creará el nodo apropiado en el árbol de búsqueda binario y luego copiará la value_typeparte del argumento al nodo. La ventaja de usar value_typees que, bueno, value_typesiempre coincide value_type , ¡no puedes escribir mal el tipo de std::pairargumentos!

La diferencia está en [3]. La función std::make_paires una función de plantilla que creará una std::pair. La firma es:

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

No he proporcionado intencionalmente los argumentos de la plantilla std::make_pair, ya que ese es el uso común. Y la implicación es que los argumentos de la plantilla se deducen de la llamada, en este caso T==K,U==V, por lo que la llamada a std::make_pairdevolverá un std::pair<K,V>(tenga en cuenta lo que falta const). La firma requiere value_typeque esté cerca pero no sea lo mismo que el valor devuelto de la llamada a std::make_pair. Debido a que está lo suficientemente cerca, creará un temporal del tipo correcto y la copia lo inicializará. Eso a su vez se copiará en el nodo, creando un total de dos copias.

Esto se puede solucionar proporcionando los argumentos de la plantilla:

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

Pero eso sigue siendo propenso a errores de la misma manera que escribir explícitamente el tipo en el caso [1].

Hasta este punto, tenemos diferentes formas de llamar insertque requieren la creación de lo value_typeexterno y la copia de ese objeto en el contenedor. Alternativamente, puede usar operator[]si el tipo es por defecto construible y asignable (enfocando intencionalmente solo en m[k]=v), y requiere la inicialización predeterminada de un objeto y la copia del valor en ese objeto.

En C ++ 11, con plantillas variadas y reenvío perfecto, hay una nueva forma de agregar elementos a un contenedor mediante la colocación (creación en el lugar). Las emplacefunciones en los diferentes contenedores hacen básicamente lo mismo: en lugar de obtener una fuente desde la cual copiar en el contenedor, la función toma los parámetros que se enviarán al constructor del objeto almacenado en el contenedor.

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

En [5], std::pair<const K, V>no se crea ni se pasa a emplace, sino que se pasan referencias al objeto ty que lo reenvía al constructor del subobjeto dentro de la estructura de datos. En este caso, no se realizan copias , lo cual es la ventaja de las alternativas de C ++ 03. Como en el caso , no anulará el valor en el mapa.uemplacevalue_typestd::pair<const K,V>emplaceinsert

Una pregunta interesante en la que no había pensado es cómo emplacese puede implementar realmente para un mapa, y ese no es un problema simple en el caso general.

Emplace: Aprovecha la referencia rvalue para usar los objetos reales que ya has creado. Esto significa que no se llama ningún constructor de copia o movimiento, ¡bueno para objetos GRANDES! O (log (N)) tiempo.

Insertar: tiene sobrecargas para la referencia estándar de lvalue y rvalue reference, así como iteradores para listas de elementos para insertar y "pistas" sobre la posición a la que pertenece un elemento. El uso de un iterador de "pista" puede hacer que la inserción de tiempo se reduzca al tiempo de contacto, de lo contrario es tiempo O (log (N)).

Operador []: comprueba si el objeto existe y, si lo hace, modifica la referencia a este objeto, de lo contrario utiliza la clave y el valor proporcionados para llamar a make_pair en los dos objetos, y luego hace el mismo trabajo que la función de inserción. Este es el tiempo O (log (N)).

make_pair: hace poco más que hacer un par.

No había "necesidad" de agregar un lugar al estándar. En c ++ 11 creo que se agregó el tipo de referencia &&. Esto eliminó la necesidad de mover la semántica y permitió la optimización de algún tipo específico de administración de memoria. En particular, la referencia de valor. El operador de inserción sobrecargado (value_type &&) no aprovecha la semántica in_place y, por lo tanto, es mucho menos eficiente. Si bien proporciona la capacidad de tratar con referencias de valor, ignora su propósito clave, que es la construcción de objetos.

Además de las oportunidades de optimización y la sintaxis más simple, una distinción importante entre la inserción y el emplazamiento es que esta última permite explícitamente conversiones . (Esto se encuentra en toda la biblioteca estándar, no solo para los mapas).

Aquí hay un ejemplo para demostrar:

#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
}

Este es ciertamente un detalle muy específico, pero cuando se trata de cadenas de conversiones definidas por el usuario, vale la pena tener esto en cuenta.

El siguiente código puede ayudarlo a comprender la "idea general" de cómo insert()difiere de 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();
}

El resultado que obtuve fue:

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

Darse cuenta de:

1. Un unordered_mapsiempre almacena internamente Fooobjetos (y no, digamos, Foo *s) como claves, que se destruyen cuando unordered_mapse destruye. Aquí, las unordered_mapteclas internas de los foos 13, 11, 5, 10, 7 y 9.

   • Técnicamente, nuestro unordered_maprealmente almacena std::pair<const Foo, int>objetos, que a su vez almacenan los Fooobjetos. Pero para comprender la "idea general" de cómo emplace()difiere de insert()(ver el cuadro resaltado a continuación), está bien imaginar temporalmente este std::pairobjeto como completamente pasivo. Una vez que comprenda esta "idea general", es importante hacer una copia de seguridad y comprender cómo el uso de este std::pairobjeto intermediario unordered_mapintroduce tecnicismos sutiles, pero importantes.

2. Insertar cada una de foo0, foo1y foo2requirió 2 llamadas a uno de Foolos constructores de copiar / mover y 2 llamadas aFoo destructor (como describo ahora):

   a. Al insertar cada uno de ellos foo0y foo1crear un objeto temporal ( foo4y foo6, respectivamente) cuyo destructor fue llamado inmediatamente después de que se completó la inserción. Además, los Foos internos del unordered_map (que son Foos 5 y 7) también tenían sus destructores llamados cuando el unordered_map fue destruido.

   si. Para insertar foo2, en su lugar, primero creamos explícitamente un objeto de par no temporal (llamado pair), que llamó Fooal constructor de copia en foo2(creando foo8como un miembro interno de pair). Luego insert()editamos este par, lo que resultó en unordered_mapllamar nuevamente al constructor de copias (on foo8) para crear su propia copia interna ( foo9). Al igual que con foos 0 y 1, el resultado final fue dos llamadas de destructor para esta inserción, con la única diferencia de que ese foo8destructor se llamó solo cuando llegamos al final de, en main()lugar de ser llamado inmediatamente después de insert()finalizar.

3. El empalme foo3resultó en solo 1 llamada al constructor copiar / mover (creando foo10internamente en unordered_map) y solo 1 llamada al Foodestructor. (Volveré a esto más tarde).

4. Para foo11, pasamos directamente el entero 11 a emplace(11, d)para que unordered_mapllame al Foo(int)constructor mientras la ejecución está dentro de su emplace()método. A diferencia de (2) y (3), ni siquiera necesitábamos algún fooobjeto preexistente para hacer esto. Es importante destacar que solo se Fooprodujo 1 llamada a un constructor (que creó foo11).

5. Luego pasamos directamente el entero 12 a insert({12, d}). A diferencia de con emplace(11, d)(cuya recuperación resultó en solo 1 llamada a un Fooconstructor), esta llamada a insert({12, d})resultó en dos llamadas al Fooconstructor (creación foo12y foo13).

Esto muestra cuál es la principal diferencia de "panorama general" entre insert()y emplace()es:

Mientras que el uso insert() casi siempre requiere la construcción o existencia de algún Fooobjeto dentro main()del alcance (seguido de una copia o movimiento), si se usa, emplace()entonces cualquier llamada a un Fooconstructor se realiza completamente internamente en unordered_map(es decir, dentro del alcance de la emplace()definición del método). Los argumentos de la clave a la que pasa emplace()se reenvían directamente a una Foollamada de constructor dentro unordered_map::emplace()de la definición (detalles adicionales opcionales: donde este objeto recién construido se incorpora de inmediato a una de unordered_maplas variables miembro para que no se llame a ningún destructor cuando la ejecución se va emplace()y no se llama ningún constructor de movimiento o copia).

Nota: La razón para el " casi " en " casi siempre " arriba se explica en I) a continuación.

3. continuación: La razón por la cual llamar al constructor de copia no const umap.emplace(foo3, d)llamada Fooes el siguiente: dado que estamos usando emplace(), el compilador sabe que foo3(un Fooobjeto no const ) está destinado a ser un argumento para algún Fooconstructor. En este caso, el Fooconstructor más adecuado es el constructor de copia no constante Foo(Foo& f2). Es por eso que umap.emplace(foo3, d)llamó a un constructor de copia mientras umap.emplace(11, d)que no lo hizo.

Epílogo:

I. Tenga en cuenta que una sobrecarga de en insert()realidad es equivalente a emplace() . Como se describe en esta página de cppreference.com , la sobrecarga template<class P> std::pair<iterator, bool> insert(P&& value)(que es la sobrecarga (2) de insert()en esta página de cppreference.com) es equivalente a emplace(std::forward<P>(value)).

II A dónde ir desde aquí?

a. Juegue con el código fuente anterior y la documentación de estudio para insert()(por ejemplo, aquí ) y emplace()(por ejemplo, aquí ) que se encuentra en línea. Si está utilizando un IDE como eclipse o NetBeans, puede obtener fácilmente su IDE para indicarle qué sobrecarga insert()o qué emplace()se está llamando (en eclipse, solo mantenga el cursor del mouse fijo sobre la llamada de función por un segundo). Aquí hay más código para probar:

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

Pronto verás qué sobrecarga del std::pairconstructor (ver referencia ) termina siendo utilizada porunordered_map puede tener un efecto importante en la cantidad de objetos que se copian, mueven, crean y / o destruyen, así como cuándo ocurre todo esto.

si. Vea lo que sucede cuando usa alguna otra clase de contenedor (por ejemplo, std::setor std::unordered_multiset) en lugar destd::unordered_map .

C. Ahora use un Gooobjeto (solo una copia renombrada de Foo) en lugar de an intcomo el tipo de rango en un unordered_map(es decir, use en unordered_map<Foo, Goo>lugar de unordered_map<Foo, int>) y vea cuántos y a qué Gooconstructores se llaman. (Spoiler: hay un efecto pero no es muy dramático).

En términos de funcionalidad o salida, ambos son iguales.

Para ambas memorias grandes, el emplazamiento de objetos está optimizado para la memoria y no utiliza constructores de copia

Para una explicación simple y detallada https://medium.com/@sandywits/all-about-emplace-in-c-71fd15e06e44