| 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). Elements are compared using binary predicatepred after being projected withproj2 andproj1, respectively.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 apply to the projected 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) (akaneedle) in the range[first1, last1) (akahaystack), after application of the projectionsproj1 andproj2 to the elements of both sequences respectively with consequencing application of the binary predicatepred to compare projected elements.If no such occurrence is found,ranges::subrange{last1, last1} is returned.
If the range to search for (akaneedle) is empty, that isfirst2== last2, then theranges::subrange{first1, first1} is returned.At mostS * N applications of the corresponding predicate and each projection, where
(1)S=ranges::distance(first2, last2) andN=ranges::distance(first1, last1);
(2)S=ranges::distance(r2) andN=ranges::distance(r1).
struct search_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{for(;;++first1){ I1 it1= first1;for(I2 it2= first2;;++it1,++it2){if(it2== last2)return{first1, it1};if(it1== last1)return{it1, it1};if(!std::invoke(pred,std::invoke(proj1,*it1),std::invoke(proj2,*it2)))break;}}} 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 search_fn search{}; |
#include <algorithm>#include <cctype>#include <iostream>#include <iterator>#include <string_view> usingnamespace std::literals; void print(int id,constauto& haystack,constauto& needle,constauto& found){std::cout<< id<<") search(\""<< haystack<<"\",\""<< needle<<"\"); ";constauto first=std::distance(haystack.begin(), found.begin());constauto last=std::distance(haystack.begin(), found.end());if(found.empty())std::cout<<"not found;";else{std::cout<<"found:\"";for(constauto x: found)std::cout<< x;std::cout<<"\";";}std::cout<<" subrange: {"<< first<<", "<< last<<"}\n";} int main(){constexprauto haystack{"abcd abcd"sv};constexprauto needle{"bcd"sv}; // the search uses iterator pairs begin()/end():constexprauto found1= std::ranges::search( haystack.begin(), haystack.end(), needle.begin(), needle.end()); print(1, haystack, needle, found1); // the search uses ranges r1, r2:constexprauto found2= std::ranges::search(haystack, needle); print(2, haystack, needle, found2); // 'needle' range is empty:constexprauto none{""sv};constexprauto found3= std::ranges::search(haystack, none); print(3, haystack, none, found3); // 'needle' will not be found:constexprauto awl{"efg"sv};constexprauto found4= std::ranges::search(haystack, awl); print(4, haystack, awl, found4); // the search uses custom comparator and projections:constexprauto bodkin{"234"sv};auto found5= std::ranges::search(haystack, bodkin,[](constint x,constint y){return x== y;},// pred[](constint x){returnstd::toupper(x);},// proj1[](constint y){return y+'A'-'1';});// proj2 print(5, haystack, bodkin, found5);}
Output:
1) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}2) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}3) search("abcd abcd", ""); not found; subrange: {0, 0}4) search("abcd abcd", "efg"); not found; subrange: {9, 9}5) search("abcd abcd", "234"); found: "bcd"; subrange: {1, 4}(C++20) | finds the first two adjacent items that are equal (or satisfy a given predicate) (algorithm function object)[edit] |
(C++20)(C++20)(C++20) | finds the first element satisfying specific criteria (algorithm function object)[edit] |
(C++20) | finds the last sequence of elements in a certain range (algorithm function object)[edit] |
(C++20) | searches for any one of a set of elements (algorithm function object)[edit] |
(C++23)(C++23) | checks if the range contains the given element or subrange (algorithm function object)[edit] |
(C++20) | returnstrue if one sequence is a subsequence of another (algorithm function object)[edit] |
(C++20) | finds the first position where two ranges differ (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] |
| searches for the first occurrence of a range of elements (function template)[edit] |
