c++ - mostrar - mapas para paginas web

C++: value_type versus make_pair, ¿cuál es más rápido para insertar un mapa?

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 consciente de que insert() es más rápido que usar []= para agregar (no actualizar) pares clave-valor a un mapa. Por favor, suponga que mi consulta es sobre agregar, no actualizar. Por lo tanto lo he restringido para insert() .

Answer 1

En realidad, hay un argumento que se debe hacer para value_type over 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 del paso por valor en make_pair versus pass-by-reference, que en teoría podría tener un impacto notable en su programa.

Otro problema que preocupa con make_pair es que make_pair generalmente creará un par de tipo std::pair<Key, Value> versus std::pair<const Key, Value> necesario dentro del map . Esto significa que podría haber otra copia innecesaria, esta vez del pair para que la conversión funcione correctamente.

En resumen, el uso de make_pair puede hacer que se make_pair dos copias completamente innecesarias de la clave y el valor, mientras que el uso del constructor value_type no tiene ninguna.

Answer 2

Es probable que el primero sea ''épsilon-más rápido'' , debido a esto (de 23.3.1 en el estándar):

typedef pair<const Key, T> value_type;

[...]

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

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

• En la segunda versión, hay una conversión que utiliza 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 std::map<K,V>::insert , que es std::pair<const KeyType, ValType> (la diferencia es la primera const .). El constructor de conversión std::pair se utilizará para crear un std::pair<const K, V> partir del std::pair<K, V> .

Para ser justos, no creo que puedas medir la diferencia (y ni siquiera estoy seguro de que los compiladores populares realmente generen un código diferente para estos).

Answer 3

Esto es sólo una suplementación.

insert( make_pair(...) ) llama al constructor de copias 4 veces de forma teórica debido a la razón que mencionaron otros respondedores.

insert( value_type(...) ) llama al constructor de copias 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 dentro del operator[] para insert( value_type( ..., mapped_type() ) ) . copy constructor se llama una vez para copiar el argumento de insert() ( pair ), y una vez para copiar-construir un nodo interno del mapa.

Por lo tanto, si usa insert con make_pair , no se puede decir que insert sea ​​siempre más rápido que el operator[] incluso para agregar. Probablemente, depende de la situación. Como usted puede saber, en vista de lo anterior, se propuso emplace para la nueva norma.

Answer 4

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 gratuitas, pero no para constructores). Una vez que se realizan todas las optimizaciones increíblemente estándar, no hay razón para que haya alguna diferencia.

No sé cómo estás probando, pero hay muchas, muchas maneras de hacerlo mal.

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