6

我有一个 Visual Studio 2008 C++03 应用程序，其中有两个标准容器。我想从一个容器中删除另一个容器中存在的所有项目（集合的交集）。

像这样的东西：

std::vector< int > items = /* 1, 2, 3, 4, 5, 6, 7 */;
std::set< int > items_to_remove = /* 2, 4, 5*/;

std::some_algorithm( items.begin, items.end(), items_to_remove.begin(), items_to_remove.end() );

assert( items == /* 1, 3, 6, 7 */ )

是否有现有的算法或模式可以做到这一点，还是我需要自己推出？

谢谢

4

6 回答 6

6

尝试：

items.erase(
    std::remove_if(
        items.begin(), items.end()
      , std::bind1st(
            std::mem_fun( &std::set< int >::count )
          , items_to_remove
        )
    )
  , items.end()
);

std::remove(_if)实际上并没有删除任何东西，因为它适用于迭代器而不是容器。它所做的是将要在范围末尾删除的元素重新排序，并将迭代器返回到容器的新末尾。然后，您调用erase以实际从容器中删除新 end之后的所有元素。

更新：如果我没记错的话，绑定到标准库组件的成员函数不是标准 C++，因为允许实现向函数添加默认参数。通过创建自己的函数或函数对象谓词来检查元素是否包含在要删除的项目集中，您会更安全。

于 2012-05-15T14:59:27.153 回答
3

就个人而言，我更喜欢为此创建小助手（我大量重用）。

template <typename Container>
class InPredicate {
public:
    InPredicate(Container const& c): _c(c) {}

    template <typename U>
    bool operator()(U const& u) {
        return std::find(_c.begin(), _c.end(), u) != _c.end();
    }

private:
    Container const& _c;
};

// Typical builder for automatic type deduction
template <typename Container>
InPredicate<Container> in(Container const& c) {
    return InPredicate<Container>(c);
}

这也有助于拥有一个真正的erase_if算法

template <typename Container, typename Predicate>
void erase_if(Container& c, Predicate p) {
    c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
}

接着：

erase_if(items, in(items_to_remove));

这是非常可读的:)

于 2012-05-15T15:14:22.277 回答
2

另一种解决方案：

有标准提供的算法 set_difference 可用于此。但它需要额外的容器来保存结果。我个人更喜欢就地进行。

std::vector< int > items;
//say items = [1,2,3,4,5,6,7,8,9]

std::set<int>items_to_remove;
//say items_to_remove = <2,4,5>

std::vector<int>result(items.size()); //as this algorithm uses output 
                           //iterator not inserter iterator for result.

std::vector<int>::iterator new_end = std::set_difference(items.begin(), 
 items.end(),items_to_remove.begin(),items_to_remove.end(),result.begin());

result.erase(new_end,result.end()); // to erase unwanted elements at the 
                                    // end.
于 2012-05-15T15:56:52.690 回答
1

您可以为此std::erase结合使用。std::remove有一个称为Erase - Remove idiom的 C++ 习语，它将帮助您完成此操作。

于 2012-05-15T14:59:30.743 回答
1

假设您有两组A和B，并且您想从 中删除B的交集 ，，I您的最终结果将是：（ 保持不变）(A,B)I = A^BA
B' = B-I

完整理论： http:
//math.comsci.us/sets/difference.html

这很简单。

  1. 创建和填充A和B
  2. 创建第三个中间向量，I
  3. 将内容复制B到I
  4. 对于包含元素a_j的每个元素，搜索元素；如果在 中找到该元素，请将其删除AjIa_jI

最后，可以在此处找到删除单个元素的代码：
如何从具有特定值的 stl 向量中删除项目？

搜索项目的代码在这里：
如何查找项目是否存在于 std::vector 中？

祝你好运！

于 2012-05-15T15:06:32.117 回答
0

这是一种更“动手”的就地方法，它不需要花哨的功能，也不需要对向量进行排序：

#include <vector>

template <class TYPE>
void remove_intersection(std::vector<TYPE> &items, const std::vector<TYPE> &items_to_remove)
{
    for (int i = 0; i < (int)items_to_remove.size(); i++) {
        for (int j = 0; j < (int)items.size(); j++) {
            if (items_to_remove[i] == items[j]) {
                items.erase(items.begin() + j);
                j--;//Roll back the iterator to prevent skipping over
            }
        }
    }
}

如果您知道每个集合中的多重性是 1 （不是multiset），那么您实际上可以用 a 替换该j--;行以break;获得更好的性能。

于 2015-05-24T11:53:33.837 回答