| 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::input_iterator I1,std::sentinel_for<I1> S1, std::input_iterator I2,std::sentinel_for<I2> S2, | (1) | (since C++20) |
template<ranges::input_range R1,ranges::input_range R2, std::weakly_incrementable O,class Comp=ranges::less, | (2) | (since C++20) |
Helper types | ||
template<class I,class O> using set_difference_result=ranges::in_out_result<I, O>; | (3) | (since C++20) |
Copies the elements from the sorted input range[first1, last1) which are not found in the sorted input range[first2, last2) to the output range beginning atresult.
The behavior is undefined if
The function-like entities described on this page arealgorithm function objects (informally known asniebloids), that is:
Contents |
| first1, last1 | - | the iterator-sentinel pair defining the first sorted inputrange of elements |
| first2, last2 | - | the iterator-sentinel pair defining the second sorted inputrange of elements |
| r1 | - | the first sorted input range |
| r2 | - | the second sorted input range |
| result | - | the beginning of the output range |
| comp | - | comparator 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 |
{last1, result_last}, whereresult_last is the end of the constructed range.
At most\(\scriptsize 2\cdot(N_1+N_2)-1\)2·(N1+N2)-1 comparisons and applications of each projection, where\(\scriptsize N_1\)N1 and\(\scriptsize N_2\)N2 areranges::distance(first1, last1) andranges::distance(first2, last2), respectively.
struct set_difference_fn{template<std::input_iterator I1,std::sentinel_for<I1> S1,std::input_iterator I2,std::sentinel_for<I2> S2,std::weakly_incrementable O,class Comp=ranges::less,class Proj1=std::identity,class Proj2=std::identity> requiresstd::mergeable<I1, I2, O, Comp, Proj1, Proj2>constexpr ranges::set_difference_result<I1, O> operator()(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp={}, Proj1 proj1={}, Proj2 proj2={})const{while(!(first1== last1 or first2== last2)){if(std::invoke(comp,std::invoke(proj1,*first1),std::invoke(proj2,*first2))){*result=*first1;++first1;++result;}elseif(std::invoke(comp,std::invoke(proj2,*first2),std::invoke(proj1,*first1)))++first2;else{++first1;++first2;}}returnranges::copy(std::move(first1), std::move(last1), std::move(result));} template<ranges::input_range R1,ranges::input_range R2,std::weakly_incrementable O,class Comp=ranges::less,class Proj1=std::identity,class Proj2=std::identity> requiresstd::mergeable<ranges::iterator_t<R1>,ranges::iterator_t<R2>, O, Comp, Proj1, Proj2>constexpr ranges::set_difference_result<ranges::borrowed_iterator_t<R1>, O> operator()(R1&& r1, R2&& r2, O result, Comp comp={}, Proj1 proj1={}, Proj2 proj2={})const{return(*this)(ranges::begin(r1),ranges::end(r1),ranges::begin(r2),ranges::end(r2), std::move(result), std::move(comp), std::move(proj1), std::move(proj2));}}; inlineconstexpr set_difference_fn set_difference{}; |
#include <algorithm>#include <cassert>#include <iostream>#include <iterator>#include <string_view>#include <vector> auto print=[](constauto& v,std::string_view end=""){std::cout<<"{ ";for(auto n{v.size()};auto i: v)std::cout<< i<<(--n?", ":" ");std::cout<<"} "<< end;}; struct Order// a struct with some very interesting data{int order_id{}; friendstd::ostream& operator<<(std::ostream& os,const Order& ord){return os<<'{'<< ord.order_id<<'}';}}; int main(){constauto v1={1,2,5,5,5,9};constauto v2={2,5,7};std::vector<int> diff{}; std::ranges::set_difference(v1, v2,std::back_inserter(diff)); print(v1,"∖ "); print(v2,"= "); print(diff,"\n\n"); // We want to know which orders "cut" between old and new states:conststd::vector<Order> old_orders{{1},{2},{5},{9}};conststd::vector<Order> new_orders{{2},{5},{7}};std::vector<Order> cut_orders(old_orders.size()+ new_orders.size()); auto[old_orders_end, cut_orders_last]= std::ranges::set_difference(old_orders, new_orders, cut_orders.begin(),{},&Order::order_id,&Order::order_id);assert(old_orders_end== old_orders.end()); std::cout<<"old orders = "; print(old_orders,"\n");std::cout<<"new orders = "; print(new_orders,"\n");std::cout<<"cut orders = "; print(cut_orders,"\n"); cut_orders.erase(cut_orders_last, end(cut_orders));std::cout<<"cut orders = "; print(cut_orders,"\n");}
Output:
{ 1, 2, 5, 5, 5, 9 } ∖ { 2, 5, 7 } = { 1, 5, 5, 9 } old orders = { {1}, {2}, {5}, {9} } new orders = { {2}, {5}, {7} } cut orders = { {1}, {9}, {0}, {0}, {0}, {0}, {0} } cut orders = { {1}, {9} }(C++20) | computes the union of two sets (algorithm function object)[edit] |
(C++20) | computes the intersection of two sets (algorithm function object)[edit] |
| computes the symmetric difference between two sets (algorithm function object)[edit] | |
(C++20) | returnstrue if one sequence is a subsequence of another (algorithm function object)[edit] |
| computes the difference between two sets (function template)[edit] |
