Przejdź do głównej zawartości

std::ranges::partition_point() algorithm

// (1)
constexpr I
partition_point( I first, S last, Pred pred, Proj proj = {} );

// (2)
constexpr ranges::borrowed_iterator_t<R>
partition_point( R&& r, Pred pred, Proj proj = {} );

The type of arguments are generic and have the following constraints:

  • I - std::forward_iterator
  • S - std::sentinel_for<I>
  • R - std::ranges::forward_range
  • Pred:
    • (1) - std::indirect_unary_predicate<std::projected<I, Proj>>
    • (2) - std::indirect_unary_predicate<std::projected<ranges::iterator_t<R>, Proj>>
  • Proj - (none)

The Proj template argument has the following default type std::identity for all overloads.

Examines the partitioned (as if by ranges::partition) range [first; last) or r and locates the end of the first partition, that is, the projected element that does not satisfy pred or last if all projected elements satisfy pred.

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

Parameters

first
last

The range of elements to examine.

r

The range of elements to examine.

pred

The predicate to apply to the projected elements.

proj

The projection to apply to the elements.

Return value

The iterator past the end of the first partition within [first; last) or the iterator equal to last if all projected elements satisfy pred.

Complexity

Given N as ranges::distance(first, last):

Performs O(log(N)) applications of the predicate pred and projection proj.

However, if sentinels don't model std::sized_sentinel_for<I>, the number of iterator increments is O(N).

Exceptions

(none)

Possible implementation

partition_point(1) and partition_point(2)
#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>

auto print_seq = [](auto rem, auto first, auto last)
{
for (std::cout << rem; first != last; std::cout << *first++ << ' ') {}
std::cout << '\n';
};

int main()
{
std::array v {1, 2, 3, 4, 5, 6, 7, 8, 9};

auto is_even = [](int i) { return i % 2 == 0; };

std::ranges::partition(v, is_even);
print_seq("After partitioning, v: ", v.cbegin(), v.cend());

const auto pp = std::ranges::partition_point(v, is_even);
const auto i = std::ranges::distance(v.cbegin(), pp);
std::cout << "Partition point is at " << i << "; v[" << i << "] = " << *pp << '\n';

print_seq("First partition (all even elements): ", v.cbegin(), pp);
print_seq("Second partition (all odd elements): ", pp, v.cend());
}

Notes

This algorithm is a more general form of ranges::lower_bound, which can be expressed in terms of ranges::partition_point with the predicate [&](auto const& e) { return std::invoke(pred, e, value); });.

Examples

Main.cpp

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>

auto print_seq = [](auto rem, auto first, auto last)
{
for (std::cout << rem; first != last; std::cout << *first++ << ' ') {}
std::cout << '\n';
};

int main()
{
std::array v {1, 2, 3, 4, 5, 6, 7, 8, 9};

auto is_even = [](int i) { return i % 2 == 0; };

std::ranges::partition(v, is_even);
print_seq("After partitioning, v: ", v.cbegin(), v.cend());

const auto pp = std::ranges::partition_point(v, is_even);
const auto i = std::ranges::distance(v.cbegin(), pp);
std::cout << "Partition point is at " << i << "; v[" << i << "] = " << *pp << '\n';

print_seq("First partition (all even elements): ", v.cbegin(), pp);
print_seq("Second partition (all odd elements): ", pp, v.cend());
}
Possible Output
After partitioning, v: 2 4 6 8 5 3 7 1 9
Partition point is at 4; v[4] = 5
First partition (all even elements): 2 4 6 8
Second partition (all odd elements): 5 3 7 1 9
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::partition_point() algorithm

// (1)
constexpr I
partition_point( I first, S last, Pred pred, Proj proj = {} );

// (2)
constexpr ranges::borrowed_iterator_t<R>
partition_point( R&& r, Pred pred, Proj proj = {} );

The type of arguments are generic and have the following constraints:

  • I - std::forward_iterator
  • S - std::sentinel_for<I>
  • R - std::ranges::forward_range
  • Pred:
    • (1) - std::indirect_unary_predicate<std::projected<I, Proj>>
    • (2) - std::indirect_unary_predicate<std::projected<ranges::iterator_t<R>, Proj>>
  • Proj - (none)

The Proj template argument has the following default type std::identity for all overloads.

Examines the partitioned (as if by ranges::partition) range [first; last) or r and locates the end of the first partition, that is, the projected element that does not satisfy pred or last if all projected elements satisfy pred.

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

Parameters

first
last

The range of elements to examine.

r

The range of elements to examine.

pred

The predicate to apply to the projected elements.

proj

The projection to apply to the elements.

Return value

The iterator past the end of the first partition within [first; last) or the iterator equal to last if all projected elements satisfy pred.

Complexity

Given N as ranges::distance(first, last):

Performs O(log(N)) applications of the predicate pred and projection proj.

However, if sentinels don't model std::sized_sentinel_for<I>, the number of iterator increments is O(N).

Exceptions

(none)

Possible implementation

partition_point(1) and partition_point(2)
#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>

auto print_seq = [](auto rem, auto first, auto last)
{
for (std::cout << rem; first != last; std::cout << *first++ << ' ') {}
std::cout << '\n';
};

int main()
{
std::array v {1, 2, 3, 4, 5, 6, 7, 8, 9};

auto is_even = [](int i) { return i % 2 == 0; };

std::ranges::partition(v, is_even);
print_seq("After partitioning, v: ", v.cbegin(), v.cend());

const auto pp = std::ranges::partition_point(v, is_even);
const auto i = std::ranges::distance(v.cbegin(), pp);
std::cout << "Partition point is at " << i << "; v[" << i << "] = " << *pp << '\n';

print_seq("First partition (all even elements): ", v.cbegin(), pp);
print_seq("Second partition (all odd elements): ", pp, v.cend());
}

Notes

This algorithm is a more general form of ranges::lower_bound, which can be expressed in terms of ranges::partition_point with the predicate [&](auto const& e) { return std::invoke(pred, e, value); });.

Examples

Main.cpp

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>

auto print_seq = [](auto rem, auto first, auto last)
{
for (std::cout << rem; first != last; std::cout << *first++ << ' ') {}
std::cout << '\n';
};

int main()
{
std::array v {1, 2, 3, 4, 5, 6, 7, 8, 9};

auto is_even = [](int i) { return i % 2 == 0; };

std::ranges::partition(v, is_even);
print_seq("After partitioning, v: ", v.cbegin(), v.cend());

const auto pp = std::ranges::partition_point(v, is_even);
const auto i = std::ranges::distance(v.cbegin(), pp);
std::cout << "Partition point is at " << i << "; v[" << i << "] = " << *pp << '\n';

print_seq("First partition (all even elements): ", v.cbegin(), pp);
print_seq("Second partition (all odd elements): ", pp, v.cend());
}
Possible Output
After partitioning, v: 2 4 6 8 5 3 7 1 9
Partition point is at 4; v[4] = 5
First partition (all even elements): 2 4 6 8
Second partition (all odd elements): 5 3 7 1 9
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.