我有两个数组或 vector ,说:
int first[] = {0,0,1,1,2,2,3,3,3};
int second[] = {1,3};
我想摆脱第一组中的1和3, set_difference 只能摆脱这些值的第一次出现,但这不是我想要的。
我是否应该通过迭代第二个范围来使用 remove_copy 来执行此操作,并且每次从第一组中删除一个条目。
用C++做到这一点的最佳方法是什么?
最佳答案
编写专门的set_difference:
template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator set_difference_any( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result )
{
while ( first1 != last1 && first2 != last2 )
if ( *first1 < *first2 ) {
*result = *first1;
++first1;
++result;
} else if ( *first2 < *first1 ) {
++first2;
} else {
++first1;
//++first2; // this is the difference to set_difference
}
return std::copy( first1, last1, result );
}
然后将其应用于问题:
#include "set_difference_any.h"
#include <boost/range.hpp>
#include <iterator>
#include <vector>
std::vector<int> result;
set_difference_any( boost::begin( first ), boost::end( first ),
boost::begin( second ), boost::end( second ),
std::back_inserter( result ) );
该算法是线性的(最大
last1-first1 + last2-first2
比较)