Defined in header
Call signature
template<std::forward_iteratorI1,std::sentinel_for<I1>S1,std::forward_iteratorI2,std::sentinel_for<I2>S2,classPred=ranges::equal_to,classProj1=std::identity,classProj2=std::identity>requiresstd::indirectly_comparable<I1,I2,Pred,Proj1,Proj2>constexprranges::subrange<I1>find_end(I1first1,S1last1,I2first2,S2last2,Predpred={},Proj1proj1={},Proj2proj2={}); (1) (since C++20)template<ranges::forward_rangeR1,ranges::forward_rangeR2,classPred=ranges::equal_to,classProj1=std::identity,classProj2=std::identity>requiresstd::indirectly_comparable<ranges::iterator_t<R1>,ranges::iterator_t<R2>,Pred,Proj1,Proj2>constexprranges::borrowed_subrange_t<R1>find_end(R1&&r1,R2&&r2,Predpred={},Proj1proj1={},Proj2proj2={}); (2) (since C++20)template</*execution-policy*/Ep,std::random_access_iteratorI1,std::sized_sentinel_for<I1>S1,std::random_access_iteratorI2,std::sized_sentinel_for<I2>S2,classPred=ranges::equal_to,classProj1=identity,classProj2=identity>requiresstd::indirectly_comparable<I1,I2,Pred,Proj1,Proj2>ranges::subrange<I1>find_end(Ep&&policy,I1first1,S1last1,I2first2,S2last2,Predpred={},Proj1proj1={},Proj2proj2={}); (3) (since C++26)template</*execution-policy*/Ep,/*sized-random-access-range*/R1,/*sized-random-access-range*/R2,classPred=ranges::equal_to,classProj1=identity,classProj2=identity>requiresstd::indirectly_comparable<ranges::iterator_t<R1>,ranges::iterator_t<R2>,Pred,Proj1,Proj2>ranges::borrowed_subrange_t<R1>find_end(Ep&&policy,R1&&r1,R2&&r2,Predpred={},Proj1proj1={},Proj2proj2={}); (4) (since C++26)For the definition of /*execution-policy*/, see
; for the definition of /*sized-random-access-range*/, see
.
Searches for the last occurrence of the target range in the source range. The elements (projected by proj1 and proj2 respectively) are compared using the binary predicate pred.
1) The source range is [first1, last1), and the target range is [first2, last2).
2) The source range is r1, and the target range is r2.
3,4) Same as (1,2), but executed according to policy.
The function-like entities described on this page are
(informally known as niebloids), that is:
Explicit template argument lists cannot be specified when calling any of them.
None of them are visible to
.
When any of them are found by
as the name to the left of the function-call operator,
is inhibited.
Parameters
first1, last1 - the iterator-sentinel pair defining the source
first2, last2 - the iterator-sentinel pair defining the target
r1 - the source range r2 - the target range pred - the predicate to be applied to the (projected) elements proj1 - the projection to be applied to the elements in the source range proj2 - the projection to be applied to the elements in the target range policy - the
to use Return value
A subrange corresponding to the last occurrence of the target range in the source range.
If the target range is empty or it does not appear in the source range, an empty range is returned.
Complexity
Given N1 as ranges::distance(first1,last1) or ranges::distance(r1), and N2 as ranges::distance(first2,last2) or ranges::distance(r2):
1,2) At most N2⋅(N1-N2+1) applications of pred, proj1 and proj2.
3,4)𝓞(N2⋅(N1-N2+1)) applications of pred, proj1 and proj2.
Exceptions
3,4) During the execution process:
If the temporary memory resources required for parallelization are not available,
is thrown.
If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for
,
is invoked).
Notes
An implementation can improve efficiency of the search if the iterator types model
by searching from the end towards the begin. Modelling
may improve the comparison speed. All this however does not change the theoretical complexity of the worst case.
Possible implementation
structfind_end_fn{template<std::forward_iteratorI1,std::sentinel_for<I1>S1,std::forward_iteratorI2,std::sentinel_for<I2>S2,classPred=ranges::equal_to,classProj1=std::identity,classProj2=std::identity>requiresstd::indirectly_comparable<I1,I2,Pred,Proj1,Proj2>constexprranges::subrange<I1>operator()(I1first1,S1last1,I2first2,S2last2,Predpred={},Proj1proj1={},Proj2proj2={})const{if(first2==last2){autolast_it=ranges::next(first1,last1);return{last_it,last_it};}autoresult=ranges::search(std::move(first1),last1,first2,last2,pred,proj1,proj2);if(result.empty())returnresult;for(;;){autonew_result=ranges::search(std::next(result.begin()),last1,first2,last2,pred,proj1,proj2);if(new_result.empty())returnresult;elseresult=std::move(new_result);}}template<ranges::forward_rangeR1,ranges::forward_rangeR2,classPred=ranges::equal_to,classProj1=std::identity,classProj2=std::identity>requiresstd::indirectly_comparable<ranges::iterator_t<R1>,ranges::iterator_t<R2>,Pred,Proj1,Proj2>constexprranges::borrowed_subrange_t<R1>operator()(R1&&r1,R2&&r2,Predpred={},Proj1proj1={},Proj2proj2={})const{return(*this)(ranges::begin(r1),ranges::next(ranges::begin(r1),ranges::end(r1)),ranges::begin(r2),ranges::next(ranges::begin(r2),ranges::end(r2)),std::move(pred),std::move(proj1),std::move(proj2));}};inlineconstexprfind_end_fnfind_end{};Example
Run this code
#include<algorithm>#include<array>#include<cctype>#include<iostream>#include<ranges>#include<string_view>voidprint(constautohaystack,constautoneedle){constautopos=std::distance(haystack.begin(),needle.begin());std::cout<<"In \"";for(constautoc:haystack)std::cout<<c;std::cout<<"\" found \"";for(constautoc:needle)std::cout<<c;std::cout<<"\" at position ["<<pos<<".."<<pos+needle.size()<<")\n"<<std::string(4+pos,' ')<<std::string(needle.size(),'^')<<'\n';}intmain(){usingnamespacestd::literals;usingstd::ranges::find_end;constexprautosecret{"password password word..."sv};constexprautowanted{"password"sv};constexprautofound1=find_end(secret.cbegin(),secret.cend(),wanted.cbegin(),wanted.cend());print(secret,found1);constexprautofound2=find_end(secret,"word"sv);print(secret,found2);constautofound3=find_end(secret,"ORD"sv,[](constcharx,constchary){// uses a binary predicatereturnstd::tolower(x)==std::tolower(y);});print(secret,found3);constautofound4=find_end(secret,"SWORD"sv,{},{},[](charc){returnstd::tolower(c);});// projects the 2nd rangeprint(secret,found4);static_assert(find_end(secret,"PASS"sv).empty());// => not found}Output:
In "password password word..." found "password" at position [9..17) ^^^^^^^^ In "password password word..." found "word" at position [18..22) ^^^^ In "password password word..." found "ord" at position [19..22) ^^^ In "password password word..." found "sword" at position [12..17) ^^^^^ See also
finds the last sequence of elements in a certain range
(function template)
ranges::find_lastranges::find_last_ifranges::find_last_if_not
(C++23)(C++23)(C++23)
finds the last element satisfying specific criteria
(algorithm function object)
ranges::findranges::find_ifranges::find_if_not
(C++20)(C++20)(C++20)
finds the first element satisfying specific criteria
(algorithm function object)
(C++20)
searches for any one of a set of elements
(algorithm function object)
(C++20)
finds the first two adjacent items that are equal (or satisfy a given predicate)
(algorithm function object)
(C++20)
searches for the first occurrence of a range of elements
(algorithm function object)
(C++20)
searches for the first occurrence of a number consecutive copies of an element in a range
(algorithm function object)