c ++ map find () à éventuellement insérer (): comment optimiser les opérations?

Question

J'utilise la structure de données de la carte STL et au moment où mon code appelle pour la première fois find () : si la clé ne figurait pas précédemment dans la carte, elle appelle insert (). , sinon il ne fait rien.

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

Je me demandais s’il existait un meilleur moyen que celui-ci, car, autant que je sache, dans le cas où je veux insérer une clé qui n’est pas encore présente, j’effectue 2 recherches dans les structures de données de carte: pour find () , un dans insert () (qui correspond à l'opérateur [] ).

Merci d'avance pour toute suggestion.

Answer 1

Normalement, si vous effectuez une recherche et éventuellement une insertion, vous souhaitez conserver (et récupérer) l'ancienne valeur si elle existait déjà. Si vous souhaitez simplement écraser une ancienne valeur, map [foo_obj] = "une valeur" & <; code> le fera.

Voici comment obtenir l'ancienne valeur ou en insérer une nouvelle si elle n'existait pas, avec une seule recherche de carte:

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]

C’est un langage assez répandu pour que vous souhaitiez utiliser une fonction d’aide:

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 vous souhaitez ignorer un calcul coûteux pour v s'il existe déjà (mémoization, par exemple), vous pouvez également le généraliser:

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;
}

où, par exemple,

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 le type mappé n'est pas constructible par défaut, demandez à F de fournir une valeur par défaut ou ajoutez un autre argument à get_else_compute.

Answer 2

Il existe deux approches principales. La première consiste à utiliser la fonction insert prenant un type valeur et renvoyant un itérateur et une valeur booléenne indiquant si une insertion a eu lieu et renvoyant un itérateur à l'élément existant avec la même clé ou au nouvel élément inséré.

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") );

L'avantage de ceci est que c'est simple. L'inconvénient majeur est que vous construisez toujours une nouvelle valeur pour le second paramètre, qu'une insertion soit nécessaire ou non. Dans le cas d'une chaîne, cela n'a probablement pas d'importance. Si votre valeur est chère à construire, cela risque de vous faire perdre plus que nécessaire.

Pour contourner ce problème, utilisez la version "hint" de insert.

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") );
}

Il est garanti que l'insertion est en temps constant amorti si l'élément est inséré immédiatement après l'itérateur fourni, d'où le - , si possible.

Modifier

Si ce besoin de - semble étrange, alors il l'est. Il existe un défaut ouvert (233) dans la norme qui met en évidence ce problème, bien que la description du problème s’appliquant à map soit plus claire dans le problème en double 246 .

Answer 3

Dans votre exemple, vous souhaitez insérer une information non trouvée. Si la construction par défaut et le réglage de la valeur après cela ne sont pas chers, je suggérerais une version plus simple avec 1 recherche:

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 votre exemple indique ce que vous voulez réellement, pensez à ajouter cette valeur sous la forme str Foo :: s , vous avez déjà l'objet, vous n'avez donc aucune recherche à effectuer, vérifiez s'il contient les valeurs par défaut. valeur pour ce membre. Et gardez les objs dans std :: set . Même l'extension de la classe FooWithValue2 peut être moins chère que d'utiliser map .

Mais si joindre des données via la carte comme celle-ci est vraiment nécessaire ou si vous souhaitez mettre à jour uniquement si elle existait, Jonathan a la réponse.