En los mapas STL, ¿es mejor usar map :: insert que []?

201

Hace un tiempo, tuve una discusión con un colega sobre cómo insertar valores en los mapas STL . Preferí map[key] = value; porque se siente natural y es claro de leer, mientras que él prefirió map.insert(std::make_pair(key, value))

Simplemente le pregunté y ninguno de nosotros puede recordar la razón por la cual insertar es mejor, pero estoy seguro de que no fue solo una preferencia de estilo, sino que hubo una razón técnica como la eficiencia. La referencia de SGI STL simplemente dice "Estrictamente hablando, esta función miembro es innecesaria: existe solo por conveniencia".

¿Alguien puede decirme esa razón, o solo estoy soñando que hay una?

danio
fuente
2
Gracias por todas las excelentes respuestas, han sido realmente útiles. Esta es una gran demostración de desbordamiento de pila en su mejor momento. No sabía cuál debería ser la respuesta aceptada: netjeff es más explícito sobre el comportamiento diferente, Greg Rogers mencionó problemas de rendimiento. Ojalá pudiera marcar los dos.
danio
66
En realidad, con C ++ 11, probablemente sea mejor usar map :: emplace que evita la doble construcción
einpoklum
@einpoklum: En realidad, Scott Meyers sugiere lo contrario en su charla "La búsqueda evolutiva de C ++ eficaz".
Thomas Eding
3
@einpoklum: Ese es el caso cuando se emplaza en la memoria recién construida. Pero debido a algunos requisitos estándar para el mapa, existen razones técnicas por las cuales el emplazamiento puede ser más lento que la inserción. La charla está disponible gratuitamente en youtube, como este enlace youtube.com/watch?v=smqT9Io_bKo @ ~ 38-40 min mark. Para un enlace SO, aquí está stackoverflow.com/questions/26446352/…
Thomas Eding
1
De hecho, discutiría algo de lo que presentó Meyers, pero eso está más allá del alcance de este hilo de comentarios y de todos modos, supongo que tengo que retractar mi comentario anterior.
einpoklum

Respuestas:

240

Cuando escribes

map[key] = value;

no hay forma de saber si reemplazaste el valuefor keyo si creaste uno nuevo keycon value.

map::insert() solo creará:

using std::cout; using std::endl;
typedef std::map<int, std::string> MyMap;
MyMap map;
// ...
std::pair<MyMap::iterator, bool> res = map.insert(MyMap::value_type(key,value));
if ( ! res.second ) {
    cout << "key " <<  key << " already exists "
         << " with value " << (res.first)->second << endl;
} else {
    cout << "created key " << key << " with value " << value << endl;
}

Para la mayoría de mis aplicaciones, generalmente no me importa si estoy creando o reemplazando, por lo que utilizo el más fácil de leer map[key] = value.

netjeff
fuente
16
Cabe señalar que map :: insert nunca reemplaza valores. Y en el caso general, diría que es mejor usar en (res.first)->secondlugar de valuetambién en el segundo caso.
dalle
1
Actualicé para ser más claro que map :: insert nunca reemplaza. Dejé el elseporque creo que usar valuees más claro que el iterador. Solo si el tipo del valor tuviera una copia inusual u op == sería diferente, y ese tipo causaría otros problemas al usar contenedores STL como map.
netjeff
1
map.insert(std::make_pair(key,value))debería ser map.insert(MyMap::value_type(key,value)). El tipo devuelto desde make_pairno coincide con el tipo tomado inserty la solución actual requiere una conversión
David Rodríguez - dribeas
1
hay una manera de saber si ha insertado o simplemente asignado operator[], simplemente compare el tamaño antes y después. Imho poder llamar map::operator[]solo para tipos construibles predeterminados es mucho más importante.
idclev 463035818
@ DavidRodríguez-dribeas: Buena sugerencia, actualicé el código en mi respuesta.
netjeff
53

Los dos tienen una semántica diferente cuando se trata de la clave que ya existe en el mapa. Entonces no son realmente directamente comparables.

Pero la versión del operador [] requiere la construcción predeterminada del valor y luego la asignación, por lo que si esto es más costoso que copiar la construcción, entonces será más costoso. A veces, la construcción predeterminada no tiene sentido, y entonces sería imposible usar la versión del operador [].

