Defined in header
Call signature
template<std::input_iteratorI1,std::sentinel_for<I1>S1,std::input_iteratorI2,std::sentinel_for<I2>S2,std::weakly_incrementableO,classComp=ranges::less,classProj1=std::identity,classProj2=std::identity>requiresstd::mergeable<I1,I2,O,Comp,Proj1,Proj2>constexprset_difference_result<I1,O>set_difference(I1first1,S1last1,I2first2,S2last2,Oresult,Compcomp={},Proj1proj1={},Proj2proj2={}); (1) (since C++20)template<ranges::input_rangeR1,ranges::input_rangeR2,std::weakly_incrementableO,classComp=ranges::less,classProj1=std::identity,classProj2=std::identity>requiresstd::mergeable<ranges::iterator_t<R1>,ranges::iterator_t<R2>,O,Comp,Proj1,Proj2>constexprset_difference_result<ranges::borrowed_iterator_t<R1>,O>set_difference(R1&&r1,R2&&r2,Oresult,Compcomp={},Proj1proj1={},Proj2proj2={}); (2) (since C++20)Helper types
template<classI,classO>usingset_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 at result.
The behavior is undefined if
the input ranges are not sorted with respect to comp and proj1 or proj2, respectively, or
the resulting range overlaps with either of the input ranges.
1) Elements are compared using the given binary comparison function comp.
2) Same as (1), but uses r1 as the first range and r2 as the second range, as if using ranges::begin(r1) as first1, ranges::end(r1) as last1, ranges::begin(r2) as first2, and ranges::end(r2) as last2.
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 first sorted input
of elements first2, last2 - the iterator-sentinel pair defining the second sorted input
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 Return value
{last1,result_last}, where result_last is the end of the constructed range.
Complexity
At most 2·(N1+N2)-1 comparisons and applications of each projection, where N1 and N2 are ranges::distance(first1,last1) and ranges::distance(first2,last2), respectively.
Possible implementation
structset_difference_fn{template<std::input_iteratorI1,std::sentinel_for<I1>S1,std::input_iteratorI2,std::sentinel_for<I2>S2,std::weakly_incrementableO,classComp=ranges::less,classProj1=std::identity,classProj2=std::identity>requiresstd::mergeable<I1,I2,O,Comp,Proj1,Proj2>constexprranges::set_difference_result<I1,O>operator()(I1first1,S1last1,I2first2,S2last2,Oresult,Compcomp={},Proj1proj1={},Proj2proj2={})const{while(!(first1==last1orfirst2==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_rangeR1,ranges::input_rangeR2,std::weakly_incrementableO,classComp=ranges::less,classProj1=std::identity,classProj2=std::identity>requiresstd::mergeable<ranges::iterator_t<R1>,ranges::iterator_t<R2>,O,Comp,Proj1,Proj2>constexprranges::set_difference_result<ranges::borrowed_iterator_t<R1>,O>operator()(R1&&r1,R2&&r2,Oresult,Compcomp={},Proj1proj1={},Proj2proj2={})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));}};inlineconstexprset_difference_fnset_difference{};Example
Run this code
#include<algorithm>#include<cassert>#include<iostream>#include<iterator>#include<string_view>#include<vector>autoprint=[](constauto&v,std::string_viewend=""){std::cout<<"{ ";for(auton{v.size()};autoi:v)std::cout<<i<<(--n?", ":" ");std::cout<<"} "<<end;};structOrder// a struct with some very interesting data{intorder_id{};friendstd::ostream&operator<<(std::ostream&os,constOrder&ord){returnos<<'{'<<ord.order_id<<'}';}};intmain(){constautov1={1,2,5,5,5,9};constautov2={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} } See also