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

90

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?

Superpolock
fuente
4
Me corrigieron y tenía la intención de usar std :: map :: lower_bound en lugar de std :: map :: find.
Superpolock

Respuestas:

147

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
}
lucas
fuente
2
De hecho, así es como funciona Find, el truco es que combina la búsqueda necesaria para encontrar e insertar. Por supuesto, también lo hace con insertar y luego mirar el segundo valor de retorno.
puetzk
1
Dos preguntas: 1) ¿En qué se diferencia el uso de lower_bound del uso de buscar para un mapa? 2) Para un 'mapa', ¿no es cierto que la op de la derecha de && es siempre verdadera cuando 'lb! = Mymap.end ()'?
Richard Corden
11
@Richard: find () devuelve end () si la clave no existe, lower_bound devuelve la posición donde debería estar el elemento (que a su vez se puede usar como sugerencia de inserción). @puetzek: ¿No "simplemente insertar" sobrescribiría el valor de referencia para las claves existentes? No está seguro si el OP desea eso.
peterchen
2
¿Alguien sabe si hay algo similar para unordered_map?
Giovanni Funchal
3
@peterchen map :: insert no sobrescribe el valor existente si existe, consulte cplusplus.com/reference/map/map/insert .
Chris Drew
11

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.

Richard Corden
fuente
8

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.

gbjbaanb
fuente
5

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

PiNoYBoY82
fuente
3

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.

gman
fuente
1
Una versión de la inserción de STL devuelve un par que contiene un iterador y un bool. El bool indica si lo encontró o no, el iterador es la entrada encontrada o la entrada insertada. Esto es difícil de superar por la eficiencia; imposible, diría yo.
Zan Lynx
4
No, la respuesta marcada utilizada lower_bound, no find. Como resultado, si no se encontró la clave, devolvió un iterador al punto de inserción, no al final. Como resultado, es más rápido.
Steven Sudit
1

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.

Adam Tegen
fuente
Me hubiera encantado. Pero no hay hash_map en la biblioteca estándar de C ++, y los PHB no permiten código fuera de eso.
Superpolock
1
std :: tr1 :: unordered_map es el mapa hash que se propone agregar al siguiente estándar y debería estar disponible en la mayoría de las implementaciones actuales de STL.
beldaz
1

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.

Stonky
fuente
1
Debido a que (ciertamente antes de C ++ 11) usar insertar significa que aún tiene que crear un std::map::value_typeobjeto, la respuesta aceptada evita incluso eso.
KillianDS
-1

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.

Mark Ransom
fuente
1
Esto no es exactamente cierto. La STL es diferente a la mayoría de las otras bibliotecas en que proporciona requisitos explícitos de big-O para la mayoría de sus operaciones. Hay una diferencia garantizada entre 2 * O (log n) y 1 * O (log n), independientemente de la implementación que utilicen las funciones para lograr ese comportamiento O (log n). Si esa diferencia es significativa o no en su plataforma es una cuestión diferente. Pero la diferencia siempre estará ahí.
srm
@srm que define los requisitos de big-O todavía no le dice cuánto tiempo tomará una operación en términos absolutos. La diferencia garantizada de la que hablas no existe.
Mark Ransom
-2

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.


fuente
No, si la entrada existe, devuelve una referencia a la entrada existente.
Kris Kumler
2
-1 para esta respuesta. Como dijo Kris K, usar map [key] = value sobrescribirá la entrada existente, no la "preservará" como se requiere en la pregunta. No puede probar la existencia usando map [key], porque devolverá un objeto construido predeterminado si la clave no existe, y lo creará como la entrada para la clave
netjeff
El punto es probar si el mapa ya está poblado y solo agregar / sobrescribir si no está allí. El uso de map [key] asume que el valor ya está ahí siempre.
srm