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?

*"What data structure do I then use when I want the keys to be ordered in the same way as the initializer list?"* Probably one without `unordered` in the name. ;-) — Kos, Mar 05 '14 at 16:03
Well, I'm allready using `unordered_map`, and it's hash function still re-arranges the keys. — tmaric, Mar 05 '14 at 16:04
@graham.reeds, no since the keys are sorted using string comparison in this case. — tmaric, Mar 05 '14 at 16:06
Sounds like a job for [Boost.Multiindex](http://www.boost.org/doc/libs/1_55_0/libs/multi_index/doc/index.html). A multiindex container can be accessed in multiple ways depending on the context. For example, you could mix a hashed index container (for key-based lookup) with a sequenced index container (for ordered, sequential lookup). — ComicSansMS, Mar 05 '14 at 16:11

score 5 · Accepted Answer · edited May 23 '17 at 12:28

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:

Bartek Banachewicz · Answer 2 · 2014-03-05T16:14:04.670

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.

edited Mar 05 '14 at 16:14

answered Mar 05 '14 at 16:02

Bartek Banachewicz

38,596
7
91
135

But won't map sort the keys alphabetically? This is definitely not what I want - the order should be the same as in the initializer list. – tmaric Mar 05 '14 at 16:04
@BartekBanachewicz, but then I have *linear complexity* instead of *average constant complexity* in the access of keys: whenever I call `operator["someStringName"]` I need to parse (in the worst case) all the keys to find "someStringName". – tmaric Mar 05 '14 at 16:10
@tmaric You should have probably stated that more clearly in the question. Then you'd easily find it's a duplicate. – Bartek Banachewicz Mar 05 '14 at 16:12
Banachiewicz: I don't understand your point honestly - I clearly asked for the order of the elements in the initializer list to be preserved. Key-sorting containers are immidiately not an option. Hand made containers make the element access complexity much worse. – tmaric Mar 05 '14 at 16:14

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

2 Answers2