| Constrained algorithms and algorithms on ranges(C++20) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Constrained algorithms, e.g.ranges::copy,ranges::sort, ... | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Execution policies(C++17) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Numeric operations | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Operations on uninitialized memory | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
std::ranges| Non-modifying sequence operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Modifying sequence operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Partitioning operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Sorting operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Binary search operations (on sorted ranges) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Set operations (on sorted ranges) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Heap operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Minimum/maximum operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Permutation operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Fold operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Operations on uninitialized storage | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Return types | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
Defined in header <algorithm> | ||
Call signature | ||
template<std::forward_iterator I1,std::sentinel_for<I1> S1, std::forward_iterator I2,std::sentinel_for<I2> S2, | (1) | (since C++20) |
template<ranges::forward_range R1,ranges::forward_range R2, class Pred=ranges::equal_to, | (2) | (since C++20) |
[first2, last2) in the range[first1, last1), after projection withproj1 andproj2 respectively. The projected elements are compared using the binary predicatepred.The function-like entities described on this page arealgorithm function objects (informally known asniebloids), that is:
Contents |
| first1, last1 | - | the iterator-sentinel pair defining therange of elements to examine (akahaystack) |
| first2, last2 | - | the iterator-sentinel pair defining therange of elements to search for (akaneedle) |
| r1 | - | the range of elements to examine (akahaystack) |
| r2 | - | the range of elements to search for (akaneedle) |
| pred | - | binary predicate to compare the elements |
| proj1 | - | projection to apply to the elements in the first range |
| proj2 | - | projection to apply to the elements in the second range |
[first2, last2) in range[first1, last1) (after projections withproj1 andproj2). If[first2, last2) is empty or if no such sequence is found, the return value is effectively initialized with{last1, last1}.At most\(\scriptsize S\cdot(N-S+1)\)S·(N-S+1) applications of the corresponding predicate and each projection, where\(\scriptsize S\)S isranges::distance(first2, last2) and\(\scriptsize N\)N isranges::distance(first1, last1) for(1), or\(\scriptsize S\)S isranges::distance(r2) and\(\scriptsize N\)N isranges::distance(r1) for(2).
An implementation can improve efficiency of the search if the input iterators modelstd::bidirectional_iterator by searching from the end towards the begin. Modelling thestd::random_access_iterator may improve the comparison speed. All this however does not change the theoretical complexity of the worst case.
struct find_end_fn{template<std::forward_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> requiresstd::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>constexprranges::subrange<I1> operator()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred={}, Proj1 proj1={}, Proj2 proj2={})const{if(first2== last2){auto last_it=ranges::next(first1, last1);return{last_it, last_it};}auto result=ranges::search( std::move(first1), last1, first2, last2, pred, proj1, proj2); if(result.empty())return result; for(;;){auto new_result=ranges::search(std::next(result.begin()), last1, first2, last2, pred, proj1, proj2);if(new_result.empty())return result;else result= std::move(new_result);}} template<ranges::forward_range R1,ranges::forward_range R2,class Pred=ranges::equal_to,class Proj1=std::identity,class Proj2=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, 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));}}; inlineconstexpr find_end_fn find_end{}; |
#include <algorithm>#include <array>#include <cctype>#include <iostream>#include <ranges>#include <string_view> void print(constauto haystack,constauto needle){constauto pos=std::distance(haystack.begin(), needle.begin());std::cout<<"In\"";for(constauto c: haystack)std::cout<< c;std::cout<<"\" found\"";for(constauto c: needle)std::cout<< c;std::cout<<"\" at position ["<< pos<<".."<< pos+ needle.size()<<")\n"<<std::string(4+ pos,' ')<<std::string(needle.size(),'^')<<'\n';} int main(){usingnamespace std::literals;constexprauto secret{"password password word..."sv};constexprauto wanted{"password"sv}; constexprauto found1= std::ranges::find_end( secret.cbegin(), secret.cend(), wanted.cbegin(), wanted.cend()); print(secret, found1); constexprauto found2= std::ranges::find_end(secret,"word"sv); print(secret, found2); constauto found3= std::ranges::find_end(secret,"ORD"sv,[](constchar x,constchar y){// uses a binary predicatereturnstd::tolower(x)==std::tolower(y);}); print(secret, found3); constauto found4= std::ranges::find_end(secret,"SWORD"sv,{},{},[](char c){returnstd::tolower(c);});// projects the 2nd range print(secret, found4); static_assert(std::ranges::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) ^^^^^
(C++23)(C++23)(C++23) | finds the last element satisfying specific criteria (algorithm function object)[edit] |
(C++20)(C++20)(C++20) | finds the first element satisfying specific criteria (algorithm function object)[edit] |
(C++20) | searches for any one of a set of elements (algorithm function object)[edit] |
(C++20) | finds the first two adjacent items that are equal (or satisfy a given predicate) (algorithm function object)[edit] |
(C++20) | searches for the first occurrence of a range of elements (algorithm function object)[edit] |
(C++20) | searches for the first occurrence of a number consecutive copies of an element in a range (algorithm function object)[edit] |
| finds the last sequence of elements in a certain range (function template)[edit] |
