std::ranges::stable_sort(3)

💖 std::ranges::stable_sort 💖

okay so bestie, welcome to the C++ Standard Library manual page for std::ranges::stable_sort — yes, the self-titled icon 💅. We’re gonna get into the stable-sort-for-ranges vibe, and I promise we keep every single detail. iykyk ✨

---

💅 NAME 💅

std::ranges::stable_sort — std::ranges::stable_sort (the name is literally the name, and honestly? main character energy 🫶).

---

🌸 Synopsis 🌸

Defined in header <algorithm> — call signature time ✨

          template< std::random_access_iterator I, std::sentinel_for<I>
          S,

                    class Comp = ranges::less, class Proj = std::identity
       (since C++20)
          >                                                               (1)
       (constexpr since
          requires std::sortable<I, Comp, Proj>
       C++26)

              I stable_sort( I first, S last, Comp comp = {}, Proj proj =
          {} );
          template< ranges::random_access_range R, class Comp =
       ranges::less,
                                                                              (since
       C++20)
                    class Proj = std::identity >                          (2)
       (constexpr since
          requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
       C++26)
          ranges::borrowed_iterator_t<R>

              stable_sort( R&& r, Comp comp = {}, Proj proj = {} );

okay so the vibe is: this sorts the elements in the range [first, last) in non-descending order. The order of equivalent elements is stable — i.e. guaranteed to be preserved. periodt 💖

A sequence is sorted with respect to a comparator comp if, for any iterator it pointing to the sequence and any non-negative integer n such that it + n is a valid iterator pointing to an element of the sequence, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it) evaluates to false.

1. Elements are compared using the given binary comparison function comp.
2. Same as (1), but uses r as the range, as if using ranges::begin(r) as first and ranges::end(r) as last.

The function-like entities described on this page are niebloids, that is:

• Explicit template argument lists cannot be specified when calling any of them.
• None of them are visible to argument-dependent lookup.
• When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.

In practice, they may be implemented as function objects, or with special compiler extensions. no cap, that’s the whole niebloid lore 🦋

---

🎀 Parameters 🎀

• first, last — iterator-sentinel defining the range to sort.
• r — the range to sort.
• comp — comparison to apply to the projected elements.
• proj — projection to apply to the elements.

---

⭐ Return value ⭐

An iterator equal to last. that’s it, that’s the return value bestie ✨

---

🔥 Complexity 🔥

N·log(N) comparisons, if extra memory is available; where N is ranges::distance(first, last). N·log²(N) comparisons otherwise. Twice as many projections as the number of comparisons in both cases.

---

🦋 Notes 🦋

The feature-test macro situation is giving:

• __cpp_lib_constexpr_algorithms — value 202306L; feature: constexpr stable sorting.

---

🌈 Possible implementation 🌈

This implementation only shows the slower algorithm used when no additional memory is available. See also implementation in MSVC STL and 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 //< since 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 //< since 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));
           } };

---

🍓 Example 🍓

       // Run this code

        #include <algorithm>
        #include <array>
        #include <functional>
        #include <iomanip>
        #include <iostream>

        void print(auto const& seq)
        {
            for (auto const& elem : seq)
                std::cout << elem << ' ';
            std::cout << '\n';
        }

        struct Particle
        {
            std::string name; double mass; // MeV
            friend std::ostream& operator<<(std::ostream& os, Particle const&
       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};

            // sort using the default operator<
            std::ranges::stable_sort(s);
            print(s);

            // sort using a standard library compare function object
            std::ranges::stable_sort(s, std::ranges::greater());
            print(s);

            // sort using a custom function object
            struct
            {
                bool operator()(int a, int b) const
                {
                    return a < b;
                }
            } customLess;
            std::ranges::stable_sort(s.begin(), s.end(), customLess);
            print(s);

            // sort using a lambda expression
            std::ranges::stable_sort(s, [](int a, int b) { return a > b; });
            print(s);

            // sort with projection
            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); //< sort
       by name
            print(particles);
            std::ranges::stable_sort(particles, {}, &Particle::mass); //< sort
       by mass
            print(particles);
        }

---

💀 Output 💀

        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

---

👑 See also 👑

• ranges::sort (C++20) — sorts a range into ascending order (niebloid).
• ranges::partial_sort (C++20) — sorts the first N elements of a range (niebloid).
• ranges::stable_partition (C++20) — divides elements into two groups while preserving their relative order (niebloid).
• stable_sort — sorts a range of elements while preserving order between equal elements (function template).

---

source: cppreference.com · version/date: 2024.06.10 · bye bestie, go sort something stable 💜🫶