Как получить медианное значение на неупорядоченной карте?

Question

Я пытаюсь написать алгоритм сортировки для следующей неупорядоченной карты. Я видел this вопрос, и я пытаюсь реализовать его для неупорядоченной карты, но она не работает!

Примечание. Мне не разрешено использовать какие-либо функции сортировки STL.

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

Answer 1

Как указано в комментариях, вы не можете сортировать unordered_map на месте, потому что его value_type является std::pair<const Key, T> (обратите внимание на const!) Для unordered_map<Key,T>. Это означает, что вы не можете менять элементы на карте, поэтому вы не можете их отсортировать. Вам нужно будет скопировать данные в другой структуры данных, как вектор, то вы можете использовать некоторые «доморощенные» версию std::nth_element на нем:

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

Вы должны реализовать свои nth_element с линейной сложностью в среднем. (Если количество входных значений является четным, вам нужно использовать среднее значение обоих средних значений.)

Answer 2

Неупорядоченная карта не имеет порядка (как следует из названия), и таким образом найти медиану в неупорядоченной карте не имеет смысла. Если вам нужно найти медиану - используйте вспомогательный массив и выполните некоторую реализацию алгоритма nth_element. Этот шаг будет с линейной сложностью.