[C++] std::map을 value 기준으로 정렬하기

std::map 정렬

map의 자료구조는 기본적으로 key 값 기준 오름차순 기반 정렬을 하고 있다

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

 

만약 우리가 key 값 기준 내림차순으로 변경하기 위해선 3번째 인자에 greater<>()를 넣어주면 된다

// 키, 데이터, compare
map<int, string, greater<int>> m;

value 값 기반 정렬하기

map에는 정렬 함수가 따로 없어서, vector를 활용해야한다. 구체적으로, map은 tree형태로 되어져있고, tree 형태를 만드는 과정에서 key을 기준으로 정렬을 한다. 완성된 tree를 지지고 볶고 하지는 않기 때문에 sort()가 존재하지 않는다.

pair 기반의 vector에 map이 가지고 있는 pair를 모두 넣고 정렬을 하면 value값 기준 정렬이 가능해진다.

 

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

 

pair vector에 넣고 value 기준 정렬

void sort(map<string, int>& map) {
	vector<pair<string, int> > vec;

	for (auto& it : map) {
		vec.emplace_back(it);
	}

	// 우리가 위에서 정의한 cmp
	sort(vec.begin(), vec.end(), cmp);

	for (auto& it : vec)
		cout << it.first << " " << it.second << endl;
}

map value 기반 정렬 활용

#include <iostream>
#include <string>
#include <map>
#include <vector>

// 코드 단순화 (귀차니즘..)
#define pp pair<string, int>
#define mm map<string, int>

using namespace std;

// 사용자 정의 비교함수
bool cmp(const pp& a,
         const pp& b)
{
    return a.second < b.second;
}

// sort 담당함수
void sort(const mm& map)
{
    vector<pp> vec;

    for (auto& it : map) {
        vec.push_back(it);
    }

    sort(vec.begin(), vec.end(), cmp);

    for (auto& it : vec) {
        cout << " 할일 " << it.first << " 중요도 : " << it.second << endl;
    }
}

int main ()
{
    mm todo = {
		{"블로깅", 3},
		{"프로그래밍", 1},
		{"운동", 2}
	};
    sort(todo);
}

 

[C++] std::map을 value 기준으로 정렬하기 - 널두