How to get median value in unordered map?

Question

I am trying to write a sorting algorithm for the following unordered map. I have seen this question and I am trying to implement it for an unordered map, but it is not working!

Note- I am not allowed to use any STL sort functions.

void quickSort(unordered_map<string, int> map, unordered_map<string, int>::iterator left,unordered_map<string, int>::iterator right) {

    unordered_map<string, int>::iterator i=left;
    unordered_map<string, int>::iterator j=right;
    unordered_map<string, int>::iterator pivot = std::advance(map.begin(), map.size() / 2);

    unordered_map<string, int> tmp;
}

int main(){
    unordered_map<string, int> map;
    map["blah"] = 2;
    map["the"] = 5;
    quickSort(map,map.begin(),map.end());
}

You **cannot** sort an `unordered_map` in-place. You need to transfer the values to a different container (e.g. a `vector`). — Konrad Rudolph, Sep 08 '14 at 10:41
Just out of curiosity: Why are you not allowed to use `std::sort()` at all? Is this some kind of homework? — TobiMcNamobi, Sep 08 '14 at 10:44
@TobiMcNamobi I want to create my own sorting algorithm and then optimize it — Bernard, Sep 08 '14 at 10:47
@Bernard The reason is that an `unordered_map` is *unordered*. If you want details, look at some references/implementations. Basically, it uses hashing, which makes it impossible to tinker the internal storage. — Nelfeal, Sep 08 '14 at 10:49
@TobiMcNamobi you do not need to perform a full sort to find the median — Ivaylo Strandjev, Sep 08 '14 at 10:52

score 2 · Answer 1 · answered Sep 08 '14 at 10:52

2

An unordered map does not have order(as its name implies) and thus finding the median in an unordered map does not make sense. If you need to find the median - use a auxiliary array and perform some implementation of nth_element algorithm in it. This step would be with linear complexity.

answered Sep 08 '14 at 10:52

Ivaylo Strandjev

69,226
18
123
176

@Bernard you can not write a sort function for unordered map as this will make it no longer be **unordered**. – Ivaylo Strandjev Sep 08 '14 at 10:54

Baum mit Augen · Accepted Answer · 2014-09-08T13:37:40.990

As stated in the comments, you cannot sort a unordered_map in place because its value_type is std::pair<const Key, T> (note the const!) for an unordered_map<Key,T>. This means that you cannot swap elements in the map, so you cannot sort it. You will need to copy the data into another data-structure like a vector, then you can use some "home-grown" version of std::nth_element on it:

std::vector<std::pair<Key,T>> med {map.begin(), map.end()};
my_nth_element(med.begin(), med.end(), med.begin() + med.size() / 2);
auto median = med[med.size()/2];

You should implement your nth_element with linear complexity on average. (If the number of input values happens to be even, you need to use the mean of both middle-values.)

How to get median value in unordered map?

2 Answers2