Jaki jest najskuteczniejszy sposób usuwania duplikatów i sortowania wektora?

274

Muszę wziąć wektor C ++ z potencjalnie dużą ilością elementów, usunąć duplikaty i posortować.

Obecnie mam poniższy kod, ale to nie działa.

vec.erase(
      std::unique(vec.begin(), vec.end()),
      vec.end());
std::sort(vec.begin(), vec.end());

Jak mogę to poprawnie zrobić?

Ponadto, czy szybciej jest najpierw usunąć duplikaty (podobnie jak w kodowaniu powyżej) czy najpierw wykonać sortowanie? Jeśli najpierw wykonam sortowanie, czy na pewno pozostanie posortowane po std::uniquewykonaniu?

Czy jest jeszcze inny (być może bardziej wydajny) sposób na wykonanie tego wszystkiego?

Kyle Ryan
źródło
3
Zakładam, że nie masz możliwości sprawdzenia przed włożeniem, aby uniknąć duplikatów?
Joe
Poprawny. To byłoby idealne.
Kyle Ryan
29
Sugerowałbym poprawienie powyższego kodu lub naprawdę wskazanie, że jest on ZŁY. std :: unique zakłada, że ​​zakres jest już posortowany.
Matthieu M.,

Odpowiedzi:

584

Zgadzam się z R. Pate i Toddem Gardnerem ; std::setmoże być dobrym pomysłem tutaj. Nawet jeśli utkniesz przy użyciu wektorów, jeśli masz wystarczającą liczbę duplikatów, lepiej byłoby stworzyć zestaw do brudnej roboty.

Porównajmy trzy podejścia:

Wystarczy użyć wektora, sortuj + unikatowe

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

Konwertuj na zestaw (ręcznie)

set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

Konwertuj na zestaw (za pomocą konstruktora)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

Oto jak działają one jako liczba zmian duplikatów:

porównanie podejść wektorowych i ustawionych

Podsumowanie : gdy liczba duplikatów jest wystarczająco duża, konwersja na zestaw jest w rzeczywistości szybsza, a następnie zrzucenie danych z powrotem do wektora .

I z jakiegoś powodu ręczne wykonanie konwersji zestawu wydaje się być szybsze niż użycie konstruktora zestawu - przynajmniej na losowych danych zabawki, których użyłem.

Nate Kohl
źródło
61
Jestem zszokowany, że podejście konstruktora jest konsekwentnie gorsze mierzalnie niż ręczne. Zrobiłbyś to, poza niewielkim stałym kosztem, po prostu robiłby to ręcznie. Czy ktoś może to wyjaśnić?
Ari
17
Fajnie, dzięki za wykres. Czy możesz podać, jakie są jednostki dla liczby duplikatów? (tj. w przybliżeniu, jak duży jest „wystarczająco duży”)?
Kyle Ryan
5
@Kyle: Jest dość duży. Użyłem zestawów danych z 1 000 000 losowo narysowanych liczb całkowitych od 1 do 1000, 100 i 10 dla tego wykresu.
Nate Kohl
5
Myślę, że twoje wyniki są błędne. W moich testach im bardziej zduplikowane elementy, tym szybszy wektor (porównawczy), faktycznie skaluje się na odwrót. Czy skompilowałeś z włączonymi optymalizacjami i wyłączonymi kontrolami czasu wykonywania ?. Po mojej stronie wektor jest zawsze szybszy, do 100x w zależności od liczby duplikatów. VS2013, cl / Ox -D_SECURE_SCL = 0.
davidnr
39
Wydaje się, że brakuje opisu osi x.
BartoszKP
72

Zredagowałem profilowanie Nate'a Kohla i uzyskałem różne wyniki. W moim przypadku testowym bezpośrednie sortowanie wektora jest zawsze bardziej wydajne niż użycie zestawu. Dodałem nową, bardziej wydajną metodę, używając unordered_set.

Pamiętaj, że unordered_setmetoda działa tylko wtedy, gdy masz dobrą funkcję skrótu dla typu, którego potrzebujesz unikatowo i posortowanego. Dla ints jest to łatwe! (Standardowa biblioteka zawiera domyślny skrót, który jest po prostu funkcją tożsamości). Nie zapomnij również posortować na końcu, ponieważ zestaw_uporządkowany jest, no, nieuporządkowany :)

Zrobiłem trochę kopania wewnątrz seti unordered_setwdrożenia i odkrył, że konstruktor faktycznie zbudować nowy węzeł dla każdego elementu, przed sprawdzeniem jego wartości w celu określenia, czy powinien to być rzeczywiście włożona (w realizacji programu Visual Studio, przynajmniej).

Oto 5 metod:

f1: Tylko używając vector, sort+unique

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

f2: Konwertuj na set(za pomocą konstruktora)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

f3: Konwertuj na set(ręcznie)

set<int> s;
for (int i : vec)
    s.insert(i);
vec.assign( s.begin(), s.end() );

f4: Konwertuj na unordered_set(za pomocą konstruktora)

unordered_set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );

f5: Konwertuj na unordered_set(ręcznie)

unordered_set<int> s;
for (int i : vec)
    s.insert(i);
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );

Zrobiłem test z wektorem 100 000 000 ints wybranych losowo w zakresach [1,10], [1,1000] i [1,100000]

Wyniki (w sekundach im mniejsze, tym lepiej):

range         f1       f2       f3       f4      f5
[1,10]      1.6821   7.6804   2.8232   6.2634  0.7980
[1,1000]    5.0773  13.3658   8.2235   7.6884  1.9861
[1,100000]  8.7955  32.1148  26.5485  13.3278  3.9822
alexk7
źródło
4
W przypadku liczb całkowitych możesz użyć sortowania radix, który jest znacznie szybszy niż std :: sort.
Changming Sun
2
Szybka wskazówka, aby użyć sortlub uniquemetod, musisz#include <algorithm>
Davmrtl
3
@ChangmingSun Zastanawiam się, dlaczego optymalizator wydawał się nie działać na F4? Liczby są diametralnie różne od f5. To nie ma dla mnie żadnego sensu.
sandthorn
1
@sandthorn Jak wyjaśniono w mojej odpowiedzi, implementacja buduje węzeł (w tym dynamiczny przydział) dla każdego elementu z sekwencji wejściowej, co jest marnotrawstwem dla każdej wartości, która ostatecznie jest duplikatem. Optymalizator nie może wiedzieć, że może to pominąć.
alexk7
Ach, to przypomina mi jedną z przemówień Scotta Meyera o CWUK sceneriach, które mają naturę możliwości spowolnienia tego emplacerodzaju budowy.
sandthorn,
57

