ejemplo - map find c++

c++ map find() para posiblemente insertar(): ¿cómo optimizar las operaciones?

Question

Estoy usando la estructura de datos del mapa STL, y en el momento en que mi código primero invoca a find () : si la clave no estaba previamente en el mapa, llama a insert () , de lo contrario no hace nada.

map<Foo*, string>::iterator it;
it = my_map.find(foo_obj);   // 1st lookup

if(it == my_map.end()){
  my_map[foo_obj] = "some value";  // 2nd lookup
}else{
  // ok do nothing.
}

Me preguntaba si hay una forma mejor que esta, porque por lo que puedo decir, en este caso cuando quiero insertar una clave que aún no está presente, realizo 2 búsquedas en las estructuras de datos del mapa: una para buscar ( ) , uno en el inserto () (que corresponde al operador [] ).

Gracias de antemano por cualquier sugerencia.

Answer 1

En su ejemplo, desea insertar cuando no se encuentra. Si la construcción predeterminada y el valor del valor posterior no son costosos, sugeriría una versión más simple con 1 búsqueda:

string& r = my_map[foo_obj];    // only lookup & insert if not existed
if (r == "") r = "some value";  // if default (obj wasn''t in map), set value
                                // else existed already, do nothing

Si su ejemplo dice lo que realmente quiere, considere agregar ese valor como str Foo::s en str Foo::s lugar, ya tiene el objeto, por lo que no se necesitarían búsquedas, solo verifique si tiene un valor predeterminado para ese miembro. Y mantén los objs en el std::set . Incluso extender la class FooWithValue2 puede ser más barato que usar el map .

Pero si realmente es necesario unir datos a través del mapa de esta manera o si desea actualizar solo si existió, Jonathan tiene la respuesta.

Answer 2

Hay dos enfoques principales. La primera es usar la función de inserción que toma un tipo de valor y que devuelve un iterador y un bool que indican si se realizó una inserción y devuelve un iterador al elemento existente con la misma clave o al elemento recién insertado.

map<Foo*, string>::iterator it;
it = my_map.find(foo_obj);   // 1st lookup

my_map.insert( map<Foo*, string>::value_type(foo_obj, "some_value") );

La ventaja de esto es que es simple. La principal desventaja es que siempre se construye un nuevo valor para el segundo parámetro, ya sea que se requiera o no una inserción. En el caso de una cuerda, esto probablemente no importa. Si su valor es costoso construir esto puede ser más inútil de lo necesario.

Una forma de evitar esto es usar la versión ''insinuación'' de la inserción.

std::pair< map<foo*, string>::iterator, map<foo*, string>::iterator >
    range = my_map.equal_range(foo_obj);

if (range.first == range.second)
{
    if (range.first != my_map.begin())
        --range.first;

    my_map.insert(range.first, map<Foo*, string>::value_type(foo_obj, "some_value") );
}

Se garantiza que la inserción está en tiempo constante amortizado solo si el elemento se inserta inmediatamente después del iterador suministrado, por lo tanto, -- si es posible.

Editar

Si esta necesidad parece extraña, entonces es. Hay un defecto abierto (233) en la norma que destaca este problema, aunque la descripción del problema que se aplica al map es más clara en el problema duplicado 246 .

Answer 3

Normalmente, si realiza una búsqueda y tal vez una inserción, entonces desea conservar (y recuperar) el valor antiguo si ya existía. Si solo desea sobrescribir cualquier valor anterior, map[foo_obj]="some value" lo hará.

A continuación, le indicamos cómo obtener el valor anterior o insertar uno nuevo si no existiera, con una búsqueda en el mapa:

typedef std::map<Foo*,std::string> M;
typedef M::iterator I;
std::pair<I,bool> const& r=my_map.insert(M::value_type(foo_obj,"some value"));
if (r.second) { 
    // value was inserted; now my_map[foo_obj]="some value"
} else {
    // value wasn''t inserted because my_map[foo_obj] already existed.
    // note: the old value is available through r.first->second
    // and may not be "some value"
}
// in any case, r.first->second holds the current value of my_map[foo_obj]

Este es un idioma lo suficientemente común como para usar una función auxiliar:

template <class M,class Key>
typename M::mapped_type &
get_else_update(M &m,Key const& k,typename M::mapped_type const& v) {
    return m.insert(typename M::value_type(k,v)).first->second;
}

get_else_update(my_map,foo_obj,"some value");

Si tiene un cálculo costoso para v que desea omitir si ya existe (por ejemplo, memoria), puede generalizarlo también:

template <class M,class Key,class F>
typename M::mapped_type &
get_else_compute(M &m,Key const& k,F f) {
   typedef typename M::mapped_type V;
   std::pair<typename M::iterator,bool> r=m.insert(typename M::value_type(k,V()));
   V &v=r.first->second;
   if (r.second)
      f(v);
   return v;
}

donde por ejemplo

struct F {
  void operator()(std::string &val) const 
  { val=std::string("some value")+" that is expensive to compute"; }
};
get_else_compute(my_map,foo_obj,F());

Si el tipo mapeado no es constructible por defecto, haga que F proporcione un valor predeterminado o agregue otro argumento a get_else_compute.