Przejdź do głównej zawartości

std::ranges::find() algorithm

// (1)
constexpr I
find( I first, S last, const T& value, Proj proj = {} );

// (2)
constexpr ranges::borrowed_iterator_t<R>
find( R&& r, const T& value, Proj proj = {} );

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

  • I - std::input_iterator
  • S - std::sentinel_for<I>
  • T - (none)
  • Proj - (none)
  • (2) - R - std::ranges::input_range

The Proj template argument has a default type of std::identity for all overloads.

Additionally, each overload has the following constraints:

  • (1) - indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>>
  • (2) - indirect_binary_predicate<ranges::equal_to, projected<ranges::iterator_t<R>, Proj>, const T*>

(The std:: namespace was ommitted here for readability)

Returns the last element in the range [first; last) that satisfies specific criteria:

  • (1) Searches for an element equal to value (using operator==)

  • (2) Same as (1), but uses r as the source 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.

Parameters

first
last

The range of elements to apply the function to.

r

The range of elements to apply the function to.

value

Value to compare the elements too.

proj

Projection to apply to the elements.

Return value

  • (1) Let i be the last iterator in the range [first; last) for which *i == value is true. Returns a value of type ranges::subrange<I> initialized as follows:

    {
    i,
    last
    }

    or { last, last } if no such iterator is found.

  • (2) Same as (1) but the return type is ranges::borrowed_subrange_t<I>.

Complexity

Exactly last - first applications of the predicate and projection.

Exceptions

(none)

Possible implementation

These implementations only show the slower algorithm used when I models forward_iterator.

find(1) and find(2)
struct find_last_fn
{
template<std::forward_iterator I, std::sentinel_for<I> S,
class T, class Proj = std::identity>
requires std::indirect_binary_predicate<ranges::equal_to, std::projected<I, Proj>,
const T*>
constexpr ranges::subrange<I>
operator()(I first, S last, const T &value, Proj proj = {}) const
{
// Note: if I is mere forward_iterator, we may only go from begin to end.
I found {};
for (; first != last; ++first)
if (std::invoke(proj, *first) == value)
found = first;

if (found == I {})
return {first, first};

return {found, std::ranges::next(found, last)};
}

template<ranges::forward_range R, class T, class Proj = std::identity>
requires std::indirect_binary_predicate<ranges::equal_to,
std::projected<ranges::iterator_t<R>, Proj>,
const T*>
constexpr ranges::borrowed_subrange_t<R>
operator()(R&& r, const T &value, Proj proj = {}) const
{
return this->operator()(ranges::begin(r), ranges::end(r), value, std::ref(proj));
}
};

inline constexpr find_last_fn find_last;

Notes

ranges::find_last has better efficiency on common implementations if I models bidirectional_iterator or (better) random_access_iterator.

Examples

Main.cpp
#include <algorithm>
#include <forward_list>
#include <iomanip>
#include <iostream>
#include <string_view>