std::unique usuwa zduplikowane elementy tylko wtedy, gdy są sąsiadami: musisz najpierw posortować wektor, zanim zadziała on zgodnie z twoimi zamierzeniami.

std::unique jest zdefiniowany jako stabilny, więc wektor będzie nadal sortowany po uruchomieniu na nim unikalnego.

jskinner
źródło
42

Nie jestem pewien, do czego go używasz, więc nie mogę tego powiedzieć ze 100% pewnością, ale normalnie, kiedy myślę o „posortowanym, unikalnym” pojemniku, myślę o std :: set . Może lepiej pasować do twojej skrzynki użytkownika:

std::set<Foo> foos(vec.begin(), vec.end()); // both sorted & unique already

W przeciwnym razie posortowanie przed wywołaniem unikalnego (jak wskazały inne odpowiedzi) jest dobrym rozwiązaniem.

Todd Gardner
źródło
Do rzeczy! std :: set jest określony jako posortowany unikalny zestaw. Większość implementacji wykorzystuje wydajne uporządkowane drzewo binarne lub coś podobnego.
notnoop
+1 Myśl o zestawie również. Nie chciałem powielać tej odpowiedzi
Tom
Czy gwarantowane jest sortowanie std :: set? Ma to sens w praktyce, ale czy wymaga tego standard?
MadCoder,
1
Tak, patrz 23.1.4.9 „Podstawową właściwością iteratorów kontenerów asocjacyjnych jest to, że iterują one przez kontenery w kolejności malejącej kluczy, w których wartość nie-malejąca jest zdefiniowana przez porównanie użyte do ich zbudowania”
Todd Gardner
1
@MadCoder: niekoniecznie „ma sens”, że zestaw jest implementowany w sposób posortowany. Istnieją również zestawy zaimplementowane przy użyciu tabel skrótów, które nie są sortowane. W rzeczywistości większość ludzi woli używać tabel skrótów, jeśli są dostępne. Ale konwencja nazewnictwa w C ++ zdarza się tak, że posortowane pojemniki asocjacyjne są nazywane po prostu „set” / „map” (analogicznie do TreeSet / TreeMap w Javie); a zaszyfrowane kontenery asocjacyjne, które zostały pominięte w standardzie, nazywane są „hash_set” / „hash_map” (SGI STL) lub „unordered_set” / „unordered_map” (TR1) (analogicznie do HashSet i HashMap w Javie)
newacct
22

std::uniquedziała tylko na kolejnych seriach zduplikowanych elementów, więc lepiej najpierw posortuj. Jest jednak stabilny, więc wektor pozostanie posortowany.

David Seiler
źródło
18

Oto szablon, który możesz dla Ciebie zrobić:

template<typename T>
void removeDuplicates(std::vector<T>& vec)
{
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}

nazwij to tak:

removeDuplicates<int>(vectorname);
DShook
źródło
2
+1 Templatize away! - ale możesz po prostu napisać removeDuplicates (vec), bez wyraźnego podawania argumentów szablonu
Faisal Vali
10
Lub jeszcze lepiej, po prostu weź iteratory szablonów bezpośrednio (początek i koniec), i możesz uruchomić go na innych strukturach poza wektorem.
Kyle Ryan,
Do diabła, szablony! szybka poprawka dla małych list, pełny styl STL. +1 thx
QuantumKarl
@Kyle - tylko w innych kontenerach, które mają erase()metodę, w przeciwnym razie musisz zwrócić nowy iterator końcowy i mieć kod wywołujący obcinający kontener.
Toby Speight,
8

Wydajność to skomplikowana koncepcja. Są względy dotyczące czasu i przestrzeni, a także ogólne pomiary (w których otrzymujesz tylko niejasne odpowiedzi, takie jak O (n)) w porównaniu do konkretnych (np. Sortowanie bąbelkowe może być znacznie szybsze niż szybkie sortowanie, w zależności od charakterystyki wejściowej).

Jeśli masz stosunkowo niewiele duplikatów, sortowanie, a następnie unikanie i usuwanie wydają się być dobrym rozwiązaniem. Jeśli miałeś stosunkowo dużo duplikatów, utworzenie zestawu z wektora i pozwolenie mu na wykonanie ciężkiego podnoszenia może go łatwo pokonać.

Nie koncentruj się tylko na wydajności czasu. Sortowanie + unikanie + wymazywanie działa w przestrzeni O (1), podczas gdy konstrukcja zestawu działa w przestrzeni O (n). I żadne z nich nie nadaje się bezpośrednio do zmniejszania równoległości map (dla naprawdę dużych zestawów danych).


źródło
Co dałoby ci zdolność mapowania / zmniejszania? Jedyne, co mogę wymyślić, to rozproszony rodzaj scalania i nadal możesz użyć tylko jednego wątku w końcowym scaleniu.
Zan Lynx,
1
Tak, musisz mieć jeden kontrolujący węzeł / wątek. Problem można jednak podzielić tyle razy, ile jest to konieczne, aby nałożyć górne ograniczenia na liczbę wątków roboczych / potomnych, którymi zajmuje się wątek kontrolny / macierzysty, oraz na rozmiar zbioru danych, który każdy węzeł liścia musi przetworzyć. Nie wszystkie problemy można łatwo rozwiązać za pomocą funkcji zmniejszania mapy, po prostu chciałem zauważyć, że są ludzie, którzy mają do czynienia z podobnymi (na powierzchni, w każdym razie) problemami z optymalizacją, gdzie radzenie sobie z 10 terabajtami danych nazywa się „wtorek”.
7

Musisz to posortować, zanim zadzwonisz, uniqueponieważ uniqueusuwa tylko duplikaty znajdujące się obok siebie.

