Why does `std::unordered_map` "speak like the Yoda" - re-arrange elements?

Question

When trying to write the std::string keys of an std::unordered_map in the following example, the keys get written in a different order than the one given by the initializer list:

#include <iostream>
#include <unordered_map>


class Data
{
    typedef std::unordered_map<std::string, double> MapType; 
    typedef MapType::const_iterator const_iterator;

    MapType map_; 

    public: 

        Data(const std::initializer_list<std::string>& i)
        {
            int counter = 0; 
            for (const auto& name : i)
            {
                map_[name] = counter; 
            }
        }


        const_iterator begin() const
        {
            return map_.begin(); 
        }

        const_iterator end() const
        {
            return map_.end(); 
        }

};

std::ostream& operator<<(std::ostream& os, const Data&  d)
{
    for (const auto& pair : d)
    {
        os << pair.first << " ";  
    }
    return os; 
}

using namespace std;

int main(int argc, const char *argv[])
{
    Data d = {"Why", "am", "I", "sorted"}; 

    // The unordered_map speaks like Yoda.
    cout << d << endl;

    return 0;
}

I expected to see 'Why am I sorted', but I got a Yoda-like output:

sorted I am Why 

Reading on the unordered_map here, I saw this:

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements, since once hash is computed, it refers to the exact bucket the element is placed into.

Is this why the elements are not ordered in the same way as in the initializer list?

What data structure do I then use when I want the keys to be ordered in the same way as the initializer list? Should I internally keep a vector of strings to somehow save the argument order? Can the bucket organization be turned off somehow by choosing a specific hashing function?

Answer 1

What data structure do I then use when I want the keys to be ordered in the same way as the initializer list? Should I internally keep a vector of strings to somehow save the argument order?

Maybe all you want is actually a list/vector of (key, value) pairs?

If you want both O(1) lookup (hashmap) and iteration in the same order as insertion - then yes, using a vector together with an unordered_map sounds like a good idea. For example, Django's SortedDict (Python) does exactly that, here's the source for inspiration:

https://github.com/django/django/blob/master/django/utils/datastructures.py#L122

Python 2.7's OrderedDict is a bit more fancy (map values point to doubly-linked list links), see:

http://code.activestate.com/recipes/576693-ordered-dictionary-for-py24/

---

I'm not aware of an existing C++ implementation in standard libs, but this might get you somewhere. See also:

• a C++ hash map that preserves the order of insertion
• A std::map that keep track of the order of insertion?

Answer 2

unordered_map is, by definition, unordered, so you shall not expect any ordering when accessing the map sequentially.

If you don't want elements sorted by the key value, just use a container that keeps your order of insertion, be it a vector, deque, list or whatever, of pair<key, value> element type if you insist on using it.

Then, if an alement B is added after element A, it will always appear later. This holds true for initializer_list initialization as well.

You could probably use something like Boost.MultiIndex to keep it both sorted by insertion order and arbitrary key.