std:: map insert o std:: map find?

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 un find seguido de un insert (en ausencia de optimizaciones del compilador). Como se indicó anteriormente, esto se debe a que la búsqueda a través del mapa solo se lleva a cabo una vez.

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

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;
  }
}

Con el fin de call 'insert' estamos pagando por la costosa llamada para construir nuestro tipo de valor - y por lo que dijiste en la pregunta no usarás 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 el 'find' para verificar si necesitamos construir el elemento.

Alternativamente, el tipo de valor del mapa se puede cambiar para almacenar los controladores de los datos utilizando su tipo de puntero inteligente favorito. La llamada a 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 el 2, find devolverá un iterador, insert hace lo mismo y buscará el mapa de todos modos para determinar si la entrada ya existe.

So.. su preferencia personal. Siempre intento insertar y luego actualizar si es necesario, pero a algunas personas no les gusta manejar el par que se devuelve.

Pensaría que si haces un find y luego insertas, el costo adicional sería cuando no encuentras la clave y realizas el insert después. Es como mirar a través de los libros en orden alfabético y no encontrar el libro, luego mirar a través de los libros de nuevo para ver dónde insertarlo. Se reduce a cómo va a manejar las llaves y si están cambiando constantemente. Ahora hay cierta flexibilidad en que si no lo encuentras, puedes registrar, excepción, hacer lo que quieras...

Estoy perdido en la respuesta de arriba.

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

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 la cosa nueva.

Si le preocupa la eficiencia, es posible que desee revisar hash_map.

Típicamente map se implementa como un árbol binario. Dependiendo de sus necesidades, un hash_map puede ser más eficiente.

No parece que tenga suficientes puntos para dejar un comentario, pero la respuesta marcada parece ser larga para mí - cuando considera que insert devuelve el iterador de todos modos, ¿por qué buscar lower_bound, cuando solo puede usar el iterador devuelto. Extraño.

Cualquier respuesta sobre la eficiencia dependerá de la implementación exacta de su STL. La única manera de saberlo con certeza es compararlo en ambos sentidos. Supongo que es poco probable que la diferencia sea significativa, así que decide en función del estilo que prefieras.

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

Si haces un find y luego un insert, estás realizando 2 x O(log N) cuando recibes una falta, ya que el find solo te permite saber si necesitas insertar no a dónde debe ir el insert (lower_bound podría ayudarte allí). Solo una inserción recta y luego examinar el resultado es el camino que iría.