Ist es in STL-Karten besser, map :: insert als [] zu verwenden?

201

Vor einiger Zeit hatte ich eine Diskussion mit einem Kollegen darüber, wie Werte in STL- Maps eingefügt werden . Ich habe es vorgezogen, map[key] = value; weil es sich natürlich anfühlt und klar zu lesen ist, während er es vorgezogen hat map.insert(std::make_pair(key, value))

Ich habe ihn nur gefragt und keiner von uns kann sich an den Grund erinnern, warum Insert besser ist, aber ich bin sicher, dass es nicht nur eine Stilvorliebe war, sondern dass es einen technischen Grund wie Effizienz gab. In der SGI STL-Referenz heißt es einfach: "Genau genommen ist diese Mitgliedsfunktion nicht erforderlich: Sie existiert nur zur Vereinfachung."

Kann mir jemand diesen Grund nennen oder träume ich nur davon, dass es einen gibt?

danio
quelle
2
Vielen Dank für all die tollen Antworten - sie waren wirklich hilfreich. Dies ist eine großartige Demo des Stapelüberlaufs von seiner besten Seite. Ich war hin und her gerissen, was die akzeptierte Antwort sein sollte: netjeff geht expliziter auf das unterschiedliche Verhalten ein, Greg Rogers erwähnte Leistungsprobleme. Ich wünschte, ich könnte beides ankreuzen.
Danio
6
Tatsächlich ist es mit C ++ 11 wahrscheinlich am besten, map :: emplace zu verwenden, wodurch die doppelte Konstruktion
vermieden wird
@einpoklum: Eigentlich schlägt Scott Meyers in seinem Vortrag "Die sich entwickelnde Suche nach effektivem C ++" etwas anderes vor.
Thomas Eding
3
@einpoklum: Dies ist der Fall, wenn Sie in einen neu erstellten Speicher einfügen. Aufgrund einiger Standardanforderungen für die Karte gibt es jedoch technische Gründe, warum das Einlegen langsamer sein kann als das Einfügen. Der Vortrag ist auf youtube frei verfügbar, beispielsweise über diesen Link youtube.com/watch?v=smqT9Io_bKo @ ~ 38-40 min mark. Für einen SO-Link finden Sie hier stackoverflow.com/questions/26446352/…
Thomas Eding
1
Ich würde tatsächlich mit einigen von dem streiten, was Meyers präsentiert hat, aber das geht über den Rahmen dieses Kommentarthreads hinaus und ich denke, ich muss meinen früheren Kommentar zurückziehen.
Einpoklum

Antworten:

240

Wenn du schreibst

map[key] = value;

Es gibt keine Möglichkeit zu sagen, ob Sie ersetzt die valuefür key, oder wenn Sie erstellt eine neue keymit value.

map::insert() wird nur erstellen:

using std::cout; using std::endl;
typedef std::map<int, std::string> MyMap;
MyMap map;
// ...
std::pair<MyMap::iterator, bool> res = map.insert(MyMap::value_type(key,value));
if ( ! res.second ) {
    cout << "key " <<  key << " already exists "
         << " with value " << (res.first)->second << endl;
} else {
    cout << "created key " << key << " with value " << value << endl;
}

Bei den meisten meiner Apps ist es mir normalerweise egal, ob ich sie erstelle oder ersetze, daher verwende ich die leichter lesbaren map[key] = value.

