std::map insertar o std::map buscar?

Question

Suponiendo un mapa donde desea conservar las entradas existentes.El 20% de las veces, la entrada que estás 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 insertar y luego actuar en función de si el iterador indica o no que el registro se insertó o no?

Answer 1

La respuesta es que no haces ninguna de las dos cosas.En lugar de eso, desea hacer algo sugerido por el punto 24 de STL efectivo por 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
}

Answer 2

La respuesta a esta pregunta también depende de qué tan costoso sea crear el tipo de valor que estás 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 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 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;
  }
}

Para llamar a 'insertar', estamos pagando la costosa llamada para construir nuestro tipo de valor y, por lo que dijo en la pregunta, no utilizará 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 datos utilizando su tipo de puntero inteligente favorito.La llamada a insertar utiliza un puntero nulo (muy barato de construir) y sólo si es necesario se construye el nuevo tipo de datos.

Answer 3

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

Entonces..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.

Answer 4

Creo que si busca y luego inserta, el costo adicional sería cuando no encuentre la clave y luego realice la inserción.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 claves 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...

Answer 5

Estoy perdido en la respuesta principal.

Find devuelve map.end() si no encuentra nada, lo que significa que si estás 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 el doble de lento que

map.insert

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

Answer 6

Si le preocupa la eficiencia, es posible que desee consultar mapa_hash<>.

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

Answer 7

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

Answer 8

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 decide según el estilo que prefieras.

Answer 9

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

Sí, bastante justo.

Si realiza una búsqueda y luego una inserción, está realizando 2 x O (log N) cuando falla, ya que la búsqueda solo le permite saber si necesita insertar, no donde debe ir la inserción (el límite inferior podría ayudarlo allí) .Simplemente insertarlo directamente y luego examinar el resultado es el camino que seguiría.