Как удалить дубликаты из unsorted std :: vector, сохраняя исходный порядок с использованием алгоритмов?

У меня есть массив целых чисел, в котором мне нужно удалить дубликаты, сохраняя при этом порядок первого вхождения каждого целого числа. Я вижу, как это делается, но представьте себе, что лучше использовать алгоритмы STL лучше? Вставка не входит в мой контроль, поэтому я не могу проверить дубликаты перед вставкой.

int unsortedRemoveDuplicates(std::vector &numbers) { std::set uniqueNumbers; std::vector::iterator allItr = numbers.begin(); std::vector::iterator unique = allItr; std::vector::iterator endItr = numbers.end(); for (; allItr != endItr; ++allItr) { const bool isUnique = uniqueNumbers.insert(*allItr).second; if (isUnique) { *unique = *allItr; ++unique; } } const int duplicates = endItr - unique; numbers.erase(unique, endItr); return duplicates; } 

Как это можно сделать с использованием алгоритмов STL?

Наивный способ – использовать std::set как вам все говорят. Это слишком много, и у него плохая локализация кэша (медленная).
Умный способ – правильно использовать std::vector (обязательно посмотрите сноску внизу):

 #include  #include  struct target_less { template bool operator()(It const &a, It const &b) const { return *a < *b; } }; struct target_equal { template bool operator()(It const &a, It const &b) const { return *a == *b; } }; template It uniquify(It begin, It const end) { std::vector v; v.reserve(static_cast(std::distance(begin, end))); for (It i = begin; i != end; ++i) { v.push_back(i); } std::sort(v.begin(), v.end(), target_less()); v.erase(std::unique(v.begin(), v.end(), target_equal()), v.end()); std::sort(v.begin(), v.end()); size_t j = 0; for (It i = begin; i != end && j != v.size(); ++i) { if (i == v[j]) { using std::iter_swap; iter_swap(i, begin); ++j; ++begin; } } return begin; } 

Затем вы можете использовать его так:

 int main() { std::vector v; v.push_back(6); v.push_back(5); v.push_back(5); v.push_back(8); v.push_back(5); v.push_back(8); v.erase(uniquify(v.begin(), v.end()), v.end()); } 

* Примечание. Это разумный способ в типичных случаях , когда количество дубликатов не слишком велико. Более подробный анализ производительности см. В соответствующем ответе на соответствующий вопрос .

Звучит как работа для std :: copy_if . Определите предикат, который отслеживает уже обработанные элементы и возвращает false, если они есть.

Если у вас нет поддержки на C ++ 11, вы можете использовать неуклюжие имена std :: remove_copy_if и инвертировать логику.

