std:: stable_sort

From cppreference.net

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

범위 내의 요소들을 비내림차순으로 정렬합니다. [ first , last ) 동등한 요소들의 순서는 보존됨이 보장됩니다.

1) 요소들은 정렬되어 있으며 operator < (C++20 이전) std:: less { } (C++20 이후) 에 따라 정렬됩니다.

3) 요소들은 comp 를 기준으로 정렬됩니다.

2,4) (1,3) 와 동일하지만, policy 에 따라 실행됩니다.

다음 모든 조건이 만족될 때만 이 오버로드들이 오버로드 해결에 참여합니다:

std:: is_execution_policy_v < std:: decay_t < ExecutionPolicy >> 가 true 인 경우.	(C++20 이전)
std:: is_execution_policy_v < std:: remove_cvref_t < ExecutionPolicy >> 가 true 인 경우.	(C++20 이후)

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

* first 의 타입이 Swappable 가 아닙니다.	(C++11 이전)
`RandomIt` 이 ValueSwappable 가 아닙니다. * first 의 타입이 MoveConstructible 가 아닙니다. * first 의 타입이 MoveAssignable 가 아닙니다.	(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 요구사항을 충족해야 함.

복잡도

주어진 $\scriptsize N$ $N$ 을 last - first 로:

1,2)

O(N\cdotlog(N))

비교를 사용하며 operator < (C++20 이전) std:: less { } (C++20 이후) 충분한 추가 메모리가 사용 가능한 경우, 그렇지 않으면

O(N\cdotlog 2 (N))

비교를 수행합니다.

3,4)

O(N\cdotlog(N))

비교자 comp 의 적용 횟수 (충분한 추가 메모리가 사용 가능한 경우), 그렇지 않으면

O(N\cdotlog 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

참고 항목

sort	범위를 오름차순으로 정렬 (함수 템플릿)
partial_sort	범위의 첫 N개 요소를 정렬 (함수 템플릿)
stable_partition	요소들의 상대적 순서를 유지하며 두 그룹으로 분할 (함수 템플릿)
ranges::stable_sort (C++20)	동일한 요소들 간의 순서를 유지하며 범위의 요소들을 정렬 (알고리즘 함수 객체)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants

std:: stable_sort

목차

매개변수

복잡도

예외

가능한 구현

참고 사항

예제

참고 항목