Удаление одинаковых элементов в двух векторах C ++

Question

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

Моя реализация выглядит следующим образом:

for (int i = vec1.size() - 1; i >= 0; i--) {
     for (int j = 0; j < vec2.size(); j++) {
          if (vec1[i] == vec2[j]) {
             vec1.erase(vec1.begin() + i);
             vec2.erase(vec2.begin() + j);
          }
     }
}

Однако, хотя это работает в большинстве случаев, я сталкиваюсь с тем, что это не так. Это то, как я перебираю эти векторы, или я все делаю неправильно?

Answer 1

Попробуйте использовать std::set_difference, чтобы вычесть один вектор из другого, и они объединят эти вычитания с помощью std::merge. Но для использования этих функций необходимо отсортировать векторы, поэтому сначала используйте std::sort. Код здесь:

void TraceVector( std::vector<int> v, const std::string& title )
{
    if ( !title.empty() )
    {
        std::cout << title << std::endl;
    }

    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ","));
    std::cout << std::endl;
}

int main() {

    std::vector<int> Vec1 {7, 1, 2, 5, 5, 5, 8, 9};
    std::vector<int> Vec2 {3, 2, 5, 7, 10};
    std::vector<int> Difference1; // Contains subtraction Vec1 - Vec2
    std::vector<int> Difference2;// Contains subtraction Vec2 - Vec1
    std::vector<int> Merged; // RESULT Merged vector after subtractions

    //Need to be sorted
    std::sort(Vec1.begin(), Vec1.end());
    std::sort(Vec2.begin(), Vec2.end());

    TraceVector(Vec1, "Vec1 sorted is: ");
    TraceVector(Vec2, "Vec2 sorted is: ");

    //Make subtractions
    std::set_difference(Vec1.begin(), Vec1.end(), Vec2.begin(), Vec2.end(),
                        std::inserter(Difference1, Difference1.begin()));
    std::set_difference(Vec2.begin(), Vec2.end(), Vec1.begin(), Vec1.end(),
                        std::inserter(Difference2, Difference2.begin()));


    TraceVector(Difference1, "Difference is: ");
    TraceVector(Difference2, "Difference is: ");

    //Merge subtrctions
    std::merge(Difference1.begin(), Difference1.end(), Difference2.begin(), Difference2.end(), back_inserter(Merged));
    TraceVector(Merged, "Merged is: ");
}

Вывод:

Vec1 sorted is: 
1,2,5,5,5,7,8,9,
Vec2 sorted is: 
2,3,5,7,10,
Difference is: 
1,5,5,8,9,
Difference is: 
3,10,
Merged is: 
1,3,5,5,8,9,10,
Program ended with exit code: 0

Answer 2

Проблема заключается в том, что вы продолжаете получать доступ к vec1[i], когда зацикливаетесь на vec2 после удаления элемента из vec1 и vec2. Это вызывает неопределенное поведение, если вы делаете это после удаления последнего элемента в vec1, так как vec1[i] больше не действителен. Добавьте оператор break в if, чтобы исправить это.

for (int i = vec1.size() - 1; i >= 0; i--) {
     for (int j = 0; j < vec2.size(); j++) {
          if (vec1[i] == vec2[j]) {
             vec1.erase(vec1.begin() + i);
             vec2.erase(vec2.begin() + j);
             break; // Look at next element in vec1
          }
     }
}

Существует также более эффективный способ сделать это (O(n*log(n)+m*log(m)+n+m) вместо O(n*m) для n=vec1.size() и m=vec2.size()). Это включает в себя сортировку векторов. Я оставлю это вам, чтобы выяснить.

Answer 3

На самом деле вам вообще не нужно повторять в обратном направлении. В этом случае ваш код может быть:

for (int i = 0; i < vec1.size(); i++) {
     for (int j = 0; j < vec2.size(); j++) {
          if (vec1[i] == vec2[j]) {
             vec1.erase(vec1.begin() + i);
             vec2.erase(vec2.begin() + j);
          }
     }
}

Но подождите ... что происходит после того, как мы стерли элемент? Тогда у всех элементов после этого их индексы уменьшатся на 1, поэтому мы пропустим следующий элемент! Чтобы исправить это, мы можем добавить эту маленькую модификацию:

             vec1.erase(vec1.begin() + i--);
             vec2.erase(vec2.begin() + j--);
                                       ^^^^

Это будет работать, даже когда мы меняем размер, стирая, потому что мы проверяем размер vec2 каждого цикла! Но что, если мы в конечном итоге удалим последний элемент vec1? Мы не будем снова сравнивать его размер, пока не проведем итерацию all до vec2, что будет проблемой в вашем примере vec1 = {2}, vec2 = {2, 2, 2}. Чтобы это исправить, мы можем просто выйти из внутреннего цикла и повторить проверку на vec2.

Сложите все это вместе (и замените ваш оператор индекса на .at() вызовы, чтобы у нас была проверка границ), и вы получите:

for (int i = 0; i < vec1.size(); i++) {
     for (int j = 0; j < vec2.size(); j++) {
          if (vec1.at(i) == vec2.at(j)) {
             vec1.erase(vec1.begin() + i--);
             vec2.erase(vec2.begin() + j--);
             break;
          }
     }
}

(см. Здесь в действии: ideone )

Answer 4

Если вы можете сортировать, вы можете сделать что-то вроде этого:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {

  std::vector<int> ex {3, 1, 2, 3, 3, 4, 5}, as {2, 3, 6, 1, 1, 1}, tmp;

  std::sort(std::begin(ex), std::end(ex));
  std::sort(std::begin(as), std::end(as));

  as.erase(
    std::remove_if(
      std::begin(as),std::end(as),
      [&](int const& s){
        bool found = std::binary_search(std::begin(ex), std::end(ex), s);
        if (found) {
          tmp.push_back(s);
        }
        return found;}), std::end(as));
  for (auto const& i : tmp) {
    ex.erase(std::remove(std::begin(ex),std::end(ex), i), std::end(ex));
  }

}