netjeff
quelle
16
Es sollte beachtet werden, dass map :: insert niemals Werte ersetzt. Und im allgemeinen Fall würde ich sagen, dass es besser ist, (res.first)->secondals valueauch im zweiten Fall zu verwenden.
Dale
1
Ich habe aktualisiert, um klarer zu machen, dass map :: insert niemals ersetzt wird. Ich habe das verlassen, elseweil ich denke, dass die Verwendung valueklarer ist als der Iterator. Nur wenn der Typ des Werts einen ungewöhnlichen Kopierer oder op == hätte, wäre dies anders, und dieser Typ würde andere Probleme bei der Verwendung von STL-Containern wie map verursachen.
Netjeff
1
map.insert(std::make_pair(key,value))sollte sein map.insert(MyMap::value_type(key,value)). Der Typ, der von zurückgegeben wird, make_pairstimmt nicht mit dem Typ überein, der von genommen wird, insertund die aktuelle Lösung erfordert eine Konvertierung
David Rodríguez - dribeas
1
Es gibt eine Möglichkeit zu erkennen, ob Sie eingefügt oder nur zugewiesen operator[]haben. Vergleichen Sie einfach die Größe vorher und nachher. Es map::operator[]ist viel wichtiger, nur konstruierbare Standardtypen aufrufen zu können .
idclev 463035818
@ DavidRodríguez-dribeas: Guter Vorschlag, ich habe den Code in meiner Antwort aktualisiert.
Netjeff
53

Die beiden haben unterschiedliche Semantiken, wenn es um den Schlüssel geht, der bereits in der Karte vorhanden ist. Sie sind also nicht direkt vergleichbar.

Für die Version operator [] muss der Wert jedoch standardmäßig erstellt und anschließend zugewiesen werden. Wenn dies also teurer ist als die Kopierkonstruktion, ist dies teurer. Manchmal macht die Standardkonstruktion keinen Sinn, und dann ist es unmöglich, die operator [] -Version zu verwenden.

Greg Rogers
quelle
1
make_pair erfordert möglicherweise einen Kopierkonstruktor - das wäre schlimmer als der Standardkonstruktor. +1 sowieso.
1
Die Hauptsache ist, wie Sie sagten, dass sie unterschiedliche Semantik haben. Also ist keiner besser als der andere, benutze einfach den, der das tut, was du brauchst.
Jalf
Warum sollte der Kopierkonstruktor schlechter sein als der Standardkonstruktor, gefolgt von einer Zuweisung? Wenn dies der Fall ist, hat die Person, die die Klasse geschrieben hat, etwas übersehen, da jeder Operator = dies auch im Kopierkonstruktor tun sollte.
Steve Jessop
1
Manchmal ist die Standardkonstruktion so teuer wie die Zuweisung selbst. Zuordnung und Kopierkonstruktion sind natürlich gleichwertig.
Greg Rogers
@Arkadiy In einem optimierten Build entfernt der Compiler häufig viele unnötige Aufrufe von Kopierkonstruktoren.
antred
35

Eine andere Sache zu beachten std::map :

myMap[nonExistingKey]; erstellt einen neuen Eintrag in der Karte, der mit verschlüsselt ist nonExistingKey auf einen Standardwert initialisiert ist.

Das erschreckte mich zum Teufel, als ich es das erste Mal sah (während ich meinen Kopf gegen einen bösen alten Käfer schlug). Hätte es nicht erwartet. Für mich sieht das nach einer Get-Operation aus, und ich habe den "Nebeneffekt" nicht erwartet. Bevorzugen Sie, map.find()wenn Sie von Ihrer Karte kommen.

Hawkeye Parker
quelle
3
Das ist eine anständige Ansicht, obwohl Hash-Maps für dieses Format ziemlich universell sind. Es könnte eine dieser "Kuriositäten sein, die niemand für seltsam hält", nur weil sie die gleichen Konventionen verwenden
Stephen J
19

Wenn der Leistungstreffer des Standardkonstruktors kein Problem darstellt, wählen Sie aus Liebe zu Gott die besser lesbare Version.

:) :)

Torlack
quelle
5
Zweite! Muss das markieren. Zu viele Leute tauschen Stumpfheit gegen Nano-Sekunden-Beschleunigungen aus. Erbarme dich unserer armen Seelen, die solche Gräueltaten aufrechterhalten müssen!
Mr.Ree
6
Greg Rogers schrieb: "Die beiden haben unterschiedliche Semantiken, wenn es um den Schlüssel geht, der bereits in der Karte vorhanden ist. Sie sind also nicht wirklich direkt vergleichbar."
Dale
Dies ist eine alte Frage und Antwort. Aber "besser lesbare Version" ist ein dummer Grund. Denn was am besten lesbar ist, hängt von der Person ab.
Vallentin
14

