c++ - mapas - std map remove

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

Apenas habrá una 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.

Entonces ... se trata de 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 2

Creo que si haces una búsqueda y luego insertas, el costo adicional será cuando no encuentres la clave y realices la inserción después. 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 encuentras, puedes registrar, hacer una excepción, hacer lo que quieras ...

Answer 3

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 4

Estoy perdido en la respuesta superior.

Find devuelve map.end () si no encuentra nada, lo que significa que si agrega 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á allí, una vez más para encontrar el lugar donde poner lo nuevo.

Answer 5

La respuesta a esta pregunta también depende de cuán caro es 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 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 tiene lugar 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 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 primero realizar el ''buscar'' para verificar si necesitamos construir el elemento.

Alternativamente, el tipo de valor del mapa se puede cambiar para almacenar identificadores a los datos usando 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 6

La respuesta es que tú tampoco. En su lugar, desea hacer algo sugerido por el artículo 24 de Effective STL 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
}

Answer 7

No parece tener suficientes puntos para dejar un comentario, pero la respuesta marcada parece ser larga para mí: cuando consideras que la inserción devuelve el iterador de todos modos, ¿por qué ir a la búsqueda de límite inferior, cuando puedes usar el iterador devuelto? Extraño.

Answer 8

Si le preocupa la eficacia, le hash_map<> consultar hash_map<> .

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

Answer 9

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

Sí, es justo.

Si haces una búsqueda y luego una inserción estás realizando 2 x O (log N) cuando te pierdes, ya que el hallazgo solo te permite saber si necesitas insertar dónde debería ir la inserción (lower_bound podría ayudarte). . Solo una inserción recta y luego examinar el resultado es la forma en que iría.