C ++ ordered a hash?

Question

Perl has a structure called the "ordered hash" of Tie::IxHash . It can be used as a hash table / map. Entries are in insertion order.

I wonder if there is such a thing in C ++.

Here is an example Perl snippet:

 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

As pointed out by @ kerrek-sb, you can use the Boost Multi-index Containers container library. Just wondering if this can be done with STL.

Answer 1

Yes and no. No, there is no one specifically designed to provide exactly the same functionality. But yes, you can do the same in several ways. If you expect to access the data in the first place in the entered order, then the obvious way to go is a simple vector of pairs:

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

This keeps order, just keeping items in order. If you need to access them by key, you can use std::find to linearly search for a specific element. This minimizes the use of additional memory due to slow key access if you receive a lot of items.

If you need faster key access with more elements, you can use Boost MultiIndex. If you really want to avoid this, you can easily create your own index. To do this, start by entering your elements in std::unordered_map (or perhaps std::map ). This gives quick access by key, but without access in the input order. However, it returns an iterator for each element as it is inserted into the map. You can simply save these iterators to a vector to access in insertion order. Although the principle of this is quite simple, the code is a bit on the clumsy side, so that is nice:

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

This allows you to access either by key:

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

... or in the order of entry:

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

At the moment, I have shown the basic mechanism for this - if you want to use it a lot, you probably want to wrap it in a class to hide some ugliness and keep things pretty and clean under normal use.

Answer 2

An associative container that remembers the insertion order is not part of the C ++ standard library, but it can be implemented using existing STL containers.

For example, to emulate ordered map inserts, you can use a combination of std::map (for quick searches) and std::list (to maintain the order of the keys). Here is an example demonstrating the idea:

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

Developing this code as a replacement for a full container, such as std::map , requires considerable effort.

Answer 3

C ++ has standard containers for this. An unordered map looks like you are looking for:

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