Hat C++ Hash bestellt?

Question

Perl hat eine Struktur namens "geordneten Hash"Tie::IxHash. Man kann es als Hashtable/Map verwenden. Die Einträge sind in der Reihenfolge der Einfügung.

Frage mich, ob es so etwas in C++ gibt.

Hier ein Beispiel Perl-Schnipsel:

use Tie::IxHash; 

tie %food_color, "Tie::IxHash"; 
$food_color{Banana} = "Yellow"; 
$food_color{Apple} = "Green"; 
$food_color{Lemon} = "Yellow"; 

print "In insertion order, the foods are:\n"; 
foreach $food (keys %food_color) { 
    print " $food\n"; #will print the entries in order 
} 

Update 1

Wie @ kerrek-sb wies darauf hin, kann man Multi-Index Container-Bibliothek Erhöhung verwenden. Frage mich nur, ob es mit STL möglich ist.

Answer 1

Ja und nein. Nein, es gibt niemanden, der genau die gleiche Funktionalität bieten soll. Aber ja, Sie können das Gleiche auf verschiedene Arten tun. Wenn Sie die Daten in erster Linie in der Reihenfolge eingefügt Zugang erwarten, dann ist der offensichtliche Weg zu gehen, wäre eine einfache Vektor von Paaren sein:

std::vector<std::string, std::string> food_colors; 

food_colors.push_back({"banana", "yellow"}); 
food_colors.push_back({"apple", "green"}); 
food_colors.push_back({"lemon", "yellow"}); 

for (auto const &f : food_colors) 
    std::cout << f.first << ": " << f.second << "\n"; 

Der Bestellung bewahrt, indem einfach die Elemente, um zu speichern. Wenn Sie mit einem Schlüssel darauf zugreifen möchten, können Sie std::find verwenden, um eine lineare Suche nach einem bestimmten Objekt durchzuführen. Das minimiert den zusätzlichen Speicherverbrauch auf Kosten des langsamen Zugriffs durch den Schlüssel, wenn Sie viele Elemente erhalten.

Wenn Sie einen schnelleren Zugriff mit einer großen Anzahl von Elementen wünschen, können Sie einen Boost MultiIndex verwenden. Wenn Sie das wirklich vermeiden wollen, können Sie ganz einfach einen eigenen Index erstellen. Um dies zu tun, würden Sie beginnen, indem Sie Ihre Artikel in eine std::unordered_map (oder vielleicht eine std::map) einfügen. Dies ermöglicht einen schnellen Zugriff per Schlüssel, aber keinen Zugriff in der Reihenfolge der Anzeigen. Es gibt jedoch einen Iterator für jedes Element zurück, wenn es in die Map eingefügt wird. Sie können diese Iteratoren einfach in einem Vektor speichern, um Zugriff in der Reihenfolge des Einfügens zu erhalten. Obwohl das Prinzip der dies recht einfach ist, zu der Code ist ein bisschen auf der ungeschickte Seite, legte es schön:

std::map<std::string, std::string> fruit; 
std::vector<std::map<std::string, std::string>::iterator> in_order; 

in_order.push_back(fruit.insert(std::make_pair("banana", "yellow")).first); 
in_order.push_back(fruit.insert(std::make_pair("apple", "green")).first); 
in_order.push_back(fruit.insert(std::make_pair("lemon", "yellow")).first); 

Dieser Zugang ermöglicht entweder durch Schlüssel:

// ripen the apple: 
fruit["apple"] = "red"; 

...oder in Auftrag:

for (auto i : in_order) 
    std::cout << i->first << ": " << i->second << "\n"; 

Im Moment habe ich den grundlegenden Mechanismus gezeigt, dies zu tun - wenn Sie es verwenden viel wollte, dann würden Sie wahrscheinlich, dass wickeln wollen in eine schöne Klasse bis zu Verstecken Sie etwas von der Hässlichkeit und die Dinge halten schön und sauber im normalen Gebrauch.

Answer 2

Ein assoziativer Container, der die Reihenfolge der Insertion merkt, gehört nicht zur C++ - Standardbibliothek, aber es ist einfach, eine mit vorhandenen STL-Containern zu implementieren.

Zum Beispiel kann eine Kombination aus std::map (für schnelles Nachschlagen) und std::list (um die Reihenfolge der Schlüssel zu verwalten) verwendet werden, um eine Karte mit eingefügter Reihenfolge zu emulieren. Hier ist ein Beispiel, das die Idee demonstriert:

#include <unordered_map> 
#include <list> 
#include <stdexcept> 

template<typename K, typename V> 
class InsOrderMap { 
    struct value_pos { 
    V value; 
    typename std::list<K>::iterator pos_iter; 
    value_pos(V value, typename std::list<K>::iterator pos_iter): 
     value(value), pos_iter(pos_iter) {} 
    }; 

    std::list<K> order; 
    std::unordered_map<K, value_pos> map; 

    const value_pos& locate(K key) const { 
    auto iter = map.find(key); 
    if (iter == map.end()) 
     throw std::out_of_range("key not found"); 
    return iter->second; 
    } 

public: 
    void set(K key, V value) { 
    auto iter = map.find(key); 
    if (iter != map.end()) { 
     // no order change, just update value 
     iter->second.value = value; 
     return; 
    } 
    order.push_back(key); 
    map.insert(std::make_pair(key, value_pos(value, --order.end()))); 
    } 

    void erase(K key) { 
    order.erase(locate(key).pos_iter); 
    map.erase(key); 
    } 

    V operator[](K key) const { 
    return locate(key).value; 
    } 

    // iterate over the mapping with a function object 
    // (writing a real iterator is too much code for this example) 
    template<typename F> 
    void walk(F fn) const { 
    for (auto key: order) 
     fn(key, (*this)[key]); 
    } 
}; 

// TEST 

#include <string> 
#include <iostream> 
#include <cassert> 

int main() 
{ 
    typedef InsOrderMap<std::string, std::string> IxHash; 

    IxHash food_color; 
    food_color.set("Banana", "Yellow"); 
    food_color.set("Apple", "Green"); 
    food_color.set("Lemon", "Yellow"); 

    assert(food_color["Banana"] == std::string("Yellow")); 
    assert(food_color["Apple"] == std::string("Green")); 
    assert(food_color["Lemon"] == std::string("Yellow")); 

    auto print = [](std::string k, std::string v) { 
    std::cout << k << ' ' << v << std::endl; 
    }; 
    food_color.walk(print); 
    food_color.erase("Apple"); 
    std::cout << "-- without apple" << std::endl; 
    food_color.walk(print); 
    return 0; 
} 

Entwicklung dieses Code in einen Drop-in-Ersatz für einen vollwertigen Container wie std::map erheblichen Aufwand erfordert.

Answer 3

C++ hat dafür Standardcontainer. Eine ungeordnete Karte scheint wie das, was Sie suchen:

std::unordered_map <std::string, std::string> mymap = {{"Banana", "Yellow" }, {"Orange","orange" } }