Eine std :: map, die die Einfügereihenfolge verfolgt?

113

Ich habe derzeit eine std::map<std::string,int>, die einen ganzzahligen Wert in einer eindeutigen Zeichenfolgenkennung speichert, und ich schaue mit der Zeichenfolge nach. Es macht meistens das, was ich will, außer dass es die Einfügereihenfolge nicht verfolgt. Wenn ich also die Karte iteriere, um die Werte auszudrucken, werden sie nach der Zeichenfolge sortiert. aber ich möchte, dass sie nach der Reihenfolge der (ersten) Einfügung sortiert werden.

Ich habe darüber nachgedacht, vector<pair<string,int>>stattdessen a zu verwenden, aber ich muss die Zeichenfolge nachschlagen und die Ganzzahlwerte etwa 10.000.000 Mal erhöhen, damit ich nicht weiß, ob a std::vectorsignifikant langsamer ist.

Gibt es eine Möglichkeit zur Verwendung std::mapoder gibt es einen anderen stdBehälter, der meinen Anforderungen besser entspricht?

[Ich bin auf GCC 3.4 und habe wahrscheinlich nicht mehr als 50 Wertepaare in meinem std::map].

Vielen Dank.

mehrsprachig
quelle
8
Ein Teil der schnellen Suchzeit für std :: map hat damit zu tun, dass es in der richtigen Reihenfolge sortiert ist, sodass es eine binäre Suche durchführen kann. Ich kann deinen Kuchen einfach nicht haben und ihn auch essen!
Bobobobo
1
Was hast du damals benutzt?
Aggsol

Antworten:

56

Wenn Sie nur 50 Werte in std :: map haben, können Sie diese vor dem Ausdrucken in std :: vector kopieren und mit dem entsprechenden Funktor über std :: sort sortieren.

Oder Sie könnten boost :: multi_index verwenden . Es können mehrere Indizes verwendet werden. In Ihrem Fall könnte es folgendermaßen aussehen:

struct value_t {
      string s;
      int    i;
};
struct string_tag {};
typedef multi_index_container<
    value_t,
    indexed_by<
        random_access<>, // this index represents insertion order
        hashed_unique< tag<string_tag>, member<value_t, string, &value_t::s> >
    >
> values_t;
Kirill V. Lyadvinsky
quelle
Das ist großartig! Boost hat sogar einen Mitglieder-Selektor, der die Arbeit erledigt!
xtofl
2
Ja, multi_index ist mein Lieblingsfeature in Boost :)
Kirill V. Lyadvinsky
3
@Kristo: Es geht nicht um die Containergröße, sondern darum, die vorhandene Implementierung für genau dieses Problem wiederzuverwenden. Das ist edel. Zugegeben, C ++ ist keine funktionale Sprache, daher ist die Syntax etwas ausgefeilt.
xtofl
4
Seit wann geht es beim Programmieren um das Speichern von Tastenanschlägen?
GManNickG
1
Vielen Dank für die Veröffentlichung. Gibt es ein Buch "Boost Multi-Index für Dummies"? Ich könnte es benutzen ...
Don Bright
25

Sie können a std::vectormit a std::tr1::unordered_map(einer Hash-Tabelle) kombinieren . Hier ist ein Link zur Dokumentation von Boost für unordered_map. Sie können den Vektor verwenden, um die Einfügereihenfolge zu verfolgen, und die Hash-Tabelle, um die häufigen Suchvorgänge durchzuführen. Wenn Sie Hunderttausende von Suchvorgängen durchführen, kann der Unterschied zwischen der Suche nach O (log n) std::mapund O (1) für eine Hash-Tabelle erheblich sein.

std::vector<std::string> insertOrder;
std::tr1::unordered_map<std::string, long> myTable;

// Initialize the hash table and record insert order.
myTable["foo"] = 0;
insertOrder.push_back("foo");
myTable["bar"] = 0;
insertOrder.push_back("bar");
myTable["baz"] = 0;
insertOrder.push_back("baz");

/* Increment things in myTable 100000 times */

