std::partial_sort_copy - cppreference.com (original) (raw)

Sorts some of the elements in the range [first, last) in ascending order, storing the result in the range [d_first, d_last).

At most d_last - d_first of the elements are placed sorted to the range [d_first, d_first + n). n is the number of elements to sort (std::min(std::distance(first, last), d_last - d_first)). The order of equal elements is not guaranteed to be preserved.

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

2. 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 all following conditions are satisfied:

If *first is not writable to d_first, the program is ill-formed.

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

Contents

• 1 Parameters
• 2 Return value
• 3 Complexity
• 4 Exceptions
• 5 Possible implementation
• 6 Example
• 7 Defect reports
• 8 See also

[edit] Parameters

[edit] Return value

An iterator to the element defining the upper boundary of the sorted range, i.e. d_first + std::min(std::distance(first, last), d_last - d_first).

[edit] Complexity

Given \(\scriptsize N\)N as std::distance(first, last), \(\scriptsize D\)D as d_last - d_first:

1,2) Approximately \(\scriptsize N \cdot \log(\min(N,D))\)N·log(min(N,D)) comparisons using operator<(until C++20)std::less{}(since C++20).

3,4) Approximately \(\scriptsize N \cdot \log(\min(N,D))\)N·log(min(N,D)) applications of the comparator comp.

[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] Example

The following code sorts a vector of integers and copies them into a smaller and a larger vector.

#include #include #include #include #include #include   void println(std::string_view rem, const auto& v) { std::cout << rem; if constexpr (std::is_scalar_v<std::decay_t<decltype(v)>>) std::cout << v; else for (int e : v) std::cout << e << ' '; std::cout << '\n'; }   int main() { const auto v0 = {4, 2, 5, 1, 3}; std::vector v1{10, 11, 12}; std::vector v2{10, 11, 12, 13, 14, 15, 16}; std::vector::iterator it;   it = std::partial_sort_copy(v0.begin(), v0.end(), v1.begin(), v1.end()); println("Writing to the smaller vector in ascending order gives: ", v1);   if (it == v1.end()) println("The return value is the end iterator", ' ');   it = std::partial_sort_copy(v0.begin(), v0.end(), v2.begin(), v2.end(), std::greater());   println("Writing to the larger vector in descending order gives: ", v2); println("The return value is the iterator to ", *it); }

Output:

Writing to the smaller vector in ascending order gives: 1 2 3 The return value is the end iterator Writing to the larger vector in descending order gives: 5 4 3 2 1 15 16 The return value is the iterator to 15

[edit] Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

[edit] See also