boost/poly_collection/algorithm.hpp
/* Copyright 2016-2020 Joaquin M Lopez Munoz. * Distributed under the Boost Software License, Version 1.0. * (See accompanying file LICENSE_1_0.txt or copy at * http://www.boost.org/LICENSE_1_0.txt) * * See http://www.boost.org/libs/poly_collection for library home page. */ #ifndef BOOST_POLY_COLLECTION_ALGORITHM_HPP #define BOOST_POLY_COLLECTION_ALGORITHM_HPP #if defined(_MSC_VER) #pragma once #endif #include <algorithm> #include <boost/poly_collection/detail/auto_iterator.hpp> #include <boost/poly_collection/detail/functional.hpp> #include <boost/poly_collection/detail/iterator_traits.hpp> #include <boost/poly_collection/detail/segment_split.hpp> #include <boost/poly_collection/detail/type_restitution.hpp> #include <iterator> #include <random> #include <type_traits> #include <utility> /* Improved performance versions of std algorithms over poly_collection. * poly_collection::alg is expected to be faster than the homonym std::alg * because the latter does a traversal over a segmented structured, where * incrementing requires checking for segment change, whereas the former * for-loops over flat segments. * Additionally, poly_collection::alg<Ti...>(...,f) *restitutes* Ti when * passing elements to f, i.e. if the concrete type of the element is Ti * then f is invoked with a [const] Ti&, which can dramatically improve * performance when f has specific overloads for Ti (like, for instance, * generic lambdas) as static optimization can kick in (devirtualization * being a particular example). */ namespace boost{ namespace poly_collection{ namespace detail{ namespace algorithm{ template<typename Iterator> using enable_if_poly_collection_iterator=typename std::enable_if< !std::is_void<typename poly_collection_of<Iterator>::type>::value >::type*; BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_all_of,std::all_of) template< typename... Ts,typename Iterator,typename Predicate, enable_if_poly_collection_iterator<Iterator> =nullptr > bool all_of(const Iterator& first,const Iterator& last,Predicate pred) { auto alg=restitute_range<Ts...>(std_all_of{},pred); for(auto i:detail::segment_split(first,last))if(!alg(i))return false; return true; } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_any_of,std::any_of) template< typename... Ts,typename Iterator,typename Predicate, enable_if_poly_collection_iterator<Iterator> =nullptr > bool any_of(const Iterator& first,const Iterator& last,Predicate pred) { auto alg=restitute_range<Ts...>(std_any_of{},pred); for(auto i:detail::segment_split(first,last))if(alg(i))return true; return false; } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_none_of,std::none_of) template< typename... Ts,typename Iterator,typename Predicate, enable_if_poly_collection_iterator<Iterator> =nullptr > bool none_of(const Iterator& first,const Iterator& last,Predicate pred) { auto alg=restitute_range<Ts...>(std_none_of{},pred); for(auto i:detail::segment_split(first,last))if(!alg(i))return false; return true; } struct for_each_alg { template<typename InputIterator,typename Function> void operator()( InputIterator first,InputIterator last,Function& f)const /* note the & */ { for(;first!=last;++first)f(*first); } }; template< typename... Ts,typename Iterator,typename Function, enable_if_poly_collection_iterator<Iterator> =nullptr > Function for_each(const Iterator& first,const Iterator& last,Function f) { for_each_segment(first,last,restitute_range<Ts...>(for_each_alg{},f)); return f; } struct for_each_n_alg { template< typename InputIterator,typename Size,typename Function > InputIterator operator()( InputIterator first,Size n,Function& f)const /* note the & */ { for(;n>0;++first,(void)--n)f(*first); return first; } }; template< typename... Ts,typename Iterator,typename Size,typename Function, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator for_each_n(const Iterator& first,Size n,Function f) { using traits=iterator_traits<Iterator>; using local_base_iterator=typename traits::local_base_iterator; if(n<=0)return first; auto alg=restitute_iterator<Ts...>( cast_return<local_base_iterator>(for_each_n_alg{})); auto lbit=traits::local_base_iterator_from(first); auto sit=traits::base_segment_info_iterator_from(first); for(;;){ auto m=sit->end()-lbit; if(n<=m){ auto it=alg(sit->type_info(),lbit,n,f); return traits::iterator_from( it,traits::end_base_segment_info_iterator_from(first)); } else{ alg(sit->type_info(),lbit,m,f); n-=m; } ++sit; lbit=sit->begin(); } } template< typename Algorithm,typename... Ts, typename Iterator,typename... Args, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator generic_find( const Iterator& first,const Iterator& last,Args&&... args) { using traits=iterator_traits<Iterator>; using local_base_iterator=typename traits::local_base_iterator; auto alg=restitute_range<Ts...>( cast_return<local_base_iterator>(Algorithm{}), std::forward<Args>(args)...); for(auto i:detail::segment_split(first,last)){ auto it=alg(i); if(it!=i.end()) return traits::iterator_from( it,traits::end_base_segment_info_iterator_from(last)); } return last; } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find,std::find) template< typename... Ts,typename Iterator,typename T, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator find(const Iterator& first,const Iterator& last,const T& x) { return generic_find<std_find,Ts...>(first,last,x); } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_if,std::find_if) template< typename... Ts,typename Iterator,typename Predicate, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator find_if(const Iterator& first,const Iterator& last,Predicate pred) { return generic_find<std_find_if,Ts...>(first,last,pred); } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_if_not,std::find_if_not) template< typename... Ts,typename Iterator,typename Predicate, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator find_if_not(const Iterator& first,const Iterator& last,Predicate pred) { return generic_find<std_find_if_not,Ts...>(first,last,pred); } /* find_end defined after search below */ BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_first_of,std::find_first_of) template< typename... Ts,typename Iterator,typename ForwardIterator, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator find_first_of( const Iterator& first1,const Iterator& last1, ForwardIterator first2,ForwardIterator last2) { return generic_find<std_find_first_of,Ts...>(first1,last1,first2,last2); } template< typename... Ts,typename Iterator, typename ForwardIterator,typename BinaryPredicate, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator find_first_of( const Iterator& first1,const Iterator& last1, ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) { return generic_find<std_find_first_of,Ts...>(first1,last1,first2,last2,pred); } template<typename... Ts> struct adjacent_find_alg { template< typename LocalIterator,typename BinaryPredicate,typename LocalBaseIterator > LocalBaseIterator operator()( LocalIterator first,LocalIterator last,BinaryPredicate pred, bool& carry,const std::type_info* prev_info, /* note the &s */ LocalBaseIterator& prev)const { if(first==last)return LocalBaseIterator{last}; if(carry){ auto p=restitute_iterator<Ts...>(deref_to(pred)); if(p(*prev_info,prev,first))return prev; } auto res=std::adjacent_find(first,last,pred); if(res==last){ carry=true; prev_info=&typeid( typename std::iterator_traits<LocalIterator>::value_type); prev=LocalBaseIterator{last-1}; } else carry=false; return LocalBaseIterator{res}; } }; template< typename... Ts,typename Iterator,typename BinaryPredicate, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator adjacent_find( const Iterator& first,const Iterator& last,BinaryPredicate pred) { using traits=iterator_traits<Iterator>; using local_base_iterator=typename traits::local_base_iterator; bool carry=false; const std::type_info* prev_info{&typeid(void)}; local_base_iterator prev; return generic_find<adjacent_find_alg<Ts...>,Ts...>( first,last,pred,carry,prev_info,prev); } template< typename... Ts,typename Iterator, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator adjacent_find(const Iterator& first,const Iterator& last) { return algorithm::adjacent_find<Ts...>(first,last,transparent_equal_to{}); } template< typename Algorithm,typename... Ts, typename Iterator,typename... Args, enable_if_poly_collection_iterator<Iterator> =nullptr > std::ptrdiff_t generic_count( const Iterator& first,const Iterator& last,Args&&... args) { auto alg=restitute_range<Ts...>(Algorithm{},std::forward<Args>(args)...); std::ptrdiff_t res=0; for(auto i:detail::segment_split(first,last))res+=alg(i); return res; } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_count,std::count) template< typename... Ts,typename Iterator,typename T, enable_if_poly_collection_iterator<Iterator> =nullptr > std::ptrdiff_t count(const Iterator& first,const Iterator& last,const T& x) { return generic_count<std_count,Ts...>(first,last,x); } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_count_if,std::count_if) template< typename... Ts,typename Iterator,typename Predicate, enable_if_poly_collection_iterator<Iterator> =nullptr > std::ptrdiff_t count_if( const Iterator& first,const Iterator& last,Predicate pred) { return generic_count<std_count_if,Ts...>(first,last,pred); } struct mismatch_alg { template< typename InputIterator1, typename InputIterator2,typename BinaryPredicate > InputIterator1 operator()( InputIterator1 first1,InputIterator1 last1, InputIterator2& first2,BinaryPredicate pred)const /* note the & */ { while(first1!=last1&&pred(*first1,*first2)){ ++first1; ++first2; } return first1; } template< typename InputIterator1, typename InputIterator2,typename BinaryPredicate > InputIterator1 operator()( InputIterator1 first1,InputIterator1 last1, InputIterator2& first2,InputIterator2 last2, /* note the & */ BinaryPredicate pred)const { while(first1!=last1&&first2!=last2&&pred(*first1,*first2)){ ++first1; ++first2; } return first1; } }; template< typename... Ts,typename Iterator, typename InputIterator,typename BinaryPredicate, enable_if_poly_collection_iterator<Iterator> =nullptr > std::pair<Iterator,InputIterator> mismatch( const Iterator& first1,const Iterator& last1, InputIterator first2,BinaryPredicate pred) { auto it=generic_find<mismatch_alg,Ts...>(first1,last1,first2,pred); return {it,first2}; } template< typename... Ts,typename Iterator,typename InputIterator, enable_if_poly_collection_iterator<Iterator> =nullptr > std::pair<Iterator,InputIterator> mismatch( const Iterator& first1,const Iterator& last1,InputIterator first2) { return algorithm::mismatch<Ts...>( first1,last1,first2,transparent_equal_to{}); } template< typename... Ts,typename Iterator, typename InputIterator,typename BinaryPredicate, enable_if_poly_collection_iterator<Iterator> =nullptr > std::pair<Iterator,InputIterator> mismatch( const Iterator& first1,const Iterator& last1, InputIterator first2,InputIterator last2,BinaryPredicate pred) { auto it=generic_find<mismatch_alg,Ts...>(first1,last1,first2,last2,pred); return {it,first2}; } template< typename... Ts,typename Iterator,typename InputIterator, enable_if_poly_collection_iterator<Iterator> =nullptr > std::pair<Iterator,InputIterator> mismatch( const Iterator& first1,const Iterator& last1, InputIterator first2,InputIterator last2) { return algorithm::mismatch<Ts...>( first1,last1,first2,last2,transparent_equal_to{}); } struct equal_alg { template< typename InputIterator1, typename InputIterator2,typename BinaryPredicate > bool operator()( InputIterator1 first1,InputIterator1 last1, InputIterator2& first2,BinaryPredicate pred)const /* note the & */ { for(;first1!=last1;++first1,++first2){ if(!pred(*first1,*first2))return false; } return true; } template< typename InputIterator1, typename InputIterator2,typename BinaryPredicate > bool operator()( InputIterator1 first1,InputIterator1 last1, InputIterator2& first2,InputIterator2 last2, /* note the & */ BinaryPredicate pred)const { for(;first1!=last1&&first2!=last2;++first1,++first2){ if(!pred(*first1,*first2))return false; } return first1==last1; /* don't check first2==last2 as op is partial */ } }; template< typename... Ts,typename Iterator, typename InputIterator,typename BinaryPredicate, enable_if_poly_collection_iterator<Iterator> =nullptr > bool equal( const Iterator& first1,const Iterator& last1, InputIterator first2,BinaryPredicate pred) { auto alg=restitute_range<Ts...>(equal_alg{},first2,pred); for(auto i:detail::segment_split(first1,last1))if(!alg(i))return false; return true; } template< typename... Ts,typename Iterator,typename InputIterator, enable_if_poly_collection_iterator<Iterator> =nullptr > bool equal( const Iterator& first1,const Iterator& last1,InputIterator first2) { return algorithm::equal<Ts...>(first1,last1,first2,transparent_equal_to{}); } template< typename... Ts,typename Iterator, typename InputIterator,typename BinaryPredicate, enable_if_poly_collection_iterator<Iterator> =nullptr > bool equal( const Iterator& first1,const Iterator& last1, InputIterator first2,InputIterator last2,BinaryPredicate pred) { auto alg=restitute_range<Ts...>(equal_alg{},first2,last2,pred); for(auto i:detail::segment_split(first1,last1))if(!alg(i))return false; return first2==last2; } template< typename... Ts,typename Iterator,typename InputIterator, enable_if_poly_collection_iterator<Iterator> =nullptr > bool equal( const Iterator& first1,const Iterator& last1, InputIterator first2,InputIterator last2) { return algorithm::equal<Ts...>( first1,last1,first2,last2,transparent_equal_to{}); } template< typename Iterator, enable_if_poly_collection_iterator<Iterator> =nullptr > std::ptrdiff_t fast_distance(const Iterator& first,const Iterator& last) { using traits=iterator_traits<Iterator>; if(first==last)return 0; auto sfirst=traits::base_segment_info_iterator_from(first), slast=traits::base_segment_info_iterator_from(last); if(sfirst==slast){ return std::distance( traits::local_base_iterator_from(first), traits::local_base_iterator_from(last)); } else{ std::ptrdiff_t m=std::distance( traits::local_base_iterator_from(first),sfirst->end()); while(++sfirst!=slast)m+=std::distance(sfirst->begin(),sfirst->end()); if(slast!=traits::end_base_segment_info_iterator_from(last)){ m+=std::distance( slast->begin(),traits::local_base_iterator_from(last)); } return m; } } template< typename... Ts,typename Iterator, typename ForwardIterator,typename BinaryPredicate, enable_if_poly_collection_iterator<Iterator> =nullptr > bool is_permutation_suffix( const Iterator& first1,const Iterator& last1, ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) { using traits=iterator_traits<Iterator>; auto send=traits::end_base_segment_info_iterator_from(last1); for(auto i:detail::segment_split(first1,last1)){ for(auto lbscan=i.begin();lbscan!=i.end();++lbscan){ auto& info=i.type_info(); auto p=head_closure( restitute_iterator<Ts...>(deref_1st_to(pred)),info,lbscan); auto scan=traits::iterator_from(lbscan,send); if(algorithm::find_if<Ts...>(first1,scan,p)!=scan)continue; std::ptrdiff_t matches=std::count_if(first2,last2,p); if(matches==0|| matches!=algorithm::count_if<Ts...>(scan,last1,p))return false; } } return true; } template< typename... Ts,typename Iterator, typename ForwardIterator,typename BinaryPredicate, enable_if_poly_collection_iterator<Iterator> =nullptr > bool is_permutation( Iterator first1,Iterator last1,ForwardIterator first2,BinaryPredicate pred) { std::tie(first1,first2)=algorithm::mismatch<Ts...>(first1,last1,first2,pred); auto last2=std::next(first2,algorithm::fast_distance(first1,last1)); return is_permutation_suffix<Ts...>(first1,last1,first2,last2,pred); } template< typename... Ts,typename Iterator,typename ForwardIterator, enable_if_poly_collection_iterator<Iterator> =nullptr > bool is_permutation( const Iterator& first1,const Iterator& last1,ForwardIterator first2) { return algorithm::is_permutation<Ts...>( first1,last1,first2,transparent_equal_to{}); } template< typename... Ts,typename Iterator, typename ForwardIterator,typename BinaryPredicate, enable_if_poly_collection_iterator<Iterator> =nullptr > bool is_permutation( Iterator first1,Iterator last1, ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) { std::tie(first1,first2)=algorithm::mismatch<Ts...>( first1,last1,first2,last2,pred); if(algorithm::fast_distance(first1,last1)!=std::distance(first2,last2)) return false; else return is_permutation_suffix<Ts...>(first1,last1,first2,last2,pred); } template< typename... Ts,typename Iterator,typename ForwardIterator, enable_if_poly_collection_iterator<Iterator> =nullptr > bool is_permutation( const Iterator& first1,const Iterator& last1, ForwardIterator first2,ForwardIterator last2) { return algorithm::is_permutation<Ts...>( first1,last1,first2,last2,transparent_equal_to{}); } template< typename... Ts,typename Iterator, typename ForwardIterator,typename BinaryPredicate, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator search( const Iterator& first1,const Iterator& last1, ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) { using traits=iterator_traits<Iterator>; auto send=traits::end_base_segment_info_iterator_from(last1); for(auto i:detail::segment_split(first1,last1)){ for(auto lbit=i.begin(),lbend=i.end();lbit!=lbend;++lbit){ Iterator it=traits::iterator_from(lbit,send); if(algorithm::mismatch<Ts...>(it,last1,first2,last2,pred).second==last2) return it; } } return last1; } template< typename... Ts,typename Iterator,typename ForwardIterator, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator search( const Iterator& first1,const Iterator& last1, ForwardIterator first2,ForwardIterator last2) { return algorithm::search<Ts...>( first1,last1,first2,last2,transparent_equal_to{}); } template< typename... Ts,typename Iterator, typename ForwardIterator,typename BinaryPredicate, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator find_end( Iterator first1,Iterator last1, ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) { if(first2==last2)return last1; for(Iterator res=last1;;){ Iterator res1=algorithm::search<Ts...>(first1,last1,first2,last2,pred); if(res1==last1)return res; else{ first1=res=res1; ++first1; } } } template< typename... Ts,typename Iterator,typename ForwardIterator, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator find_end( const Iterator& first1,const Iterator& last1, ForwardIterator first2,ForwardIterator last2) { return algorithm::find_end<Ts...>( first1,last1,first2,last2,transparent_equal_to{}); } struct search_n_alg { template< typename ForwardIterator,typename Size, typename T,typename BinaryPredicate > ForwardIterator operator()( ForwardIterator first,ForwardIterator last, Size count,bool& carry,Size& remain,const T& x, /* note the &s */ BinaryPredicate pred)const { for(;first!=last;++first){ if(!pred(*first,x)){carry=false;remain=count;continue;} auto res=first; for(;;){ if(--remain==0||++first==last)return res; if(!pred(*first,x)){carry=false;remain=count;break;} } } return last; } }; template< typename... Ts,typename Iterator, typename Size,typename T,typename BinaryPredicate, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator search_n( const Iterator& first,const Iterator& last, Size count,const T& x,BinaryPredicate pred) { using traits=iterator_traits<Iterator>; using local_base_iterator=typename traits::local_base_iterator; if(count<=0)return first; bool carry=false; auto remain=count; auto alg=restitute_range<Ts...>( cast_return<local_base_iterator>(search_n_alg{}), count,carry,remain,x,pred); local_base_iterator prev; for(auto i:detail::segment_split(first,last)){ auto it=alg(i); if(it!=i.end()){ if(remain==0) return traits::iterator_from( carry?prev:it, traits::end_base_segment_info_iterator_from(last)); else if(!carry){prev=it;carry=true;} } } return last; } template< typename... Ts,typename Iterator, typename Size,typename T, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator search_n( const Iterator& first,const Iterator& last,Size count,const T& x) { return algorithm::search_n<Ts...>( first,last,count,x,transparent_equal_to{}); } template< typename Algorithm,typename... Ts, typename Iterator,typename OutputIterator,typename... Args, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator generic_copy( const Iterator& first,const Iterator& last,OutputIterator res,Args&&... args) { for(auto i:detail::segment_split(first,last)){ auto alg=restitute_range<Ts...>( Algorithm{},res,std::forward<Args>(args)...); res=alg(i); } return res; } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy,std::copy) template< typename... Ts,typename Iterator,typename OutputIterator, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator copy( const Iterator& first,const Iterator& last,OutputIterator res) { return generic_copy<std_copy,Ts...>(first,last,res); } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy_n,std::copy_n) template< typename... Ts,typename Iterator,typename Size,typename OutputIterator, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator copy_n(const Iterator& first,Size count,OutputIterator res) { using traits=iterator_traits<Iterator>; if(count<=0)return res; auto lbit=traits::local_base_iterator_from(first); auto sit=traits::base_segment_info_iterator_from(first); for(;;){ auto n=(std::min)(count,sit->end()-lbit); auto alg=restitute_iterator<Ts...>(std_copy_n{},n,res); res=alg(sit->type_info(),lbit); if((count-=n)==0)break; ++sit; lbit=sit->begin(); } return res; } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy_if,std::copy_if) template< typename... Ts,typename Iterator,typename OutputIterator,typename Predicate, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator copy_if( const Iterator& first,const Iterator& last,OutputIterator res,Predicate pred) { return generic_copy<std_copy_if,Ts...>(first,last,res,pred); } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_move,std::move) template< typename... Ts,typename Iterator,typename OutputIterator, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator move( const Iterator& first,const Iterator& last,OutputIterator res) { return generic_copy<std_move,Ts...>(first,last,res); } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_transform,std::transform) template< typename... Ts,typename Iterator, typename OutputIterator,typename UnaryOperation, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator transform( const Iterator& first,const Iterator& last, OutputIterator res,UnaryOperation op) { return generic_copy<std_transform,Ts...>(first,last,res,op); } struct transform2_alg { template< typename InputIterator1,typename InputIterator2, typename OutputIterator,typename BinaryOperation > OutputIterator operator()( InputIterator1 first1,InputIterator1 last1, OutputIterator res, /* third place for compatibility with generic_copy */ InputIterator2& first2, BinaryOperation op)const /* note the & */ { while(first1!=last1)*res++=op(*first1++,*first2++); return res; } }; template< typename... Ts,typename Iterator,typename InputIterator, typename OutputIterator,typename BinaryOperation, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator transform( const Iterator& first1,const Iterator& last1,InputIterator first2, OutputIterator res,BinaryOperation op) { return generic_copy<transform2_alg,Ts...>(first1,last1,res,first2,op); } struct replace_copy_alg { /* std::replace_copy broken in VS2015, internal ticket VSO#279818 * "<algorithm>: replace_copy() and replace_copy_if() shouldn't use the * conditional operator". */ template<typename InputIterator,typename OutputIterator,typename T> OutputIterator operator()( InputIterator first,InputIterator last,OutputIterator res, const T& old_x,const T& new_x) { for(;first!=last;++first,++res){ if(*first==old_x)*res=new_x; else *res=*first; } return res; } }; template< typename... Ts,typename Iterator,typename OutputIterator,typename T, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator replace_copy( const Iterator& first,const Iterator& last,OutputIterator res, const T& old_x,const T& new_x) { return generic_copy<replace_copy_alg,Ts...>(first,last,res,old_x,new_x); } struct replace_copy_if_alg { /* std::replace_copy_if broken in VS2015, internal ticket VSO#279818 * "<algorithm>: replace_copy() and replace_copy_if() shouldn't use the * conditional operator". */ template< typename InputIterator,typename OutputIterator, typename Predicate,typename T > OutputIterator operator()( InputIterator first,InputIterator last,OutputIterator res, Predicate pred,const T& new_x) { for(;first!=last;++first,++res){ if(pred(*first))*res=new_x; else *res=*first; } return res; } }; template< typename... Ts,typename Iterator,typename OutputIterator, typename Predicate,typename T, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator replace_copy_if( const Iterator& first,const Iterator& last,OutputIterator res, Predicate pred,const T& new_x) { return generic_copy<replace_copy_if_alg,Ts...>(first,last,res,pred,new_x); } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_remove_copy,std::remove_copy) template< typename... Ts,typename Iterator,typename OutputIterator,typename T, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator remove_copy( const Iterator& first,const Iterator& last,OutputIterator res,const T& x) { return generic_copy<std_remove_copy,Ts...>(first,last,res,x); } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET( std_remove_copy_if,std::remove_copy_if) template< typename... Ts,typename Iterator,typename OutputIterator,typename Predicate, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator remove_copy_if( const Iterator& first,const Iterator& last,OutputIterator res,Predicate pred) { return generic_copy<std_remove_copy_if,Ts...>(first,last,res,pred); } template<typename... Ts> struct unique_copy_alg { template< typename LocalIterator,typename OutputIterator, typename BinaryPredicate,typename LocalBaseIterator > OutputIterator operator()( LocalIterator first,LocalIterator last, OutputIterator res, BinaryPredicate pred, bool& carry,const std::type_info* prev_info, /* note the &s */ LocalBaseIterator& prev)const { if(carry){ auto p=restitute_iterator<Ts...>(deref_to(pred)); for(;first!=last;++first)if(!p(*prev_info,prev,first))break; } if(first==last)return res; res=std::unique_copy(first,last,res,pred); carry=true; prev_info=&typeid( typename std::iterator_traits<LocalIterator>::value_type); prev=LocalBaseIterator{last-1}; return res; } }; template< typename... Ts,typename Iterator, typename OutputIterator,typename BinaryPredicate, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator unique_copy( const Iterator& first,const Iterator& last, OutputIterator res,BinaryPredicate pred) { using traits=iterator_traits<Iterator>; using local_base_iterator=typename traits::local_base_iterator; bool carry=false; const std::type_info* prev_info{&typeid(void)}; local_base_iterator prev; return generic_copy<unique_copy_alg<Ts...>,Ts...>( first,last,res,pred,carry,prev_info,prev); } template< typename... Ts,typename Iterator,typename OutputIterator, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator unique_copy( const Iterator& first,const Iterator& last,OutputIterator res) { return algorithm::unique_copy<Ts...>(first,last,res,transparent_equal_to{}); } template< typename... Ts,typename Iterator,typename OutputIterator, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator rotate_copy( const Iterator& first,const Iterator& middle,const Iterator& last, OutputIterator res) { res=algorithm::copy<Ts...>(middle,last,res); return algorithm::copy<Ts...>(first,middle,res); } struct sample_alg { template< typename InputIterator,typename OutputIterator, typename Distance,typename UniformRandomBitGenerator > OutputIterator operator()( InputIterator first,InputIterator last, OutputIterator res,Distance& n,Distance& m, /* note the &s */ UniformRandomBitGenerator& g)const { for(;first!=last&&n!=0;++first){ auto r=std::uniform_int_distribution<Distance>(0,--m)(g); if (r<n){ *res++=*first; --n; } } return res; } }; template< typename... Ts,typename Iterator,typename OutputIterator, typename Distance,typename UniformRandomBitGenerator, enable_if_poly_collection_iterator<Iterator> =nullptr > OutputIterator sample( const Iterator& first,const Iterator& last, OutputIterator res,Distance n,UniformRandomBitGenerator&& g) { Distance m=algorithm::fast_distance(first,last); n=(std::min)(n,m); for(auto i:detail::segment_split(first,last)){ auto alg=restitute_range<Ts...>(sample_alg{},res,n,m,g); res=alg(i); if(n==0)return res; } return res; /* never reached */ } template< typename... Ts,typename Iterator,typename Predicate, enable_if_poly_collection_iterator<Iterator> =nullptr > bool is_partitioned(const Iterator& first,const Iterator& last,Predicate pred) { auto it=algorithm::find_if_not<Ts...>(first,last,pred); if(it==last)return true; return algorithm::none_of<Ts...>(++it,last,pred); } BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET( std_partition_copy,std::partition_copy) template< typename... Ts,typename Iterator, typename OutputIterator1,typename OutputIterator2,typename Predicate, enable_if_poly_collection_iterator<Iterator> =nullptr > std::pair<OutputIterator1,OutputIterator2> partition_copy( const Iterator& first,const Iterator& last, OutputIterator1 rest,OutputIterator2 resf,Predicate pred) { for(auto i:detail::segment_split(first,last)){ auto alg=restitute_range<Ts...>(std_partition_copy{},rest,resf,pred); std::tie(rest,resf)=alg(i); } return {rest,resf}; } template<typename Predicate,typename... Ts> struct partition_point_pred { partition_point_pred(const Predicate& pred):pred(pred){} template<typename Iterator> bool operator()(const Iterator& it)const { using traits=iterator_traits<Iterator>; auto p=restitute_iterator<Ts...>(deref_to(pred)); return p( traits::base_segment_info_iterator_from(it)->type_info(), traits::local_base_iterator_from(it)); } Predicate pred; }; template< typename... Ts,typename Iterator,typename Predicate, enable_if_poly_collection_iterator<Iterator> =nullptr > Iterator partition_point( const Iterator& first,const Iterator& last,Predicate pred) { auto_iterator<Iterator> afirst{first},alast{last}; partition_point_pred<Predicate,Ts...> p{pred}; return *std::partition_point(afirst,alast,p); } } /* namespace poly_collection::detail::algorithm */ } /* namespace poly_collection::detail */ /* non-modifying sequence operations */ using detail::algorithm::all_of; using detail::algorithm::any_of; using detail::algorithm::none_of; using detail::algorithm::for_each; using detail::algorithm::for_each_n; using detail::algorithm::find; using detail::algorithm::find_if; using detail::algorithm::find_if_not; using detail::algorithm::find_end; using detail::algorithm::find_first_of; using detail::algorithm::adjacent_find; using detail::algorithm::count; using detail::algorithm::count_if; using detail::algorithm::mismatch; using detail::algorithm::equal; using detail::algorithm::is_permutation; using detail::algorithm::search; using detail::algorithm::search_n; /* modifying sequence operations */ using detail::algorithm::copy; using detail::algorithm::copy_n; using detail::algorithm::copy_if; /* copy_backward requires BidirectionalIterator */ using detail::algorithm::move; /* move_backward requires BidirectionalIterator */ /* swap_ranges requires Swappable */ /* iter_swap requires Swappable */ using detail::algorithm::transform; /* replace requires Assignable */ /* replace_if requires Assignable */ using detail::algorithm::replace_copy; using detail::algorithm::replace_copy_if; /* fill requires Assignable */ /* fill_n requires Assignable */ /* generate requires Assignable */ /* generate_n requires Assignable */ /* remove requires MoveAssignable */ /* remove_if requires MoveAssignable */ using detail::algorithm::remove_copy; using detail::algorithm::remove_copy_if; /* unique requires MoveAssignable */ using detail::algorithm::unique_copy; /* reverse requires BidirectionalIterator */ /* reverse_copy requires BidirectionalIterator */ /* rotate requires MoveAssignable */ using detail::algorithm::rotate_copy; using detail::algorithm::sample; /* shuffle requires RandomAccessIterator */ using detail::algorithm::is_partitioned; /* partition requires Swappable */ /* stable_partition requires Swappable */ using detail::algorithm::partition_copy; using detail::algorithm::partition_point; /* sorting and related operations not provided */ } /* namespace poly_collection */ } /* namespace boost */ #endif