Difference between revisions of "cpp/algorithm/stable sort"

Latest revision as of 21:46, 22 May 2024

Defined in header `<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)

Sorts the elements in the range [first, last) in non-descending order. The order of equivalent elements is guaranteed to be preserved.

1) Elements are sorted with respect to operator<(until C++20)std::less{}(since C++20).

3) Elements are sorted with respect to comp.

2,4) Same as (1,3), but executed according to policy.

These overloads participate in overload resolution only if

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> is true.	(until C++20)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> is true.	(since C++20)

If any of the following conditions is satisfied, the behavior is undefined:

The type of *first is not Swappable.	(until C++11)
`RandomIt` is not ValueSwappable. The type of first is not MoveConstructible. The type of first is not MoveAssignable.	(since C++11)

first, last	-	the range of elements to sort
policy	-	the execution policy to use. See execution policy for details.
comp	-	comparison function object (i.e. an object that satisfies the requirements of Compare) which returns true if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1& a, const Type2& b); While the signature does not need to have const&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) `Type1` and `Type2` regardless of value category (thus, `Type1&` is not allowed, nor is `Type1` unless for `Type1` a move is equivalent to a copy(since C++11)). The types Type1 and Type2 must be such that an object of type RandomIt can be dereferenced and then implicitly converted to both of them.
Type requirements
- `RandomIt` must meet the requirements of LegacyRandomAccessIterator.
- `Compare` must meet the requirements of Compare.

[edit] Complexity

Given $\scriptsize N$ $N$ as last - first:

1,2)

O(N\cdotlog(N))

comparisons using operator<(until C++20)std::less{}(since C++20) if enough extra memory is available, otherwise

O(N\cdotlog 2 (N))

comparisons.

3,4)

O(N\cdotlog(N))

applications of the comparator comp if enough extra memory is available, otherwise

O(N\cdotlog 2 (N))

applications.

[edit] Exceptions

The overloads with a template parameter named ExecutionPolicy report errors as follows:

If execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the standard policies, std::terminate is called. For any other ExecutionPolicy, the behavior is implementation-defined.
If the algorithm fails to allocate memory, std::bad_alloc is thrown.

[edit] Possible implementation

See also the implementations in libstdc++ and libc++.

[edit] Notes

This function attempts to allocate a temporary buffer equal in size to the sequence to be sorted. If the allocation fails, the less efficient algorithm is chosen.

Feature-test macro	Value	Std	Feature
`__cpp_lib_constexpr_algorithms`	202306L	(C++26)	constexpr stable sorting, overloads (1), (3)

[edit] Example

Run this code

#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>
 
struct Employee
{
    int age;
    std::string name; // Does not participate in comparisons
};
 
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';
}

Output:

32, Arthur
108, Zaphod
108, Ford

[edit] See also

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

@@ Line 1: / Line 1: @@
 {{cpp/title|stable_sort}}
-{{cpp/algorithm/sidebar}}
+{{cpp/algorithm/navbar}}
-{{ddcl list begin}}
+{{dcl begin}}
-{{ddcl list header | algorithm}}
+{{dcl header|algorithm}}
-{{ddcl list item | num=1 |
+{{dcla|num=1|constexpr=c++26|
-template< class RandomAccessIterator >
+template< class RandomIt >
-void stable_sort( RandomAccessIterator first, RandomAccessIterator last );
+void stable_sort( RandomIt first, RandomIt last );
 }}
-{{ddcl list item | num=2 |
+{{dcl|num=2|since=c++17|
-template< class RandomAccessIterator, class Compare >
+template< class ExecutionPolicy, class RandomIt >
-void stable_sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp );
+void stable_sort( ExecutionPolicy&& policy,
+                  RandomIt first, RandomIt last );
 }}
-{{ddcl list end}}
+{{dcla|num=3|constexpr=c++26|
+template< class RandomIt, class Compare >
+void stable_sort( RandomIt first, RandomIt last, Compare comp );
+}}
+{{dcl|num=4|since=c++17|
+template< class ExecutionPolicy, class RandomIt, class Compare >
+void stable_sort( ExecutionPolicy&& policy,
+                  RandomIt first, RandomIt last, Compare comp );
+}}
+{{dcl end}}
-Sorts the elements in the range {{tt|[first, last)}} in ascending order. The order of equal elements is guaranteed to be preserved. The first version uses {{c|operator<}} to compare the elements, the second version uses the given comparison function {{tt|comp}}.
+Sorts the elements in the range {{range|first|last}} in non-descending order. The order of equivalent elements is guaranteed to be preserved.
-===Parameters===
+@1@ Elements are {{rlp|/#Requirements|sorted}} with respect to {{rev inl|until=c++20|{{c/core|operator<}}}}{{rev inl|since=c++20|{{c|std::less{}<!---->}}}}.
-{{param list begin}}
-{{param list item | first, last | the range of elements to sort}}
-{{param list cmp | comp | p1=RandomAccessIterator}}
-{{param list end}}
-===Return value===
+@3@ Elements are sorted with respect to {{c|comp}}.
-(none)
+@2,4@ Same as {{v|1,3}}, but executed according to {{c|policy}}.
+@@ {{cpp/algorithm/parallel overload precondition|plural=yes}}
+If any of the following conditions is satisfied, the behavior is undefined:
+{{rev begin}}
+{{rev|until=c++11|
+* The type of {{c|*first}} is not {{named req|Swappable}}.
+}}
+{{rev|since=c++11|
+* {{tt|RandomIt}} is not {{named req|ValueSwappable}}.
+* The type of {{c|*first}} is not {{named req|MoveConstructible}}.
+* The type of {{c|*first}} is not {{named req|MoveAssignable}}.
+}}
+{{rev end}}
+===Parameters===
+{{par begin}}
+{{par|first, last|the range of elements to sort}}
+{{par exec pol}}
+{{par cmp ord|comp|p1=RandomIt}}
+{{par hreq}}
+{{par req named|RandomIt|RandomAccessIterator}}
+{{par req named|Compare|Compare}}
+{{par end}}
 ===Complexity===
-{{math|O(N&middot;log<sup>2</sup>(N))}}, where {{c|1=N = std::distance(first, last)}} applications of {{tt|cmp}}. If additional memory is available, then the complexity is {{math|O(N&middot;log(N)}}.
+Given {{mathjax-or|\(\scriptsize N\)|N}} as {{c|last - first}}:
+@1,2@ {{mathjax-or|\(\scriptsize O(N \cdot \log(N))\)|O(N·log(N))}} comparisons using {{rev inl|until=c++20|{{c/core|operator<}}}}{{rev inl|since=c++20|{{c|std::less{}<!---->}}}} if enough extra memory is available, otherwise {{mathjax-or|\(\scriptsize O(N \cdot \log^{2}(N))\)|O(N·log{{su|p=2}}(N))}} comparisons.
+@3,4@ {{mathjax-or|\(\scriptsize O(N \cdot \log(N))\)|O(N·log(N))}} applications of the comparator {{c|comp}} if enough extra memory is available, otherwise {{mathjax-or|\(\scriptsize O(N \cdot \log^{2}(N))\)|O(N·log{{su|p=2}}(N))}} applications.
+===Exceptions===
+{{cpp/algorithm/parallel exceptions reporting behavior|singular=no}}
+===Possible implementation===
+See also the implementations in [https://github.com/gcc-mirror/gcc/blob/d9375e490072d1aae73a93949aa158fcd2a27018/libstdc%2B%2B-v3/include/bits/stl_algo.h#L4977 libstdc++] and [https://github.com/llvm-mirror/libcxx/blob/a12cb9d211019d99b5875b6d8034617cbc24c2cc/include/algorithm#L4696 libc++].
+===Notes===
+This function attempts to allocate a temporary buffer equal in size to the sequence to be sorted. If the allocation fails, the less efficient algorithm is chosen.
+{{feature test macro|__cpp_lib_constexpr_algorithms|{{c/core|constexpr}} stable sorting, overloads {{vl|1}}, {{vl|3}}|value=202306L|std=C++26}}
 ===Example===
 {{example
- |
+|code=
-  | code=
+#include <algorithm>
-  | output=
+#include <array>
+#include <iostream>
+#include <string>
+#include <vector>
+struct Employee
+{
+    int age;
+    std::string name; // Does not participate in comparisons
+};
+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';
+}
+|output=
+, Arthur
+, Zaphod
+, Ford
 }}
 ===See also===
-{{dcl list begin}}
+{{dsc begin}}
-{{dcl list template | cpp/algorithm/dcl list partial_sort}}
+{{dsc inc|cpp/algorithm/dsc sort}}
-{{dcl list template | cpp/algorithm/dcl list sort}}
+{{dsc inc|cpp/algorithm/dsc partial_sort}}
-{{dcl list end}}
+{{dsc inc|cpp/algorithm/dsc stable_partition}}
+{{dsc inc|cpp/algorithm/ranges/dsc stable_sort}}
+{{dsc end}}
+{{langlinks|de|es|fr|it|ja|pt|ru|zh}}

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)
Metaprogramming library (C++11)
Diagnostics library
General utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Localizations library
Input/output library
Filesystem library (C++17)
Regular expressions library (C++11)
Concurrency support library (C++11)
Execution support library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.com

Namespaces

Variants

Views

Actions

Difference between revisions of "cpp/algorithm/stable sort"

Latest revision as of 21:46, 22 May 2024

Contents

[edit] Parameters