Обведите два вектора, удалите элементы 1

Question

У меня есть следующий игрушечный код, предназначенный для удаления дубликатов из вектора:

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();
      }
    }
  }
}

Я делаю немного более сложное сравнение в реальном коде, но не хотел путать вопросы. Проблема заключается в ошибке сегментации, которая неизбежно следует за выполнением этого: я думаю, это связано с тем, что я удаляю элемент, а затем продолжаю зацикливаться на том же векторе.

Как я могу заставить код работать? Это даже правильная отправная точка? Заранее спасибо

Answer 1

Попробуйте 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());

  }

Answer 2

Если бы я хотел сохранить вашу логику, насколько это возможно, я бы сделал это так.

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, но другие публикуют сообщения об этом, как я вижу. Тем не менее, хорошо понимать, как работают векторные методы, даже если вы можете обойти их в этом случае.

Answer 3

Это правда.После удаления элемента ваш итератор становится недействительным.Вы должны создавать новый итератор каждый раз, когда удаляете элемент.

Answer 4

Если 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());
}