edycja: 38 sekund ...

David Johnstone
źródło
7

uniqueusuwa tylko kolejne zduplikowane elementy (co jest konieczne, aby działało w czasie liniowym), dlatego najpierw należy wykonać sortowanie. Pozostanie posortowane po połączeniu z unique.

Piotr
źródło
7

Jeśli nie chcesz zmieniać kolejności elementów, możesz wypróbować to rozwiązanie:

template <class T>
void RemoveDuplicatesInVector(std::vector<T> & vec)
{
    set<T> values;
    vec.erase(std::remove_if(vec.begin(), vec.end(), [&](const T & value) { return !values.insert(value).second; }), vec.end());
}
jury
źródło
Być może użyj zestawu nieuporządkowanego zamiast zestawu (i doładuj :: remove_erase_if, jeśli jest dostępny)
gast128
4

Zakładając, że a jest wektorem, usuń ciągłe duplikaty za pomocą

a.erase(unique(a.begin(),a.end()),a.end());działa w czasie O (n) .

KPMG
źródło
1
ciągłe duplikaty. ok, więc potrzebuje std::sortpierwszego.
v.oddou
2

Jak już wspomniano, uniquewymaga posortowanego pojemnika. Ponadto uniquetak naprawdę nie usuwa elementów z kontenera. Zamiast tego są one kopiowane do końca, uniquezwraca iterator wskazujący na pierwszy taki zduplikowany element i oczekuje się, że zadzwonisz, eraseaby faktycznie usunąć elementy.

Max Lybbert
źródło
Czy unikalny wymaga posortowanego kontenera, czy po prostu zmienia kolejność wprowadzania, aby nie zawierał sąsiadujących duplikatów? Myślałem o tym drugim.
@Pate, masz rację. To nie wymaga. Usuwa sąsiadujące duplikaty.
Bill Lynch,
Jeśli masz kontener, który może mieć duplikaty, i chcesz kontener, który nie ma żadnych zduplikowanych wartości w dowolnym miejscu kontenera, musisz najpierw posortować kontener, a następnie przekazać go do unikalnego, a następnie użyć kasowania, aby faktycznie usunąć duplikaty . Jeśli chcesz po prostu usunąć sąsiadujące duplikaty, nie będziesz musiał sortować kontenera. Ale skończysz na zduplikowanych wartościach: 1 2 2 3 2 4 2 5 2 zostanie zmieniony na 1 2 3 2 4 2 5 2, jeśli zostanie przeniesiony do unikatowego bez sortowania, 1 2 3 4 5, jeśli zostanie posortowany, przeniesiony do unikatowego i skasowany .
Max Lybbert,
2

Standardowe podejście sugerowane przez Nate Kohla, po prostu za pomocą wektora, sortowania + unikatowego:

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

nie działa dla wektora wskaźników.

Przyjrzyj się dokładnie temu przykładowi na cplusplus.com .

W ich przykładzie „tak zwane duplikaty” przeniesione na koniec są faktycznie pokazane jako? (niezdefiniowane wartości), ponieważ te „tak zwane duplikaty” są CZASAMI „dodatkowymi elementami”, a CZASAMI są „brakujące elementy” w oryginalnym wektorze.

Problem występuje podczas używania std::unique()na wektorze wskaźników do obiektów (wycieki pamięci, zły odczyt danych z HEAP, duplikowanie zwolnień, które powodują błędy segmentacji itp.).

Oto moje rozwiązanie problemu zamienić std::unique()z ptgi::unique().

Zobacz plik ptgi_unique.hpp poniżej:

// ptgi::unique()
//
// Fix a problem in std::unique(), such that none of the original elts in the collection are lost or duplicate.
// ptgi::unique() has the same interface as std::unique()
//
// There is the 2 argument version which calls the default operator== to compare elements.
//
// There is the 3 argument version, which you can pass a user defined functor for specialized comparison.
//
// ptgi::unique() is an improved version of std::unique() which doesn't looose any of the original data
// in the collection, nor does it create duplicates.
//
// After ptgi::unique(), every old element in the original collection is still present in the re-ordered collection,
// except that duplicates have been moved to a contiguous range [dupPosition, last) at the end.
//
// Thus on output:
//  [begin, dupPosition) range are unique elements.
//  [dupPosition, last) range are duplicates which can be removed.
// where:
//  [] means inclusive, and
//  () means exclusive.
//
// In the original std::unique() non-duplicates at end are moved downward toward beginning.
// In the improved ptgi:unique(), non-duplicates at end are swapped with duplicates near beginning.
//
// In addition if you have a collection of ptrs to objects, the regular std::unique() will loose memory,
// and can possibly delete the same pointer multiple times (leading to SEGMENTATION VIOLATION on Linux machines)
// but ptgi::unique() won't.  Use valgrind(1) to find such memory leak problems!!!
//
// NOTE: IF you have a vector of pointers, that is, std::vector<Object*>, then upon return from ptgi::unique()
// you would normally do the following to get rid of the duplicate objects in the HEAP:
//
//  // delete objects from HEAP
//  std::vector<Object*> objects;
//  for (iter = dupPosition; iter != objects.end(); ++iter)
//  {
//      delete (*iter);
//  }
//
//  // shrink the vector. But Object * pointers are NOT followed for duplicate deletes, this shrinks the vector.size())
//  objects.erase(dupPosition, objects.end));
//
// NOTE: But if you have a vector of objects, that is: std::vector<Object>, then upon return from ptgi::unique(), it
// suffices to just call vector:erase(, as erase will automatically call delete on each object in the
// [dupPosition, end) range for you:
//
//  std::vector<Object> objects;
//  objects.erase(dupPosition, last);
//
//==========================================================================================================
// Example of differences between std::unique() vs ptgi::unique().
//
//  Given:
//      int data[] = {10, 11, 21};
//
//  Given this functor: ArrayOfIntegersEqualByTen:
//      A functor which compares two integers a[i] and a[j] in an int a[] array, after division by 10:
//  
//  // given an int data[] array, remove consecutive duplicates from it.
//  // functor used for std::unique (BUGGY) or ptgi::unique(IMPROVED)
//
//  // Two numbers equal if, when divided by 10 (integer division), the quotients are the same.
//  // Hence 50..59 are equal, 60..69 are equal, etc.
//  struct ArrayOfIntegersEqualByTen: public std::equal_to<int>
//  {
//      bool operator() (const int& arg1, const int& arg2) const
//      {
//          return ((arg1/10) == (arg2/10));
//      }
//  };
//  
//  Now, if we call (problematic) std::unique( data, data+3, ArrayOfIntegersEqualByTen() );
//  
//  TEST1: BEFORE UNIQ: 10,11,21
//  TEST1: AFTER UNIQ: 10,21,21
//  DUP_INX=2
//  
//      PROBLEM: 11 is lost, and extra 21 has been added.
//  
//  More complicated example:
//  
//  TEST2: BEFORE UNIQ: 10,20,21,22,30,31,23,24,11
//  TEST2: AFTER UNIQ: 10,20,30,23,11,31,23,24,11
//  DUP_INX=5
//  
//      Problem: 21 and 22 are deleted.
//      Problem: 11 and 23 are duplicated.
//  
//  
//  NOW if ptgi::unique is called instead of std::unique, both problems go away:
//  
//  DEBUG: TEST1: NEW_WAY=1
//  TEST1: BEFORE UNIQ: 10,11,21
//  TEST1: AFTER UNIQ: 10,21,11
//  DUP_INX=2
//  
//  DEBUG: TEST2: NEW_WAY=1
//  TEST2: BEFORE UNIQ: 10,20,21,22,30,31,23,24,11
//  TEST2: AFTER UNIQ: 10,20,30,23,11,31,22,24,21
//  DUP_INX=5
//
//  @SEE: look at the "case study" below to understand which the last "AFTER UNIQ" results with that order:
//  TEST2: AFTER UNIQ: 10,20,30,23,11,31,22,24,21
//
//==========================================================================================================
// Case Study: how ptgi::unique() works:
//  Remember we "remove adjacent duplicates".
//  In this example, the input is NOT fully sorted when ptgi:unique() is called.
//
//  I put | separatators, BEFORE UNIQ to illustrate this
//  10  | 20,21,22 |  30,31 |  23,24 | 11
//
//  In example above, 20, 21, 22 are "same" since dividing by 10 gives 2 quotient.
//  And 30,31 are "same", since /10 quotient is 3.
//  And 23, 24 are same, since /10 quotient is 2.
//  And 11 is "group of one" by itself.
//  So there are 5 groups, but the 4th group (23, 24) happens to be equal to group 2 (20, 21, 22)
//  So there are 5 groups, and the 5th group (11) is equal to group 1 (10)
//
//  R = result
//  F = first
//
//  10, 20, 21, 22, 30, 31, 23, 24, 11
//  R    F
//
//  10 is result, and first points to 20, and R != F (10 != 20) so bump R:
//       R
//       F
//
//  Now we hits the "optimized out swap logic".
//  (avoid swap because R == F)
//
//  // now bump F until R != F (integer division by 10)
//  10, 20, 21, 22, 30, 31, 23, 24, 11
//       R   F              // 20 == 21 in 10x
//       R       F              // 20 == 22 in 10x
//       R           F          // 20 != 30, so we do a swap of ++R and F
//  (Now first hits 21, 22, then finally 30, which is different than R, so we swap bump R to 21 and swap with  30)
//  10, 20, 30, 22, 21, 31, 23, 24, 11  // after R & F swap (21 and 30)
//           R       F 
//
//  10, 20, 30, 22, 21, 31, 23, 24, 11
//           R          F           // bump F to 31, but R and F are same (30 vs 31)
//           R               F      // bump F to 23, R != F, so swap ++R with F
//  10, 20, 30, 22, 21, 31, 23, 24, 11
//                  R           F       // bump R to 22
//  10, 20, 30, 23, 21, 31, 22, 24, 11  // after the R & F swap (22 & 23 swap)
//                  R            F      // will swap 22 and 23
//                  R                F      // bump F to 24, but R and F are same in 10x
//                  R                    F  // bump F, R != F, so swap ++R  with F
//                      R                F  // R and F are diff, so swap ++R  with F (21 and 11)
//  10, 20, 30, 23, 11, 31, 22, 24, 21
//                      R                F  // aftter swap of old 21 and 11
//                      R                  F    // F now at last(), so loop terminates
//                          R               F   // bump R by 1 to point to dupPostion (first duplicate in range)
//
//  return R which now points to 31
//==========================================================================================================
// NOTES:
// 1) the #ifdef IMPROVED_STD_UNIQUE_ALGORITHM documents how we have modified the original std::unique().
// 2) I've heavily unit tested this code, including using valgrind(1), and it is *believed* to be 100% defect-free.
//
//==========================================================================================================
// History:
//  130201  dpb [email protected] created
//==========================================================================================================

#ifndef PTGI_UNIQUE_HPP
#define PTGI_UNIQUE_HPP

// Created to solve memory leak problems when calling std::unique() on a vector<Route*>.
// Memory leaks discovered with valgrind and unitTesting.


#include <algorithm>        // std::swap

// instead of std::myUnique, call this instead, where arg3 is a function ptr
//
// like std::unique, it puts the dups at the end, but it uses swapping to preserve original
// vector contents, to avoid memory leaks and duplicate pointers in vector<Object*>.

#ifdef IMPROVED_STD_UNIQUE_ALGORITHM
#error the #ifdef for IMPROVED_STD_UNIQUE_ALGORITHM was defined previously.. Something is wrong.
#endif

#undef IMPROVED_STD_UNIQUE_ALGORITHM
#define IMPROVED_STD_UNIQUE_ALGORITHM

// similar to std::unique, except that this version swaps elements, to avoid
// memory leaks, when vector contains pointers.
//
// Normally the input is sorted.
// Normal std::unique:
// 10 20 20 20 30   30 20 20 10
// a  b  c  d  e    f  g  h  i
//
// 10 20 30 20 10 | 30 20 20 10
// a  b  e  g  i    f  g  h  i
//
// Now GONE: c, d.
// Now DUPS: g, i.
// This causes memory leaks and segmenation faults due to duplicate deletes of same pointer!


