std :: map Einsatz oder std :: map finden?

StackOverflow https://stackoverflow.com/questions/97050

  •  01-07-2019
  •  | 
  •  

Frage

Unter der Annahme einer Karte, wo Sie vorhandene Einträge erhalten möchten. 20% der Zeit, der Eintrag Sie einfügen neue Daten. Gibt es einen Vorteil zu std :: map tun :: finden dann std :: map :: insert mit, dass Iterator zurückgegeben? Oder ist es schneller, den Einsatz zu versuchen, und dann handeln basierend auf, ob der Iterator zeigt die Aufzeichnung wurde oder nicht eingefügt?

War es hilfreich?

Lösung

Die Antwort ist, dass Sie auch nicht. Stattdessen wollen Sie etwas von Artikel vorgeschlagen tun 24 von 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
}

Andere Tipps

Die Antwort auf diese Frage hängt auch davon ab, wie teuer es ist, den Werttyp erstellen Sie in der Karte sind 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 int, die oben wird effizienter als ein durch einen Einsatz gefolgt finden (in Abwesenheit von Compiler-Optimierungen). Wie oben erwähnt, ist dies, weil die Suche durch die Karte einmal erfolgt nur.

Allerdings erfordert der Aufruf einzufügen, dass Sie bereits den neuen „Wert“ haben aufgebaut: 

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 nennen ‚Einfügen‘ wir sind für den teueren Anruf zahlen unseren Werttyp zu konstruieren - und von dem, was man in der Frage gesagt werden Sie nicht dieses neue Wert 20% der Zeit. Im obigen Fall, wenn die Karte Werttyp ist keine Option zu ändern, dann ist es effizienter, zuerst die ‚finden‘ auszuführen zu prüfen, ob wir das Element konstruieren müssen.

Alternativ kann der Wert Typ der Karte zu speichern geändert werden Griffe auf die Daten Ihren Liebling Smart-Pointer-Typen. Der Aufruf von Insert verwendet einen Null-Zeiger (sehr billig zu konstruieren) und nur bei Bedarf ist der neue Datentyp aufgebaut ist.

Es wird kaum ein Unterschied in der Geschwindigkeit zwischen den 2, kehren findet einen Iterator, einfügen macht die gleichen und wird die Karte sucht ohnehin zu bestimmen, ob der Eintrag bereits vorhanden ist.

So .. sein auf den persönlichen Vorlieben. Ich habe immer Einsatz versuchen und dann aktualisieren, wenn nötig, aber einige Leute nicht, wie das Paar der Handhabung, der zurückgegeben wird.

Ich würde denken, wenn Sie ein einfügen finden Sie dann die zusätzlichen Kosten wäre, wenn Sie den Einsatz nach den Schlüssel nicht finden und durchführen. Es ist eine Art wie der Blick durch Bücher in alphabetischer Reihenfolge und nicht das Buch zu finden, dann durch die Bücher sucht wieder zu sehen, wo es einzufügen. Es läuft darauf hinaus, wie Sie die Schlüssel werden Handhabung und wenn sie sich ständig verändern. Jetzt gibt es eine gewisse Flexibilität bei, dass, wenn Sie es nicht finden, können Sie sich einloggen, Ausnahme, tun, was Sie wollen ...

Ich bin auf der Top-Antwort verloren.

Finden kehrt map.end (), wenn er nichts finden, was bedeutet, wenn Sie hinzufügen, neue 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, da sie zweimal suchen müssen. Einmal zu sehen, ob es da ist, wieder den Ort zu finden, die neue Sache zu stellen.

Wenn Sie sich über die Effizienz betrifft, sollten Sie hash_map <> .

Normalerweise Karte <> als Binärbaum implementiert. Je nach Bedarf kann ein hash_map effizienter sein.

Ich scheine nicht genug Punkte zu haben, um einen Kommentar zu hinterlassen, aber die tickte Antwort scheint mir lange umständliche zu werden - wenn man bedenkt, dass Einsatz der Iterator gibt sowieso, warum lower_bound gehen auf der Suche, wenn Sie nur die verwenden können, Iterator zurückgegeben. Seltsam.

Jede Antworten zu Effizienz über die genaue Umsetzung Ihrer STL ab. Der einzige Weg, um sicher zu wissen ist es in beiden Richtungen zu Benchmark. Ich würde vermuten, dass der Unterschied unwahrscheinlich ist, bedeutend zu sein, so entscheiden auf der Grundlage der Stil, den Sie bevorzugen.

Karte [key] - lassen stl sort it out. Das ist die Kommunikation Ihre Absicht, am effektivsten.

Ja, meinetwegen.

Wenn Sie eine Suche zu tun und dann ein Einsatz Sie ausführen, 2 x O (log N), wenn Sie eine Chance vertan als die einzige finden bekommen lässt Sie wissen, wenn Sie nicht einsetzen müssen, wo der Einsatz gehen sollte (lower_bound könnte helfen Du da drüben). Nur gerade Einsatz und dann das Ergebnis der Prüfung ist der Weg, den ich gehen würde.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top