std :: inserción de mapa o std :: búsqueda de mapa?

Suponiendo un mapa donde desea conservar las entradas existentes. El 20% del tiempo, la entrada que está insertando son datos nuevos. ¿Hay alguna ventaja en hacer std :: map :: find y luego std :: map :: insert usando ese iterador devuelto? ¿O es más rápido intentar la inserción y luego actuar en función de si el iterador indica que el registro se insertó o no?

La respuesta es ninguna de las dos cosas. En su lugar, desea hacer algo sugerido por el artículo 24 de STL eficaz de Scott Meyers :

typedef map<int, int> MapType;    // Your map type may vary, just change the typedef

MapType mymap;
// Add elements to map here
int k = 4;   // assume we're searching for keys equal to 4
int v = 0;   // assume we want the value 0 associated with the key of 4

MapType::iterator lb = mymap.lower_bound(k);

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first)))
{
    // key already exists
    // update lb->second if you care to
}
else
{
    // the key does not exist in the map
    // add it to the map
    mymap.insert(lb, MapType::value_type(k, v));    // Use lb as a hint to insert,
                                                    // so it can avoid another lookup
}

La respuesta a esta pregunta también depende de lo caro que sea crear el tipo de valor que está almacenando en el mapa:

typedef std::map <int, int> MapOfInts;
typedef std::pair <MapOfInts::iterator, bool> IResult;

void foo (MapOfInts & m, int k, int v) {
  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

Para un tipo de valor como un int, lo anterior será más eficiente que una búsqueda seguida de una inserción (en ausencia de optimizaciones del compilador). Como se indicó anteriormente, esto se debe a que la búsqueda en el mapa solo se realiza una vez.

Sin embargo, la llamada para insertar requiere que ya tenga construido el nuevo "valor":

class LargeDataType { /* ... */ };
typedef std::map <int, LargeDataType> MapOfLargeDataType;
typedef std::pair <MapOfLargeDataType::iterator, bool> IResult;

void foo (MapOfLargeDataType & m, int k) {

  // This call is more expensive than a find through the map:
  LargeDataType const & v = VeryExpensiveCall ( /* ... */ );

  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

Para llamar a 'insertar' estamos pagando por la costosa llamada para construir nuestro tipo de valor, y por lo que dijo en la pregunta, no usará este nuevo valor el 20% del tiempo. En el caso anterior, si cambiar el tipo de valor del mapa no es una opción, entonces es más eficiente realizar primero la 'búsqueda' para verificar si necesitamos construir el elemento.

Alternativamente, el tipo de valor del mapa se puede cambiar para almacenar identificadores de los datos usando su tipo de puntero inteligente favorito. La llamada para insertar usa un puntero nulo (muy barato de construir) y solo si es necesario se construye el nuevo tipo de datos.

Apenas habrá diferencia de velocidad entre los 2, find devolverá un iterador, insert hará lo mismo y buscará en el mapa de todos modos para determinar si la entrada ya existe.

Así que ... depende de las preferencias personales. Siempre intento insertar y luego actualizar si es necesario, pero a algunas personas no les gusta manejar el par que se devuelve.

Creo que si busca y luego inserta, el costo adicional sería cuando no encuentre la clave y realice la inserción después. Es como mirar libros en orden alfabético y no encontrar el libro, y luego volver a mirar los libros para ver dónde insertarlo. Todo se reduce a cómo manejará las teclas y si cambian constantemente. Ahora hay cierta flexibilidad en el sentido de que si no lo encuentra, puede iniciar sesión, hacer una excepción, hacer lo que quiera ...

Estoy perdido en la respuesta principal.

Find devuelve map.end () si no encuentra nada, lo que significa que si está agregando cosas nuevas, entonces

iter = map.find();
if (iter == map.end()) {
  map.insert(..) or map[key] = value
} else {
  // do nothing. You said you did not want to effect existing stuff.
}

es dos veces más lento que

map.insert

para cualquier elemento que no esté ya en el mapa, ya que tendrá que buscar dos veces. Una vez para ver si está ahí, otra vez para encontrar el lugar donde poner lo nuevo.

Si le preocupa la eficiencia, le recomendamos que consulte hash_map <> .

Normalmente map <> se implementa como un árbol binario. Dependiendo de sus necesidades, un hash_map puede ser más eficiente.

Parece que no tengo suficientes puntos para dejar un comentario, pero la respuesta marcada parece ser larga para mí: cuando consideras que insertar devuelve el iterador de todos modos, ¿por qué buscar lower_bound, cuando solo puedes usar el iterador devuelto? Extraño.

Cualquier respuesta sobre la eficiencia dependerá de la implementación exacta de su STL. La única forma de saberlo con certeza es compararlo en ambos sentidos. Supongo que es poco probable que la diferencia sea significativa, así que decida según el estilo que prefiera.

map [key] - deja que stl lo resuelva. Eso es comunicar su intención de la manera más efectiva.

Sí, bastante justo.

Si hace una búsqueda y luego una inserción, está realizando 2 x O (log N) cuando obtiene un error, ya que la búsqueda solo le permite saber si necesita insertar, no dónde debe ir la inserción (lower_bound podría ayudarlo allí) . Solo un inserto recto y luego examinar el resultado es el camino que seguiría.