namespace ptgi {

// Return the position of the first in range of duplicates moved to end of vector.
//
// uses operator==  of class for comparison
//
// @param [first, last) is a range to find duplicates within.
//
// @return the dupPosition position, such that [dupPosition, end) are contiguous
// duplicate elements.
// IF all items are unique, then it would return last.
//
template <class ForwardIterator>
ForwardIterator unique( ForwardIterator first, ForwardIterator last)
{
    // compare iterators, not values
    if (first == last)
        return last;

    // remember the current item that we are looking at for uniqueness
    ForwardIterator result = first;

    // result is slow ptr where to store next unique item
    // first is  fast ptr which is looking at all elts

    // the first iterator moves over all elements [begin+1, end).
    // while the current item (result) is the same as all elts
    // to the right, (first) keeps going, until you find a different
    // element pointed to by *first.  At that time, we swap them.

    while (++first != last)
    {
        if (!(*result == *first))
        {
#ifdef IMPROVED_STD_UNIQUE_ALGORITHM
            // inc result, then swap *result and *first

//          THIS IS WHAT WE WANT TO DO.
//          BUT THIS COULD SWAP AN ELEMENT WITH ITSELF, UNCECESSARILY!!!
//          std::swap( *first, *(++result));

            // BUT avoid swapping with itself when both iterators are the same
            ++result;
            if (result != first)
                std::swap( *first, *result);
#else
            // original code found in std::unique()
            // copies unique down
            *(++result) = *first;
#endif
        }
    }

    return ++result;
}

template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique( ForwardIterator first, ForwardIterator last, BinaryPredicate pred)
{
    if (first == last)
        return last;

    // remember the current item that we are looking at for uniqueness
    ForwardIterator result = first;

    while (++first != last)
    {
        if (!pred(*result,*first))
        {
#ifdef IMPROVED_STD_UNIQUE_ALGORITHM
            // inc result, then swap *result and *first

//          THIS COULD SWAP WITH ITSELF UNCECESSARILY
//          std::swap( *first, *(++result));
//
            // BUT avoid swapping with itself when both iterators are the same
            ++result;
            if (result != first)
                std::swap( *first, *result);

#else
            // original code found in std::unique()
            // copies unique down
            // causes memory leaks, and duplicate ptrs
            // and uncessarily moves in place!
            *(++result) = *first;
#endif
        }
    }

    return ++result;
}

// from now on, the #define is no longer needed, so get rid of it
#undef IMPROVED_STD_UNIQUE_ALGORITHM

} // end ptgi:: namespace

#endif

A oto program testowy UNIT, którego testowałem:

// QUESTION: in test2, I had trouble getting one line to compile,which was caused  by the declaration of operator()
// in the equal_to Predicate.  I'm not sure how to correctly resolve that issue.
// Look for //OUT lines
//
// Make sure that NOTES in ptgi_unique.hpp are correct, in how we should "cleanup" duplicates
// from both a vector<Integer> (test1()) and vector<Integer*> (test2).
// Run this with valgrind(1).
//
// In test2(), IF we use the call to std::unique(), we get this problem:
//
//  [dbednar@ipeng8 TestSortRoutes]$ ./Main7
//  TEST2: ORIG nums before UNIQUE: 10, 20, 21, 22, 30, 31, 23, 24, 11
//  TEST2: modified nums AFTER UNIQUE: 10, 20, 30, 23, 11, 31, 23, 24, 11
//  INFO: dupInx=5
//  TEST2: uniq = 10
//  TEST2: uniq = 20
//  TEST2: uniq = 30
//  TEST2: uniq = 33427744
//  TEST2: uniq = 33427808
//  Segmentation fault (core dumped)
//
// And if we run valgrind we seen various error about "read errors", "mismatched free", "definitely lost", etc.
//
//  valgrind --leak-check=full ./Main7
//  ==359== Memcheck, a memory error detector
//  ==359== Command: ./Main7
//  ==359== Invalid read of size 4
//  ==359== Invalid free() / delete / delete[]
//  ==359== HEAP SUMMARY:
//  ==359==     in use at exit: 8 bytes in 2 blocks
//  ==359== LEAK SUMMARY:
//  ==359==    definitely lost: 8 bytes in 2 blocks
// But once we replace the call in test2() to use ptgi::unique(), all valgrind() error messages disappear.
//
// 130212   dpb [email protected] created
// =========================================================================================================

#include <iostream> // std::cout, std::cerr
#include <string>
#include <vector>   // std::vector
#include <sstream>  // std::ostringstream
#include <algorithm>    // std::unique()
#include <functional>   // std::equal_to(), std::binary_function()
#include <cassert>  // assert() MACRO

#include "ptgi_unique.hpp"  // ptgi::unique()



// Integer is small "wrapper class" around a primitive int.
// There is no SETTER, so Integer's are IMMUTABLE, just like in JAVA.

class Integer
{
private:
    int num;
public:

    // default CTOR: "Integer zero;"
    // COMPRENSIVE CTOR:  "Integer five(5);"
    Integer( int num = 0 ) :
        num(num)
    {
    }

    // COPY CTOR
    Integer( const Integer& rhs) :
        num(rhs.num)
    {
    }

    // assignment, operator=, needs nothing special... since all data members are primitives

    // GETTER for 'num' data member
    // GETTER' are *always* const
    int getNum() const
    {
        return num;
    }   

    // NO SETTER, because IMMUTABLE (similar to Java's Integer class)

    // @return "num"
    // NB: toString() should *always* be a const method
    //
    // NOTE: it is probably more efficient to call getNum() intead
    // of toString() when printing a number:
    //
    // BETTER to do this:
    //  Integer five(5);
    //  std::cout << five.getNum() << "\n"
    // than this:
    //  std::cout << five.toString() << "\n"

    std::string toString() const
    {
        std::ostringstream oss;
        oss << num;
        return oss.str();
    }
};

// convenience typedef's for iterating over std::vector<Integer>
typedef std::vector<Integer>::iterator      IntegerVectorIterator;
typedef std::vector<Integer>::const_iterator    ConstIntegerVectorIterator;