Greg Rogers
fuente
1
make_pair puede requerir un constructor de copia, que sería peor que el predeterminado. +1 de todos modos.
1
Lo principal es, como dijiste, que tienen una semántica diferente. Entonces, ninguno es mejor que el otro, solo use el que haga lo que necesita.
jalf
¿Por qué el constructor de copia sería peor que el constructor predeterminado seguido de la asignación? Si es así, entonces la persona que escribió la clase se ha perdido algo, porque cualquier operador = hace, deberían haber hecho lo mismo en el constructor de la copia.
Steve Jessop
1
A veces, la construcción predeterminada es tan costosa como la tarea misma. Naturalmente, la asignación y la construcción de la copia serán equivalentes.
Greg Rogers
@Arkadiy En una compilación optimizada, el compilador a menudo eliminará muchas llamadas innecesarias de constructor de copias.
antred
35

Otra cosa a tener en cuenta std::map :

myMap[nonExistingKey]; creará una nueva entrada en el mapa, clave para nonExistingKey inicializada a un valor predeterminado.

Esto me asustó muchísimo la primera vez que lo vi (mientras me golpeaba la cabeza contra un desagradable error heredado). No lo hubiera esperado. Para mí, eso parece una operación de obtención, y no esperaba el "efecto secundario". Prefiere map.find()cuando salgas de tu mapa.

Hawkeye Parker
fuente
3
Esa es una vista decente, aunque los mapas hash son bastante universales para este formato. Podría ser una de esas "rarezas que nadie piensa que es extraño" solo por lo generalizadas que usan las mismas convenciones
Stephen J,
19

Si el éxito del constructor predeterminado no es un problema, por favor, por amor de Dios, ve con la versión más legible.

:)

Torlack
fuente
55
¡Segundo! Tengo que marcar esto. Demasiadas personas intercambian obtusos por aceleraciones de nano segundos. ¡Ten piedad de nosotros, pobres almas que deben mantener tales atrocidades!
Mr.Ree
66
Como escribió Greg Rogers: "Los dos tienen una semántica diferente cuando se trata de la clave que ya existe en el mapa. Por lo tanto, no son realmente directamente comparables".
dalle
Esta es una vieja pregunta y respuesta. Pero la "versión más legible" es una razón estúpida. Porque lo que es más legible depende de la persona.
vallentin
14

insert es mejor desde el punto de excepción la seguridad.

La expresión map[key] = valuees en realidad dos operaciones:

  1. map[key] - Crear un elemento de mapa con valor predeterminado.
  2. = value - copiando el valor en ese elemento.

Puede ocurrir una excepción en el segundo paso. Como resultado, la operación se realizará solo parcialmente (se agregó un nuevo elemento al mapa, pero ese elemento no se inicializó con value). La situación cuando una operación no está completa, pero se modifica el estado del sistema, se llama operación con "efecto secundario".

