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.

Answer 2

An associative container that remembers insertion order does not come with the C++ standard library, but it is straightforward to implement one using existing STL containers.

For example, a combination of std::map (for fast lookup) and std::list (to maintain key ordering) can be used to emulate an insertion-ordered map. Here is an example that demonstrates 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 into a drop-in replacement for a full-fledged container such as std::map requires considerable effort.

Answer 3

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

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