// convenience typedef's for iterating over std::vector<Integer*>
typedef std::vector<Integer*>::iterator     IntegerStarVectorIterator;
typedef std::vector<Integer*>::const_iterator   ConstIntegerStarVectorIterator;

// functor used for std::unique or ptgi::unique() on a std::vector<Integer>
// Two numbers equal if, when divided by 10 (integer division), the quotients are the same.
// Hence 50..59 are equal, 60..69 are equal, etc.
struct IntegerEqualByTen: public std::equal_to<Integer>
{
    bool operator() (const Integer& arg1, const Integer& arg2) const
    {
        return ((arg1.getNum()/10) == (arg2.getNum()/10));
    }
};

// functor used for std::unique or ptgi::unique on a std::vector<Integer*>
// Two numbers equal if, when divided by 10 (integer division), the quotients are the same.
// Hence 50..59 are equal, 60..69 are equal, etc.
struct IntegerEqualByTenPointer: public std::equal_to<Integer*>
{
    // NB: the Integer*& looks funny to me!
    // TECHNICAL PROBLEM ELSEWHERE so had to remove the & from *&
//OUT   bool operator() (const Integer*& arg1, const Integer*& arg2) const
//
    bool operator() (const Integer* arg1, const Integer* arg2) const
    {
        return ((arg1->getNum()/10) == (arg2->getNum()/10));
    }
};

void test1();
void test2();
void printIntegerStarVector( const std::string& msg, const std::vector<Integer*>& nums );

int main()
{
    test1();
    test2();
    return 0;
}

// test1() uses a vector<Object> (namely vector<Integer>), so there is no problem with memory loss
void test1()
{
    int data[] = { 10, 20, 21, 22, 30, 31, 23, 24, 11};

    // turn C array into C++ vector
    std::vector<Integer> nums(data, data+9);

    // arg3 is a functor
    IntegerVectorIterator dupPosition = ptgi::unique( nums.begin(), nums.end(), IntegerEqualByTen() );

    nums.erase(dupPosition, nums.end());

    nums.erase(nums.begin(), dupPosition);
}

//==================================================================================
// test2() uses a vector<Integer*>, so after ptgi:unique(), we have to be careful in
// how we eliminate the duplicate Integer objects stored in the heap.
//==================================================================================
void test2()
{
    int data[] = { 10, 20, 21, 22, 30, 31, 23, 24, 11};

    // turn C array into C++ vector of Integer* pointers
    std::vector<Integer*> nums;

    // put data[] integers into equivalent Integer* objects in HEAP
    for (int inx = 0; inx < 9; ++inx)
    {
        nums.push_back( new Integer(data[inx]) );
    }

    // print the vector<Integer*> to stdout
    printIntegerStarVector( "TEST2: ORIG nums before UNIQUE", nums );

    // arg3 is a functor
#if 1
    // corrected version which fixes SEGMENTATION FAULT and all memory leaks reported by valgrind(1)
    // I THINK we want to use new C++11 cbegin() and cend(),since the equal_to predicate is passed "Integer *&"

//  DID NOT COMPILE
//OUT   IntegerStarVectorIterator dupPosition = ptgi::unique( const_cast<ConstIntegerStarVectorIterator>(nums.begin()), const_cast<ConstIntegerStarVectorIterator>(nums.end()), IntegerEqualByTenPointer() );

    // DID NOT COMPILE when equal_to predicate declared "Integer*& arg1, Integer*&  arg2"
//OUT   IntegerStarVectorIterator dupPosition = ptgi::unique( const_cast<nums::const_iterator>(nums.begin()), const_cast<nums::const_iterator>(nums.end()), IntegerEqualByTenPointer() );


    // okay when equal_to predicate declared "Integer* arg1, Integer*  arg2"
    IntegerStarVectorIterator dupPosition = ptgi::unique(nums.begin(), nums.end(), IntegerEqualByTenPointer() );
#else
    // BUGGY version that causes SEGMENTATION FAULT and valgrind(1) errors
    IntegerStarVectorIterator dupPosition = std::unique( nums.begin(), nums.end(), IntegerEqualByTenPointer() );
#endif

    printIntegerStarVector( "TEST2: modified nums AFTER UNIQUE", nums );
    int dupInx = dupPosition - nums.begin();
    std::cout << "INFO: dupInx=" << dupInx <<"\n";

    // delete the dup Integer* objects in the [dupPosition, end] range
    for (IntegerStarVectorIterator iter = dupPosition; iter != nums.end(); ++iter)
    {
        delete (*iter);
    }

    // shrink the vector
    // NB: the Integer* ptrs are NOT followed by vector::erase()
    nums.erase(dupPosition, nums.end());


    // print the uniques, by following the iter to the Integer* pointer
    for (IntegerStarVectorIterator iter = nums.begin(); iter != nums.end();  ++iter)
    {
        std::cout << "TEST2: uniq = " << (*iter)->getNum() << "\n";
    }

    // remove the unique objects from heap
    for (IntegerStarVectorIterator iter = nums.begin(); iter != nums.end();  ++iter)
    {
        delete (*iter);
    }

    // shrink the vector
    nums.erase(nums.begin(), nums.end());

    // the vector should now be completely empty
    assert( nums.size() == 0);
}

