std::ranges::stable_sort

template< std::random_access_iterator I, std::sentinel_for<I> S,
          class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
    I stable_sort( I first, S last, Comp comp = {}, Proj proj = {} );

template< ranges::random_access_range R, class Comp = ranges::less,
          class Proj = std::identity >
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
ranges::borrowed_iterator_t<R>
    stable_sort( R&& r, Comp comp = {}, Proj proj = {} );

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

시퀀스는 비교기 comp에 대해 정렬되어 있다고 합니다. 만약 시퀀스를 가리키는 임의의 반복자 it와 n이 시퀀스의 요소를 가리키는 유효한 반복자이도록 하는 임의의 음이 아닌 정수 it + n에 대해 std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it)이 false로 평가된다면 그렇습니다.

이 페이지에 설명된 함수 유사 개체들은 알고리즘 함수 객체입니다 (비공식적으로 niebloids라고 함). 즉, 다음과 같습니다:

• 이들 중 하나를 호출할 때 명시적 템플릿 인자 목록을 지정할 수 없습니다.
• 이들 중 어떤 것도 인자 종속 검색에 보이지 않습니다.
• 이들 중 하나가 일반적인 비한정 검색에 의해 함수 호출 연산자의 왼쪽 이름으로 발견되면, 인자 종속 검색이 억제됩니다.

매개변수

반환값

last 와 동일한 반복자.

복잡도

\(\scriptsize N\cdot\log{(N)}\) N·log(N) 비교(추가 메모리가 사용 가능한 경우); 여기서 \(\scriptsize N\) N 은 ranges:: distance ( first, last ) 입니다. \(\scriptsize N\cdot\log^2{(N)}\) N·log²(N) 비교(추가 메모리가 없는 경우). 두 경우 모두 비교 횟수의 두 배에 해당하는 프로젝션 연산이 수행됩니다.

참고 사항

가능한 구현

이 구현은 추가 메모리를 사용할 수 없을 때 사용되는 느린 알고리즘만 보여줍니다. 또한 MSVC STL 와 libstdc++ 의 구현도 참조하십시오.

struct stable_sort_fn
{
    template<std::random_access_iterator I, std::sentinel_for<I> S,
             class Comp = ranges::less, class Proj = std::identity>
    requires std::sortable<I, Comp, Proj>
    constexpr //< C++26부터
    I operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        auto count = ranges::distance(first, last);
        auto mid = first + count / 2;
        auto last_it = first + count;
        if (count <= 1)
            return last_it;
        (*this)(first, mid, std::ref(comp), std::ref(proj));
        (*this)(mid, last_it, std::ref(comp), std::ref(proj));
        ranges::inplace_merge(first, mid, last_it);
        return last_it;
    }
    template<ranges::random_access_range R, class Comp = ranges::less,
             class Proj = std::identity>
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr //< C++26부터
    ranges::borrowed_iterator_t<R> operator()(R&& r, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), std::move(comp), std::move(proj));
    }
};
inline constexpr stable_sort_fn stable_sort{};

예제

#include <algorithm>
#include <array>
#include <functional>
#include <iomanip>
#include <iostream>
void print(const auto& seq)
{
    for (const auto& elem : seq)
        std::cout << elem << ' ';
    std::cout << '\n';
}
struct Particle
{
    std::string name; double mass; // MeV
    friend std::ostream& operator<<(std::ostream& os, const Particle& p)
    {
        return os << '\n' << std::left << std::setw(8) << p.name << " : " << p.mass;
    }
};
int main()
{
    std::array s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    // 기본 operator<를 사용하여 정렬
    std::ranges::stable_sort(s);
    print(s);
    // 표준 라이브러리 비교 함수 객체를 사용하여 정렬
    std::ranges::stable_sort(s, std::ranges::greater());
    print(s);
    // 사용자 정의 함수 객체를 사용하여 정렬
    struct
    {
        bool operator()(int a, int b) const { return a < b; }
    } customLess;
    std::ranges::stable_sort(s.begin(), s.end(), customLess);
    print(s);
    // 람다 표현식을 사용하여 정렬
    std::ranges::stable_sort(s, [](int a, int b) { return a > b; });
    print(s);
    // 프로젝션을 사용한 정렬
    Particle particles[]
    {
        {"Electron", 0.511}, {"Muon", 105.66}, {"Tau", 1776.86},
        {"Positron", 0.511}, {"Proton", 938.27}, {"Neutron", 939.57}
    };
    print(particles);
    std::ranges::stable_sort(particles, {}, &Particle::name); //< 이름으로 정렬
    print(particles);
    std::ranges::stable_sort(particles, {}, &Particle::mass); //< 질량으로 정렬
    print(particles);
}

0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
Electron : 0.511
Muon     : 105.66
Tau      : 1776.86
Positron : 0.511
Proton   : 938.27
Neutron  : 939.57
Electron : 0.511
Muon     : 105.66
Neutron  : 939.57
Positron : 0.511
Proton   : 938.27
Tau      : 1776.86
Electron : 0.511
Positron : 0.511
Muon     : 105.66
Proton   : 938.27
Neutron  : 939.57
Tau      : 1776.86

참고 항목