| 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 | ||
| (1) | ||
template<std::forward_iterator I,std::sentinel_for<I> S,class T, class Pred=ranges::equal_to,class Proj=std::identity> | (since C++20) (until C++26) | |
template<std::forward_iterator I,std::sentinel_for<I> S, class Pred=ranges::equal_to,class Proj=std::identity, | (since C++26) | |
| (2) | ||
template<ranges::forward_range R,class T, class Pred=ranges::equal_to,class Proj=std::identity> | (since C++20) (until C++26) | |
template<ranges::forward_range R, class Pred=ranges::equal_to,class Proj=std::identity, | (since C++26) | |
[first, last) for thefirst sequence ofcount elements whose projected values are each equal to the givenvalue according to the binary predicatepred.The function-like entities described on this page arealgorithm function objects (informally known asniebloids), that is:
Contents |
| first, last | - | the iterator-sentinel pair defining therange of elements to examine (akahaystack) |
| r | - | the range of elements to examine (akahaystack) |
| count | - | the length of the sequence to search for |
| value | - | the value to search for (akaneedle) |
| pred | - | the binary predicate that compares the projected elements withvalue |
| proj | - | the projection to apply to the elements of the range to examine |
[first, last) that designate the found subsequence.If no such subsequence is found, returnsstd::ranges::subrange{last, last}.
Ifcount<=0, returnsstd::ranges::subrange{first, first}.Linear: at mostranges::distance(first, last) applications of the predicate and the projection.
An implementation can improve efficiency of the searchin average if the iterators modelstd::random_access_iterator.
| Feature-test macro | Value | Std | Feature |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type | 202403 | (C++26) | List-initialization for algorithms |
struct search_n_fn{template<std::forward_iterator I,std::sentinel_for<I> S,class Pred=ranges::equal_to,class Proj=std::identity,class T= std::projected_value_t<I, Proj>> requiresstd::indirectly_comparable<I,const T*, Pred, Proj>constexprranges::subrange<I> operator()(I first, S last,std::iter_difference_t<I> count,const T& value, Pred pred={}, Proj proj={})const{if(count<=0)return{first, first};for(; first!= last;++first)if(std::invoke(pred,std::invoke(proj,*first), value)){ I start= first;std::iter_difference_t<I> n{1};for(;;){if(n++== count)return{start,std::next(first)};// foundif(++first== last)return{first, first};// not foundif(!std::invoke(pred,std::invoke(proj,*first), value))break;// not equ to value}}return{first, first};} template<ranges::forward_range R,class Pred=ranges::equal_to,class Proj=std::identity,class T= std::projected_value_t<ranges::iterator_t<R>, Proj>> requiresstd::indirectly_comparable<ranges::iterator_t<R>,const T*, Pred, Proj>constexprranges::borrowed_subrange_t<R> operator()(R&& r,ranges::range_difference_t<R> count,const T& value, Pred pred={}, Proj proj={})const{return(*this)(ranges::begin(r),ranges::end(r), std::move(count), value, std::move(pred), std::move(proj));}}; inlineconstexpr search_n_fn search_n{}; |
#include <algorithm>#include <cassert>#include <complex>#include <iomanip>#include <iostream>#include <iterator>#include <string>#include <vector> int main(){namespace ranges= std::ranges; staticconstexprauto nums={1,2,2,3,4,1,2,2,2,1};constexprint count{3};constexprint value{2};typedefint count_t, value_t; constexprauto result1= ranges::search_n( nums.begin(), nums.end(), count, value); static_assert// found( result1.size()== count&&std::distance(nums.begin(), result1.begin())==6&&std::distance(nums.begin(), result1.end())==9); constexprauto result2= ranges::search_n(nums, count, value); static_assert// found( result2.size()== count&&std::distance(nums.begin(), result2.begin())==6&&std::distance(nums.begin(), result2.end())==9); constexprauto result3= ranges::search_n(nums, count, value_t{5}); static_assert// not found( result3.size()==0&& result3.begin()== result3.end()&& result3.end()== nums.end()); constexprauto result4= ranges::search_n(nums, count_t{0}, value_t{1}); static_assert// not found( result4.size()==0&& result4.begin()== result4.end()&& result4.end()== nums.begin()); constexprchar symbol{'B'};auto to_ascii=[](constint z)->char{return'A'+ z-1;};auto is_equ=[](constchar x,constchar y){return x== y;}; std::cout<<"Find a sub-sequence "<<std::string(count, symbol)<<" in the "; std::ranges::transform(nums,std::ostream_iterator<char>(std::cout,""), to_ascii);std::cout<<'\n'; auto result5= ranges::search_n(nums, count, symbol, is_equ, to_ascii);if(not result5.empty())std::cout<<"Found at position "<<ranges::distance(nums.begin(), result5.begin())<<'\n'; std::vector<std::complex<double>> nums2{{4,2},{4,2},{1,3}};#ifdef __cpp_lib_algorithm_default_value_typeauto it= ranges::search_n(nums2,2,{4,2});#elseauto it= ranges::search_n(nums2,2,std::complex<double>{4,2});#endifassert(it.size()==2);}
Output:
Find a sub-sequence BBB in the ABBCDABBBAFound at position 6
(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++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 range of elements (algorithm function object)[edit] |
| searches for the first occurrence of a number consecutive copies of an element in a range (function template)[edit] |
