Przejdź do głównej zawartości

std::ranges::partial_sort_copy() algorithm

// (1)
constexpr partial_sort_copy_result<I1, I2>
partial_sort_copy( I1 first, S1 last, I2 result_first, S2 result_last,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );

// (2)
constexpr partial_sort_copy_result<ranges::borrowed_iterator_t<R1>,
ranges::borrowed_iterator_t<R2>>
partial_sort_copy( R1&& r, R2&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );

The type of arguments are generic and have following constraints:

  • I1, I2 - std::input_iterator, std::random_access_iterator
  • S1, S2 - std::sentinel_for<I1>, std::sentinel_for<I2>
  • R1, R2 - std::ranges::input_range, std::ranges::random_access_range
  • Comp - (none)
  • Proj1, Proj2 - (none)

The Proj1, Proj2 and Comp template arguments have, the following default types for all overloads: std::identity, std::identity, ranges::less.

Additionally, each overload has the following constraints:

  • (1):
    std::indirectly_copyable<I1, I2>
    && std::sortable<I2, Comp, Proj2>
    && std::indirect_strict_weak_order<
    Comp,
    std::projected<I1, Proj1>,
    std::projected<I2, Proj2>
    >
  • (2):
    std::indirectly_copyable<ranges::iterator_t<R1>, ranges::iterator_t<R2>>
    && std::sortable<ranges::iterator_t<R2>, Comp, Proj2>
    && std::indirect_strict_weak_order<
    Comp,
    std::projected<ranges::iterator_t<R1>, Proj1>,
    std::projected<ranges::iterator_t<R2>, Proj2>
    >

With the helper types defined as follows:

template< class I, class O >
using partial_sort_copy_result = ranges::in_out_result<I, O>;

Given L1 as ranges::distance(first, last), L2 as ranges::distance(result_first, result_last) and N as ranges::min(L1, L2):

Copies the first N elements from the source range [first; last), as if it was partially sorted with respect to comp and proj1, into the destination range [result_first; result_first + N).

uwaga

The order of equal elements is not guaranteed to be preserved.

  • (1) The source range elements are projected using the function object proj1, and the destination elements are projected using the function object proj2.

  • (2) Same as (1), but uses r as the source range and result_r as the destination range, as if using ranges::begin(r) as first, ranges::end(r) as last, ranges::begin(result_r) as result_first, and ranges::end(result_r) as result_last.

The function-like entities described on this page are niebloids.

Parameters

first
last

The source range to copy from.

r

The source range to copy from.

result_first
result_last

The destination range.

result_r

The destination range.

comp

Comparison object to apply to the projected elements.

proj1

Projection to apply to the elements of the source range.

proj2

Projection to apply to the elements of the destination range.

Return value

Given L1 as ranges::distance(first, last), L2 as ranges::distance(result_first, result_last) and N as ranges::min(L1, L2):

An object of type ranges::partial_sort_copy_result initialized as follows:

{
last,
result_first + N
}.

Complexity

Given L1 as ranges::distance(first, last), L2 as ranges::distance(result_first, result_last) and N as ranges::min(L1, L2):

At most L1 * log(N) comparisons and 2 * L1 * log(N) projections.

Exceptions

(none)

Possible implementation

partial_sort_copy(1) and partial_sort_copy(2)
struct partial_sort_copy_fn
{
template<std::input_iterator I1, std::sentinel_for<I1> S1,
std::random_access_iterator I2, std::sentinel_for<I2> S2,
class Comp = ranges::less, class Proj1 = std::identity,
class Proj2 = std::identity>
requires std::indirectly_copyable<I1, I2> && std::sortable<I2, Comp, Proj2> &&
std::indirect_strict_weak_order<Comp, std::projected<I1, Proj1>,
std::projected<I2, Proj2>>
constexpr ranges::partial_sort_copy_result<I1, I2>
operator()( I1 first, S1 last, I2 result_first, S2 result_last,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} ) const
{
if (result_first == result_last)
return {std::move(ranges::next(std::move(first), std::move(last))),
std::move(result_first)};

auto out_last {result_first};
// copy first N elements
for (; !(first == last or out_last == result_last); ++out_last, ++first)
*out_last = *first;

// convert N copied elements into a max-heap
ranges::make_heap(result_first, out_last, comp, proj2);

// process the rest of the input range (if any), preserving the heap property
for (; first != last; ++first)
{
if (std::invoke(comp, std::invoke(proj1, *first),
std::invoke(proj2, *result_first)))
{
// pop out the biggest item and push in a newly found smaller one
ranges::pop_heap(result_first, out_last, comp, proj2);
*(out_last - 1) = *first;
ranges::push_heap(result_first, out_last, comp, proj2);
}
}

// first N elements in the output range is still
// a heap - convert it into a sorted range
ranges::sort_heap(result_first, out_last, comp, proj2);

return {std::move(first), std::move(out_last)};
}

