7

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 相比。

有没有更简单的方法？

4

5 回答 5

5

Usingstd::set_difference是在 C++ 中执行此操作的惯用方式。您偶然发现了 C++/STL 与许多其他语言之间的主要区别之一（双关语）。STL 不直接将操作与数据结构捆绑在一起。这就是为什么std::set不实施差异例程的原因。

基本上，诸如std::set_difference将操作结果写入另一个对象之类的算法。有趣的是，该算法并不要求其中一个或两个操作数实际上都是std::set. 算法的定义是：

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

要求：结果范围不得与任何一个原始范围重叠。输入范围必须按相同的顺序排列operator<。

返回：构造范围的结束。

复杂性：最多2 * ((last1 - first1) + (last2 - first2)) - 1比较

有趣的区别是 C++ 版本适用于任何两个排序范围。在大多数语言中，在访问集合差异算法之前，您必须强制或将调用对象（左操作数）转换为集合。

这与您的问题并不真正相关，但这就是各种集合算法被建模为独立算法而不是成员方法的原因。

于 2011-05-22T11:16:09.687 回答
4

您应该遍历第二组：

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

这可能 比使用-将唯一对象复制到新容器中便宜，但它需要线性时间，虽然不会复制任何东西，但是.std::set_differenceset_difference.eraseO(n * log( n ) )

换句话说，取决于容器，您可以选择适合您的情况更快的方式。

谢谢你 David Rodríguez - dribeas的评论！（：

编辑：Doh！我一开始就想到了 BOOST_FOREACH，但我错了它不能使用.. - 你不需要迭代器，只需要值.. 正如 user763305 他/她自己所说的那样。

于 2011-05-22T10:59:17.297 回答
4

在 c++ 中，集合中没有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++ );
        }
    }
}

该算法的性能在参数的大小上是线性的，并且不需要额外的副本，因为它修改了第一个参数。

于 2011-05-22T11:58:04.083 回答
1

您也可以remove_if编写自己的函子来测试集合中的存在性，例如

std::remove_if(s1.begin(), s1.end(), ExistIn(s2));

我想这set_difference更有效，因为它可能只扫描两组

于 2011-05-22T16:36:24.353 回答
1

Python set 是无序的，与有序的 std::set 相比，它更像是 C++ std::unordered_set。

David Rodríguez 的算法依赖于 std::set 是有序的这一事实，因此可以按照算法中展示的方式遍历 lhs 和 rhs 集。

对于适用于有序集和无序集的更通用的解决方案，如果您要强制/保留 Python 集的“无序性”性质，则 Kiril Kirov 的算法应该是安全的采用。

于 2013-06-03T19:49:15.073 回答