C++: value_type versus make_pair, ¿cuál es más rápido para la inserción de mapas?

Question

typedef map<KeyType, ValType> KVMap; 
KVMap kvmap; 

kvmap.insert(KVMap::value_type(key, val)); 
kvmap.insert(make_pair(key, val)); 

¿Cuál de las opciones anteriores para insertar en un mapa STL es siempre más rápida? ¿Por qué?

Nota: Soy muy consciente de que insert() es más rápido que usar []= para agregar (sin actualizar) los pares clave-valor a un mapa. Supongamos que mi consulta es sobre agregar, no actualizar. Por lo tanto, lo he restringido a insert().

Answer 1

Lo más probable es que la primera será 'rápido-épsilon', debido a esto (de 23.3.1 de la norma) :

typedef pair<const Key, T> value_type; 

[...] 

pair<iterator, bool> insert(const value_type& x); 

• En la primera versión, se construyen directamente el tipo apropiado esperado por std::map<K,V>::insert

• En la segunda versión, se trata de una conversión con el constructor de plantillas std::pair. De hecho, std::make_pair probablemente deducirá sus argumentos de plantilla a KeyType y ValType, devolviendo así un std::pair<KeyType, ValType>.

  Esto no coincide con el tipo de parámetro de std::map<K,V>::insert, que es std::pair<const KeyType, ValType> (la diferencia es const -calificado primero). El constructor de conversión std::pair se usará para crear un std::pair<const K, V> desde el std::pair<K, V>.

Para ser justos, no creo que incluso podría medir la diferencia (y ni siquiera estoy seguro de que los compiladores populares en realidad se generará un código diferente para estos).

Answer 2

Son fundamentalmente lo mismo. KVMap::value_type es un typedef para std::pair<KeyType, ValType>, así que eso es solo llamar al constructor. std::make_pair es una función de plantilla que simplemente llama al constructor (existe porque los tipos de plantilla se pueden deducir para funciones libres, pero no para constructores). Una vez que se realizan todas las optimizaciones increíblemente estándar, no hay ninguna razón para que haya alguna diferencia.

No sé cómo lo está probando, pero hay muchas, muchas formas de hacerlo bien.

En cuanto a insert() y la asignación a través de operator[], este último tiene que trabajar más conceptualmente (cuando agrega un nuevo elemento de esta manera, primero se supone que construye un elemento por defecto y luego lo asigna encima) , pero dependiendo del ValType, podría ser optimizado básicamente en lo mismo otra vez.

Answer 3

En realidad hay un argumento para value_type sobre make_pair. Esto se debe a que, por diversas razones arcanas, make_pair acepta sus argumentos por valor. Por otro lado, value_type, un alias para std::pair<const Key, value>, tendrá su constructor llamado con los argumentos pasados ​​por referencia const. Existe una pérdida potencial de eficiencia por el valor de paso en make_pair en comparación con la referencia de paso por paso, que en teoría podría tener un impacto notable en su programa.

Otra cuestión que estar preocupado con make_pairmake_pair es que generalmente crear un par de tipo std::pair<Key, Value> frente al std::pair<const Key, Value> necesaria dentro de la map. Esto significa que puede haber otra copia innecesaria, esta vez del pair para que la conversión funcione correctamente.

En resumen, usar make_pair podría causar dos copias completamente innecesarias de la clave y el valor para hacerse, mientras que el constructor value_type no tiene ninguno.

Answer 4

Esto es solo un complemento.

insert(make_pair(...)) llama al constructor de copias 4 veces debido a la razón por la que se han mencionado otros respondedores.

insert(value_type(...)) llamadas copy constructor 2 veces.

operator[] llama al constructor predeterminado una vez y copia el constructor 2 veces en una implementación típica. el constructor predeterminado se llama adentro operator[] para insert(value_type(..., mapped_type())). copy constructor se llama una vez para copiar el argumento insert() (pair), y una vez para copiar y construir un nodo interno del mapa.

Por lo tanto, si se utiliza con insertmake_pair, no puede decirse que insert es siempre más rápido que operator[] incluso para la adición. Probablemente, depende de la situación. Como ya sabrá, a la vista de lo anterior, se propuso emplace para la nueva norma .