insert ist aus Sicht der Ausnahmesicherheit besser.

Der Ausdruck map[key] = valuebesteht eigentlich aus zwei Operationen:

  1. map[key] - Erstellen eines Kartenelements mit Standardwert.
  2. = value - Kopieren des Wertes in dieses Element.

Im zweiten Schritt kann eine Ausnahme auftreten. Infolgedessen wird die Operation nur teilweise ausgeführt (ein neues Element wurde zur Karte hinzugefügt, aber dieses Element wurde nicht mit initialisiert value). Die Situation, in der eine Operation nicht abgeschlossen ist, der Systemstatus jedoch geändert wird, wird als Operation mit "Nebenwirkung" bezeichnet.

insertBetrieb gibt eine starke Garantie, bedeutet, dass es keine Nebenwirkungen hat ( https://en.wikipedia.org/wiki/Exception_safety ). insertist entweder vollständig erledigt oder die Karte bleibt unverändert.

http://www.cplusplus.com/reference/map/map/insert/ :

Wenn ein einzelnes Element eingefügt werden soll, gibt es im Ausnahmefall keine Änderungen im Container (starke Garantie).

anton_rh
quelle
1
Noch wichtiger ist, dass für das Einfügen kein Wert erforderlich ist, um standardmäßig konstruierbar zu sein.
UmNyobe
13

Wenn Ihre Anwendung geschwindigkeitskritisch ist, empfehle ich die Verwendung des Operators [], da insgesamt 3 Kopien des Originalobjekts erstellt werden, von denen 2 temporäre Objekte sind und früher oder später als zerstört wurden.

In insert () werden jedoch 4 Kopien des Originalobjekts erstellt, von denen 3 temporäre Objekte (nicht unbedingt "temporäre") sind und zerstört werden.

Dies bedeutet zusätzliche Zeit für: 1. Zuweisung eines Objektspeichers 2. Ein zusätzlicher Konstruktoraufruf 3. Ein zusätzlicher Destruktoraufruf 4. Eine Freigabe des Objektspeichers

Wenn Ihre Objekte groß sind, Konstruktoren typisch sind, Destruktoren viel Ressourcen freisetzen, zählen die obigen Punkte noch mehr. In Bezug auf die Lesbarkeit denke ich, dass beide fair genug sind.

Die gleiche Frage kam mir in den Sinn, aber nicht über die Lesbarkeit, sondern über die Geschwindigkeit. Hier ist ein Beispielcode, durch den ich den Punkt kennengelernt habe, den ich erwähnt habe.

class Sample
{
    static int _noOfObjects;

    int _objectNo;
public:
    Sample() :
        _objectNo( _noOfObjects++ )
    {
        std::cout<<"Inside default constructor of object "<<_objectNo<<std::endl;
    }

    Sample( const Sample& sample) :
    _objectNo( _noOfObjects++ )
    {
        std::cout<<"Inside copy constructor of object "<<_objectNo<<std::endl;
    }

    ~Sample()
    {
        std::cout<<"Destroying object "<<_objectNo<<std::endl;
    }
};
int Sample::_noOfObjects = 0;


int main(int argc, char* argv[])
{
    Sample sample;
    std::map<int,Sample> map;

    map.insert( std::make_pair<int,Sample>( 1, sample) );
    //map[1] = sample;
    return 0;
}

Ausgabe bei Verwendung von insert () Ausgabe bei Verwendung des Operators []

Rampal Chaudhary
quelle
4
Führen Sie diesen Test nun erneut aus, wobei die vollständigen Optimierungen aktiviert sind.
antred
2
Überlegen Sie auch, was Operator [] tatsächlich tut. Zuerst wird die Karte nach einem Eintrag durchsucht, der dem angegebenen Schlüssel entspricht. Wenn es einen findet, überschreibt es den Wert dieses Eintrags mit dem angegebenen. Ist dies nicht der Fall, wird ein neuer Eintrag mit dem angegebenen Schlüssel und Wert eingefügt. Je größer Ihre Karte wird, desto länger dauert der Operator [], um die Karte zu durchsuchen. Irgendwann wird dies einen zusätzlichen Kopieraufruf mehr als wettmachen (wenn dieser sogar im endgültigen Programm verbleibt, nachdem der Compiler seine Optimierungsmagie ausgeführt hat).
antred
1
@antred, insertmuss die gleiche Suche durchführen, also kein Unterschied zu [](weil Kartenschlüssel eindeutig sind).
Gr.
Schöne Illustration, was mit den Ausdrucken los ist - aber was machen diese 2 Codebits tatsächlich? Warum sind überhaupt 3 Kopien des Originalobjekts erforderlich?
Rbennett485
1. muss den Zuweisungsoperator implementieren, sonst werden im Destruktor falsche Zahlen angezeigt. 2. Verwenden Sie std :: move, wenn Sie ein Paar erstellen, um ein übermäßiges Kopieren zu vermeiden. "Map.insert (std :: make_pair <int, Sample> (1, std: : move (sample))); "
Fl0
10

In C ++ 11 denke ich, dass der beste Weg, ein Paar in eine STL-Map einzufügen, ist:

typedef std::map<int, std::string> MyMap;
MyMap map;

auto& result = map.emplace(3,"Hello");

Das Ergebnis ist ein Paar mit:

  • Das erste Element (result.first) zeigt auf das eingefügte Paar oder auf das Paar mit diesem Schlüssel, wenn der Schlüssel bereits vorhanden ist.

  • Zweites Element (result.second), true, wenn die Einfügung korrekt oder falsch war, ist ein Fehler aufgetreten.

PS: Wenn Sie sich nicht für die Bestellung interessieren, können Sie std :: unordered_map verwenden;)

