Justificación de la semántica de inserción de mapas estándar de C++

Question

Estoy un poco confundido por la semántica de std::map::insert. Quiero decir, no me quejo, el estándar es el estándar y el API es lo que es. Aún así,

insert voluntad

los controles de operación de inserción para cada elemento insertado si existe otro elemento que ya están en el recipiente con el mismo valor de clave , de ser así, el elemento no se ha insertado y su valor mapeado no es cambiado de ninguna manera.

Y - sólo en su versión de un solo argumento pair<iterator,bool> insert (const value_type& x); será incluso le dirá si es que inserta el valor (nueva, posiblemente diferente) a la llave (s). Por lo que yo entiendo, las versiones del iterador ignorarán silenciosamente las inserciones si la clave ya existe.

Para mí, esto es simplemente contrario a la intuición, Hubiera esperado que la parte de valor se sobrescribiera y la parte de valor anterior fuera descartada en la inserción. Obviamente, los diseñadores de STL pensaban de manera diferente: ¿alguien sabe la razón (histórica) o puede dar una explicación detallada de cómo la semántica existente tiene (más) sentido?

Por ejemplo:

Hay algunas formas básicas para implementar inserto en un mapa de clave única como std::map:

• insertar, reemplazar si ya existe
• inserción, ignorar si ya existe (este es el comportamiento de std :: map)
• insertar, lanzar error si ya existe
• inserción, UB, si ya existe

Ahora estoy tratando de entender por qué insert_or_ignore tiene más sentido que insert_or_replace (o insert_or_error)!

---

mirase en mi copia de TC++PL (por desgracia sólo tengo la edición alemana), y curiosamente, BS escribe en el capítulo 17.4.1.7 (operaciones de lista de mapa): (traducción aproximada siento del alemán)

(...) Por lo general, uno no le importa si una clave (sic) es de reciente insertado o ya existía antes de la llamada a insert() (...)

Lo cual, me parece, solo sería válido para conjunto, y no para mapa, porque para un mapa, si el valor proporcionado se insertó o el anterior permanece en el mapa, sí hay alguna diferencia . (Obviamente no importa la clave, ya que esa es equivalente.)

---

Nota: Sé acerca operator[] y sé acerca del artículo 24 de la Effective STL y no propuso efficientAddOrUpdate función. Solo tengo curiosidad por un razonamiento en la semántica de insert porque, personalmente, les encuentro contra la intuición.

Answer 1

No conozco un fundamento oficial, pero señalaría la dualidad con operator[].

Parece obvio que a uno le gustaría los dos sabores de inserción:

• puramente aditivo
• aditivo/destructivos

Si vemos un map como una escasa representación de una matriz, entonces la presencia de operator[] tiene sentido. No sé si existían diccionarios preexistentes y dictó esta sintaxis (tal vez, por qué no).

También, todos Los contenedores STL tienen varias sobrecargas de insert, y esta similitud de interfaces es lo que permite la Programación genérica. Por lo tanto, tenemos al menos dos contendientes para la API: operator[] y insert.

Ahora, en C++, si lee:

array[4] = 5; 

se naturaly que el contenido de la celda en el índice 4 se ha actualizado de forma destructiva. Como tal, es natural que map::operator[] devuelva una referencia para permitir esta actualización destructiva.

En este punto, ahora necesitamos una versión puramente aditiva también, y tenemos este método insert por ahí. Por qué no ?

Por supuesto uno podría haber dado insert la misma semántica que operator[] y luego seguir adelante y poner en práctica un método insert_or_ignore en la parte superior. Sin embargo, esto hubiera sido más trabajo.

Por lo tanto, aunque estoy de acuerdo que podría ser sorprendente, creo que mi razonamiento no es demasiado defectuoso y puede ser una probable explicación de las circunstancias que nos llevan aquí :)

---

En cuanto a las alternativas que propuso :

• inserción, UB, si ya existe

Afortunadamente, ¡no lo es!

• inserción, tiro de error si ya existe

Sólo Java (y derivados) es una excepción-loco. C++ se concibió en una época en la que se utilizaban excepciones por circunstancias excepcionales.

• insertar, reemplazar si ya existe
• inserción, ignorar si ya existe (este es el comportamiento de std :: mapa)

Estamos de acuerdo en que la elección estaba entre uno de aquellos. Tenga en cuenta que aunque map eligió la segunda opción, no omite por completo ignorar el hecho de que el elemento ya existía, al menos en la versión de elemento único, ya que le advierte que el elemento no se insertó.

Answer 2

Desde insert() no espera que se toquen objetos existentes en el contenedor. Es por eso que simple no los toca.

Answer 3

pair<iterator,bool> < - ¿No dice la parte bool si la inserción tiene éxito o no?

Puede actualizar la parte del valor del iterador devuelto si la parte bool es falsa para actualizar el elemento existente con la misma clave.

Answer 4

El método de inserción no es exactamente lo que está buscando, parece que ... El método de inserción está hecho para hacer exactamente lo que su nombre implica ... insertar valores. Estoy de acuerdo en que la capacidad de crear un valor si uno no está presente y reemplazar el que está allí de otra manera es importante en algunas situaciones, pero en otros simplemente preferiría no manejar excepciones, devolver valores, etc. si solo quiere hacer una inserción solo si el valor no está presente.

Parece que el método que está buscando (como BoBTFish indicado anteriormente) es probablemente el operador []. Sólo lo utilizan de esta manera:

myMap["key"] = "value"; 

Esto pasará a través de su mapa y encontrar la "llave" clave, y sustituir el valor correspondiente con "valor". Si la clave no está allí, la creará. Ambos métodos son muy útiles en diferentes situaciones, y me he encontrado usando ambos solo dependiendo de lo que necesito.

Answer 5

No pretendo conocer la razón original para la decisión, pero no es demasiado difícil crear una. Creo que ;-)

El comportamiento actual de "insertar o ignorar" hace que sea muy fácil implementar los otros dos, al menos para aquellos de nosotros que no estamos por encima de crear y usar funciones que no son miembros para complementar el funcionalidad estándar de la biblioteca ("¡no es OOP-y suficiente!").

Ejemplo (escrito en el acto, por lo que los errores pueden estar presentes):

template<typename Map> 
void insert_or_update(Map& map, typename Map::value_type const& x) 
{ 
    std::pair<typename Map::iterator, bool> result = map.insert(x); 
    if (!result.second) 
    result.first->second = x.second; // or throw an exception (consider using 
            // a different function name, though) 
} 

tenga en cuenta que tal como está, la función anterior en realidad no difiere mucho de operator[] - sí, evita la inicialización por defecto , pero al mismo tiempo (porque soy flojo) no aprovecha la semántica de movimientos que su STL actualizada probablemente ya admite para operator[].

De todos modos, cualquier otro comportamiento de inserción para map habría hecho más tedioso implementar los otros, ya que map::find solo devuelve un centinela final si la clave no está ya en el mapa. Con la ayuda de <algorithm> (y especialmente lower_bound) sería, por supuesto, todavía será posible escribir funciones accesorias performant sin ahogarse ellos detalles de implementación y las construcciones genéricas feos como los bucles ;-).