C++ std::pair 정렬방법

pair 참 편한 클래스죠. 덕분에 문제풀 때 구조체 만드는 수고를 덜 수 있습니다.

std::pair는 <utility> 헤더에 들어있습니다.

 

template<
    class T1,
    class T2
> struct pair;

정의는 뭐 궁금하지 않으시겠지만 이렇게 생겼고요.

 

std::pair의 정렬 방법에 대해 알아봅시다.

template< class RandomIt, class Compare >
constexpr void sort( RandomIt first, RandomIt last, Compare comp );

기본적으로 std::sort를 보면 세 번째 인자로 Comparator(비교자?)를 넣을 수 있습니다.

comparator를 넣지 않으면 기본값으로 std::less가 사용됩니다. 즉 오름차순(비내림차순)으로 정렬됩니다.

 

template <class _Ty1, class _Ty2>
_NODISCARD constexpr bool operator<(const pair<_Ty1, _Ty2>& _Left, const pair<_Ty1, _Ty2>& _Right) {
    return _Left.first < _Right.first || (!(_Right.first < _Left.first) && _Left.second < _Right.second);
}

std::pair는 비교 연산자들이 정의되어 있는데요, less operator의 구현을 보면 first 값 먼저 비교하고, 그 다음 second 값을 비교하는 걸 알 수 있습니다.

그래서 이 점을 염두해서 문제풀 때 first, second값의 순서를 정하는 게 좋겠죠.

 

'난 그냥 second->first로 정렬하고싶다'라고 하시면 less operator를 오버로딩하거나 comparator를 만들면 됩니다. 여러 방법이 있지만 제일 간단한 방법은 lambda 함수를 만드는겁니다.

 

//y, x 좌표
vector<pair<int, int> > pts = { {1, 1}, {1, 2}, {2, 1}, {2, 2} };

// (1) y(first) -> x(second) 순으로 오름차순 정렬
sort(pts.begin(), pts.end());

// (2) y(first) -> x(second) 순으로 내림차순 정렬
sort(pts.begin(), pts.end(), std::greater());

// (3) x(second) -> y(first) 순으로 오름차순 정렬
sort(pts.begin(), pts.end(), [](auto& lhs, auto& rhs) {
	if (lhs.second == rhs.second)
		return lhs.first < rhs.first;
	return lhs.second < rhs.second;
});

// (4) x(second) -> y(first) 순으로 내림차순 정렬
sort(pts.begin(), pts.end(), [](auto& lhs, auto& rhs) {
	if (lhs.second == rhs.second)
		return lhs.first > rhs.first;
	return lhs.second > rhs.second;
});

이런식으로 만들면 됩니다. auto로 써놓은 부분은 std::pair<int, int>인데 길어서 그냥 auto를 사용했습니다.

근데 비주얼스튜디오 인텔리센스가 auto 타입 감지를 못하고 <unnamed>로 나오네요. 컴파일은 잘 되니까 뭐 상관없습니다.