insertar vs emplace vs operador[] en el mapa c++

dictionary operators

Question

Estoy usando mapas por primera vez y me di cuenta de que hay muchas maneras de insertar un elemento. Puede usar emplace() , operator[] o insert() , además de variantes como usar value_type o make_pair . Si bien hay mucha información sobre todos ellos y preguntas sobre casos particulares, aún 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 emplazamiento al estándar? ¿Hay algo que no fuera posible antes sin eso?

Answer 1

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 este último permite conversiones explícitas . (Esto se encuentra en toda la biblioteca estándar, no solo para 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
}

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

Answer 2

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>

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

    std::cout << "/numap.insert(std::pair<Foo, int>(foo0, d))/n";
    umap.insert(std::pair<Foo, int>(foo0, d));
    //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)));
    //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_map siempre almacena internamente objetos Foo (y no, por ejemplo, Foo * s) como claves, que se destruyen cuando se destruye el unordered_map . Aquí, las claves internas de unordered_map eran foos 13, 11, 5, 10, 7 y 9.

   • Por lo tanto, técnicamente, nuestro unordered_map realidad almacena objetos std::pair<const Foo, int> , que a su vez almacenan los objetos Foo . Pero para comprender la "idea general" de cómo se diferencia emplace() de insert() (vea el recuadro resaltado a continuación), está bien imaginar temporalmente que este objeto std::pair es completamente pasivo. Una vez que comprenda esta "idea general", es importante hacer una copia de seguridad y comprender cómo el uso de este objeto intermediario std::pair mediante unordered_map introduce tecnicismos sutiles pero importantes.

2. Insertar cada uno de foo0 , foo1 y foo2 requirió 2 llamadas a uno de los constructores de copiar / mover de Foo y 2 llamadas al destructor de Foo (como ahora lo describo):

   a. Al insertar cada uno de foo0 y foo1 creó un objeto temporal ( foo4 y foo6 , respectivamente) cuyo destructor fue llamado inmediatamente después de que se completara la inserción. Además, los Foo internos de unordered_map (que son foos 5 y 7) también tenían sus destructores llamados cuando se destruyó el mapa desordenado.

   segundo. Para insertar foo2 , primero creamos un par no temporal ( foo8 ), que llamaba al constructor de copia de Foo , y luego lo foo8 , lo que dio como resultado que unordered_map llamara al constructor de copia nuevamente para crear una copia interna ( foo9 ). Al igual que con los foos 0 y 1, el resultado final fueron dos llamadas al destructor para esta inserción con la única diferencia de que el foo8 de foo8 solo se foo8 cuando llegamos al final de main() .

3. foo3 resultó en solo 1 copia / llamada de constructor de movimiento (creando foo10 internamente) y solo 1 llamada al destructor de Foo . (Volveré a esto más tarde).

4. Para foo11 , pasamos directamente el número entero 11 para que unordered_map llamara al constructor Foo(int) . A diferencia de (3), ni siquiera necesitábamos algún objeto Foo preexistente para hacer esto.

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

Mientras que el uso de insert() casi siempre requiere la construcción o existencia de algún objeto Foo en el alcance de main() (seguido de una copia o movimiento), si usa emplace() entonces cualquier llamada a un constructor se realiza completamente internamente en el unordered_map (es decir, dentro del alcance de la definición del método emplace() ). El argumento (s) para la clave que pasa a emplace() se reenvía directamente a una llamada de constructor Foo dentro de unordered_map (detalles adicionales opcionales: donde este objeto recién construido se incorpora inmediatamente en una de las variables miembro de unordered_map para que no destructor se emplace() cuando la ejecución deja a emplace() y no se llaman constructores de movimiento o copia).

Nota: La razón de la casi en casi siempre se explica en I) a continuación.

3. continúa: La razón por la cual llamar a umap.emplace(foo3, d) llamado constructor de copias no umap.emplace(foo3, d) Foo es el siguiente: dado que estamos usando emplace() , el compilador sabe que foo3 (un objeto Foo no const) es pretende ser un argumento para algún constructor de Foo . En este caso, el constructor de Foo más apropiado es la construcción de copia sin conformismo Foo(Foo& f2) . Esta es la razón umap.emplace(foo3, d) cual umap.emplace(foo3, d) llamó a un constructor de copia mientras que umap.emplace(11, d) no lo hizo.

Epílogo:

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

II. A dónde ir desde aquí?

