CODEWITHSUNDEEP
c++sortingunordered-map
smatter
smatter

Reputation: 29178

Sorting std::unordered_map by key

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

Upvotes: 24

Views: 49315

Answers (5)

Jiancong
Jiancong

Reputation: 65

You can use vector to store your key value pairs, then sort them in vector, put them back at map at last.

#include <iostream>                                 
#include <unordered_map>                                 
#include <algorithm>                                 
#include <vector>                                 

using namespace std;                                

int main(){                                
    unordered_map<string, int> sdict = {{"hello", 11 }, {"world", 52}, {"tommy", 3}};               
    unordered_map<string, int> resdict;          

    vector<pair<string, int>> tmp;
    for (auto& i : sdict)                                         
        tmp.push_back(i);                                

    for (auto& i : sdict)       
        cout <<  i.first << " => " << i.second << endl;  

    // sort with descending order.
    sort(tmp.begin(), tmp.end(),                                   
    [&](pair<string, int>& a, pair<string, int>& b) { return a.second < b.second; });

    for (auto& i : tmp)                          
    {                           
        resdict[i.first] = i.second;                   
    }                                

    cout << "After sort." << endl;   
    for (auto& i : resdict)     
        cout <<  i.first << " => " << i.second << endl;           
    return 0;                                              

}

Compile with following commands.

g++ --std=c++11 test_sort_ordered_map.cpp

The result is:

tommy => 3
hello => 11
world => 52
After sort.
world => 52
hello => 11
tommy => 3

Upvotes: 0

AhLeung
AhLeung

Reputation: 207

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] << ' ';
}

Upvotes: 3

David Hammen
David Hammen

Reputation: 33116

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] << ' ';
}

Upvotes: 31

Xeo
Xeo

Reputation: 131789

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));
}

Upvotes: 14

ronag
ronag

Reputation: 51255

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;

Upvotes: 43

Related Questions