[C++ / STL] sort 함수를 활용한 오름차순 / 내림차순 정렬
blog post
얼마전 현장 코딩 테스트에서 Sort 함수를 활용한 내림차순 정렬을 구현하려고 했는데 키워드가 생각이 안나서 써먹지 못한 경험이 있습니다. 결국은 직접 내림차순 정렬을 구현했는데, C++ STL의 기본 알고리즘 중에 greater<> 와 less<>를 활용하면 정렬을 아주 간단하게 구현할 수 있습니다.
우선 STL Sort 함수의 기본 포맷은 다음과 같습니다.
default (1)
template <class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);
custom (2)
template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
다른 STL의 알고리즘 관련 함수와 비슷하게 sort 함수도 마찬가지로 기본적으로 이더레이터 범위, 그리고 Compare 파라미터를 통하여 콜백 함수를 선택적으로 처리할 수 있습니다. 아래 코드에서 보시는 것과 같이 기본 정렬 방식은 오름차순입니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {3,2,6,5,8,1,9,7,4};
sort(v.begin(), v.end());
for(auto& i : v)
cout << i << " ";
return 0;
}
결과:
1 2 3 4 5 6 7 8 9
하지만 앞서 말씀드렸다시피 이를 내림차순으로 정렬해야 한다면 어떻게 구현하면 될까요? 간단합니다. Compare 파라미터에 우리가 직접 비교하는 함수를 콜백하도록 해주면 됩니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(int i, int j)
{
return j < i;
}
int main()
{
vector<int> v = {3,2,6,5,8,1,9,7,4};
sort(v.begin(), v.end(), compare);
for(auto& i : v)
cout << i << " ";
return 0;
}
결과:
9 8 7 6 5 4 3 2 1
하지만 이보다 더 간편하게 구현할 수도 있습니다. 아래와 같이 greater<>() 임시객체를 콜하는 방법이죠.
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int main()
{
vector<int> v = {3,2,6,5,8,1,9,7,4};
sort(v.begin(), v.end(), greater<>());
for(auto& i : v)
cout << i << " ";
return 0;
}
결과:
9 8 7 6 5 4 3 2 1
참고로 위에서 greater 대신 less<>() 함수를 사용하면 sort의 기본 정렬 방식인 오름차순을 명시적으로 지정해줄 수 있습니다.
그럼 이제 greater의 내부도 살펴봐야겠습니다. greater는 다음과 같이 템플릿으로 정의되어 있습니다.
template< class T >
struct greater; (until C++14)
template< class T = void >
struct greater; (since C++14)
보시는 바와 같이 템플릿 특수화 처리된 struct로 <functional> 헤더에 정의되어 있습니다. 특히 template을 통한 타입 추론은 C++14부터 지원한다는 점을 기억하셔야 합니다. 즉, 컴파일러 버전에 따라 C++14를 지원하는 이전의 버전까지는 아래와 같이 명시적으로 타입을 지정해줘야 함을 의미합니다.
sort(v.begin(), v.end(), greater<int>());
만약 C++11에서 추론 타입을 명시적으로 지정해주지 않을 경우 다음과 같이 에러가 발생합니다.
main.cpp: In function ‘int main()’:
main.cpp:11:38: error: wrong number of template arguments (0, should be 1)
sort(v.begin(), v.end(), greater<>());
^
In file included from /usr/include/c++/6/string:48:0,
from /usr/include/c++/6/bits/locale_classes.h:40,
from /usr/include/c++/6/bits/ios_base.h:41,
from /usr/include/c++/6/ios:42,
from /usr/include/c++/6/ostream:38,
from /usr/include/c++/6/iostream:39,
from main.cpp:1:
/usr/include/c++/6/bits/stl_function.h:371:12: note: provided for ‘template struct std::greater’
struct greater : public binary_function<_Tp, _Tp, bool>
^~~~~~~
C++ 14부터는 기본적으로 template 특수화를 통하여 타입 생략(void 처리)이 가능하고 Compare로 들어오는 파라미터에 대한 타입 추론이 가능하기 때문에 int를 생략할 수 있었던 것입니다. 따라서 greater<> 와 같이 표현이 가능한 것입니다. greater<>뒤의 ()는 operator입니다. 아래와 같이 greater<>의 오퍼레이터()가 <functional> header에 정의되어 있습니다. 앞서 제가 직접 bool 타입으로 정의하였던 compare(int i, int j) 와 거의 동일하게 정의되어 있는 것을 알 수 있습니다.
constexpr bool operator()(const T &lhs, const T &rhs) const
{
return lhs > rhs;
}
마지막으로 greater<>()를 직접 sort()의 compare 파라미터에 넘겨주는 방법은 C++의 임시객체 생성을 활용한 방식입니다. 객체를 만들어 둘 필요 없이 잠시 함수의 비교 기능만 사용하기 위해 greater의 임시객체를 생성하여 파라미터로 넘긴 것입니다. 임시객체에 대한 개념은 More Effective C++ 항목 19[임시객체의 원류를 정확히 이해하자] 편을 참고하시기 바랍니다.
less<>()도 위의 greater 개념과 같습니다. 다만 두 값의 비교만 역으로 진행됩니다.
