0

我有以下玩具代码，旨在从向量中删除重复项：

void overlap_removal(vector<int> &vec1, vector<int> &vec2) {
  for (vector<int>::iterator it1 = vec1.begin(); it1 != vec1.end(); ++it1) {
    for (vector<int>::iterator it2 = vec2.begin(); it2 != vec2.end(); ++it2) {
      if ((*it1)*(*it2) < 10) {
        vec1.erase();
      }
    }
  }
}

我在真实代码中做了一个稍微复杂的比较，但不想混淆问题。问题是在执行此操作后不可避免地会出现分段错误：我认为这是因为我正在删除一个元素，然后继续循环同一向量。

我怎样才能使代码工作？这甚至是正确的起点吗？提前致谢

4

4 回答 4

10

尝试remove_if。

基本思想是您提供一个函数对象，如果应该删除传入的元素，则返回 true ：

  class ItemInOtherVectorPred
  {
      const std::vector<int>& otherVec;

      ItemInOtherVectorPred(const std::vector<int>& vec) : otherVec(vec) {}

      // return true if removeVecsElem should be deleted
      bool operator()(const int& removeVecsElem) const
      {
          return (otherVec.find(removeVecsElem) != otherVec.end())
      }
  }

然后你使用该对象的一个​​实例来告诉 remove_if 要从你的向量中删除什么。

  void overlap_removal(vector<int> &vec1, vector<int> &vec2) 
  {
     ItemInOtherVectorPred trueIfItemInOtherVecPred( vec2);
     vector<int>::iterator eraseBeg = 
             std::remove_if( vec1.begin(), vec1.end(), trueIfItemInOtherVecPred);
     vec1.erase(eraseBeg, vec1.end());

  }
于 2010-09-26T14:59:50.927 回答
3

如果我想尽可能地保留你的逻辑，我会这样做。

it1在外部循环结束时更新，具体取决于是否在内部循环中找到匹配项。

使用引用传递参数以避免复制输入并确保第一个输入反映更改。

第二个vector是const。

void overlap_removal(vector<int>& vec1, const vector<int>& vec2) {
  for (vector<int>::iterator it1 = vec1.begin(); it1 != vec1.end(); ) {
    bool match(false);
    for (vector<int>::const_iterator it2 = vec2.begin(); it2 != vec2.end(); ++it2) {
      if (*it1 == *it2) {
        match = true;
        break;
      }
    }
    if (match)
    {
      it1 = vec1.erase(it1);
    }
    else
    {
       ++it1;
    }
  }
}

使用 STL 功能有更好的方法来做到这一点，但我看到其他人正在发布。尽管如此，了解向量方法的工作原理还是很好的，即使您可以在这种情况下绕过它们。

于 2010-09-26T15:02:34.873 回答
1

确实如此。删除元素后，迭代器无效。每次删除元素时都必须创建一个新的迭代器。

于 2010-09-26T15:02:19.927 回答
0

如果 vec2 很大或有很多重复元素（在此函数中一遍又一遍地无用地扫描），则对第二个向量进行排序并将其放入（无序）集合中可能更有效，以降低复杂性。

#include <vector>
#include <unordered_set>
#include <iostream>
#include <iterator>
#include <algorithm>
void overlap_removal(std::vector<int> &v1, const std::vector<int> &v2) 
{
    std::unordered_set<int> s(v2.begin(), v2.end());
    v1.erase(std::remove_if(v1.begin(), v1.end(),
                            [&s](int i){return s.count(i);}),
             v1.end());
}
int main()
{
    std::vector<int> v1 = {5,6,3,2,3,5,1,2,1};
    std::vector<int> v2 = {2,3};
    overlap_removal(v1, v2);
    copy(v1.begin(), v1.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

或者，保持 C++98

struct IsInSet {
    const std::set<int>& m_s;
    IsInSet(const std::set<int>& s) : m_s(s) {} 
    bool operator()(int i) const { return m_s.count(i); }
};
void overlap_removal(std::vector<int> &v1, const std::vector<int> &v2) 
{
    std::set<int> s(v2.begin(), v2.end());
    v1.erase( std::remove_if(v1.begin(), v1.end(), IsInSet(s)), v1.end());
}
于 2010-09-26T16:40:56.203 回答