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

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.

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;

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

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

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

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.

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.

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.

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.

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
}

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.

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.

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

Verwendung boost::multi_indexmit Karten- und Listenindizes.

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.