insertLa operación ofrece una garantía sólida, lo que significa que no tiene efectos secundarios ( https://en.wikipedia.org/wiki/Exception_safety ). insertestá completamente hecho o deja el mapa en estado no modificado.

http://www.cplusplus.com/reference/map/map/insert/ :

Si se inserta un solo elemento, no hay cambios en el contenedor en caso de excepción (garantía sólida).

anton_rh
fuente
1
lo que es más importante, insertar no requiere que el valor sea por defecto construible
UmNyobe
13

Si su aplicación es crítica para la velocidad, aconsejaré usar el operador [] porque crea un total de 3 copias del objeto original, de las cuales 2 son objetos temporales y tarde o temprano se destruyen como.

Pero en insert (), se crean 4 copias del objeto original de las cuales 3 son objetos temporales (no necesariamente "temporales") y se destruyen.

Lo que significa tiempo extra para: 1. Una asignación de memoria de objetos 2. Una llamada de constructor adicional 3. Una llamada de destructor adicional 4. Una desasignación de memoria de objetos

Si sus objetos son grandes, los constructores son típicos, los destructores liberan muchos recursos, los puntos anteriores cuentan aún más. En cuanto a la legibilidad, creo que ambos son lo suficientemente justos.

La misma pregunta vino a mi mente pero no sobre la legibilidad sino la velocidad. Aquí hay un código de muestra a través del cual llegué a conocer el punto que mencioné.

class Sample
{
    static int _noOfObjects;

    int _objectNo;
public:
    Sample() :
        _objectNo( _noOfObjects++ )
    {
        std::cout<<"Inside default constructor of object "<<_objectNo<<std::endl;
    }

    Sample( const Sample& sample) :
    _objectNo( _noOfObjects++ )
    {
        std::cout<<"Inside copy constructor of object "<<_objectNo<<std::endl;
    }

    ~Sample()
    {
        std::cout<<"Destroying object "<<_objectNo<<std::endl;
    }
};
int Sample::_noOfObjects = 0;


int main(int argc, char* argv[])
{
    Sample sample;
    std::map<int,Sample> map;

    map.insert( std::make_pair<int,Sample>( 1, sample) );
    //map[1] = sample;
    return 0;
}

Salida cuando se usa insert () Salida cuando se usa el operador []

Rampal Chaudhary
fuente
44
Ahora ejecute esa prueba nuevamente con las optimizaciones completas habilitadas.
antred
2
Además, considere lo que hace realmente el operador []. Primero busca en el mapa una entrada que coincida con la clave especificada. Si encuentra uno, sobrescribe el valor de esa entrada con el especificado. Si no lo hace, inserta una nueva entrada con la clave y el valor especificados. Cuanto más grande sea su mapa, más tiempo le tomará al operador [] buscarlo. En algún momento, esto compensará con creces una copia adicional de llamada o copia (si eso permanece en el programa final después de que el compilador haya hecho su magia de optimización).
antred
1
@antred, inserttiene que hacer la misma búsqueda, por lo que no hay diferencia en eso desde [](porque las teclas del mapa son únicas).
Sz.
Bonita ilustración de lo que está sucediendo con las impresiones, pero ¿qué están haciendo realmente estos 2 bits de código? ¿Por qué son necesarias 3 copias del objeto original?
rbennett485
1. debe implementar el operador de asignación, o obtendrá números incorrectos en el destructor 2. use std :: move al construir el par para evitar el exceso de construcción de copia "map.insert (std :: make_pair <int, Sample> (1, std: : mover (muestra))); "
Fl0
10

Ahora en c ++ 11 creo que la mejor manera de insertar un par en un mapa STL es:

typedef std::map<int, std::string> MyMap;
MyMap map;

auto& result = map.emplace(3,"Hello");

El resultado será un par con:

  • Primer elemento (resultado.primero), apunta al par insertado o apunta al par con esta clave si la clave ya existe.

  • Segundo elemento (resultado.segundo), verdadero si la inserción fue correcta o falsa, algo salió mal.

PD: Si no tiene dudas sobre el orden, puede usar std :: unordered_map;)

¡Gracias!

GutiMac
fuente
9

Un problema con map :: insert () es que no reemplazará un valor si la clave ya existe en el mapa. He visto código C ++ escrito por programadores de Java donde esperaban que insert () se comportara de la misma manera que Map.put () en Java, donde se reemplazan los valores.

Anthony calambre
fuente
2

Una nota es que también puedes usar Boost.Assign :

using namespace std;
using namespace boost::assign; // bring 'map_list_of()' into scope

void something()
{
    map<int,int> my_map = map_list_of(1,2)(2,3)(3,4)(4,5)(5,6);
}
rlbond
fuente
1

Aquí hay otro ejemplo, que muestra que operator[] sobrescribe el valor de la clave si existe, pero .insert no sobrescribe el valor si existe.