Vielen Dank!

GutiMac
quelle
9

Ein Problem mit map :: insert () ist, dass es keinen Wert ersetzt, wenn der Schlüssel bereits in der Map vorhanden ist. Ich habe C ++ - Code gesehen, der von Java-Programmierern geschrieben wurde, bei denen erwartet wurde, dass sich insert () genauso verhält wie Map.put () in Java, wo Werte ersetzt werden.

Anthony Cramp
quelle
2

Ein Hinweis ist, dass Sie auch Boost.Assign verwenden können :

using namespace std;
using namespace boost::assign; // bring 'map_list_of()' into scope

void something()
{
    map<int,int> my_map = map_list_of(1,2)(2,3)(3,4)(4,5)(5,6);
}
rlbond
quelle
1

Hier ist ein weiteres Beispiel zeigt , dass operator[] überschreibt den Wert für den Schlüssel , wenn es vorhanden ist , aber .insert nicht überschreiben Sie den Wert , wenn es vorhanden ist .

void mapTest()
{
  map<int,float> m;


  for( int i = 0 ; i  <=  2 ; i++ )
  {
    pair<map<int,float>::iterator,bool> result = m.insert( make_pair( 5, (float)i ) ) ;

    if( result.second )
      printf( "%d=>value %f successfully inserted as brand new value\n", result.first->first, result.first->second ) ;
    else
      printf( "! The map already contained %d=>value %f, nothing changed\n", result.first->first, result.first->second ) ;
  }

  puts( "All map values:" ) ;
  for( map<int,float>::iterator iter = m.begin() ; iter !=m.end() ; ++iter )
    printf( "%d=>%f\n", iter->first, iter->second ) ;

  /// now watch this.. 
  m[5]=900.f ; //using operator[] OVERWRITES map values
  puts( "All map values:" ) ;
  for( map<int,float>::iterator iter = m.begin() ; iter !=m.end() ; ++iter )
    printf( "%d=>%f\n", iter->first, iter->second ) ;

}
Bobobobo
quelle
1

Dies ist ein eher eingeschränkter Fall, aber nach den Kommentaren, die ich erhalten habe, halte ich es für erwähnenswert.

Ich habe in der Vergangenheit gesehen, dass Leute Karten in Form von verwenden

map< const key, const val> Map;

Um Fällen von versehentlichem Überschreiben von Werten auszuweichen, schreiben Sie dann einige andere Code-Teile ein:

