Was ist der effizienteste Weg, um Duplikate zu löschen und einen Vektor zu sortieren?

274

Ich muss einen C ++ - Vektor mit möglicherweise vielen Elementen nehmen, Duplikate löschen und sortieren.

Ich habe derzeit den folgenden Code, aber es funktioniert nicht.

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

Wie kann ich das richtig machen?

Ist es außerdem schneller, zuerst die Duplikate zu löschen (ähnlich wie oben codiert) oder zuerst die Sortierung durchzuführen? Wenn ich die Sortierung zuerst durchführe, bleibt sie nach der std::uniqueAusführung garantiert sortiert ?

Oder gibt es einen anderen (vielleicht effizienteren) Weg, dies alles zu tun?

Kyle Ryan
quelle
3
Ich gehe davon aus, dass Sie nicht die Möglichkeit haben, vor dem Einfügen zu prüfen, um Dupes zu vermeiden.
Joe
Richtig. Das wäre ideal.
Kyle Ryan
29
Ich würde vorschlagen, den obigen Code zu korrigieren oder wirklich anzuzeigen, dass er FALSCH ist. std :: unique geht davon aus, dass der Bereich bereits sortiert ist.
Matthieu M.

Antworten:

583

Ich stimme R. Pate und Todd Gardner zu ; a std::setkönnte hier eine gute Idee sein. Selbst wenn Sie keine Vektoren mehr verwenden und genügend Duplikate haben, ist es möglicherweise besser, ein Set für die Drecksarbeit zu erstellen.

Vergleichen wir drei Ansätze:

Nur mit Vektor sortieren + eindeutig

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

In Set konvertieren (manuell)

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

In Set konvertieren (mit einem Konstruktor)

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

So verhalten sich diese, wenn sich die Anzahl der Duplikate ändert:

Vergleich von Vektor- und Mengenansätzen

Zusammenfassung : Wenn die Anzahl der Duplikate groß genug ist, ist es tatsächlich schneller, in eine Menge zu konvertieren und die Daten dann wieder in einen Vektor zu kopieren .

Und aus irgendeinem Grund scheint die manuelle Set-Konvertierung schneller zu sein als die Verwendung des Set-Konstruktors - zumindest bei den von mir verwendeten Spielzeug-Zufallsdaten.

Nate Kohl
quelle
61
Ich bin schockiert, dass der Konstruktoransatz durchweg messbar schlechter ist als der manuelle. Sie würden das, abgesehen von einem winzigen konstanten Overhead, nur das manuelle tun. Kann jemand das erklären?
Ari
17
Cool, danke für die Grafik. Können Sie einen Eindruck davon geben, wie hoch die Anzahl der Duplikate ist? (dh wie groß ist "groß genug")?
Kyle Ryan
5
@ Kyle: Es ist ziemlich groß. Ich habe für dieses Diagramm Datensätze mit 1.000.000 zufällig gezeichneten Ganzzahlen zwischen 1 und 1000, 100 und 10 verwendet.
Nate Kohl
5
Ich denke, Ihre Ergebnisse sind falsch. In meinen Tests skaliert der schnellere Vektor (Vergleich) umso schneller, je mehr doppelte Elemente vorhanden sind. Haben Sie mit aktivierten Optimierungen und deaktivierten Laufzeitprüfungen kompiliert? Auf meiner Seite ist der Vektor immer schneller, bis zu 100x, abhängig von der Anzahl der Duplikate. VS2013, cl / Ox -D_SECURE_SCL = 0.
Davidnr
39
Die Beschreibung der x-Achse scheint zu fehlen.
BartoszKP
72

Ich habe die Profilerstellung von Nate Kohl überarbeitet und unterschiedliche Ergebnisse erzielt. In meinem Testfall ist das direkte Sortieren des Vektors immer effizienter als die Verwendung eines Satzes. Ich habe eine neue effizientere Methode hinzugefügt, indem ich eine unordered_set.

unordered_setBeachten Sie, dass die Methode nur funktioniert, wenn Sie eine gute Hash-Funktion für den Typ haben, den Sie eindeutig und sortiert benötigen. Für Ints ist das einfach! (Die Standardbibliothek bietet einen Standard-Hash, der einfach die Identitätsfunktion ist.) Vergessen Sie auch nicht, am Ende zu sortieren, da unordered_set ungeordnet ist :)

Ich habe ein wenig in die setund unordered_set-Implementierung gegraben und festgestellt, dass der Konstruktor tatsächlich für jedes Element einen neuen Knoten erstellt, bevor ich seinen Wert überprüfe, um festzustellen, ob er tatsächlich eingefügt werden soll (zumindest in der Visual Studio-Implementierung).

