Namespaces
Variants

    std::stable_sort

    From ko.cppreference.net
     
    C++
     
    알고리즘 라이브러리
    제약 알고리즘 및 범위 알고리즘 (C++20)
    제약 알고리즘 (예: ranges::copy, ranges::sort, ...
    정렬 및 관련 연산
    분할 연산
    (C++11)    
    (C++11)

    정렬 연산
    이진 검색 연산
    (분할된 범위에서)
    집합 연산 (정렬된 범위에서)
    병합 연산 (정렬된 범위에서)
    힙 연산
    최소/최대 연산
    (C++11)
    (C++17)
    사전식 비교 연산
    (C++20)
    순열 연산


     
    헤더에 정의됨 <algorithm> 
    template< class RandomIt >
void stable_sort( RandomIt first, RandomIt last );
    		(1) (constexpr since C++26) 
    template< class ExecutionPolicy, class RandomIt >
void stable_sort( ExecutionPolicy&& policy,
                  RandomIt first, RandomIt last );
    		(2) (since C++17) 
    template< class RandomIt, class Compare >
void stable_sort( RandomIt first, RandomIt last, Compare comp );
    		(3) (constexpr since C++26) 
    template< class ExecutionPolicy, class RandomIt, class Compare >
void stable_sort( ExecutionPolicy&& policy,
                  RandomIt first, RandomIt last, Compare comp );
    		(4) (since C++17)

    범위 [first, last)의 요소를 오름차순으로 정렬합니다. 동등한 요소의 순서는 유지됨이 보장됩니다.

    1) 요소는 정렬 에 대해 operator<(until C++20)std::less{}(since C++20).
    3) 요소는 에 대해 정렬됩니다 comp.
    2,4) 와 동일함 (1,3), 그러나 에 따라 실행됨 policy.
    이 오버로드들은 다음 표현식의 값이 true인 경우에만 오버로드 해결에 참여합니다:

    std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>

    		(until C++20)

    std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>

    		(since C++20)

    다음 조건 중 하나라도 만족하면 동작은 정의되지 않습니다:

    (until C++11)
    (since C++11)

    매개변수

    first, last - 정렬할 요소들의 범위 를 정의하는 반복자 쌍
    policy - 사용할 실행 정책
    comp - 비교 함수 객체(즉, Compare 요구사항을 만족하는 객체)로 첫 번째 인수가 두 번째 인수보다 작은 경우(즉, 순서상 앞서는 경우) ​ true 를 반환함.

    비교 함수의 시그니처는 다음과 동일해야 함:

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

    시그니처에 const & 가 필요하지는 않지만, 함수는 전달된 객체를 수정해서는 안 되며, 값 범주 에 관계없이 (가능한 const) Type1 및 Type2 타입의 모든 값을 받아들일 수 있어야 함(따라서 Type1& 는 허용되지 않으며 , Type1 도 Type1 에 대해 이동이 복사와 동등하지 않는 한 허용되지 않음 (C++11부터) ).
    Type1 및 Type2 타입은 RandomIt 타입의 객체를 역참조한 후 두 타입 모두로 암시적으로 변환할 수 있어야 함. ​

    타입 요구사항
    -
    RandomIt 는 LegacyRandomAccessIterator 요구사항을 충족해야 함.
    -
    Compare 는 Compare 요구사항을 충족해야 함.

    복잡도

    주어진 N 을 last - first 로:

    1,2) O(N·log(N)) 비교를 사용하며 operator < (C++20 이전) std:: less { } (C++20 이후) 충분한 추가 메모리가 사용 가능한 경우, 그렇지 않으면 O(N·log 2
    (N))     비교를 수행합니다.
    3,4) O(N·log(N)) 비교자 comp 의 적용 횟수 (충분한 추가 메모리가 사용 가능한 경우), 그렇지 않으면 O(N·log 2
    (N))     회 적용됩니다.

    예외

    ExecutionPolicy 라는 템플릿 매개변수를 사용하는 오버로드는 다음과 같이 오류를 보고합니다:

    • 알고리즘의 일부로 호출된 함수 실행 중 예외가 발생하고 ExecutionPolicy 가 표준 정책 중 하나인 경우, std::terminate 가 호출됩니다. 다른 ExecutionPolicy 의 경우 동작은 구현에 따라 정의됩니다.
    • 알고리즘이 메모리 할당에 실패하는 경우, std::bad_alloc 이 throw됩니다.

    가능한 구현

    다음 구현도 참조하십시오: libstdc++ 와 libc++ .

    참고 사항

    이 함수는 정렬할 시퀀스와 동일한 크기의 임시 버퍼 할당을 시도합니다. 할당이 실패할 경우, 덜 효율적인 알고리즘이 선택됩니다.

    기능 테스트 매크로 값 표준 기능
    __cpp_lib_constexpr_algorithms 202306L (C++26) constexpr 안정 정렬, 오버로드 ( 1 ) , ( 3 )

    예제

    이 코드 실행 
    #include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>
struct Employee
{
    int age;
    std::string name; // 비교에 참여하지 않음
};
bool operator<(const Employee& lhs, const Employee& rhs)
{
    return lhs.age < rhs.age;
}
#if __cpp_lib_constexpr_algorithms >= 202306L
consteval auto get_sorted()
{
    auto v = std::array{3, 1, 4, 1, 5, 9};
    std::stable_sort(v.begin(), v.end());
    return v;
}
static_assert(std::ranges::is_sorted(get_sorted()));
#endif
int main()
{
    std::vector<Employee> v{{108, "Zaphod"}, {32, "Arthur"}, {108, "Ford"}};
    std::stable_sort(v.begin(), v.end());
    for (const Employee& e : v)
        std::cout << e.age << ", " << e.name << '\n';
}

    출력: 

    32, Arthur
108, Zaphod
108, Ford

    참고

    		 요소 범위를 정렬합니다
    (함수 템플릿 & 알고리즘 함수 객체)
    (C++20)
    		범위의 처음 N개 요소를 정렬합니다
    (함수 템플릿 & 알고리즘 함수 객체)
    (C++20)
    		요소를 두 그룹으로 나누면서 각 그룹 내 상대적 순서를 유지합니다
    (함수 템플릿 & 알고리즘 함수 객체)
    (C++20)
    (C++20)
    		동등한 요소 간 상대적 순서를 유지하면서 요소 범위를 정렬합니다
    (알고리즘 함수 객체)