//@ print to stdout the string: "info_msg: num1, num2, .... numN\n"
void printIntegerStarVector( const std::string& msg, const std::vector<Integer*>& nums )
{
    std::cout << msg << ": ";
    int inx = 0;
    ConstIntegerStarVectorIterator  iter;

    // use const iterator and const range!
    // NB: cbegin() and cend() not supported until LATER (c++11)
    for (iter = nums.begin(), inx = 0; iter != nums.end(); ++iter, ++inx)
    {
        // output a comma seperator *AFTER* first
        if (inx > 0)
            std::cout << ", ";

        // call Integer::toString()
        std::cout << (*iter)->getNum();     // send int to stdout
//      std::cout << (*iter)->toString();   // also works, but is probably slower

    }

    // in conclusion, add newline
    std::cout << "\n";
}
Joe
źródło
Nie rozumiem tutaj uzasadnienia. Więc jeśli masz pojemnik ze wskaźnikami i chcesz usunąć duplikaty, jak to wpływa na obiekty wskazywane przez wskaźniki? Nie dojdzie do wycieków pamięci, ponieważ jest co najmniej jeden wskaźnik (i dokładnie jeden w tym kontenerze), który na nie wskazuje. Cóż, myślę, że twoja metoda może mieć jakąś zaletę z dziwnymi przeciążonymi operatorami lub dziwnymi funkcjami porównywania, które wymagają szczególnej uwagi.
kccqzy
Nie jestem pewien, czy rozumiem twój punkt widzenia. Weźmy prosty przypadek wektora <int *>, w którym 4 wskaźniki wskazują na liczby całkowite {1, 2. 2, 3}. Jest posortowane, ale po wywołaniu std :: unique 4 wskaźniki są wskaźnikami do liczb całkowitych {1, 2, 3, 3}. Teraz masz dwa identyczne wskaźniki do 3, więc jeśli wywołasz funkcję delete, usuwa duplikat. ZŁY! Po drugie, zauważ, że 2. 2. brakuje, wyciek pamięci.
Joe
kccqzy, oto przykładowy program, dzięki któremu lepiej rozumiesz moją odpowiedź:
joe
@joe: Nawet jeśli po std::unique[1, 2, 3, 2] nie można wywołać delete na 2, ponieważ pozostawiłoby to wiszący wskaźnik na 2! => Po prostu nie nazywaj delete na elementach pomiędzy, newEnd = std::uniquea std::endponieważ nadal masz wskaźniki do tych elementów w [std::begin, newEnd)!
MFH,
2
@ArneVogel: Być może dla trywialnych wartości „działa dobrze”. To raczej bezcelowe zadzwonić uniquena zasadzie vector<unique_ptr<T>>, jak tylko powielona wartość taka może zawierać wektor jest nullptr.
Ben Voigt
2

Z biblioteką Ranges (pochodzącą z C ++ 20) możesz po prostu używać

action::unique(vec);

Zauważ, że faktycznie usuwa zduplikowane elementy, a nie tylko je przenosi.

LF
źródło
1

Informacje o testach porównawczych alexK7. Próbowałem ich i uzyskałem podobne wyniki, ale gdy zakres wartości wynosi 1 milion, przypadki przy użyciu std :: sort (f1) i przy użyciu std :: unordered_set (f5) dają podobny czas. Gdy zakres wartości wynosi 10 milionów, f1 jest szybsze niż f5.

Jeśli zakres wartości jest ograniczony, a wartości nie są oznaczone int, możliwe jest użycie std :: vector, którego rozmiar odpowiada podanemu zakresowi. Oto kod:

void DeleteDuplicates_vector_bool(std::vector<unsigned>& v, unsigned range_size)
{
    std::vector<bool> v1(range_size);
    for (auto& x: v)
    {
       v1[x] = true;    
    }
    v.clear();

    unsigned count = 0;
    for (auto& x: v1)
    {
        if (x)
        {
            v.push_back(count);
        }
        ++count;
    }
}
Michaił Semenow
źródło
1

sort (v.begin (), v.end ()), v.erase (unique (v.begin (), v, end ()), v.end ());

Johanna
źródło
1

Jeśli szukasz wydajności i używania std::vector, polecam ten, który zapewnia ten link do dokumentacji .

std::vector<int> myvector{10,20,20,20,30,30,20,20,10};             // 10 20 20 20 30 30 20 20 10
std::sort(myvector.begin(), myvector.end() );
const auto& it = std::unique (myvector.begin(), myvector.end());   // 10 20 30 ?  ?  ?  ?  ?  ?
                                                                   //          ^
myvector.resize( std::distance(myvector.begin(),it) ); // 10 20 30
Gines Hidalgo
źródło
cplusplus.com nie jest w żaden sposób oficjalną dokumentacją.
Ilya Popov
0
std::set<int> s;
std::for_each(v.cbegin(), v.cend(), [&s](int val){s.insert(val);});
v.clear();
std::copy(s.cbegin(), s.cend(), v.cbegin());
Wes
źródło
1
być może zmień rozmiar wektora po jego wyczyszczeniu, aby przy budowaniu wektora był tylko 1 przydział pamięci. Może wolę std :: move zamiast std :: copy, aby przenieść ints do wektora zamiast kopiować je, ponieważ zestaw nie będzie później potrzebny.
YoungJohn
0

Jeśli nie chcesz modyfikować wektora (kasowanie, sortowanie), możesz użyć biblioteki Newtona. W podbibliotece algorytmu znajduje się wywołanie funkcji, copy_single

template <class INPUT_ITERATOR, typename T>
    void copy_single( INPUT_ITERATOR first, INPUT_ITERATOR last, std::vector<T> &v )

więc możesz:

std::vector<TYPE> copy; // empty vector
newton::copy_single(first, last, copy);

gdzie kopia jest wektorem, w którym chcesz push_back kopię unikalnych elementów. ale pamiętaj, że wypychasz elementy i nie tworzysz nowego wektora

w każdym razie jest to szybsze, ponieważ nie kasujesz () elementów (co zajmuje dużo czasu, z wyjątkiem pop_back () z powodu zmiany przypisania)

Robię eksperymenty i jest to szybsze.

Możesz także użyć:

std::vector<TYPE> copy; // empty vector
newton::copy_single(first, last, copy);
original = copy;

czasami jest jeszcze szybszy.

Moises Rojo
źródło
1
Ta funkcja jest obecna w standardowej bibliotece jako unique_copy.
LF,
0

Bardziej zrozumiały kod z: https://en.cppreference.com/w/cpp/algorithm/unique

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cctype>

int main() 
{
    // remove duplicate elements
    std::vector<int> v{1,2,3,1,2,3,3,4,5,4,5,6,7};
    std::sort(v.begin(), v.end()); // 1 1 2 2 3 3 3 4 4 5 5 6 7 
    auto last = std::unique(v.begin(), v.end());
    // v now holds {1 2 3 4 5 6 7 x x x x x x}, where 'x' is indeterminate
    v.erase(last, v.end()); 
    for (int i : v)
      std::cout << i << " ";
    std::cout << "\n";
}