int main()
{
constexpr static auto v = {1, 2, 3, 1, 2, 3, 1, 2};

{
constexpr auto i1 = std::ranges::find_last(v.begin(), v.end(), 3);
constexpr auto i2 = std::ranges::find_last(v, 3);
static_assert(std::ranges::distance(v.begin(), i1.begin()) == 5);
static_assert(std::ranges::distance(v.begin(), i2.begin()) == 5);
}
{
constexpr auto i1 = std::ranges::find_last(v.begin(), v.end(), -3);
constexpr auto i2 = std::ranges::find_last(v, -3);
static_assert(i1.begin() == v.end());
static_assert(i2.begin() == v.end());
}

auto abs = [](int x) { return x < 0 ? -x : x; };

{
auto pred = [](int x) { return x == 3; };
constexpr auto i1 = std::ranges::find_last_if(v.begin(), v.end(), pred, abs);
constexpr auto i2 = std::ranges::find_last_if(v, pred, abs);
static_assert(std::ranges::distance(v.begin(), i1.begin()) == 5);
static_assert(std::ranges::distance(v.begin(), i2.begin()) == 5);
}
{
auto pred = [](int x) { return x == -3; };
constexpr auto i1 = std::ranges::find_last_if(v.begin(), v.end(), pred, abs);
constexpr auto i2 = std::ranges::find_last_if(v, pred, abs);
static_assert(i1.begin() == v.end());
static_assert(i2.begin() == v.end());
}

{
auto pred = [](int x) { return x == 1 or x == 2; };
constexpr auto i1 = std::ranges::find_last_if_not(v.begin(), v.end(), pred, abs);
constexpr auto i2 = std::ranges::find_last_if_not(v, pred, abs);
static_assert(std::ranges::distance(v.begin(), i1.begin()) == 5);
static_assert(std::ranges::distance(v.begin(), i2.begin()) == 5);
}
{
auto pred = [](int x) { return x == 1 or x == 2 or x == 3; };
constexpr auto i1 = std::ranges::find_last_if_not(v.begin(), v.end(), pred, abs);
constexpr auto i2 = std::ranges::find_last_if_not(v, pred, abs);
static_assert(i1.begin() == v.end());
static_assert(i2.begin() == v.end());
}

using P = std::pair<std::string_view, int>;
std::forward_list<P> list
{
{"one", 1}, {"two", 2}, {"three", 3},
{"one", 4}, {"two", 5}, {"three", 6},
};
auto cmp_one = [](const std::string_view &s) { return s == "one"; };

// find latest element that satisfy the comparator, and projecting pair::first
const auto subrange = std::ranges::find_last_if(list, cmp_one, &P::first);

// print the found element and the "tail" after it
for (P const& e : subrange)
std::cout << '{' << std::quoted(e.first) << ", " << e.second << "} ";
std::cout << '\n';
}
Output
{"one", 4} {"two", 5} {"three", 6}
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::find() algorithm

// (1)
constexpr I
find( I first, S last, const T& value, Proj proj = {} );

// (2)
constexpr ranges::borrowed_iterator_t<R>
find( R&& r, const T& value, Proj proj = {} );

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

  • I - std::input_iterator
  • S - std::sentinel_for<I>
  • T - (none)
  • Proj - (none)
  • (2) - R - std::ranges::input_range

The Proj template argument has a default type of std::identity for all overloads.

Additionally, each overload has the following constraints:

  • (1) - indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>>
  • (2) - indirect_binary_predicate<ranges::equal_to, projected<ranges::iterator_t<R>, Proj>, const T*>

(The std:: namespace was ommitted here for readability)

Returns the last element in the range [first; last) that satisfies specific criteria:

  • (1) Searches for an element equal to value (using operator==)

  • (2) Same as (1), but uses r as the source 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.

Parameters

first
last

The range of elements to apply the function to.

r

The range of elements to apply the function to.

value

Value to compare the elements too.

proj

Projection to apply to the elements.

Return value

  • (1) Let i be the last iterator in the range [first; last) for which *i == value is true. Returns a value of type ranges::subrange<I> initialized as follows:

    {
    i,
    last
    }

    or { last, last } if no such iterator is found.

  • (2) Same as (1) but the return type is ranges::borrowed_subrange_t<I>.

Complexity

Exactly last - first applications of the predicate and projection.

Exceptions

(none)

Possible implementation

These implementations only show the slower algorithm used when I models forward_iterator.

