std::ranges::find_first_of() algorithm
- since C++20
- Simplified
- Detailed
// (1)
constexpr I1 find_first_of( I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
// (2)
constexpr ranges::borrowed_iterator_t<R1>
find_first_of(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
The type of arguments are generic and have the following constraints:
I1
,I2
-std::input_iterator
,std::forward_iterator
S1
,S2
-std::sentinel_for<I1>
,std::sentinel_for<I2>
Pred
- (none)Proj1
,Proj2
- (none)R1
,R2
-std::ranges::input_range
,std::ranges::forward_range
The Proj1
and Proj2
template arguments have a default type of std::identity
for all overloads.
Additionally, each overload has the following constraints:
- (1) -
indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
- (2) -
indirectly_comparable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, Pred, Proj1, Proj2>
(The std::
namespace was ommitted here for readability)
// (1)
template<
std::input_iterator I1,
std::sentinel_for<I1> S1,
std::forward_iterator I2,
std::sentinel_for<I2> S2,
class Pred = ranges::equal_to,
class Proj1 = std::identity,
class Proj2 = std::identity
>
requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr I1 find_first_of( I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
// (2)
template<
ranges::input_range R1,
ranges::forward_range R2,
class Pred = ranges::equal_to,
class Proj1 = std::identity,
class Proj2 = std::identity
>
requires std::indirectly_comparable< ranges::iterator_t<R1>,
ranges::iterator_t<R2>,
Pred, Proj1, Proj2 >
constexpr ranges::borrowed_iterator_t<R1>
find_first_of(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
-
(1) Searches the range [
first1
;last1
) for any of the elements in the range [first2
;last2
), after projecting the ranges withproj1
andproj2
respectively. The projected elements are compared using the binary predicatepred
. -
(2) Same as (1), but uses
r1
as the first source range andr2
as the second source range, as if usingranges::begin(r1)
asfirst1
,ranges::end(r1)
aslast1
,ranges::begin(r2)
asfirst2
andranges::end(r2)
aslast2
.
The function-like entities described on this page are niebloids.
Parameters
first1 last1 | The range of elements to examine. |
first2 last2 | The range of elements to search for. |
r1 | The range of elements to examine. |
r2 | The range of elements to search for. |
pred | Binary predicate to compare the elements with. |
proj1 | Projection to apply to the elements in the first range. |
proj2 | Projection to apply to the elements in the second range. |
Return value
Iterator to the first element in the range [first1
; last1
) that is equal to an element from the range [first2
; last2
) after projection.
If no such element is found, an iterator comparing equal to last1
is returned.
Complexity
Given:
- (1)
S
asranges::distance(first2, last2)
andN
asranges::distance(first1, last1)
- (2)
S
asranges::distance(r2)
andN
asranges::distance(r1)
At most S * N applications of the predicate and each projection.
Exceptions
(none)
Possible implementation
ranges::find_first_of(1) and ranges::find_first_of(2)
struct find_first_of_fn
{
template<std::input_iterator I1, std::sentinel_for<I1> S1,
std::forward_iterator I2, std::sentinel_for<I2> S2,
class Pred = ranges::equal_to,
class Proj1 = std::identity,
class Proj2 = std::identity>
requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr I1 operator()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {}) const
{
for (; first1 != last1; ++first1)
for (auto i = first2; i != last2; ++i)
if (std::invoke(pred, std::invoke(proj1, *first1), std::invoke(proj2, *i)))
return first1;
return first1;
}
template<ranges::input_range R1, ranges::forward_range R2,
class Pred = ranges::equal_to,
class Proj1 = std::identity,
class Proj2 = std::identity>
requires std::indirectly_comparable<ranges::iterator_t<R1>,
ranges::iterator_t<R2>,
Pred, Proj1, Proj2>
constexpr ranges::borrowed_iterator_t<R1>
operator()(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {}) const
{
return (*this)(ranges::begin(r1), ranges::end(r1),
ranges::begin(r2), ranges::end(r2),
std::move(pred), std::move(proj1), std::move(proj2));
}
;
inline constexpr find_first_of_fn find_first_of {};
Examples
#include <algorithm>
#include <iostream>
#include <iterator>
int main()
{
namespace rng = std::ranges;
constexpr static auto haystack = {1, 2, 3, 4};
constexpr static auto needles = {0, 3, 4, 3};
constexpr auto found1 = rng::find_first_of(haystack.begin(), haystack.end(),
needles.begin(), needles.end());
static_assert(std::distance(haystack.begin(), found1) == 2);
constexpr auto found2 = rng::find_first_of(haystack, needles);
static_assert(std::distance(haystack.begin(), found2) == 2);
constexpr static auto negatives = {-6, -3, -4, -3};
constexpr auto not_found = rng::find_first_of(haystack, negatives);
static_assert(not_found == haystack.end());
constexpr auto found3 = rng::find_first_of(haystack, negatives,
[](int x, int y) { return x == -y; }); // uses a binary comparator
static_assert(std::distance(haystack.begin(), found3) == 2);
struct P { int x, y; };
constexpr static auto p1 = { P{1, -1}, P{2, -2}, P{3, -3}, P{4, -4} };
constexpr static auto p2 = { P{5, -5}, P{6, -3}, P{7, -5}, P{8, -3} };
// Compare only P::y data members by projecting them:
const auto found4 = rng::find_first_of(p1, p2, {}, &P::y, &P::y);
std::cout << "First equivalent element {" << found4->x << ", " << found4->y
<< "} was found at position " << std::distance(p1.begin(), found4)
<< ".\n";
}
First equivalent element {3, -3} was found at position 2.
Hover to see the original license.