// Print the final results.
for (int i = 0; i < insertOrder.size(); ++i)
{
    const std::string &s = insertOrder[i];
    std::cout << s << ' ' << myTable[s] << '\n';
}
Michael Kristofik
quelle
4
@xtofl, Wie macht das meine Antwort nicht hilfreich und verdient daher eine Abwertung? Ist mein Code in irgendeiner Weise falsch?
Michael Kristofik
Dies ist der beste Weg, dies zu tun. Sehr günstige Speicherkosten (für nur 50 Zeichenfolgen!), Ermöglichen std::mapdas Arbeiten wie vorgesehen (dh durch Sortieren beim Einfügen selbst) und schnelle Laufzeit. (Ich habe dies gelesen, nachdem ich meine Version geschrieben habe, in der ich std :: list verwendet habe!)
bobobobo
Ich denke, std :: vector oder std :: list ist Geschmackssache und nicht klar, was besser ist. (Vektor hat wahlfreien Zugriff, der nicht benötigt wird, hat auch zusammenhängenden Speicher, der auch nicht benötigt wird. List speichert die Reihenfolge ohne die Kosten einer dieser beiden Funktionen, z. B. Neuzuweisungen während des Wachstums).
Oliver Schönrock
14

Halten Sie eine Parallele list<string> insertionOrder.

Wenn es Zeit zum Drucken ist, iterieren Sie in der Liste und suchen Sie in der Karte .

each element in insertionOrder  // walks in insertionOrder..
    print map[ element ].second // but lookup is in map
Bobobobo
quelle
1
Dies war auch mein erster Gedanke, aber er dupliziert die Schlüssel in einem zweiten Container, oder? Im Falle eines std :: string-Schlüssels, der nicht brillant ist, oder?
Oliver Schönrock
2
@OliverSchonrock Ab C ++ 17 können Sie std::string_viewfür die Kartenschlüssel die std::stringin der insertionOrderListe angegebenen Schlüssel verwenden . Dies vermeidet das Kopieren, aber Sie müssen darauf achten, dass die insertionOrderElemente die Schlüssel in der Karte, die auf sie verweisen, überleben.
flyx
Am Ende schrieb ich einen Container, in dem Karte und Liste in einem integriert waren: codereview.stackexchange.com/questions/233177/… Keine Vervielfältigung
Oliver Schönrock
10

Tessil hat eine sehr schöne Implementierung der bestellten Karte (und des bestellten Sets), bei der es sich um eine MIT-Lizenz handelt. Sie finden es hier: bestellte-Karte

Kartenbeispiel

#include <iostream>
#include <string>
#include <cstdlib>
#include "ordered_map.h"

int main() {
tsl::ordered_map<char, int> map = {{'d', 1}, {'a', 2}, {'g', 3}};
map.insert({'b', 4});
map['h'] = 5;
map['e'] = 6;

map.erase('a');


// {d, 1} {g, 3} {b, 4} {h, 5} {e, 6}
for(const auto& key_value : map) {
    std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}


map.unordered_erase('b');

// Break order: {d, 1} {g, 3} {e, 6} {h, 5}
for(const auto& key_value : map) {
    std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}
}
aggsol
quelle
4

Wenn Sie beide Suchstrategien benötigen, erhalten Sie zwei Container. Sie können a vectormit Ihren tatsächlichen Werten verwenden intund ein map< string, vector< T >::difference_type> daneben setzen , um den Index in den Vektor zurückzugeben.

Um dies alles zu vervollständigen, können Sie beide in einer Klasse zusammenfassen.

Aber ich glaube, Boost hat einen Container mit mehreren Indizes.

xtofl
quelle
3

Was Sie wollen (ohne auf Boost zurückzugreifen), ist das, was ich als "geordneten Hash" bezeichne. Dies ist im Wesentlichen ein Mashup aus einem Hash und einer verknüpften Liste mit Zeichenfolgen- oder Ganzzahlschlüsseln (oder beiden gleichzeitig). Ein geordneter Hash behält die Reihenfolge der Elemente während der Iteration mit der absoluten Leistung eines Hash bei.

Ich habe eine relativ neue C ++ - Snippet-Bibliothek zusammengestellt, die die Lücken in der C ++ - Sprache für C ++ - Bibliotheksentwickler ausfüllt. Gehe hier hin:

https://github.com/cubiclesoft/cross-platform-cpp

Greifen:

templates/detachable_ordered_hash.cpp
templates/detachable_ordered_hash.h
templates/detachable_ordered_hash_util.h

Wenn benutzergesteuerte Daten in den Hash eingefügt werden, möchten Sie möglicherweise auch:

security/security_csprng.cpp
security/security_csprng.h

Rufen Sie es auf:

#include "templates/detachable_ordered_hash.h"
...
// The 47 is the nearest prime to a power of two
// that is close to your data size.
//
// If your brain hurts, just use the lookup table
// in 'detachable_ordered_hash.cpp'.
//
// If you don't care about some minimal memory thrashing,
// just use a value of 3.  It'll auto-resize itself.
int y;
CubicleSoft::OrderedHash<int> TempHash(47);
// If you need a secure hash (many hashes are vulnerable
// to DoS attacks), pass in two randomly selected 64-bit
// integer keys.  Construct with CSPRNG.
// CubicleSoft::OrderedHash<int> TempHash(47, Key1, Key2);
CubicleSoft::OrderedHashNode<int> *Node;
...
// Push() for string keys takes a pointer to the string,
// its length, and the value to store.  The new node is
// pushed onto the end of the linked list and wherever it
// goes in the hash.
y = 80;
TempHash.Push("key1", 5, y++);
TempHash.Push("key22", 6, y++);
TempHash.Push("key3", 5, y++);
// Adding an integer key into the same hash just for kicks.
TempHash.Push(12345, y++);
...
// Finding a node and modifying its value.
Node = TempHash.Find("key1", 5);
Node->Value = y++;
...
Node = TempHash.FirstList();
while (Node != NULL)
{
  if (Node->GetStrKey())  printf("%s => %d\n", Node->GetStrKey(), Node->Value);
  else  printf("%d => %d\n", (int)Node->GetIntKey(), Node->Value);

  Node = Node->NextList();
}

Ich bin während meiner Recherchephase auf diesen SO-Thread gestoßen, um zu sehen, ob es so etwas wie OrderedHash bereits gibt, ohne dass ich in eine riesige Bibliothek gehen muss. Ich war enttäuscht. Also habe ich meine eigenen geschrieben. Und jetzt habe ich es geteilt.

CubicleSoft
quelle
2

Sie können dies nicht mit einer Karte tun, aber Sie können zwei separate Strukturen verwenden - die Karte und den Vektor, und sie synchronisieren - das heißt, wenn Sie aus der Karte löschen, das Element suchen und aus dem Vektor löschen. Oder Sie können ein map<string, pair<int,int>>- erstellen und in Ihrem Paar die Größe () der Karte beim Einfügen speichern, um die Position zusammen mit dem Wert des int aufzuzeichnen, und dann beim Drucken das Positionselement zum Sortieren verwenden.

Faisal Vali
quelle
2

Eine andere Möglichkeit, dies zu implementieren, ist mit a mapanstelle von a vector. Ich werde Ihnen diesen Ansatz zeigen und die Unterschiede diskutieren:

Erstellen Sie einfach eine Klasse mit zwei Karten hinter den Kulissen.

#include <map>
#include <string>

using namespace std;

class SpecialMap {
  // usual stuff...

 private:
  int counter_;
  map<int, string> insertion_order_;
  map<string, int> data_;
};

Sie können dann einen Iterator data_in der richtigen Reihenfolge dem Iterator aussetzen . Die Art insertion_order_und Weise, wie Sie dies tun, wird durchlaufen , und für jedes Element, das Sie aus dieser Iteration erhalten, führen Sie eine Suche in der data_mit dem Wert von durchinsertion_order_

Sie können das effizientere hash_mapfür insertion_order verwenden, da es Ihnen nicht wichtig ist, direkt durchzugehen insertion_order_.

Zum Einfügen können Sie eine Methode wie die folgende verwenden:

void SpecialMap::Insert(const string& key, int value) {
  // This may be an over simplification... You ought to check
  // if you are overwriting a value in data_ so that you can update
  // insertion_order_ accordingly
  insertion_order_[counter_++] = key;
  data_[key] = value;
}

Es gibt viele Möglichkeiten, wie Sie das Design verbessern und sich um die Leistung sorgen können. Dies ist jedoch ein gutes Grundgerüst, um diese Funktionalität selbst zu implementieren. Sie können es als Vorlage erstellen und Paare tatsächlich als Werte in data_ speichern, damit Sie leicht auf den Eintrag in insertion_order_ verweisen können. Aber ich lasse diese Designprobleme als Übung :-).

Update : Ich denke, ich sollte etwas über die Effizienz der Verwendung von map vs. vector für insertion_order_ sagen

  • sucht direkt in Daten, in beiden Fällen sind O (1)
  • Einfügungen im Vektoransatz sind O (1), Einfügungen im Kartenansatz sind O (logn)
  • Löschungen im Vektoransatz sind O (n), da Sie nach dem zu entfernenden Element suchen müssen. Beim Kartenansatz sind sie O (logn).

Wenn Sie weniger Löschvorgänge verwenden möchten, sollten Sie möglicherweise den Vektoransatz verwenden. Der Kartenansatz wäre besser, wenn Sie eine andere Reihenfolge (wie Priorität) anstelle der Einfügereihenfolge unterstützen würden.