Это непроверенный пример:

 template  struct NotDuplicate { bool operator()(const T& element) { return s_.insert(element).second; // true if s_.insert(element); } private: std::set s_; }; 

затем

 std::vector uniqueNumbers; NotDuplicate pred; std::copy_if(numbers.begin(), numbers.end(), std::back_inserter(uniqueNumbers), std::ref(pred)); 

где std::ref использовался, чтобы избежать потенциальных проблем с алгоритмом, внутренне копирующим то, что является функтором с сохранением состояния, хотя std::copy_if не устанавливает никаких требований к побочным эффектам применяемого функтора.

 int unsortedRemoveDuplicates(std::vector& numbers) { std::set seenNums; //log(n) existence check auto itr = begin(numbers); while(itr != end(numbers)) { if(seenNums.find(*itr) != end(seenNums)) //seen? erase it itr = numbers.erase(itr); //itr now points to next element else { seenNums.insert(*itr); itr++; } } return seenNums.size(); } //3 6 3 8 9 5 6 8 //3 6 8 9 5 

Быстро и просто, C ++ 11:

 template size_t RemoveDuplicatesKeepOrder(std::vector& vec) { std::set seen; auto newEnd = std::remove_if(vec.begin(), vec.end(), [&seen](const T& value) { if (seen.find(value) != std::end(seen)) return true; seen.insert(value); return false; }); vec.erase(newEnd, vec.end()); return vec.size(); } 

Чтобы проверить эффективность предлагаемых решений, я проверил три из них, перечисленных ниже. В тестах используются случайные векторы с 1 млн элементов и разное соотношение дубликатов (0%, 1%, 2%, …, 10%, …, 90%, 100%).

  • Решение Мехрдада , в настоящее время принятый ответ:

     void uniquifyWithOrder_sort(const vector&, vector& output) { using It = vector::iterator; struct target_less { bool operator()(It const &a, It const &b) const { return *a < *b; } }; struct target_equal { bool operator()(It const &a, It const &b) const { return *a == *b; } }; auto begin = output.begin(); auto const end = output.end(); { vector v; v.reserve(static_cast(distance(begin, end))); for (auto i = begin; i != end; ++i) { v.push_back(i); } sort(v.begin(), v.end(), target_less()); v.erase(unique(v.begin(), v.end(), target_equal()), v.end()); sort(v.begin(), v.end()); size_t j = 0; for (auto i = begin; i != end && j != v.size(); ++i) { if (i == v[j]) { using std::iter_swap; iter_swap(i, begin); ++j; ++begin; } } } output.erase(begin, output.end()); } 
  • решение juanchopanza

     void uniquifyWithOrder_set_copy_if(const vector& input, vector& output) { struct NotADuplicate { bool operator()(const int& element) { return _s.insert(element).second; } private: set _s; }; vector uniqueNumbers; NotADuplicate pred; output.clear(); output.reserve(input.size()); copy_if( input.begin(), input.end(), back_inserter(output), ref(pred)); } 
  • Решение Левиафана

     void uniquifyWithOrder_set_remove_if(const vector& input, vector& output) { set seen; auto newEnd = remove_if(output.begin(), output.end(), [&seen](const int& value) { if (seen.find(value) != end(seen)) return true; seen.insert(value); return false; }); output.erase(newEnd, output.end()); } 

Они немного модифицированы для простоты и позволяют сравнивать решения на месте, а не на месте. Полный код, используемый для тестирования, доступен здесь .

Результаты показывают, что если вы знаете, что у вас будет не менее 1% дубликатов, решение remove_if с std::set является лучшим. В противном случае вы должны пойти с решением sort :

 // Intel(R) Core(TM) i7-2600 CPU @ 3.40 GHz 3.40 GHz // 16 GB RAM, Windows 7, 64 bit // // cl 19 // /GS /GL /W3 /Gy /Zc:wchar_t /Zi /Gm- /O2 /Zc:inline /fp:precise /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /WX- /Zc:forScope /Gd /Oi /MD /EHsc /nologo /Ot // // 1000 random vectors with 1 000 000 elements each. // 11 tests: with 0%, 10%, 20%, ..., 90%, 100% duplicates in vectors. // Ratio: 0 // set_copy_if : Time : 618.162 ms +- 18.7261 ms // set_remove_if : Time : 650.453 ms +- 10.0107 ms // sort : Time : 212.366 ms +- 5.27977 ms // Ratio : 0.1 // set_copy_if : Time : 34.1907 ms +- 1.51335 ms // set_remove_if : Time : 24.2709 ms +- 0.517165 ms // sort : Time : 43.735 ms +- 1.44966 ms // Ratio : 0.2 // set_copy_if : Time : 29.5399 ms +- 1.32403 ms // set_remove_if : Time : 20.4138 ms +- 0.759438 ms // sort : Time : 36.4204 ms +- 1.60568 ms // Ratio : 0.3 // set_copy_if : Time : 32.0227 ms +- 1.25661 ms // set_remove_if : Time : 22.3386 ms +- 0.950855 ms // sort : Time : 38.1551 ms +- 1.12852 ms // Ratio : 0.4 // set_copy_if : Time : 30.2714 ms +- 1.28494 ms // set_remove_if : Time : 20.8338 ms +- 1.06292 ms // sort : Time : 35.282 ms +- 2.12884 ms // Ratio : 0.5 // set_copy_if : Time : 24.3247 ms +- 1.21664 ms // set_remove_if : Time : 16.1621 ms +- 1.27802 ms // sort : Time : 27.3166 ms +- 2.12964 ms // Ratio : 0.6 // set_copy_if : Time : 27.3268 ms +- 1.06058 ms // set_remove_if : Time : 18.4379 ms +- 1.1438 ms // sort : Time : 30.6846 ms +- 2.52412 ms // Ratio : 0.7 // set_copy_if : Time : 30.3871 ms +- 0.887492 ms // set_remove_if : Time : 20.6315 ms +- 0.899802 ms // sort : Time : 33.7643 ms +- 2.2336 ms // Ratio : 0.8 // set_copy_if : Time : 33.3077 ms +- 0.746272 ms // set_remove_if : Time : 22.9459 ms +- 0.921515 ms // sort : Time : 37.119 ms +- 2.20924 ms // Ratio : 0.9 // set_copy_if : Time : 36.0888 ms +- 0.763978 ms // set_remove_if : Time : 24.7002 ms +- 0.465711 ms // sort : Time : 40.8233 ms +- 2.59826 ms // Ratio : 1 // set_copy_if : Time : 21.5609 ms +- 1.48986 ms // set_remove_if : Time : 14.2934 ms +- 0.535431 ms // sort : Time : 24.2485 ms +- 0.710269 ms 

 // Ratio: 0 // set_copy_if : Time: 666.962 ms +- 23.7445 ms // set_remove_if : Time: 736.088 ms +- 39.8122 ms // sort : Time: 223.796 ms +- 5.27345 ms // Ratio: 0.01 // set_copy_if : Time: 60.4075 ms +- 3.4673 ms // set_remove_if : Time: 43.3095 ms +- 1.31252 ms // sort : Time: 70.7511 ms +- 2.27826 ms // Ratio: 0.02 // set_copy_if : Time: 50.2605 ms +- 2.70371 ms // set_remove_if : Time: 36.2877 ms +- 1.14266 ms // sort : Time: 62.9786 ms +- 2.69163 ms // Ratio: 0.03 // set_copy_if : Time: 46.9797 ms +- 2.43009 ms // set_remove_if : Time: 34.0161 ms +- 0.839472 ms // sort : Time: 59.5666 ms +- 1.34078 ms // Ratio: 0.04 // set_copy_if : Time: 44.3423 ms +- 2.271 ms // set_remove_if : Time: 32.2404 ms +- 1.02162 ms // sort : Time: 57.0583 ms +- 2.9226 ms // Ratio: 0.05 // set_copy_if : Time: 41.758 ms +- 2.57589 ms // set_remove_if : Time: 29.9927 ms +- 0.935529 ms // sort : Time: 54.1474 ms +- 1.63311 ms // Ratio: 0.06 // set_copy_if : Time: 40.289 ms +- 1.85715 ms // set_remove_if : Time: 29.2604 ms +- 0.593869 ms // sort : Time: 57.5436 ms +- 5.52807 ms // Ratio: 0.07 // set_copy_if : Time: 40.5035 ms +- 1.80952 ms // set_remove_if : Time: 29.1187 ms +- 0.63127 ms // sort : Time: 53.622 ms +- 1.91357 ms // Ratio: 0.08 // set_copy_if : Time: 38.8139 ms +- 1.9811 ms // set_remove_if : Time: 27.9989 ms +- 0.600543 ms // sort : Time: 50.5743 ms +- 1.35296 ms // Ratio: 0.09 // set_copy_if : Time: 39.0751 ms +- 1.71393 ms // set_remove_if : Time: 28.2332 ms +- 0.607895 ms // sort : Time: 51.2829 ms +- 1.21077 ms // Ratio: 0.1 // set_copy_if : Time: 35.6847 ms +- 1.81495 ms // set_remove_if : Time: 25.204 ms +- 0.538245 ms // sort : Time: 46.4127 ms +- 2.66714 ms 

Вот что ищет WilliamKF. Он использует инструкцию стирания. Этот код хорош для списков, но не подходит для векторов. Для векторов вы не должны использовать оператор стирания.

 //makes uniques in one shot without sorting !! template inline void uniques(listtype* In) { listtype::iterator it = In->begin(); listtype::iterator it2= In->begin(); int tmpsize = In->size(); while(it!=In->end()) { it2 = it; it2++; while((it2)!=In->end()) { if ((*it)==(*it2)) In->erase(it2++); else ++it2; } it++; } } в //makes uniques in one shot without sorting !! template inline void uniques(listtype* In) { listtype::iterator it = In->begin(); listtype::iterator it2= In->begin(); int tmpsize = In->size(); while(it!=In->end()) { it2 = it; it2++; while((it2)!=In->end()) { if ((*it)==(*it2)) In->erase(it2++); else ++it2; } it++; } } в //makes uniques in one shot without sorting !! template inline void uniques(listtype* In) { listtype::iterator it = In->begin(); listtype::iterator it2= In->begin(); int tmpsize = In->size(); while(it!=In->end()) { it2 = it; it2++; while((it2)!=In->end()) { if ((*it)==(*it2)) In->erase(it2++); else ++it2; } it++; } } 

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

 //makes vectors as fast as possible unique template inline void vectoruniques(std::vector* In) { int tmpsize = In->size(); for (std::vector::iterator it = In->begin();itend()-1;it++) { T tmp = *it; for (std::vector::iterator it2 = it+1;it2end();it2++) { if (*it2!=*it) tmp = *it2; else *it2 = tmp; } } std::vector::iterator it = std::unique(In->begin(),In->end()); int newsize = std::distance(In->begin(),it); In->resize(newsize); } 

Как-то похоже, что это сработает. Я тестировал его, может быть, может кто-нибудь скажет, действительно ли это работает! Этому решению не нужен какой-либо более крупный оператор. Я имею в виду, почему использовать более высокий оператор для поиска уникальных элементов? Использование векторов:

 int myints[] = {21,10,20,20,20,30,21,31,20,20,2}; std::vector abc(myints , myints+11); vectoruniques(&abc); 

Это то, что обрабатывает типы POD и non-POD с поддержкой перемещения. Использует оператор по умолчанию == или пользовательский предикат равенства. Не требует сортировки / оператора <, генерации ключей или отдельного набора. Не знаю, является ли это более эффективным, чем другие методы, описанные выше.

 template > void remove_duplicates( Cnt& cnt, _Pr cmp = _Pr() ) { Cnt result; result.reserve( std::size( cnt ) ); // or cnt.size() if compiler doesn't support std::size() std::copy_if( std::make_move_iterator( std::begin( cnt ) ) , std::make_move_iterator( std::end( cnt ) ) , std::back_inserter( result ) , [&]( const typename Cnt::value_type& what ) { return std::find_if( std::begin( result ) , std::end( result ) , [&]( const typename Cnt::value_type& existing ) { return cmp( what, existing ); } ) == std::end( result ); } ); // copy_if cnt = std::move( result ); // place result in cnt param } // remove_duplicates 

Использование / тесты:

 { std::vector ints{ 0,1,1,2,3,4 }; remove_duplicates( ints ); assert( ints.size() == 5 ); } { struct data { std::string foo; bool operator==( const data& rhs ) const { return this->foo == rhs.foo; } }; std::vector mydata{ { "hello" }, {"hello"}, {"world"} } , mydata2 = mydata ; // use operator== remove_duplicates( mydata ); assert( mydata.size() == 2 ); // use custom predicate remove_duplicates( mydata2, []( const data& left, const data& right ) { return left.foo == right.foo; } ); assert( mydata2.size() == 2 ); } 

Вот обобщенная версия c ++ 11, которая работает с iteratorами и не выделяет дополнительное хранилище. Возможно, он имеет недостаток O (n ^ 2), но, скорее всего, быстрее для меньших размеров ввода.

 template Iter removeDuplicates(Iter begin,Iter end) { auto it = begin; while(it != end) { auto next = std::next(it); if(next == end) { break; } end = std::remove(next,end,*it); it = next; } return end; } 

….

 std::erase(removeDuplicates(vec.begin(),vec.end()),vec.end()); 

Пример кода: http://cpp.sh/5kg5n

  • Добавляет ли дублирующее значение в HashSet / HashMap прежнее значение
  • Java HashSet содержит дубликаты, если содержащийся элемент изменен
  • Поиск всех повторяющихся строк, включая «элементы с меньшими индексами»,
  • Найти дубликаты записей в MySQL
  • Давайте будем гением компьютера.