Hier sind die 5 Methoden:

f1: Nur mit vector, sort+unique

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

f2: Konvertieren in set(mit einem Konstruktor)

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

f3: Konvertieren in set(manuell)

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

f4: Konvertieren nach unordered_set(mit einem Konstruktor)

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

f5: Konvertieren in unordered_set(manuell)

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

Ich habe den Test mit einem Vektor von 100.000.000 Ints durchgeführt, der zufällig in den Bereichen [1,10], [1,1000] und [1,100000] ausgewählt wurde.

Die Ergebnisse (in Sekunden ist kleiner besser):

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
quelle
4
Für Ganzzahlen können Sie die Radix-Sortierung verwenden, die viel schneller als std :: sort ist.
Changming Sun
2
Schneller Tipp, zu verwenden sortoder uniqueMethoden, müssen Sie#include <algorithm>
Davmrtl
3
@ChangmingSun Ich frage mich, warum der Optimierer auf f4 zu versagen schien? Die Zahlen unterscheiden sich dramatisch von f5. Das ergibt für mich keinen Sinn.
Sanddorn
1
@sandthorn Wie in meiner Antwort erläutert, erstellt die Implementierung für jedes Element aus der Eingabesequenz einen Knoten (einschließlich dynamischer Zuordnung), was für jeden Wert, der letztendlich ein Duplikat ist, verschwenderisch ist. Der Optimierer kann auf keinen Fall wissen, dass er das überspringen kann.
Alexk7
Ah, das erinnert mich an eines von Scott Meyers Gesprächen über das CWUK Szenario , das die Fähigkeit besitzt, die Art des Aufbaus zu verlangsamen emplace.
Sanddorn
57

std::unique Entfernt doppelte Elemente nur, wenn sie Nachbarn sind: Sie müssen den Vektor zuerst sortieren, bevor er wie beabsichtigt funktioniert.

std::unique ist als stabil definiert, sodass der Vektor nach dem Ausführen von unique weiterhin sortiert wird.

jskinner
quelle
42

Ich bin mir nicht sicher, wofür Sie dies verwenden, daher kann ich dies nicht mit 100% iger Sicherheit sagen, aber normalerweise denke ich, wenn ich an "sortierten, eindeutigen" Container denke, an ein std :: set . Es könnte besser zu Ihrem Anwendungsfall passen:

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

Andernfalls ist das Sortieren vor dem Aufruf von unique (wie in den anderen Antworten angegeben) der richtige Weg.

Todd Gardner
quelle
Gut auf den Punkt! std :: set wird als sortierte eindeutige Menge angegeben. Die meisten Implementierungen verwenden einen effizient geordneten Binärbaum oder ähnliches.
Notnoop
+1 Auch an Set gedacht. Wollte diese Antwort nicht duplizieren
Tom
Wird std :: set garantiert sortiert? Es ist sinnvoll, dass dies in der Praxis der Fall ist, aber erfordert der Standard dies?
MadCoder
1
Ja, siehe 23.1.4.9 "Die grundlegende Eigenschaft von Iteratoren assoziativer Container besteht darin, dass sie die Container in der nicht absteigenden Reihenfolge der Schlüssel durchlaufen, wobei die nicht absteigende Reihenfolge durch den Vergleich definiert wird, mit dem sie erstellt wurden"
Todd Gardner
1
@MadCoder: Es ist nicht unbedingt "sinnvoll", dass eine Menge sortiert implementiert wird. Es gibt auch Mengen, die mit Hash-Tabellen implementiert sind, die nicht sortiert sind. Tatsächlich bevorzugen die meisten Leute die Verwendung von Hash-Tabellen, wenn diese verfügbar sind. Die Namenskonvention in C ++ geschieht jedoch nur so, dass die sortierten assoziativen Container einfach "set" / "map" heißen (analog zu TreeSet / TreeMap in Java). und die vom Standard weggelassenen assoziativen Hash-Container heißen "hash_set" / "hash_map" (SGI STL) oder "unordered_set" / "unordered_map" (TR1) (analog zu HashSet und HashMap in Java)
newacct
21

std::uniqueFunktioniert nur bei aufeinanderfolgenden Durchläufen doppelter Elemente, daher sollten Sie zuerst sortieren. Es ist jedoch stabil, sodass Ihr Vektor sortiert bleibt.

David Seiler
quelle
18