Tom
quelle
Der Kartenansatz ist auch besser, wenn Sie Elemente über die "Einfüge-ID" abrufen müssen. Wenn Sie beispielsweise das Element einfügen möchten, das als 5. eingefügt wurde, suchen Sie in insert_order mit der Taste 5 (oder 4, je nachdem, wo Sie counter_ starten). Wenn beim Vektoransatz das 5. Element gelöscht wurde, erhalten Sie tatsächlich das 6. Element, das eingefügt wurde.
Tom
2

Hier ist eine Lösung, die nur eine Standardvorlagenbibliothek erfordert, ohne den Multiindex von boost zu verwenden:
Sie können verwenden std::map<std::string,int>;und vector <data>;wo in der Karte Sie den Index der Position von Daten in Vektoren speichern und Vektor speichert Daten in Einfügereihenfolge. Hier hat der Zugriff auf Daten eine O (log n) -Komplexität. Das Anzeigen von Daten in Einfügereihenfolge hat eine O (n) -Komplexität. Das Einfügen von Daten hat eine O (log n) -Komplexität.

Beispielsweise:

#include<iostream>
#include<map>
#include<vector>

struct data{
int value;
std::string s;
}

typedef std::map<std::string,int> MapIndex;//this map stores the index of data stored 
                                           //in VectorData mapped to a string              
typedef std::vector<data> VectorData;//stores the data in insertion order

void display_data_according_insertion_order(VectorData vectorData){
    for(std::vector<data>::iterator it=vectorData.begin();it!=vectorData.end();it++){
        std::cout<<it->value<<it->s<<std::endl;
    }
}
int lookup_string(std::string s,MapIndex mapIndex){
    std::MapIndex::iterator pt=mapIndex.find(s)
    if (pt!=mapIndex.end())return it->second;
    else return -1;//it signifies that key does not exist in map
}
int insert_value(data d,mapIndex,vectorData){
    if(mapIndex.find(d.s)==mapIndex.end()){
        mapIndex.insert(std::make_pair(d.s,vectorData.size()));//as the data is to be
                                                               //inserted at back 
                                                               //therefore index is
                                                               //size of vector before
                                                               //insertion
        vectorData.push_back(d);
        return 1;
    }
    else return 0;//it signifies that insertion of data is failed due to the presence
                  //string in the map and map stores unique keys
}
Himanshu Pandey
quelle
1

Dies hängt etwas mit der Antwort von Faisals zusammen. Sie können einfach eine Wrapper-Klasse um eine Karte und einen Vektor erstellen und diese einfach synchronisieren. Durch die richtige Kapselung können Sie die Zugriffsmethode und damit den zu verwendenden Container steuern ... den Vektor oder die Karte. Dadurch wird die Verwendung von Boost oder Ähnlichem vermieden.

Polaris878
quelle
1

Eine Sache, die Sie berücksichtigen müssen, ist die geringe Anzahl von Datenelementen, die Sie verwenden. Es ist möglich, dass es schneller ist, nur den Vektor zu verwenden. Die Karte enthält einen gewissen Overhead, der dazu führen kann, dass die Suche in kleinen Datenmengen teurer ist als der einfachere Vektor. Wenn Sie also wissen, dass Sie immer ungefähr die gleiche Anzahl von Elementen verwenden, führen Sie ein Benchmarking durch und prüfen Sie, ob die Leistung der Karte und des Vektors so ist, wie Sie es wirklich glauben. Möglicherweise befindet sich die Suche in einem Vektor mit nur 50 Elementen in der Nähe der Karte.

Chad Simpkins
quelle
1

// Sollte wie dieser Mann sein!

// Dadurch bleibt die Komplexität des Einfügens O (logN) und das Löschen ist auch O (logN).

class SpecialMap {
private:
  int counter_;
  map<int, string> insertion_order_;
  map<string, int> insertion_order_reverse_look_up; // <- for fast delete
  map<string, Data> data_;
};
Ka Yan
quelle
0

Verwendung boost::multi_indexmit Karten- und Listenindizes.

Vladimir Voznesensky
quelle
-1

Eine Zuordnung von Paaren (str, int) und statischen int, die beim Einfügen inkrementiert wird, indiziert Datenpaare. Fügen Sie eine Struktur ein, die den statischen Wert mit einem index () -Mitglied zurückgeben kann.

Mike
quelle
2
Sie sollten ein Beispiel hinzufügen.
m02ph3u5