template<ranges::input_range R1, ranges::random_access_range R2,
class Comp = ranges::less, class Proj1 = std::identity,
class Proj2 = std::identity>
requires std::indirectly_copyable<ranges::iterator_t<R1>, ranges::iterator_t<R2>> &&
std::sortable<ranges::iterator_t<R2>, Comp, Proj2> &&
std::indirect_strict_weak_order<Comp, std::projected<ranges::iterator_t<R1>,
Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>>
constexpr ranges::partial_sort_copy_result<ranges::borrowed_iterator_t<R1>,
ranges::borrowed_iterator_t<R2>>
operator()( R1&& r, R2&& result_r, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {} ) const
{
return (*this)(ranges::begin(r), ranges::end(r),
ranges::begin(result_r), ranges::end(result_r),
std::move(comp), std::move(proj1), std::move(proj2));
}
};

inline constexpr partial_sort_copy_fn partial_sort_copy {};

Examples

Main.cpp
#include <algorithm>
#include <forward_list>
#include <functional>
#include <iostream>
#include <ranges>
#include <string_view>
#include <vector>

void print(std::string_view rem, std::ranges::input_range auto const& v)
{
for (std::cout << rem; const auto& e : v)
std::cout << e << ' ';
std::cout << '\n';
}

int main()
{
const std::forward_list source {4, 2, 5, 1, 3};

print("Write to the smaller vector in ascending order: ", "");

std::vector dest1 {10, 11, 12};
print("const source list: ", source);
print("destination range: ", dest1);
std::ranges::partial_sort_copy(source, dest1);
print("partial_sort_copy: ", dest1);

print("Write to the larger vector in descending order:", "");

std::vector dest2 {10, 11, 12, 13, 14, 15, 16};
print("const source list: ", source);
print("destination range: ", dest2);
std::ranges::partial_sort_copy(source, dest2, std::greater{});
print("partial_sort_copy: ", dest2);
}
Output
Write to the smaller vector in ascending order:
const source list: 4 2 5 1 3
destination range: 10 11 12
partial_sort_copy: 1 2 3
Write to the larger vector in descending order:
const source list: 4 2 5 1 3
destination range: 10 11 12 13 14 15 16
partial_sort_copy: 5 4 3 2 1 15 16
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.

std::ranges::partial_sort_copy() algorithm

// (1)
constexpr partial_sort_copy_result<I1, I2>
partial_sort_copy( I1 first, S1 last, I2 result_first, S2 result_last,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );

// (2)
constexpr partial_sort_copy_result<ranges::borrowed_iterator_t<R1>,
ranges::borrowed_iterator_t<R2>>
partial_sort_copy( R1&& r, R2&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );

The type of arguments are generic and have following constraints:

  • I1, I2 - std::input_iterator, std::random_access_iterator
  • S1, S2 - std::sentinel_for<I1>, std::sentinel_for<I2>
  • R1, R2 - std::ranges::input_range, std::ranges::random_access_range
  • Comp - (none)
  • Proj1, Proj2 - (none)

The Proj1, Proj2 and Comp template arguments have, the following default types for all overloads: std::identity, std::identity, ranges::less.

Additionally, each overload has the following constraints:

  • (1):
    std::indirectly_copyable<I1, I2>
    && std::sortable<I2, Comp, Proj2>
    && std::indirect_strict_weak_order<
    Comp,
    std::projected<I1, Proj1>,
    std::projected<I2, Proj2>
    >
  • (2):
    std::indirectly_copyable<ranges::iterator_t<R1>, ranges::iterator_t<R2>>
    && std::sortable<ranges::iterator_t<R2>, Comp, Proj2>
    && std::indirect_strict_weak_order<
    Comp,
    std::projected<ranges::iterator_t<R1>, Proj1>,
    std::projected<ranges::iterator_t<R2>, Proj2>
    >

With the helper types defined as follows:

template< class I, class O >
using partial_sort_copy_result = ranges::in_out_result<I, O>;

Given L1 as ranges::distance(first, last), L2 as ranges::distance(result_first, result_last) and N as ranges::min(L1, L2):

Copies the first N elements from the source range [first; last), as if it was partially sorted with respect to comp and proj1, into the destination range [result_first; result_first + N).

uwaga

The order of equal elements is not guaranteed to be preserved.

  • (1) The source range elements are projected using the function object proj1, and the destination elements are projected using the function object proj2.

  • (2) Same as (1), but uses r as the source range and result_r as the destination range, as if using ranges::begin(r) as first, ranges::end(r) as last, ranges::begin(result_r) as result_first, and ranges::end(result_r) as result_last.

