std :: map insert oder std :: map find?

Angenommen, Sie möchten eine Karte erstellen, in der vorhandene Einträge beibehalten werden sollen. In 20% der Fälle handelt es sich bei dem Eintrag, den Sie einfügen, um neue Daten. Gibt es einen Vorteil, wenn Sie std :: map :: find und dann std :: map :: insert mit diesem zurückgegebenen Iterator ausführen? Oder ist es schneller, das Einfügen zu versuchen und dann basierend darauf zu handeln, ob der Iterator angibt, dass der Datensatz eingefügt wurde oder nicht?

Die Antwort ist, dass Sie beides nicht tun. Stattdessen möchten Sie etwas tun, das in Punkt 24 von Effective STL von Scott Meyers vorgeschlagen wurde :

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
}

Die Antwort auf diese Frage hängt auch davon ab, wie teuer es ist, den Werttyp zu erstellen, den Sie in der Karte speichern:

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

Für einen Werttyp wie ein int ist das Obige effizienter als ein Fund, gefolgt von einer Einfügung (ohne Compiler-Optimierungen). Wie oben erwähnt, liegt dies daran, dass die Suche in der Karte nur einmal erfolgt.

Für den Aufruf zum Einfügen muss jedoch der neue "Wert" bereits erstellt sein:

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

Um 'Einfügen' aufzurufen, zahlen wir für den teuren Aufruf zur Erstellung unseres Werttyps - und nach dem, was Sie in der Frage gesagt haben, werden Sie diesen neuen Wert in 20% der Fälle nicht verwenden. Wenn im obigen Fall das Ändern des Kartenwerttyps keine Option ist, ist es effizienter, zuerst die Suche durchzuführen, um zu überprüfen, ob das Element erstellt werden muss.

Alternativ kann der Wertetyp der Karte geändert werden, um Handles für die Daten unter Verwendung Ihres bevorzugten Smart-Pointer-Typs zu speichern. Der Aufruf zum Einfügen verwendet einen Nullzeiger (sehr billig zu erstellen) und nur bei Bedarf wird der neue Datentyp erstellt.

Es wird kaum einen Geschwindigkeitsunterschied zwischen den beiden geben, find gibt einen Iterator zurück, insert macht dasselbe und durchsucht die Karte trotzdem, um festzustellen, ob der Eintrag bereits vorhanden ist.

Also ... es liegt an den persönlichen Vorlieben. Ich versuche immer einzufügen und bei Bedarf zu aktualisieren, aber einige Leute mögen es nicht, mit dem zurückgegebenen Paar umzugehen.

Ich würde denken, wenn Sie eine Suche durchführen und dann einfügen, wären die zusätzlichen Kosten, wenn Sie den Schlüssel nicht finden und die Einfügung danach durchführen. Es ist so, als würde man Bücher in alphabetischer Reihenfolge durchsehen und das Buch nicht finden und dann erneut durch die Bücher schauen, um zu sehen, wo es eingefügt werden soll. Es läuft darauf hinaus, wie Sie mit den Schlüsseln umgehen und ob sie sich ständig ändern. Jetzt gibt es eine gewisse Flexibilität: Wenn Sie es nicht finden, können Sie protokollieren, Ausnahmen machen, tun, was Sie wollen ...

Ich habe die beste Antwort verloren.

Find gibt map.end () zurück, wenn nichts gefunden wird, was bedeutet, dass Sie dann neue Dinge hinzufügen

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

ist doppelt so langsam wie

map.insert

für jedes Element, das noch nicht in der Karte enthalten ist, da es zweimal suchen muss. Einmal, um zu sehen, ob es da ist, wieder, um den Platz für das neue Ding zu finden.

Wenn Sie sich Gedanken über die Effizienz machen, sollten Sie sich hash_map <> ansehen .

In der Regel wird map <> als Binärbaum implementiert. Abhängig von Ihren Anforderungen kann eine hash_map effizienter sein.

Ich habe anscheinend nicht genug Punkte, um einen Kommentar zu hinterlassen, aber die angekreuzte Antwort scheint mir langwierig zu sein. Wenn Sie bedenken, dass insert den Iterator trotzdem zurückgibt, warum sollten Sie dann nach lower_bound suchen, wenn Sie nur den zurückgegebenen Iterator verwenden können. Seltsam.

Alle Antworten zur Effizienz hängen von der genauen Implementierung Ihrer STL ab. Die einzige Möglichkeit, dies sicher zu wissen, besteht darin, es in beide Richtungen zu vergleichen. Ich würde vermuten, dass der Unterschied wahrscheinlich nicht signifikant ist. Entscheiden Sie sich also für den Stil, den Sie bevorzugen.

map [key] - lass es stl klären. Das kommuniziert Ihre Absicht am effektivsten.

Ja, fair genug.

Wenn Sie eine Suche und dann eine Einfügung durchführen, führen Sie 2 x O (log N) aus, wenn Sie einen Fehler erhalten, da die Suche Sie nur darüber informiert, wenn Sie nicht einfügen müssen, wohin die Einfügung gehen soll (lower_bound kann Ihnen dort helfen). . Nur eine gerade Einfügung und dann das Ergebnis zu untersuchen, ist der Weg, den ich gehen würde.