정렬되지 않은지도에서 중간 값을 얻는 방법은 무엇입니까?

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을 정렬 할 수 없습니다. 즉, 맵에서 요소를 바꿀 수 없으므로이를 정렬 할 수 없습니다. 그런 다음 당신이 그것에 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 알고리즘을 일부 구현하십시오. 이 단계는 선형 복잡성이 있습니다. 코멘트에 명시된 바와 같이 그 value_type이 unordered_map<Key,T>에 대한합니다 (const주의!) std::pair<const Key, T> 때문에