Czy C++ ma uporządkowane hash?

Question

Perl ma strukturę o nazwie "zamówione hash"Tie::IxHash. Można go użyć jako hashtable/map. Wpisy są w kolejności wstawiania.

Zastanawiam się, czy jest coś takiego w C++.

Oto przykład Perl urywek:

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

Jako @ kerrek-sb wskazał, można użyć Zwiększ Multi-index Kontenery Library. Zastanów się tylko, czy można to zrobić za pomocą STL.

Answer 1

Tak i nie. Nie, nie ma nikogo, kto specjalnie chciałby zapewnić dokładnie taką samą funkcjonalność. Ale tak, możesz zrobić to samo na kilka różnych sposobów. Jeśli oczekujesz, aby uzyskać dostęp do danych przede wszystkim w celu wstawiony, to oczywistym sposobem, aby przejść byłby prosty wektor par:

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

ta zachowuje porządek po prostu przechowywanie przedmiotów w porządku. Jeśli chcesz uzyskać do nich dostęp za pomocą klucza, możesz użyć wyszukiwania std::find, aby wykonać liniowe wyszukiwanie określonego elementu. To minimalizuje dodatkową pamięć używaną, kosztem powolnego dostępu klawiszem, jeśli dostajesz dużo przedmiotów.

Jeśli chcesz mieć szybszy dostęp za pomocą klawisza z dużą liczbą elementów, możesz użyć wielokrotnego indeksu doładowania. Jeśli naprawdę chcesz tego uniknąć, możesz łatwo utworzyć własny indeks. Aby to zrobić, zacznij od wstawienia swoich elementów do std::unordered_map (lub może std::map). Zapewnia to szybki dostęp za pomocą klucza, ale brak dostępu w zamówieniu reklamowym. Zwraca jednak iterator do każdego elementu włożonego do mapy. Możesz po prostu zapisać te iteratory w wektorze, aby uzyskać dostęp w kolejności wstawiania. Choć zasada ta jest dość prosta, kod jest nieco niezdarny na bok, aby umieścić go ładnie:

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

Umożliwia dostęp poprzez klucz:

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

...lub w celu wstawienia:

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

na chwilę, ja pokazano podstawowy mechanizm ten sposób - jeśli chcesz go używać dużo, to prawdopodobnie chcesz, aby owinąć że się w ładnym do klasy ukryj trochę brzydoty i utrzymuj rzeczy ładne i czyste w normalnym użytkowaniu.

Answer 2

Zbiornik asocjacyjny, który zapamiętuje zamówienie na umieszczenie, nie jest dostarczany z biblioteką standardową C++, ale można go łatwo wdrożyć przy użyciu istniejących kontenerów STL.

Na przykład kombinacja std::map (do szybkiego wyszukiwania) i std::list (w celu zachowania porządku klawiszy) może być użyta do emulowania mapy zamówionej w trybie wstawiania. Oto przykład, który demonstruje pomysł:

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

Rozwój ten kod do zastąpienia drop-in za pełnoprawny pojemniku, takim jak std::map wymaga znacznego wysiłku.

Answer 3

C++ ma do tego standardowe kontenery. nieuporządkowana mapa Wygląda na to, czego szukasz:

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