Удаление дубликатов из первого вектора посредством значений из второго вектора(без сортировки)

Рейтинг: 0Ответов: 2Опубликовано: 24.03.2023

Всем добрый вечер. Нарисовалась такая проблема. Никак не могу удалить дубликаты значений в первом векторе. Сравниваюсь со значениями, которые находятся во втором векторе. Бегу и проверяю по одному значению весь вектор. Написал вот такую функцию. Предполагаю, что проблема с выходом за границы, но никак не могу победить... Подскажите пожалуйста, как решить проблему.

//    v{1,3,5,6,7,6,4,8}
//    v2{1,2,3,5,7,8}
        void dropDupl(std::vector<int>& v, std::vector<int>& v2)
        {
            int cht = 0;
            for (auto base = v.begin(); base != v.end(); )
            {
            
                for (auto base2 = v2.begin(); base2 != v2.end(); ++base)
                {
                    cht++;
                    if (*base == *base2)
                    {
                        v.erase(base);
                    }
                }
            }
        
        }
c# vector
Источник: Stack Overflow на русском

Ответы

▲ 3Принят

Первый цикл не меняет итератор. Второй цикл меняет чужой итератор. Если это исправить, ваш код перестанет рушиться (наверно), но проблема останется.

Не надо менять вектор по которому вы итерируетесь. Эта проблема такая распространнённая что для её решения придумана идиома erase-remove. Годные элементы сдвигаются в начало вектора (remove), когда весь вектор обработан его хвост обрезается (erase).

Если менять ваш код как можно меньше получится что-то такое:

void dropDupl(std::vector<int>& v, std::vector<int>& v2)
{
    auto dupl = [&v2](auto value)
    {
        for (auto base2 = v2.begin(); base2 != v2.end(); ++base2)
        {
            if (value == *base2)
            {
                return true;
            }
        }
        return false;
    };

    v.erase(std::remove_if(v.begin(), v.end(), dupl), v.end());
}

Или такое:

void dropDupl(std::vector<int>& v, const std::vector<int>& v2)
{
    auto dupl = [&v2](auto value)
    {
        return std::find(v2.begin(), v2.end(), value) != v2.end();
    };

    v.erase(std::remove_if(v.begin(), v.end(), dupl), v.end());
}

P.S. Рекомендую тип v2 поменять на set или unordered_set. Будет намного быстрее.

P.P.S. Если вам интересно как устроен remove_if...

p пробегает все элементы v. q указывает на элемент за последним годным. В начале пока все элементы ещё годные, p и q двигаются синхронно. Как только пройден первый негодный элемент, q начнёт отставать от p, а присваивание начнёт сдвигать годные элементы левее. После цикла все годные элементы собраны в начале вектора, q указывает на позицию за последним годным элементом:

template<typename Vector, typename Pred>
typename Vector::iterator remove_if(Vector& v, Pred pred)
{
    auto q = v.begin();
    for (auto p = v.begin(); p != v.end(); ++p) {
        if (!pred(*p)) {
            *q = *p;
            ++q;
        }
    }
    return q;
}

Настоящий исходный код remove_if имеет другой интерфейс, и работает быстрее за счёт исключения самоприсваиваний.

▲ 0

Команда erase портит итераторы и дальнейший цикл с ними не возможен. Цикл по указателям тоже не пойдёт, так как расположение в памяти может измениться.
Постоянная работа с памятью портит производительность, так-что желательно пока память не трогать.
Ваши циклы неправильны, так как вы забываете добавлять ++ base2
Пробуем цикл делать по индексам и при нахождении дубля делаем swap с последним элементом. После всей работы в конце избавляемся от этих дублей, что остались в конце вектора.

# include <vector>
void dropDupl ( std::vector<int>& v , std::vector<int> const & v2 ) {
  std::size_t vs = v . size ( ) ;
  for ( std :: size_t i = 0; i < vs ; ++ i ) {
    for ( auto base2 = v2.cbegin(); base2 != v2.cend(); ++base2 ) {
      if ( v [ i ] == * base2 ) {
        // дубли проверять не будем
        -- vs ;
        // заменяем последний элемент с этим местом
        std :: swap (v[i],v[vs]);
        // продолжим проверять с этого-же места
        -- i ;
        // выходим из второго цикла поиска
        break;
      }
    }
  }
  // теперь уже остальные элементы забываем
  v . resize ( vs ) ;
}