a. Juega con el código fuente anterior y la documentación de estudio para insert() (por ejemplo, aquí ) y emplace() (por ejemplo, here ) que se encuentra en línea. Si está utilizando un IDE como eclipse o NetBeans, puede hacer que su IDE le diga con facilidad qué sobrecarga de insert() o emplace() se llama (en eclipse, simplemente mantenga el cursor del mouse sobre la llamada de función para un segundo). Aquí hay un código más 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 to 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 cals
// 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á que qué sobrecarga del constructor std::pair (ver reference ) termina siendo usado por unordered_map puede tener un efecto importante en la cantidad de objetos que se copian, mueven, crean y / o destruyen y cuando esto ocurre.

segundo. Vea lo que sucede cuando utiliza alguna otra clase de contenedor (por ejemplo, std::set o std::unordered_multiset ) en lugar de std::unordered_map .

do. Ahora usa un objeto Goo (solo una copia renombrada de Foo ) en lugar de un int como tipo de rango en un unordered_map (es decir, usa unordered_map<Foo, Goo> lugar de unordered_map<Foo, int> ) y ve cuántos y qué constructores de Goo son llamados. (Spoiler: hay un efecto pero no es muy dramático.)

Answer 3

Emplace: aprovecha la referencia rvalue para usar los objetos reales que ya ha creado. Esto significa que no se llama a ningún constructor de copiar o mover, ¡es bueno para objetos GRANDES! O (log (N)) tiempo.

Insertar: tiene sobrecargas para referencia de valor l estándar y referencia de valor r, así como también iteradores para listas de elementos para insertar y "sugerencias" sobre la posición a la que pertenece un elemento. El uso de un iterador "sugerencia" puede hacer que la inserción de tiempo disminuya al tiempo de contant, de lo contrario es el 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 realiza 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 hubo "necesidad" de agregar emplazamiento al estándar. En c ++ 11 creo que se agregó el tipo de referencia &&. Esto eliminó la necesidad de semántica de movimiento y permitió la optimización de algún tipo específico de gestión de memoria. En particular, la referencia rvalue. 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 brinda la capacidad de tratar con las referencias de valor real, ignora su propósito clave, que es la construcción de objetos.

Answer 4

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

El operator[] es un operator[] buscar o agregar . Tratará de 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 la inicialización predeterminada y le devolverá una referencia.

La función de insert (en el elemento único sabor) toma un value_type ( std::pair<const Key,Value> ), usa la clave ( first miembro) e intenta insertarlo. Debido a que std::map no permite duplicados si hay un elemento existente, no insertará nada.

La primera diferencia entre los dos es que el operator[] necesita poder construir un valor inicializado predeterminado, y por lo tanto no se puede utilizar para los tipos de valores que no pueden inicializarse por defecto. La segunda diferencia entre los dos es lo que sucede cuando ya hay un elemento con la clave dada. La función de insert no modificará el estado del mapa, sino que devolverá un iterador al elemento (y un false que indica 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 de insert el argumento es un objeto de value_type , que se puede crear de diferentes maneras. Puedes construirlo directamente con el tipo apropiado o pasar cualquier objeto desde el que se pueda construir value_type , que es donde std::make_pair entra en juego, ya que permite la creación simple de objetos std::pair , aunque probablemente no sea Lo que quieras...

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 función de insert . La función de insert creará el nodo apropiado en el árbol de búsqueda binaria y luego copiará la parte value_type del argumento al nodo. La ventaja de utilizar value_type es que, bueno, value_type siempre coincide con value_type , ¡no se puede confundir el tipo de los argumentos std::pair !

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

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

Intencionalmente no proporcioné los argumentos de la plantilla a 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 ser T==K,U==V , por lo que la llamada a std::make_pair devolverá un std::pair<K,V> ( nota la const faltante). La firma requiere value_type que está cerca pero no es lo mismo que el valor devuelto de la llamada a std::make_pair . Debido a que está lo suficientemente cerca, creará un tipo temporal del tipo correcto y 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 escribiendo explícitamente el tipo en el caso [1].

Hasta este punto, tenemos diferentes formas de llamar a insert que requieren la creación de value_type externamente y la copia de ese objeto en el contenedor. Alternativamente, puede usar el operator[] si el tipo es predecible, 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 un reenvío perfecto, hay una nueva forma de agregar elementos a un contenedor por medio de la colocación (creación en el lugar). Las funciones emplace 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 reenviarán al constructor del objeto almacenado en el contenedor.

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

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

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