Sorting std::unordered_map by key

Question

How can I sort an unordered_map by key? I need to print an unordered_map sorted by key.

Solution 1

std::unordered_map<int, int> unordered;

std::map<int, int> ordered(unordered.begin(), unordered.end());
for(auto it = ordered.begin(); it != ordered.end(); ++it)
     std::cout << it->second;

Solution 2

An alternate solution is to construct a vector of the keys, sort the vector, and print per that sorted vector. This will be considerably faster than the approaches that constructed a map from the ordered map, but will also involve more code.

std::unordered_map<KeyType, MapType> unordered;
std::vector<KeyType> keys;

keys.reserve (unordered.size());
for (auto& it : unordered) {
    keys.push_back(it.first);
}
std::sort (keys.begin(), keys.end());
for (auto& it : keys) {
    std::cout << unordered[it] << ' ';
}

Solution 3

Are you sure you need this? Because that is not possible. An unordered_map is a hash container, that is, the keys are hashed. Inside of the container, they don't have the same representation as on the outside. Even the name implies that you can't sort it. It's one of the criteria to choose a hash container: You do not need a specific order.

If you do, get a normal map. The keys are automatically sorted in a strict-weak ordering. If you need another sort, write your own comparator.

If you only need to print it sorted, the following may be inefficient, but it's as close as you'll get if you still want to keep the unordered_map.

#include <map>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <functional>

struct map_streamer{
  std::ostream& _os;

  map_streamer(std::ostream& os) : _os(os) {}

  template<class K, class V>
  void operator()(std::pair<K,V> const& val){
    // .first is your key, .second is your value
    _os << val.first << " : " << val.second << "\n";
  }
};

template<class K, class V, class Comp>
void print_sorted(std::unordered_map<K,V> const& um, Comp pred){
  std::map<K,V> m(um.begin(), um.end(), pred);
  std::for_each(m.begin(),m.end(),map_streamer(std::cout));
}

template<class K, class V>
void print_sorted(std::unordered_map<K,V> const& um){
  print_sorted(um, std::less<int>());
}

Example on Ideone.
Note that in C++0x, you can replace the two overloads with one function with a default template argument:

template<class K, class V, class Comp = std::less<int> >
void print_sorted(std::unordered_map<K,V> const& um, Comp pred = Comp()){
  std::map<K,V> m(um.begin(), um.end(), pred);
  std::for_each(m.begin(),m.end(),map_streamer(std::cout));
}

Solution 4

Similar to David's answer, we can use std::set to sort the key first:

std::unordered_map<int, int> unordered;
std::set<int> keys;
for (auto& it : unordered) keys.insert(it.first);
for (auto& it : keys) {
    std::cout << unordered[it] << ' ';
}

View more solutions

Comments

[softwarematter]

I have declared unorderedmap as std::unordered_map<int, unsigned long> *myunorderedmap; But std::map<int, unsigned long> ordered(myunorderedmap->begin, myunorderedmap->end); gives error

[ltjax]

You could use std::ostream_iterator and std::copy instead of your own streamer thingie.

[David Hammen]

begin and end are functions. Use ordered(myunorderedmap->begin(), myunorderedmap->end()) instead of what you used and all will be fine.

[Xeo]

@Itjax: On a second thought, no, because std::for_each will give me a std::pair<K,V> and I'd need to split that anyways. My first implementation didn't work for that reason, std::pair can't be streamed.

[ltjax]

It will be even faster if you use a vector and std::sort instead of a list.

[Steven Lu]

And even marginally faster still if you reserve that vector with the required length (if you must use push_back)

[ipapadop]

And don't forget, if you don't care about retaining the elements in the initial container, make_move_iterator can be used to move the elements into the new container: std::map<int, int> ordered(std::make_move_iterator(unordered.begin()), std::make_move_iterator(unordered.end()));

[Kyle]

@Steven Lu what could you use instead of push_back if you didn't care about the order, as in this example?