const_cast< T >Map[]=val;

Ihr Grund dafür war, wie ich mich erinnere, dass sie sicher waren, dass sie in diesen bestimmten Codebits keine Kartenwerte überschreiben würden; Fahren Sie daher mit der besser lesbaren Methode fort[] .

Ich hatte noch nie direkte Probleme mit dem Code, der von diesen Leuten geschrieben wurde, aber ich bin bis heute der festen Überzeugung, dass Risiken - so gering sie auch sein mögen - nicht eingegangen werden sollten, wenn sie leicht vermieden werden können.

Verwenden Sie in Fällen, in denen es sich um Kartenwerte handelt, die unbedingt nicht überschrieben werden dürfen insert. Machen Sie keine Ausnahmen nur zur besseren Lesbarkeit.

dk123
quelle
Mehrere verschiedene Leute haben das geschrieben? Sicherlich verwendet insert(nicht input), da die const_castalle vorherigen Wert verursacht überschrieben werden, was sehr nicht-const. Oder markieren Sie den Werttyp nicht als const. (So ​​etwas ist normalerweise das ultimative Ergebnis von const_cast, daher ist es fast immer eine rote Fahne, die auf einen Fehler an einer anderen Stelle hinweist.)
Potatoswatter
@ Potatoswatter Du hast recht. Ich sehe nur, dass const_cast [] von einigen Leuten mit const-Map-Werten verwendet wird, wenn sie sicher sind, dass sie in bestimmten Codebits keinen alten Wert ersetzen werden. da [] selbst besser lesbar ist. Wie ich im letzten Teil meiner Antwort erwähnt habe, würde ich die Verwendung insertin Fällen empfehlen, in denen Sie verhindern möchten, dass Werte überschrieben werden. (Gerade geändert, inputum insert- danke)
dk123
@Potatoswatter Wenn ich mich richtig erinnere, waren die Hauptgründe, die die Leute zu verwenden scheinen, const_cast<T>(map[key])1. [] ist besser lesbar, 2. sie vertrauen auf bestimmte Codebits, sie überschreiben keine Werte und 3. sie tun es nicht Ich möchte, dass andere Teile unwissenden Codes ihre Werte überschreiben - daher die const value.
dk123
2
Ich habe noch nie davon gehört. wo hast du das gesehen Das Schreiben const_castscheint die zusätzliche "Lesbarkeit" von mehr als zu negieren [], und diese Art von Vertrauen ist fast Grund genug, einen Entwickler zu entlassen. Schwierige Laufzeitbedingungen werden durch kugelsichere Designs gelöst, nicht durch Bauchgefühle.
Potatoswatter
@Potatoswatter Ich erinnere mich, dass es während eines meiner früheren Jobs bei der Entwicklung von Lernspielen war. Ich könnte die Leute, die den Code schreiben, niemals dazu bringen, ihre Gewohnheiten zu ändern. Sie haben absolut Recht und ich stimme Ihnen voll und ganz zu. Aufgrund Ihrer Kommentare habe ich entschieden, dass dies wahrscheinlich mehr erwähnenswert ist als meine ursprüngliche Antwort, und daher habe ich es aktualisiert, um dies widerzuspiegeln. Vielen Dank!
dk123
1

Die Tatsache, dass die insert()Funktion std :: map den mit dem Schlüssel verknüpften Wert nicht überschreibt, ermöglicht es uns, Objektaufzählungscode wie folgt zu schreiben:

string word;
map<string, size_t> dict;
while(getline(cin, word)) {
    dict.insert(make_pair(word, dict.size()));
}

Es ist ein ziemlich häufiges Problem, wenn wir einige nicht eindeutige Objekte einigen IDs im Bereich 0..N zuordnen müssen. Diese IDs können später beispielsweise in Diagrammalgorithmen verwendet werden. Alternative mit operator[]würde meiner Meinung nach weniger lesbar aussehen:

string word;
map<string, size_t> dict;
while(getline(cin, word)) {
    size_t sz = dict.size();
    if (!dict.count(word))
        dict[word] = sz; 
} 
Mechatroner
quelle