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 buscar () : si la clave no estaba anteriormente en el mapa, llama a insertar () eso, 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 find () , uno en insert () (que corresponde al operador [] ).

Gracias de antemano por cualquier sugerencia.

Answer 1

Normalmente, si hace una búsqueda y quizás una inserción, querrá mantener (y recuperar) el valor antiguo si ya existía. Si solo desea sobrescribir cualquier valor anterior, map [foo_obj] = " algún valor " lo hará.

Aquí se explica 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 que quieras usar una función de ayuda:

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, la memorización), puede generalizar eso 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 asignado no es construible por defecto, haga que F proporcione un valor predeterminado, o agregue otro argumento a get_else_compute.

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 de construir, esto puede generar más desperdicio 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, de ahí el - , si es posible.

Editar

Si esta necesidad de - parece extraño, entonces es. Hay un defecto abierto (233) en el estándar que resalta este problema, aunque la descripción del problema que se aplica al mapa es más clara en el problema duplicado 246 .

Answer 3

En su ejemplo, desea insertar cuando no se encuentra. Si la construcción por defecto y la configuración del valor después de eso no son costosas, 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 su lugar, ya tiene el objeto, por lo que no sería necesario realizar búsquedas, simplemente verifique si tiene valores predeterminados Valor para ese miembro. Y mantén los objetos en el std :: set . Incluso extender clase FooWithValue2 puede ser más barato que usar mapa .

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