wyjście:

1 2 3 4 5 6 7
Jayhello
źródło
0
void removeDuplicates(std::vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++)
    {
        for (int j = i + 1; j < arr.size(); j++)
        {
            if (arr[i] > arr[j])
            {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    std::vector<int> y;
    int x = arr[0];
    int i = 0;
    while (i < arr.size())
    {
        if (x != arr[i])
        {
            y.push_back(x);
            x = arr[i];
        }
        i++;
        if (i == arr.size())
            y.push_back(arr[i - 1]);
    }
    arr = y;
}
robertlucian13
źródło
2
Witamy w StackOverflow! Proszę edytować swoje pytanie, aby dodać wyjaśnienie jak ci roboty kod i dlaczego jest to równoważne lub lepsze od innych odpowiedzi. To pytanie ma ponad dziesięć lat i ma już wiele dobrych, dobrze wyjaśnionych odpowiedzi. Bez twojego wyjaśnienia nie jest to tak przydatne i ma duże szanse na odrzucenie lub usunięcie.
Das_Geek
-1

Oto przykład problemu z duplikatem usuwania, który występuje w przypadku std :: unique (). Na komputerze z systemem LINUX program ulega awarii. Przeczytaj komentarze, aby uzyskać szczegółowe informacje.

// Main10.cpp
//
// Illustration of duplicate delete and memory leak in a vector<int*> after calling std::unique.
// On a LINUX machine, it crashes the progam because of the duplicate delete.
//
// INPUT : {1, 2, 2, 3}
// OUTPUT: {1, 2, 3, 3}
//
// The two 3's are actually pointers to the same 3 integer in the HEAP, which is BAD
// because if you delete both int* pointers, you are deleting the same memory
// location twice.
//
//
// Never mind the fact that we ignore the "dupPosition" returned by std::unique(),
// but in any sensible program that "cleans up after istelf" you want to call deletex
// on all int* poitners to avoid memory leaks.
//
//
// NOW IF you replace std::unique() with ptgi::unique(), all of the the problems disappear.
// Why? Because ptgi:unique merely reshuffles the data:
// OUTPUT: {1, 2, 3, 2}
// The ptgi:unique has swapped the last two elements, so all of the original elements in
// the INPUT are STILL in the OUTPUT.
//
// 130215   [email protected]
//============================================================================

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

#include "ptgi_unique.hpp"

// functor used by std::unique to remove adjacent elts from vector<int*>
struct EqualToVectorOfIntegerStar: public std::equal_to<int *>
{
    bool operator() (const int* arg1, const int* arg2) const
    {
        return (*arg1 == *arg2);
    }
};

void printVector( const std::string& msg, const std::vector<int*>& vnums);

int main()
{
    int inums [] = { 1, 2, 2, 3 };
    std::vector<int*> vnums;

    // convert C array into vector of pointers to integers
    for (size_t inx = 0; inx < 4; ++ inx)
        vnums.push_back( new int(inums[inx]) );

    printVector("BEFORE UNIQ", vnums);

    // INPUT : 1, 2A, 2B, 3
    std::unique( vnums.begin(), vnums.end(), EqualToVectorOfIntegerStar() );
    // OUTPUT: 1, 2A, 3, 3 }
    printVector("AFTER  UNIQ", vnums);

    // now we delete 3 twice, and we have a memory leak because 2B is not deleted.
    for (size_t inx = 0; inx < vnums.size(); ++inx)
    {
        delete(vnums[inx]);
    }
}

// print a line of the form "msg: 1,2,3,..,5,6,7\n", where 1..7 are the numbers in vnums vector
// PS: you may pass "hello world" (const char *) because of implicit (automatic) conversion
// from "const char *" to std::string conversion.

void printVector( const std::string& msg, const std::vector<int*>& vnums)
{
    std::cout << msg << ": ";

    for (size_t inx = 0; inx < vnums.size(); ++inx)
    {
        // insert comma separator before current elt, but ONLY after first elt
        if (inx > 0)
            std::cout << ",";
        std::cout << *vnums[inx];

    }
    std::cout << "\n";
}
Joe
źródło
PS: Uruchomiłem także „valgrind ./Main10” i valgrind nie znalazł problemów. ZDECYDOWANIE polecam wszystkim programistom C ++ korzystającym z LINUX, aby korzystali z tego bardzo produktywnego narzędzia, szczególnie jeśli piszesz aplikacje działające w czasie rzeczywistym, które muszą działać 24 godziny na dobę, 7 dni w tygodniu i nigdy nie wyciekać ani nie ulegać awarii!
Joe
Sedno problemu ze std :: unique można podsumować za pomocą instrukcji „std :: unique zwraca duplikaty w nieokreślonym stanie” !!!!! Dlaczego komitet normalizacyjny to zrobił, nigdy się nie dowiem. Członkowie komitetu .. jakieś komentarze ???
Joe
1
Tak, „std :: unique zwraca duplikaty w nieokreślonym stanie”. Więc po prostu nie polegaj na tablicy, która została „unikatowa” do ręcznego zarządzania pamięcią! Najprostszym sposobem na to jest użycie std :: unique_ptr zamiast surowych wskaźników.
alexk7
To wydaje się być odpowiedzią na inną odpowiedź; nie odpowiada na pytanie (w którym vectorzawiera liczby całkowite, a nie wskaźniki i nie określa komparatora).
Toby Speight
-2
void EraseVectorRepeats(vector <int> & v){ 
TOP:for(int y=0; y<v.size();++y){
        for(int z=0; z<v.size();++z){
            if(y==z){ //This if statement makes sure the number that it is on is not erased-just skipped-in order to keep only one copy of a repeated number
                continue;}
            if(v[y]==v[z]){
                v.erase(v.begin()+z); //whenever a number is erased the function goes back to start of the first loop because the size of the vector changes
            goto TOP;}}}}

Jest to funkcja, którą stworzyłem, której możesz użyć do usuwania powtórzeń. Potrzebne pliki nagłówkowe to tylko <iostream>i <vector>.

Łapie
źródło