c ++ Karte find (), um möglicherweise einfügen (): wie Operationen zu optimieren?

Question

Ich bin mit der STL Karte Datenstruktur, und im Moment meines Code zuerst aufruft finden () : Wenn der Schlüssel nicht vorher in der Karte war, ruft insert () es, sonst tut es nichts.

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

Ich habe mich gefragt, ob es einen besseren Weg, als das ist, denn soweit ich das beurteilen kann in diesem Fall, wenn ich einen Schlüssel eingefügt werden soll, der noch nicht vorhanden ist, I 2-Lookups in den Kartendatenstrukturen durchführen: ein für finden () , ein in dem insert () (das entspricht die Operator [] ).

Vielen Dank im Voraus für jede Anregung.

Answer 1

Normalerweise, wenn Sie eine Suche und vielleicht einen Einsatz machen dann wollen Sie halten (und Abrufen), den alten Wert, wenn es bereits existierte. Wenn Sie nur alle alten Wert überschrieben werden sollen, map[foo_obj]="some value" wird das tun.

Hier ist, wie Sie den alten Wert zu erhalten, oder einen neuen ein, wenn es nicht mit einer Karte Nachschlag gab es:

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]

Dies ist ein gemeinsames genug Idiom, die Sie vielleicht eine Hilfsfunktion verwenden:

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

Wenn Sie eine teure Berechnung haben für v Sie überspringen wollen, wenn es bereits vorhanden ist (z memoization), Sie können das verallgemeinern zu:

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

, wo z.

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

Wenn die abgebildete Art nicht konstruierbar ist standardmäßig, dann macht F einen Standardwert zur Verfügung stellen, oder ein anderes Argument in dem get_else_compute.

Answer 2

Es gibt zwei Ansätze. Die erste ist die Insert-Funktion zu verwenden, die einen Werttyp annimmt und welche gibt einen Iterator und einen bool, die anzeigen, ob ein Einfügungsstattgefunden hat und gibt einen Iterator, um entweder das bestehende Element mit dem gleichen Schlüssel oder das neu eingefügte Element.

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

Der Vorteil hierbei ist, dass es einfach ist. Der größte Nachteil ist, dass Sie immer einen neuen Wert für den zweiten Parameter konstruieren, ob eine Insertion erforderlich ist. Im Fall eines Strings dies wahrscheinlich keine Rolle spielt. Wenn Ihr Wert teuer ist, dies zu konstruieren kann mehr verschwenderisch als nötig.

Eine Art und Weise rundet das ist die ‚Hinweis‘ -Version des Einsatzes zu verwenden.

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

Die insertiong garantiert wird nur in der fortgeführten Anschaffungs konstanter Zeit sein, wenn das Element unmittelbar nach dem mitgelieferten Iterator eingeführt wird, damit die --, wenn möglich.

Bearbeiten

Wenn diese Notwendigkeit zu -- merkwürdig erscheint, so ist es. Es gibt einen offenen Defekt (233) in dem Standard, der dieses Problem, obwohl die Beschreibung des Problems hightlights wie es map gilt klarer im doppelten Ausgabe 246 .

Answer 3

In Ihrem Beispiel wollen Sie einfügen, wenn sie nicht gefunden wird. Wenn Standard-Konstruktion und den Wert einstellen, nachdem das nicht teuer ist, würde ich einfachere Version mit 1 Lookup vorschlagen:

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

Wenn Ihr Beispiel sagt, was Sie eigentlich wollen, sollten Sie diesen Wert als str Foo::s Zugabe stattdessen Sie bereits das Objekt haben, so würde keine Lookups benötigt werden, nur prüfen, ob es Standardwert für dieses Element hat. Und halten Sie die objs im std::set. Auch class FooWithValue2 erstreckt, kann billiger sein als map verwendet wird.

Aber wenn wie diese Daten durch die Karte Beitritt wirklich benötigt wird oder wenn Sie aktualisieren möchten, wenn es existiert, dann hat Jonathan die Antwort.