C++에서 자주 사용하게 되는 STL인 Vector, Priority Queue, Map, Set의 정렬방법을 지정하는 방법에 대한 정리.
Vector
다른 STL과 다르게, vector에는 기본적으로 정렬이 되는 자료구조가 아니기 때문에, sort함수의 도움을 받아서 vector를 정렬할 수 있으며, sort 함수의 구조는 다음과 같다.
즉, 3번째 parameter인 Compare 함수를 넘기지 않았을 때는 기본적으로 자료형의 < operator를 이용하여 정렬이 되며, 이를 임의로 지정하여 원하는 방식으로 정렬을 하게 되는 것이다.
자주 사용해 왔던 방식은 다음과 같았다.
- struct 내부에 operator< 오버라이딩
- greater / less 임시 객체를 이용
- operator() 를 멤버로 가지는 struct 생성
- bool function을 지정
허나 C++ 11부터는 bool function 대신 lambda expression도 가능하다고 하니, 한번에 정리를 해 보자면 각각은 다음과 같다.
1. struct 내부에 operator< 오버라이딩
사실상 compare function을 지정하는 이유가 단순 int, string 등의 정렬을 위하여서가 아니라, custom class등의 정렬을 위함이기 때문에, 해당 class 지정과 동시에 내부에 operator를 지정하여 정렬을 할 수 있는 쉬운 방법이다.
위와 같은 struct으로 vector를 생성하여 sort를 할 수 있을까? 불가능하다. struct자체의 operator< 를 명시하지도, sort function에 compare function도 넘겨주지 않고서는 어떤 방식으로 정렬할 지 명시를 해주지 않았기 때문이다.
1번의 방식을 사용하여서, 이름의 길이가 짧은 순으로, 이름의 길이가 같다면 나이가 많은 순으로 정렬하도록 해 보자.
그러고 나면, 다른 compare function을 지정하지 않고도 sort함수를 통해 원하는 대로 정렬할 수 있음을 알 수 있다.
이때 나는 화살표의 비교 방향을 항상
'첫번째 인자'를 앞에, '두번째 인자'를 뒤에 두고나서, 오름차순이면 뒤를 향하는 operator(<), 내림차순이면 앞을 향하는 operator(>) 라고 생각을 하고 있는데, 예를들어 parameter가 순서대로 a, b라고 할 때,
a < b -> 오름차순
a > b -> 내림차순
b < a -> 내림차순 이긴 하나 사용 x
b > a -> 오름차순 이긴 하나 사용 x
이런식으로 사용 한다. 결국 'bool 값을 true로 만드는 식으로 정렬한다'는 생각에 더하여 비교 순서를 항상 지정해 둠으로써 착오를 줄일 수 있다.
2. greater / less 임시 객체를 이용
이 방법은 int, string 혹은 pair<int, int>등 간단한 구조의 자료를 sorting 할 수 있도록 기 정의된 함수이다.
즉, '첫번째 인자'가 '두번째 인자'보다 큰지를 나타내는 나타내는 operator() 함수가 정의되어있는 함수 객체인 것.
그렇기에 첫번째 sort의 결과는, int형의 '<' 연산자를 기준으로 정렬되었기 때문에 오름차순으로 정렬이 됨을 알 수 있고, greater<>()를 이용하여 정렬을 하였을 때는 내림차순으로 정렬됨을 알 수 있다.
3. operator() 를 멤버로 가지는 struct 생성
2번에서는 기 정의된 operator() 를 이용했다면, 이 방법은 단지 내가 새로운 operator() 함수를 정의한다는 점만 다르다.
1에서와 동일하게 정렬을 할 때, struct을 위와 같이 정의하고 이를 sort함수 안에 추가함으로써 동일한 정렬을 할 수 있다. 새롭게 정의한 person 이라는 struct에 대해서는 greater()을 사용할 수 없음은 자명하게 알 수 있다.
4. bool function을 지정
꼭 operator(), operator> 만을 사용하는것이 아닌, 임의의 bool return 값을 가지는 함수를 통하여서도 sorting 방법을 정의할 수 있다.
3과 동일한 케이스를 임의의 함수로 변환한 것.
함수를 parameter로 넘기기에 마지막에 괄호가 들어가지 않아야한다는 점까지 주의하면 된다.
5. lambda expression 이용
4와 동일하나, lambda expression을 사용하여 간단하게 정의할 수 있다는 것 또한 경우에따라 빠르게 비교방법을 정의할 수 있음을 안다.