Hier ist eine Vorlage, um es für Sie zu tun:

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

nenne es wie:

removeDuplicates<int>(vectorname);
DShook
quelle
2
+1 Templatize weg! - aber Sie können einfach removeDuplicates (vec) schreiben, ohne die Vorlagenargumente explizit anzugeben
Faisal Vali
10
Oder noch besser, lassen Sie es einfach Vorlagen-Iteratoren direkt nehmen (Anfang und Ende), und Sie können es auf anderen Strukturen als einem Vektor ausführen.
Kyle Ryan
Höllen ja, Vorlagen! Schnelle Lösung für kleine Listen, voller STL-Stil. +1 thx
QuantumKarl
@Kyle - nur für andere Container mit einer erase()Methode, andernfalls müssen Sie den neuen Enditerator zurückgeben und den aufrufenden Code den Container abschneiden lassen.
Toby Speight
8

Effizienz ist ein kompliziertes Konzept. Es gibt zeitliche und räumliche Überlegungen sowie allgemeine Messungen (bei denen Sie nur vage Antworten wie O (n) erhalten) und bestimmte (z. B. kann die Blasensortierung je nach Eingabeeigenschaften viel schneller sein als die Quicksortierung).

Wenn Sie relativ wenige Duplikate haben, ist die Sortierung gefolgt von eindeutig und Löschen der richtige Weg. Wenn Sie relativ viele Duplikate hatten, könnte es leicht schlagen, einen Satz aus dem Vektor zu erstellen und ihn das schwere Heben ausführen zu lassen.

Konzentrieren Sie sich auch nicht nur auf Zeiteffizienz. Sortieren + Eindeutig + Löschen wird im O (1) -Raum ausgeführt, während die Mengenkonstruktion im O (n) -Raum ausgeführt wird. Und beides eignet sich nicht direkt für eine kartenreduzierte Parallelisierung (für wirklich große Datenmengen).


quelle
Was würde dir Karten- / Reduktionsfähigkeit geben? Das einzige, an das ich denken kann, ist eine verteilte Zusammenführungssortierung, und Sie können immer noch nur einen Thread für die endgültige Zusammenführung verwenden.
Zan Lynx
1
Ja, Sie müssen einen steuernden Knoten / Thread haben. Sie können das Problem jedoch so oft wie erforderlich aufteilen, um die Anzahl der Worker- / Child-Threads, mit denen sich der Controlling- / Parent-Thread befasst, und die Größe des Datasets, den jeder Blattknoten verarbeiten muss, zu begrenzen. Nicht alle Probleme lassen sich mit Kartenreduzierung leicht lösen. Ich wollte nur darauf hinweisen, dass es Leute gibt, die sich mit ähnlichen (ohnehin oberflächlichen) Optimierungsproblemen befassen, bei denen der Umgang mit 10 Terabyte Daten als "Dienstag" bezeichnet wird.
7

Sie müssen es sortieren, bevor Sie anrufen, uniqueweilunique nur Duplikate entfernt werden, die nebeneinander liegen.

bearbeiten: 38 Sekunden ...

David Johnstone
quelle
7

uniqueEntfernt nur aufeinanderfolgende doppelte Elemente (was erforderlich ist, damit es in linearer Zeit ausgeführt wird). Daher sollten Sie zuerst die Sortierung durchführen. Es bleibt nach dem Anruf an sortiert unique.

Peter
quelle
7

Wenn Sie die Reihenfolge der Elemente nicht ändern möchten, können Sie diese Lösung ausprobieren:

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());
}
yury
quelle
Vielleicht verwenden Sie unordered_set anstelle von set (und boost :: remove_erase_if, falls verfügbar)
gast128
4

Angenommen, a ist ein Vektor, entfernen Sie die zusammenhängenden Duplikate mit

a.erase(unique(a.begin(),a.end()),a.end());läuft in O (n) Zeit.

KPMG
quelle
1
zusammenhängende Duplikate. ok, also braucht es eine std::sorterste.
v.oddou
2

Wie bereits erwähnt, uniqueerfordert ein sortierter Container. Entfernt außerdem uniquekeine Elemente aus dem Container. Stattdessen werden sie bis zum Ende kopiert, geben uniqueeinen Iterator zurück, der auf das erste derartige doppelte Element zeigt, und es wird erwartet, dass Sie aufrufen erase, um die Elemente tatsächlich zu entfernen.

