Does C++ have ordered hash?

Question

Perl has a structure called "ordered hash" Tie::IxHash. One can use it as a hashtable/map. The entries are in the order of insertion.

Wonder if there is such a thing in C++.

Here is a sample 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 @kerrek-sb pointed out, one can use Boost Multi-index Containers Library. Just wonder if it is possible to do it with STL.

Answer 1

Yes and no. No, there's no one that that's specifically intended to provide precisely the same functionality. But yes, you can do the same in a couple of different ways. If you expect to access the data primarily in the order inserted, then the obvious way to go would be 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 preserves order by simply storing the items in order. If you need to access them by key, you can use std::find to do a linear search for a particular item. That minimizes extra memory used, at the expense of slow access by key if you get a lot of items.

If you want faster access by key with a large number of items, you could use a Boost MultiIndex. If you really want to avoid that, you can create an index of your own pretty easily. To do this, you'd start by inserting your items into a std::unordered_map (or perhaps an std::map). This gives fast access by key, but no access in insertion order. It does, however, return an iterator to each items as it's inserted into the map. You can simply store those iterators into a vector to get access in the order of insertion. Although the principle of this is fairly simple, the code is a bit on the clumsy side, to put it nicely:

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 access either by key:

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

...or in insertion order:

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

For the moment, I've shown the basic mechanism for doing this--if you wanted to use it much, you'd probably want to wrap that up into a nice class to hide some of the ugliness and the keep things pretty and clean in normal use.