STL rendimiento del mapa de inserción: [] vs. inserción

Question

Hay dos formas de inserción mapa:

m[key] = val; 

O

m.insert(make_pair(key, val)); 

Mi pregunta es, que el funcionamiento es más rápido? La gente suele decir que el primero es más lento, porque el estándar STL al principio 'inserta' un elemento predeterminado si 'clave' no existe en el mapa y luego asigna 'val' al elemento predeterminado.

Pero no veo que la segunda forma sea mejor debido a 'make_pair'. make_pair en realidad es una forma conveniente de hacer 'pair' en comparación con pair<T1, T2>(key, val). De todos modos, ambos hacen dos asignaciones, una es asignar 'clave' a 'pair.first' y dos es asignar 'val' a 'pair.second'. Después de crear el par, el mapa inserta el elemento inicializado por 'pair.second'.

Así que la primera manera es 1. '' 2. default construct of typeof(val) asignación la segunda manera es 1. Tarea 2. '' copy construct of typeof(val)

Answer 1

Tanto lograr cosas diferentes.

m[key] = val; 

insertará un nuevo par clave-valor si el key no existe ya, o se sobreponen el antiguo valor asignado a la key si ya existe.

m.insert(make_pair(key, val)); 

sólo se insertará el par si key no existe, sin embargo, nunca se sobrescribe el valor anterior. Entonces, elija de acuerdo a lo que quiere lograr.
Para la pregunta, ¿qué es más eficiente: perfil. : P Probablemente la primera manera en que diría. La asignación (también conocida como copia) es el caso en ambos sentidos, por lo que la única diferencia radica en la construcción. Como todos sabemos y deberíamos implementar, una construcción predeterminada debería ser básicamente no operativa y, por lo tanto, ser muy eficiente. Una copia es exactamente eso, una copia. Así que en la forma uno recibimos un "no-op" y una copia, y en el modo dos recibimos dos copias.
Editar: Al final, confíe en lo que le dice su perfil. Mi análisis fue apagado como @Matthieu menciona en su comentario, pero esa fue mi conjetura. :)

---

entonces, hemos C++ 0x que viene, y el doble copia en la segunda forma sería cero, ya que la pareja simplemente se puede mover ahora. Así que, al final, creo que se basa en mi primer punto: utilizar de la manera correcta para lograr lo que quieres hacer.

Answer 2

En un sistema ligeramente cargado con un montón de memoria, este código:

#include <map> 
#include <iostream> 
#include <ctime> 
#include <string> 

using namespace std; 

typedef map <unsigned int,string> MapType; 
const unsigned int NINSERTS = 1000000; 

int main() { 
    MapType m1; 
    string s = "foobar"; 
    clock_t t = clock(); 
    for (unsigned int i = 0; i < NINSERTS; i++) { 
     m1[i] = s; 
    } 
    cout << clock() - t << endl; 
    MapType m2; 
    t = clock(); 
    for (unsigned int i = 0; i < NINSERTS; i++) { 
     m2.insert(make_pair(i, s)); 
    } 
    cout << clock() - t << endl; 
} 

produce:

1547 
1453 

o similares valores en repetidas carreras. Entonces insertar es (en este caso) marginalmente más rápido.

Answer 3

Tenemos que refinar el análisis mencionando que el rendimiento relativo depende del tipo (tamaño) de los objetos que se están copiando también.

Hice un experimento similar (a nbt) con un mapa de (int -> set). Sé que es algo terrible de hacer, pero ilustrativo para este escenario.El "valor", en este caso un conjunto de ints, tiene 20 elementos.

Ejecuto un millón de iteraciones de [] = Vs. inserte operaciones y haga el conteo RDTSC/iter.

[] = set | 10731 ciclos

inserción (make_pair <>) | 26100 ciclos

Muestra la magnitud de la penalización añadida debido a la copia. Por supuesto, CPP11 (move ctor's) cambiará la imagen.

Answer 4

En cuanto al rendimiento, creo que en general son los mismos en general. Puede haber algunas excepciones para un mapa con objetos grandes, en cuyo caso debe usar [] o quizás emplace, que crea menos objetos temporales que 'insertar'. Consulte la discusión here para más detalles.

Sin embargo, puede obtener un aumento de rendimiento en casos especiales si utiliza la función 'pista' en el operador de inserción. Por lo tanto, mirando a la opción 2 de here:

iterator insert (const_iterator position, const value_type& val); 

la operación 'insertar' se puede reducir a un tiempo constante (de log (n)) si se le da un buen toque (a menudo el caso si usted sabe que va a agregar cosas en la parte posterior de su mapa).

Answer 5

Mi opinión: Vale la pena recordar que los mapas son un árbol binario balanceado, la mayoría de las modificaciones y comprobaciones toman O (logN).

Depende realmente del problema que está tratando de resolver.

1) si sólo desea insertar el valor sabiendo que no está allí todavía, continuación, [] que hacer dos cosas: a) verificar si el artículo está allí o no b) si no está allí creará un par y hará lo que hace la inserción ( doble trabajo de O (logN)), así que usaría insertar.

2) si no está seguro si está allí o no, entonces a) si verificó si el elemento está allí haciendo algo como if (map.find (item) == mp.end()) un par de líneas arriba en alguna parte, luego use insert, debido al doble trabajo [] se realizaría b) si no lo hizo, entonces depende, porque insertar no modificará el valor si está allí, [] lo hará, de lo contrario son iguales