Max Lybbert
quelle
Benötigt unique einen sortierten Container oder ordnet es einfach nur die Eingabesequenz neu an, sodass keine benachbarten Duplikate enthalten sind? Ich dachte letzteres.
@Pate, du bist richtig. Es erfordert keine. Benachbarte Duplikate werden entfernt.
Bill Lynch
Wenn Sie einen Container haben, der möglicherweise Duplikate enthält, und Sie einen Container möchten, der keine doppelten Werte im Container enthält, müssen Sie den Container zuerst sortieren, dann an Unique übergeben und dann mit Löschen die Duplikate tatsächlich entfernen . Wenn Sie einfach benachbarte Duplikate entfernen möchten, müssen Sie den Container nicht sortieren. Am Ende werden jedoch doppelte Werte angezeigt: 1 2 2 3 2 4 2 5 2 wird in 1 2 3 2 4 2 5 2 geändert, wenn es ohne Sortierung an eindeutig übergeben wird, 1 2 3 4 5, wenn sortiert, an eindeutig übergeben und gelöscht .
Max Lybbert
2

Der von Nate Kohl vorgeschlagene Standardansatz, bei dem nur Vektor, Sortierung + Einzigartigkeit verwendet wird:

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

funktioniert nicht für einen Zeigervektor.

Schauen Sie sich dieses Beispiel auf cplusplus.com genau an .

In ihrem Beispiel werden die an das Ende verschobenen "sogenannten Duplikate" tatsächlich als? (undefinierte Werte), da diese "sogenannten Duplikate" manchmal "zusätzliche Elemente" sind und manchmal "fehlende Elemente" im ursprünglichen Vektor vorhanden sind.

Bei der Verwendung tritt ein Problem auf std::unique() ein Vektor von Zeigern auf Objekte verwendet wird (Speicherlecks, schlechtes Lesen von Daten aus HEAP, doppelte Freigaben, die Segmentierungsfehler verursachen usw.).

Hier ist meine Lösung für das Problem: Ersetzen std::unique()durchptgi::unique() .

Siehe die Datei ptgi_unique.hpp unten:

// 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

Und hier ist das UNIT-Testprogramm, mit dem ich es getestet habe:

// 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
quelle
Ich verstehe die Gründe hier nicht. Wenn Sie also einen Container mit Zeigern haben und Duplikate entfernen möchten, wie wirkt sich das auf die Objekte aus, auf die die Zeiger zeigen? Es würden keine Speicherverluste auftreten, da mindestens ein Zeiger (und genau einer in diesem Container) auf sie verweist. Nun, ich denke, Ihre Methode könnte einige Vorteile mit einigen seltsam überladenen Operatoren oder seltsamen Vergleichsfunktionen haben, die besondere Überlegungen erfordern.
kccqzy
Ich bin mir nicht sicher, ob ich deinen Standpunkt verstehe. Nehmen Sie einen einfachen Fall eines Vektors <int *>, bei dem die 4 Zeiger auf ganze Zahlen {1, 2. 2, 3} zeigen. Es ist sortiert, aber nachdem Sie std :: unique aufgerufen haben, sind die 4 Zeiger Zeiger auf ganze Zahlen {1, 2, 3, 3}. Jetzt haben Sie zwei identische Zeiger auf 3. Wenn Sie also delete aufrufen, wird doppelt gelöscht. SCHLECHT! Zweitens beachten Sie, dass die 2. 2 fehlschlägt, ein Speicherverlust.
Joe
kccqzy, hier ist das Beispielprogramm, damit Sie meine Antwort besser verstehen:
Joe
@joe: Selbst wenn std::uniquedu nach [1, 2, 3, 2] nicht delete auf 2 aufrufen kannst, da dies einen baumelnden Zeiger auf 2 hinterlassen würde! => Rufen Sie einfach nicht delete für die Elemente zwischen newEnd = std::uniqueund auf, std::endda Sie noch Zeiger auf diese Elemente in haben [std::begin, newEnd)!
MFH
2
@ArneVogel: Für triviale Werte von "funktioniert gut" vielleicht. Es ist ziemlich sinnlos nennen uniqueauf ein vector<unique_ptr<T>>, wie das nur ein solcher Vektor dupliziert Wert enthalten ist nullptr.
Ben Voigt
2

Mit der Ranges-Bibliothek (in C ++ 20 erhältlich) können Sie einfach verwenden

action::unique(vec);

Beachten Sie, dass die doppelten Elemente tatsächlich entfernt und nicht nur verschoben werden.

LF
quelle
1