void mapTest()
{
  map<int,float> m;


  for( int i = 0 ; i  <=  2 ; i++ )
  {
    pair<map<int,float>::iterator,bool> result = m.insert( make_pair( 5, (float)i ) ) ;

    if( result.second )
      printf( "%d=>value %f successfully inserted as brand new value\n", result.first->first, result.first->second ) ;
    else
      printf( "! The map already contained %d=>value %f, nothing changed\n", result.first->first, result.first->second ) ;
  }

  puts( "All map values:" ) ;
  for( map<int,float>::iterator iter = m.begin() ; iter !=m.end() ; ++iter )
    printf( "%d=>%f\n", iter->first, iter->second ) ;

  /// now watch this.. 
  m[5]=900.f ; //using operator[] OVERWRITES map values
  puts( "All map values:" ) ;
  for( map<int,float>::iterator iter = m.begin() ; iter !=m.end() ; ++iter )
    printf( "%d=>%f\n", iter->first, iter->second ) ;

}
bobobobo
fuente
1

Este es un caso bastante restringido, pero a juzgar por los comentarios que he recibido, creo que vale la pena señalarlo.

He visto personas en el pasado usar mapas en forma de

map< const key, const val> Map;

para evadir casos de sobreescritura accidental de valores, pero luego seguir escribiendo otros bits de código:

const_cast< T >Map[]=val;

Recuerdo que su razón para hacerlo fue porque estaban seguros de que en estos ciertos bits de código no iban a sobrescribir los valores del mapa; por lo tanto, seguir adelante con el método más 'legible'[] .

En realidad, nunca he tenido ningún problema directo con el código que escribieron estas personas, pero hasta ahora creo firmemente que los riesgos, por pequeños que sean, no deberían tomarse cuando pueden evitarse fácilmente.

En los casos en que se trate de valores de mapas que no se deben sobrescribir, use insert. No haga excepciones simplemente por legibilidad.

dk123
fuente
¿Varias personas diferentes han escrito eso? Ciertamente use insert(no input), ya que const_casthará que se sobrescriba cualquier valor anterior, lo cual es muy no constante. O no marque el tipo de valor como const. (Ese tipo de cosas suele ser el resultado final de const_cast, por lo que es casi siempre una señal de alerta que indica un error en otro lugar.)
Potatoswatter
@Potatoswatter Tienes razón. Solo estoy viendo que algunas personas usan const_cast [] con valores de mapas de const cuando están seguras de que no reemplazarán un valor antiguo en ciertos bits de código; ya que [] es más legible. Como mencioné en la parte final de mi respuesta, recomendaría usar inserten casos en los que desee evitar que se sobrescriban los valores. (Acabo de cambiar el inputa insert- gracias)
dk123
@Potatoswatter Si no recuerdo mal, las razones principales por las que la gente parece estar usando const_cast<T>(map[key])eran 1. [] es más legible, 2. confían en ciertos bits de código que no sobrescribirán valores, y 3. no lo hacen desea que otros bits de código desconocido sobrescriban sus valores, de ahí el const value.
dk123
2
Nunca he oído hablar de esto. ¿Dónde viste esto? La escritura const_castparece más que negar la "legibilidad" adicional de [], y ese tipo de confianza es casi suficiente para despedir a un desarrollador. Las difíciles condiciones de tiempo de ejecución se resuelven con diseños a prueba de balas, no con instintos.
Potatoswatter
@Potatoswatter Recuerdo que fue durante uno de mis trabajos anteriores desarrollando juegos educativos. Nunca pude lograr que las personas que escriben el código cambien sus hábitos. Tienes toda la razón y estoy totalmente de acuerdo contigo. A partir de sus comentarios, he decidido que probablemente valga más la pena mencionar esto que mi respuesta original y, por lo tanto, lo actualicé para reflejar esto. ¡Gracias!
dk123
1

El hecho de que la función std :: map insert()no sobrescribe el valor asociado con la clave nos permite escribir un código de enumeración de objetos como este:

string word;
map<string, size_t> dict;
while(getline(cin, word)) {
    dict.insert(make_pair(word, dict.size()));
}

Es un problema bastante común cuando necesitamos asignar diferentes objetos no únicos a algunas identificaciones en el rango 0..N. Esos id se pueden usar más tarde, por ejemplo, en algoritmos de gráficos. La alternativa con operator[]parecería menos legible en mi opinión:

string word;
map<string, size_t> dict;
while(getline(cin, word)) {
    size_t sz = dict.size();
    if (!dict.count(word))
        dict[word] = sz; 
} 
Mecatroner
fuente