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

Vorausgesetzt, eine Karte, wo Sie möchten, erhalten die vorhandenen Einträge. 20% der Zeit, den Eintrag, den Sie einfügen neuer Daten. Ist es ein Vorteil zu tun, std::map::find dann std::map::insert mit, dass das zurückgegebene iterator? Oder ist es schneller, zu versuchen, die insert-und dann handeln, basierend auf, ob oder nicht der iterator gibt die Aufnahme war oder nicht eingelegt?

InformationsquelleAutor der Frage Superpolock | 2008-09-18

c++optimization stdmap stl

131

Die Antwort ist: Sie tun weder. Stattdessen wollen Sie etwas tun, vorgeschlagen durch Artikel 24 des Effective STL von Scott Meyers:

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
}

InformationsquelleAutor der Antwort luke

10

Die Antwort auf diese Frage hängt auch davon ab, wie teuer es ist, erstellen Sie den Wert-Typ, den Sie speichern in der Karte:
```
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;
  }
}
```
Einen Wert geben wie ein int, die oben genannten effizienter als ein finden, gefolgt von einer insert - (in Abwesenheit von compiler-Optimierungen). Wie oben erwähnt, ist dies, weil die Suche über die Karte, erfolgt nur einmal.

Jedoch der Aufruf von insert erfordert, dass Sie bereits über den neuen "Wert" konstruiert:
```
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 den Aufruf von 'einfügen' wir zahlen für die teuren Anruf zu konstruieren, die unseren Wert geben - und von dem, was Sie sagte, in der Frage, die Sie nicht verwenden Sie diesen neuen Wert 20% der Zeit. In dem genannten Fall, wenn die änderung der map-Wert geben ist keine option, dann ist es effizienter, zuerst die 'suchen' um zu prüfen, ob wir konstruieren müssen, das element.

Alternativ, den Wert-Typ der Karte kann geändert werden, um speichern Sie die Ziehpunkte, um die Daten mit Ihrem Lieblings-smart-pointer-Typ. Der Aufruf von insert verwendet einen null-Zeiger (sehr Billig zu konstruieren), und nur wenn notwendig ist der neue Datentyp gebaut.

InformationsquelleAutor der Antwort Richard Corden
8

Wird es kaum einen Unterschied in der Geschwindigkeit zwischen den 2, finden zurück einen iterator, legen Sie das gleiche tut, und durchsuchen Sie die Karte trotzdem zu bestimmen, ob der Eintrag bereits vorhanden ist.

So.. seine persönlichen Vorlieben. Ich versuche immer, einfügen und aktualisieren Sie, wenn nötig, aber einige Leute don T wie Umgang mit dem paar, das zurückgegeben wird.

InformationsquelleAutor der Antwort gbjbaanb
5

Ich würde denken, wenn Sie eine finden, dann legen Sie die extra Kosten würden, wenn Sie nicht finden, die Schlüssel und die Durchführung der einfügen-nach. Es ist irgendwie, als würde man durch Bücher in alphabetischer Reihenfolge, und findet nicht das Buch, dann der Blick durch die Bücher wieder, um zu sehen, wo es einzufügen. Es läuft darauf hinaus, wie Sie die Schlüsselübergabe und wenn Sie sich ständig ändern. Nun gibt es einige Flexibilität, wenn Sie es nicht finden, können Sie sich anmelden, Ausnahme, tun, was Sie wollen...

InformationsquelleAutor der Antwort PiNoYBoY82
2

Bin ich verloren, auf die top-Antwort.

Finden gibt anzeigen.Ende (), wenn Sie es nicht finden, alles, was was bedeutet, wenn Sie sind das hinzufügen neuer Dinge, dann
```
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 nicht bereits in der Karte seit wird er zu suchen haben, zweimal. Einmal zu sehen, wenn Sie da ist, wieder zu finden, den Ort, um die neue Sache.

InformationsquelleAutor der Antwort gman
1

Wenn Sie besorgt sind Energieeffizienz, Sie können prüfen wollen,hash_map<>.

In der Regel anzeigen<> ist implementiert als ein binärer Baum. Je nach Ihren Bedürfnissen, eine hash_map effizienter sein können.

InformationsquelleAutor der Antwort Adam Tegen
1

Ich nicht scheinen, um genug Punkte um einen Kommentar zu hinterlassen, aber der tickte Antwort scheint zu langatmig für mich - wenn man bedenkt, dass fügen liefert den iterator sowieso, warum gehen auf der Suche lower_bound, wenn Sie können benutzen Sie einfach den iterator zurückgegeben. Seltsam.

InformationsquelleAutor der Antwort Stonky
0

Alle Antworten über die Effektivität hängt von der genauen Implementierung der STL. Der einzige Weg, um sicher wissen, ist es zum benchmark-in beide Richtungen. Ich denke, dass der Unterschied kaum erheblich sein, so entscheiden Sie, basierend auf den Stil Sie bevorzugen.

InformationsquelleAutor der Antwort Mark Ransom
-2

map[ key ] - let stl-sort it out. Dass die Kommunikation Ihre Absicht, die meisten effektiv.

Ja, fair genug.

Wenn Sie eine finden und dann einen einfügen, die Sie gerade ausführen 2 x O(log N), wenn Sie eine verpassen, als die finden Sie nur lässt Sie wissen, wenn Sie benötigen Sie nicht, wo der stecken sollte gehen (lower_bound könnte dir da helfen). Nur eine gerade legen und dann untersuchen, das Ergebnis ist der Weg, den ich gehen würde.

InformationsquelleAutor der Antwort

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.