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::unique
Ausführung garantiert sortiert ?
Oder gibt es einen anderen (vielleicht effizienteren) Weg, dies alles zu tun?
Antworten:
Ich stimme R. Pate und Todd Gardner zu ; a
std::set
kö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
In Set konvertieren (manuell)
In Set konvertieren (mit einem Konstruktor)
So verhalten sich diese, wenn sich die Anzahl der Duplikate ändert:
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.
quelle
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_set
Beachten 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
set
undunordered_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
f2: Konvertieren in
set
(mit einem Konstruktor)f3: Konvertieren in
set
(manuell)f4: Konvertieren nach
unordered_set
(mit einem Konstruktor)f5: Konvertieren in
unordered_set
(manuell)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):
quelle
sort
oderunique
Methoden, müssen Sie#include <algorithm>
CWUK
Szenario , das die Fähigkeit besitzt, die Art des Aufbaus zu verlangsamenemplace
.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.quelle
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:
Andernfalls ist das Sortieren vor dem Aufruf von unique (wie in den anderen Antworten angegeben) der richtige Weg.
quelle
std::unique
Funktioniert nur bei aufeinanderfolgenden Durchläufen doppelter Elemente, daher sollten Sie zuerst sortieren. Es ist jedoch stabil, sodass Ihr Vektor sortiert bleibt.quelle
Hier ist eine Vorlage, um es für Sie zu tun:
nenne es wie:
quelle
erase()
Methode, andernfalls müssen Sie den neuen Enditerator zurückgeben und den aufrufenden Code den Container abschneiden lassen.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
Sie müssen es sortieren, bevor Sie anrufen,
unique
weilunique
nur Duplikate entfernt werden, die nebeneinander liegen.bearbeiten: 38 Sekunden ...
quelle
unique
Entfernt 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 sortiertunique
.quelle
Wenn Sie die Reihenfolge der Elemente nicht ändern möchten, können Sie diese Lösung ausprobieren:
quelle
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.quelle
std::sort
erste.Wie bereits erwähnt,
unique
erfordert ein sortierter Container. Entfernt außerdemunique
keine Elemente aus dem Container. Stattdessen werden sie bis zum Ende kopiert, gebenunique
einen Iterator zurück, der auf das erste derartige doppelte Element zeigt, und es wird erwartet, dass Sie aufrufenerase
, um die Elemente tatsächlich zu entfernen.quelle
Der von Nate Kohl vorgeschlagene Standardansatz, bei dem nur Vektor, Sortierung + Einzigartigkeit verwendet wird:
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:
Und hier ist das UNIT-Testprogramm, mit dem ich es getestet habe:
quelle
std::unique
du 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 zwischennewEnd = std::unique
und auf,std::end
da Sie noch Zeiger auf diese Elemente in haben[std::begin, newEnd)
!unique
auf einvector<unique_ptr<T>>
, wie das nur ein solcher Vektor dupliziert Wert enthalten istnullptr
.Mit der Ranges-Bibliothek (in C ++ 20 erhältlich) können Sie einfach verwenden
Beachten Sie, dass die doppelten Elemente tatsächlich entfernt und nicht nur verschoben werden.
quelle
Ü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:
quelle
sort (v.begin (), v.end ()), v.erase (einzigartig (v.begin (), v, end ()), v.end ());
quelle
Wenn Sie nach Leistung und Verwendung suchen
std::vector
, empfehle ich die, die dieser Dokumentationslink bietet.quelle
quelle
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
also kannst du:
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:
manchmal ist noch schneller.
quelle
unique_copy
.Verständlicherer Code von: https://en.cppreference.com/w/cpp/algorithm/unique
Ausgabe:
quelle
quelle
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.
quelle
vector
Ganzzahlen und keine Zeiger enthält und keinen Komparator angibt).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>
.quelle