find(1) and find(2)
struct find_last_fn
{
template<std::forward_iterator I, std::sentinel_for<I> S,
class T, class Proj = std::identity>
requires std::indirect_binary_predicate<ranges::equal_to, std::projected<I, Proj>,
const T*>
constexpr ranges::subrange<I>
operator()(I first, S last, const T &value, Proj proj = {}) const
{
// Note: if I is mere forward_iterator, we may only go from begin to end.
I found {};
for (; first != last; ++first)
if (std::invoke(proj, *first) == value)
found = first;

if (found == I {})
return {first, first};

return {found, std::ranges::next(found, last)};
}

template<ranges::forward_range R, class T, class Proj = std::identity>
requires std::indirect_binary_predicate<ranges::equal_to,
std::projected<ranges::iterator_t<R>, Proj>,
const T*>
constexpr ranges::borrowed_subrange_t<R>
operator()(R&& r, const T &value, Proj proj = {}) const
{
return this->operator()(ranges::begin(r), ranges::end(r), value, std::ref(proj));
}
};

inline constexpr find_last_fn find_last;

Notes

ranges::find_last has better efficiency on common implementations if I models bidirectional_iterator or (better) random_access_iterator.

Examples

Main.cpp
#include <algorithm>
#include <forward_list>
#include <iomanip>
#include <iostream>
#include <string_view>

int main()
{
constexpr static auto v = {1, 2, 3, 1, 2, 3, 1, 2};

{
constexpr auto i1 = std::ranges::find_last(v.begin(), v.end(), 3);
constexpr auto i2 = std::ranges::find_last(v, 3);
static_assert(std::ranges::distance(v.begin(), i1.begin()) == 5);
static_assert(std::ranges::distance(v.begin(), i2.begin()) == 5);
}
{
constexpr auto i1 = std::ranges::find_last(v.begin(), v.end(), -3);
constexpr auto i2 = std::ranges::find_last(v, -3);
static_assert(i1.begin() == v.end());
static_assert(i2.begin() == v.end());
}

auto abs = [](int x) { return x < 0 ? -x : x; };

{
auto pred = [](int x) { return x == 3; };
constexpr auto i1 = std::ranges::find_last_if(v.begin(), v.end(), pred, abs);
constexpr auto i2 = std::ranges::find_last_if(v, pred, abs);
static_assert(std::ranges::distance(v.begin(), i1.begin()) == 5);
static_assert(std::ranges::distance(v.begin(), i2.begin()) == 5);
}
{
auto pred = [](int x) { return x == -3; };
constexpr auto i1 = std::ranges::find_last_if(v.begin(), v.end(), pred, abs);
constexpr auto i2 = std::ranges::find_last_if(v, pred, abs);
static_assert(i1.begin() == v.end());
static_assert(i2.begin() == v.end());
}

{
auto pred = [](int x) { return x == 1 or x == 2; };
constexpr auto i1 = std::ranges::find_last_if_not(v.begin(), v.end(), pred, abs);
constexpr auto i2 = std::ranges::find_last_if_not(v, pred, abs);
static_assert(std::ranges::distance(v.begin(), i1.begin()) == 5);
static_assert(std::ranges::distance(v.begin(), i2.begin()) == 5);
}
{
auto pred = [](int x) { return x == 1 or x == 2 or x == 3; };
constexpr auto i1 = std::ranges::find_last_if_not(v.begin(), v.end(), pred, abs);
constexpr auto i2 = std::ranges::find_last_if_not(v, pred, abs);
static_assert(i1.begin() == v.end());
static_assert(i2.begin() == v.end());
}

using P = std::pair<std::string_view, int>;
std::forward_list<P> list
{
{"one", 1}, {"two", 2}, {"three", 3},
{"one", 4}, {"two", 5}, {"three", 6},
};
auto cmp_one = [](const std::string_view &s) { return s == "one"; };

// find latest element that satisfy the comparator, and projecting pair::first
const auto subrange = std::ranges::find_last_if(list, cmp_one, &P::first);

// print the found element and the "tail" after it
for (P const& e : subrange)
std::cout << '{' << std::quoted(e.first) << ", " << e.second << "} ";
std::cout << '\n';
}
Output
{"one", 4} {"two", 5} {"three", 6}
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.