C++中等价于Python的difference_update如何实现？

Question

s1和s2是集合（Python中的集合或C++中的std::set）。
要把s2中的元素添加到s1中（也就是集合的并集），你可以这样做：

Python: s1.update(s2)

C++: s1.insert(s2.begin(), s2.end());

要从s1中移除s2中的元素（也就是集合的差集），你可以这样做：

Python: s1.difference_update(s2)

那在C++中怎么做呢？下面这段代码：

s1.erase(s2.begin(), s2.end());

不行，因为s1.erase()需要s1中的迭代器。下面这段代码：

std::set<T> s3;
std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), std::inserter(s3, s3.end());
s1.swap(s3);

可以运行，但看起来有点复杂，至少比Python的写法要复杂。

有没有更简单的方法呢？

Answer 1

在C++中，集合（set）里没有一个叫做difference的方法。set_difference这个名字听起来比较复杂，因为它是一个更通用的函数，不仅仅是用来计算两个集合的差异。当然，你可以自己实现一个在集合上直接计算差异的版本：

template <typename T, typename Compare, typename Allocator>
void my_set_difference( std::set<T,Compare,Allocator>& lhs, std::set<T,Compare,Allocator> const & rhs )
{
    typedef std::set<T,Comapre,Allocator> set_t;
    typedef typename set_t::iterator iterator;
    typedef typename set_t::const_iterator const_iterator;

    const_iterator rit = rhs.begin(), rend = rhs.end();
    iterator it = lhs.begin(), end = lhs.end();
    while ( it != end && rit != rend )
    {
        if ( lhs.key_comp( *it, *rit ) ) {
            ++it;
        } else if ( lhs.key_comp( *rit, *it ) ) {
            ++rit;
        } else {
            ++rit;
            lhs.erase( it++ );
        }
    }
}

这个算法的性能是线性的，也就是说它的运行速度和输入的大小成正比，并且不需要额外的复制，因为它是直接修改第一个参数的内容。

Answer 2

你应该遍历第二组数据：

for( set< T >::iterator iter = s2.begin(); iter != s2.end(); ++iter )
{
    s1.erase( *iter );
}

这个方法 会 可能 比使用 std::set_difference 便宜。因为 set_difference 会把独特的对象复制到一个新的容器里，这个过程需要 线性 时间，而 .erase 不会复制任何东西，但它的复杂度是 O(n * log( n ) )。

换句话说，根据你使用的容器类型，你可以选择对你来说更快的方法。

感谢 David Rodríguez - dribeas 的提醒！ (:

---

编辑：哎呀！我一开始就想到了 BOOST_FOREACH，但我错了，以为它不能用……其实你不需要迭代器，只需要值就可以了……正如用户763305自己所说的。

Answer 3

在C++中，使用std::set_difference是处理这个问题的标准方法。你发现了C++/STL和很多其他编程语言之间的一个主要区别。STL（标准模板库）并不把操作直接和数据结构绑定在一起。这就是为什么std::set没有实现差集操作的原因。

简单来说，像std::set_difference这样的算法会把操作的结果写入另一个对象。值得注意的是，这个算法并不要求参与运算的两个对象一定是std::set。这个算法的定义是：

效果：将范围[first1, last1)中不在范围[first2, last2)中的元素复制到以result开头的范围。构造的范围中的元素是排序过的。

要求：结果范围不能和原始范围重叠。输入范围需要按照相同的operator<进行排序。

返回：构造范围的结束位置。

复杂度：最多需要2 * ((last1 - first1) + (last2 - first2)) - 1次比较。

有趣的地方在于，C++的这个版本可以适用于任何两个已排序的范围。在大多数语言中，你必须先把调用对象（左侧操作数）转换成一个集合，才能使用集合差集算法。

这其实和你的问题没有直接关系，但这就是为什么各种集合算法被设计成独立的算法，而不是作为成员方法的原因。