저번에는 sort 함수를 정리했었다. 이번에는 stable_sort 함수에 대해서 정리해보겠다.

stable_sort()는 sort()와 비슷하지만 다른 정렬 도구다. 첫 번째 원소가 같을 경우, 두 번째 원소의 입력 순서대로 출력을 보장한다. 즉 동일한 값에 대해 기존 순서가 보장되는, 예측할 수 있는 안정적인 정렬이다.

stable_sort란?

에 정의되어있는 함수로 아래의 형식대로 사용한다.

template <class RandomIt>
void stable_sort(RandomIt first, RandomIt last);  // (1)

template <class RandomIt, class Compare>
void stable_sort(RandomIt first, RandomIt last, Compare comp);  // (2)

// 아래 두 함수는 위와 동일하지만 ExecutionPolicy 를 추가로 받을 수 있다.
template <class ExecutionPolicy, class RandomIt>
void stable_sort(ExecutionPolicy&& policy, RandomIt first, RandomIt last);

template <class ExecutionPolicy, class RandomIt, class Compare>
void stable_sort(ExecutionPolicy&& policy, RandomIt first, RandomIt last,
                 Compare comp);

범위 내의 원소들의 오름 차순 (크기가 작은 것에서 큰 순으로) 안정 정렬을 수행한다 참고로 안정 정렬 이란, 크기가 같은 원소들의 상대적 위치가 바뀌지 않는 정렬이다.

예를 들어서 (3, a), (2, b), (2, c), (1, d) 라는 데이터가 있을 때 정수값으로 안정 정렬을 수행한다면 반드시 (1, d), (2, b), (2, c), (3, a) 가 되지, (1, d), (2, c), (2, b), (3, a) 는 될 수 없다. 왜냐하면 이전에 (2, b) 가 (2, c) 앞에 있었기 때문이다.

(1) 번 함수의 경우 operator< 를 사용해서 크기 비교를 수행한다. (2) 번 함수의 경우 비교 함수인 comp 를 이용해서 크기 비교를 수행한다.

밑의 두 함수의 경우 추가적으로 실행 방식을 첫 번째 인자로 전달할 수 있는데, 전달하는 policy 의 경우 반드시 std::is_execution_policy_v<std::remove_cvref_t> 를 만족해야 한다.

인자

• first, last: 생성된 값을 대입할 원소들의 범위를 나타낸다.
• policy : 사용할 실행 방식
• comp : 두 원소를 비교할 함수로 아래와 같은 꼴 이어야 한다.

bool cmp(const Type1 &a, const Type2 &b);

이 때 함수의 인자 타입은 반드시 const& 일 필요는 없으나, 함수안에선 반드시 전달받은 인자를 변경해서는 안된다. 또한 전달하는 인자들은 반드시 Type1 과 Type2 로 치환 가능해야만 한다.

실행예제

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Employee {
  int age;
  string name;  // Does not participate in comparisons
};

bool operator<(const Employee& lhs, const Employee& rhs) {
  return lhs.age < rhs.age;
}

int main() {
  vector<Employee> v = {
    {108, "Zaphod"},
    {32, "Arthur"},
    {108, "Ford"},
  };

  stable_sort(v.begin(), v.end());

  for (const Employee& e : v) std::cout << e.age << ", " << e.name << '\n';
}

실행결과는 아래에 있다.

32, Arthur
108, Zaphod
108, Ford