Über alexK7 Benchmarks. Ich habe sie ausprobiert und ähnliche Ergebnisse erzielt, aber wenn der Wertebereich 1 Million beträgt, erzeugen die Fälle mit std :: sort (f1) und std :: unordered_set (f5) eine ähnliche Zeit. Wenn der Wertebereich 10 Millionen beträgt, ist f1 schneller als f5.

Wenn der Wertebereich begrenzt ist und die Werte int ohne Vorzeichen sind, kann std :: vector verwendet werden, dessen Größe dem angegebenen Bereich entspricht. Hier ist der Code:

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;
    }
}
Mikhail Semenov
quelle
1

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

Yohanna
quelle
1

Wenn Sie nach Leistung und Verwendung suchen std::vector, empfehle ich die, die dieser Dokumentationslink bietet.

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
quelle
cplusplus.com ist in keiner Weise eine offizielle Dokumentation.
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());
Wir s
quelle
1
Ändern Sie möglicherweise die Größe des Vektors, nachdem Sie ihn gelöscht haben, sodass beim Erstellen des Vektors nur 1 Speicher zugewiesen wird. Vielleicht bevorzugen Sie std :: move anstelle von std :: copy, um die Ints in den Vektor zu verschieben, anstatt sie zu kopieren, da die Menge später nicht benötigt wird.
YoungJohn
0

Wenn Sie den Vektor nicht ändern möchten (Löschen, Sortieren), können Sie die Newton-Bibliothek verwenden . In der Algorithmus-Unterbibliothek gibt es den Funktionsaufruf copy_single

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

also kannst du:

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

Dabei ist copy der Vektor, in dem Sie die Kopie der eindeutigen Elemente zurückschieben möchten . aber erinnere dichDenken die Elemente zurückschieben und keinen neuen Vektor erstellen

Dies ist jedoch schneller, da Sie die Elemente nicht löschen () (was aufgrund der Neuzuweisung viel Zeit in Anspruch nimmt, außer wenn Sie pop_back () verwenden).

Ich mache einige Experimente und es ist schneller.

Sie können auch Folgendes verwenden:

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

manchmal ist noch schneller.

Moises Rojo
quelle
1
Diese Funktion ist in der Standardbibliothek als vorhanden unique_copy.
LF
0

Verständlicherer Code von: 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";
}

Ausgabe:

1 2 3 4 5 6 7
Jayhello
quelle
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
quelle
2
Willkommen bei StackOverflow! Bitte bearbeiten Sie Ihre Frage, um eine Erklärung hinzuzufügen, wie Ihr Code funktioniert und warum er gleichwertig oder besser als die anderen Antworten ist. Diese Frage ist mehr als zehn Jahre alt und hat bereits viele gute, gut erläuterte Antworten. Ohne eine Erklärung zu Ihrer ist es nicht so nützlich und hat gute Chancen, herabgestuft oder entfernt zu werden.
Das_Geek
-1

Hier ist das Beispiel für das Problem des doppelten Löschens, das bei std :: unique () auftritt. Auf einem LINUX-Computer stürzt das Programm ab. Lesen Sie die Kommentare für Details.

// 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
quelle
PS: Ich habe auch "valgrind ./Main10" ausgeführt und valgrind hat keine Probleme gefunden. Ich empfehle allen C ++ - Programmierern, die LINUX verwenden, dringend, dieses sehr produktive Tool zu verwenden, insbesondere wenn Sie Echtzeitanwendungen schreiben, die rund um die Uhr ausgeführt werden müssen und niemals auslaufen oder abstürzen!
Joe
Das Herzstück des Problems mit std :: unique kann durch diese Aussage zusammengefasst werden: "std :: unique gibt Duplikate in nicht angegebenem Zustand zurück" !!!!! Warum das Normungskomitee dies getan hat, werde ich nie erfahren. Komiteemitglieder .. irgendwelche Kommentare ???
Joe
1
Ja, "std :: unique gibt Duplikate im nicht angegebenen Zustand zurück". Verlassen Sie sich also einfach nicht auf ein Array, das "eindeutig" ist, um den Speicher manuell zu verwalten! Der einfachste Weg, dies zu tun, besteht darin, std :: unique_ptr anstelle von Rohzeigern zu verwenden.
Alexk7
Dies scheint eine Antwort auf eine andere Antwort zu sein; Es beantwortet nicht die Frage (in der die vectorGanzzahlen und keine Zeiger enthält und keinen Komparator angibt).
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;}}}}

Dies ist eine von mir erstellte Funktion, mit der Sie Wiederholungen löschen können. Die benötigten Header-Dateien sind nur <iostream>und <vector>.

GrabeS
quelle