[STL] map에서 Value를 기준으로 정렬하고 싶을 경우

참고링크: C++ STL의 값별로 맵 정렬 - GeeksforGeeks

해당 링크를 참고하면 된다.

결론은 map STL 단독으로는 Value 기준으로 sort할 수 없다.

따라서, Pair <T,T>를 담는 vector을 선언하여 map iteratior에 따라 삽입해주고

vector의 Pair second를 기준으로 다시 sort해야한다.

Sorting a Map by value in C++ STL - GeeksforGeeks

 

 

원리가 흥미로워서 정리해두려고 한다.

 

원리(위키백과 참고): 

C++의 map은 기본적으로 노드 기반으로 이루어져있는 노드 기반의 균형이진 tree구조(레드-블랙 이진트리)로 만들어질 때부터 set과 마찬가지로 삽입될 때부터 Key에 따라 자동 정렬된다.

 

레드-블랙 트리는 각각의 노드가 레드 나 블랙 인 색상 속성을 가지고 있는 이진 탐색 트리이다. 이진 탐색 트리가 가지고 있는 일반적인 조건에 다음과 같은 추가적인 조건을 만족해야 유효한(valid) 레드-블랙 트리가 된다:

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전

1. 노드는 레드 혹은 블랙 중의 하나이다.
2. 루트 노드는 블랙이다.
3. 모든 리프 노드들(NIL)은 블랙이다.
4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

위 조건들을 만족하게 되면, 레드-블랙 트리는 가장 중요한 특성을 나타내게 된다: 루트 노드부터 가장 먼 잎노드 경로까지의 거리가, 가장 가까운 잎노드 경로까지의 거리의 두 배 보다 항상 작다. 다시 말해서 레드-블랙 트리는 개략적(roughly)으로 균형이 잡혀 있다(balanced). 따라서, 삽입, 삭제, 검색시 최악의 경우(worst-case)에서의 시간복잡도가 트리의 높이(또는 깊이)에 따라 결정되기 때문에 보통의 이진 탐색 트리에 비해 효율적이라고 할 수 있다.

 

해당 블로그가 자세하게 설명을 해놓았다. -> 알고리즘 ) Red-Black Tree (tistory.com)

 

방법 1 – 쌍의 벡터를 사용하여 아이디어는 맵에서 해당 쌍 벡터에 대한 모든 내용을 복사하고 아래에 주어진 lambda 함수를 사용하여 두 번째 값에 따라 쌍의 벡터를 정렬

bool cmp(pair<T1, T2>& a,
         pair<T1, T2>& b)
{
    return a.second < b.second;
}

where T1 and T2
are the data-types 
that can be the 
same or different.

다음은 위의 접근 방식의 구현

// C++ program for the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Comparator function to sort pairs
// according to second value
bool cmp(pair<string, int>& a,
         pair<string, int>& b)
{
    return a.second < b.second;
}
  
// Function to sort the map according
// to value in a (key-value) pairs
void sort(map<string, int>& M)
{
  
    // Declare vector of pairs
    vector<pair<string, int> > A;
  
    // Copy key-value pair from Map
    // to vector of pairs
    for (auto& it : M) {
        A.push_back(it);
    }
  
    // Sort using comparator function
    sort(A.begin(), A.end(), cmp);
  
    // Print the sorted value
    for (auto& it : A) {
  
        cout << it.first << ' '
             << it.second << endl;
    }
}
  
// Driver Code
int main()
{
  
    // Declare Map
    map<string, int> M;
  
    // Given Map
    M = { { "GfG", 3 },
          { "To", 2 },
          { "Welcome", 1 } };
  
    // Function Call
    sort(M);
    return 0;
}

 

출력:

Welcome 1
To 2
GfG 3

 

기타 참고 블로그 : 

[C++] std::map을 value 기준으로 정렬하기 - doodoo's coding (0xd00d00.github.io)

[C++] std::map을 value 기준으로 정렬하기 - doodoo's coding