The function-like entities described on this page are niebloids.

Parameters

first
last

The source range to copy from.

r

The source range to copy from.

result_first
result_last

The destination range.

result_r

The destination range.

comp

Comparison object to apply to the projected elements.

proj1

Projection to apply to the elements of the source range.

proj2

Projection to apply to the elements of the destination range.

Return value

Given L1 as ranges::distance(first, last), L2 as ranges::distance(result_first, result_last) and N as ranges::min(L1, L2):

An object of type ranges::partial_sort_copy_result initialized as follows:

{
last,
result_first + N
}.

Complexity

Given L1 as ranges::distance(first, last), L2 as ranges::distance(result_first, result_last) and N as ranges::min(L1, L2):

At most L1 * log(N) comparisons and 2 * L1 * log(N) projections.

Exceptions

(none)

Possible implementation

partial_sort_copy(1) and partial_sort_copy(2)
struct partial_sort_copy_fn
{
template<std::input_iterator I1, std::sentinel_for<I1> S1,
std::random_access_iterator I2, std::sentinel_for<I2> S2,
class Comp = ranges::less, class Proj1 = std::identity,
class Proj2 = std::identity>
requires std::indirectly_copyable<I1, I2> && std::sortable<I2, Comp, Proj2> &&
std::indirect_strict_weak_order<Comp, std::projected<I1, Proj1>,
std::projected<I2, Proj2>>
constexpr ranges::partial_sort_copy_result<I1, I2>
operator()( I1 first, S1 last, I2 result_first, S2 result_last,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} ) const
{
if (result_first == result_last)
return {std::move(ranges::next(std::move(first), std::move(last))),
std::move(result_first)};

auto out_last {result_first};
// copy first N elements
for (; !(first == last or out_last == result_last); ++out_last, ++first)
*out_last = *first;

// convert N copied elements into a max-heap
ranges::make_heap(result_first, out_last, comp, proj2);

// process the rest of the input range (if any), preserving the heap property
for (; first != last; ++first)
{
if (std::invoke(comp, std::invoke(proj1, *first),
std::invoke(proj2, *result_first)))
{
// pop out the biggest item and push in a newly found smaller one
ranges::pop_heap(result_first, out_last, comp, proj2);
*(out_last - 1) = *first;
ranges::push_heap(result_first, out_last, comp, proj2);
}
}

// first N elements in the output range is still
// a heap - convert it into a sorted range
ranges::sort_heap(result_first, out_last, comp, proj2);

return {std::move(first), std::move(out_last)};
}

template<ranges::input_range R1, ranges::random_access_range R2,
class Comp = ranges::less, class Proj1 = std::identity,
class Proj2 = std::identity>
requires std::indirectly_copyable<ranges::iterator_t<R1>, ranges::iterator_t<R2>> &&
std::sortable<ranges::iterator_t<R2>, Comp, Proj2> &&
std::indirect_strict_weak_order<Comp, std::projected<ranges::iterator_t<R1>,
Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>>
constexpr ranges::partial_sort_copy_result<ranges::borrowed_iterator_t<R1>,
ranges::borrowed_iterator_t<R2>>
operator()( R1&& r, R2&& result_r, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {} ) const
{
return (*this)(ranges::begin(r), ranges::end(r),
ranges::begin(result_r), ranges::end(result_r),
std::move(comp), std::move(proj1), std::move(proj2));
}
};

inline constexpr partial_sort_copy_fn partial_sort_copy {};

Examples

Main.cpp
#include <algorithm>
#include <forward_list>
#include <functional>
#include <iostream>
#include <ranges>
#include <string_view>
#include <vector>

void print(std::string_view rem, std::ranges::input_range auto const& v)
{
for (std::cout << rem; const auto& e : v)
std::cout << e << ' ';
std::cout << '\n';
}

int main()
{
const std::forward_list source {4, 2, 5, 1, 3};

print("Write to the smaller vector in ascending order: ", "");

std::vector dest1 {10, 11, 12};
print("const source list: ", source);
print("destination range: ", dest1);
std::ranges::partial_sort_copy(source, dest1);
print("partial_sort_copy: ", dest1);

print("Write to the larger vector in descending order:", "");

std::vector dest2 {10, 11, 12, 13, 14, 15, 16};
print("const source list: ", source);
print("destination range: ", dest2);
std::ranges::partial_sort_copy(source, dest2, std::greater{});
print("partial_sort_copy: ", dest2);
}
Output
Write to the smaller vector in ascending order:
const source list: 4 2 5 1 3
destination range: 10 11 12
partial_sort_copy: 1 2 3
Write to the larger vector in descending order:
const source list: 4 2 5 1 3
destination range: 10 11 12 13 14 15 16
partial_sort_copy: 5 4 3 2 1 15 16
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.