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

Question

Suponiendo un mapa en el que desea conservar las entradas existentes. 20% de las veces, la entrada que está insertando es información nueva. ¿Hay alguna ventaja en hacer std :: map :: find then 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 fue o no insertado?

Answer 1

La respuesta es que usted no hace ninguna de las dos cosas. Por el contrario desea hacer algo sugerido por el artículo 24 de Effective STL 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

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

Por lo tanto, se trata de una preferencia personal. Siempre trato de insertar y luego actualizar si es necesario, pero a algunas personas no les gusta manejar el par que se devuelve.

Answer 3

mapa [clave] - deje que stl lo resuelva. Eso es comunicar tu intención de manera más efectiva.

Sí, es suficiente.

Si realiza una búsqueda y luego una inserción, está realizando 2 x O (log N) cuando se extravía, ya que el hallazgo solo le permite saber si necesita insertar dónde debe ir la inserción (lower_bound might Ayudamos allí). Solo una inserción recta y luego examinar el resultado es la forma en que iría.

Answer 4

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 decida según el estilo que prefiera.

Answer 5

Creo que si haces una búsqueda y luego insertas, el costo adicional será cuando no encuentres la clave y luego realices la inserción. Es como mirar los libros en orden alfabético y no encontrar el libro, luego revisar los libros nuevamente para ver dónde insertarlos. Todo se reduce a cómo manejarás las llaves y si cambian constantemente. Ahora hay algo de flexibilidad en que si no lo encuentra, puede iniciar sesión, excepción, hacer lo que quiera ...

Answer 6

Si le preocupa la eficiencia, puede consultar hash_map<>.

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

Answer 7

La respuesta a esta pregunta depende también de lo caro que es para 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 entero, lo anterior será más eficiente que un hallazgo seguido de un inserto (en ausencia de optimizaciones del compilador). Como se indicó anteriormente, esto se debe a que la búsqueda a través del mapa solo tiene lugar una vez.

Sin embargo, la llamada para insertar requiere que ya tiene el nuevo "valor" construida:

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 llamar 'Insertar' que estamos pagando por la llamada caros de construir nuestro tipo de valor - y de lo que dijiste en la pregunta, no utilizará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 primero realizar el 'buscar' para verificar si necesitamos construir el elemento.

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

Answer 8

estoy perdido en la respuesta más común.

de búsqueda devuelve map.end() si no encuentra nada que significa que si va a añadir cosas nuevas a continuación

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 tan lento como

map.insert 

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

Answer 9

Parece que no tengo suficientes puntos para dejar un comentario, pero la respuesta marcada me parece larga: cuando consideras que la inserción devuelve el iterador de todos modos, ¿por qué sigues buscando low_bound, cuando solo puedes usar el iterador regresó. Extraño.