wie finde ich Duplikate in std :: vectorstring und gebe eine Liste von ihnen zurück?

1. Machen Sie eine leere std::unordered_set<std::string>
2. Iteriere deinen Vektor und überprüfe, ob jeder Gegenstand ein Mitglied der Menge ist
3. Wenn es bereits in der Menge ist, ist dies ein Duplikat, also fügen Sie es zu Ihrer Ergebnisliste hinzu
4. Andernfalls fügen Sie dem Set hinzu.

Da jedes Duplikat nur einmal in den Ergebnissen aufgeführt sein soll, können Sie auch ein Hashset (nicht Liste) für die Ergebnisse verwenden.

IMO, Ben Voigt hat mit einer guten Grundidee angefangen, aber ich warne davor, seinen Wortlaut zu wörtlich zu nehmen.

Insbesondere mag ich nicht die Idee, nach der Zeichenfolge in der Menge zu suchen, sie dann zu Ihrer Menge hinzuzufügen, wenn sie nicht vorhanden ist, und sie der Ausgabe hinzuzufügen, wenn sie vorhanden ist. Das bedeutet im Grunde, dass jedes Mal, wenn wir auf ein neues Wort treffen, wir unsere bestehenden Wörter zweimal durchsuchen, um einmal zu prüfen, ob ein Wort vorhanden ist, und es erneut einzufügen, weil es nicht existiert. Der Großteil dieser Suche wird im Wesentlichen identisch sein - es sei denn, ein anderer Thread mutiert die Struktur in der Zwischenzeit (was eine Race-Bedingung ergeben könnte).

Stattdessen würde ich versuchen, es zu den Wörtern hinzuzufügen, die Sie gesehen haben. Das gibt pair<iterator, bool> zurück, wobei% code_% auf bool gesetzt wird, wenn und nur wenn der Wert eingefügt wurde - d. H. War vorher nicht vorhanden. Dadurch können wir die Suche nach einer vorhandenen Zeichenfolge und die Einfügung der neuen Zeichenfolge in einer einzigen Einfügung zusammenfassen:

Dies räumt auch den Fluss auf, so dass es ziemlich einfach ist, den Test zu einem Funktor zu machen, den wir dann mit true verwenden können, um unsere Ergebnisse direkt zu produzieren:

Je nachdem, ob mir die Code-Einfachheit oder die Ausführungsgeschwindigkeit am Herzen lag, verwende ich möglicherweise std::remove_copy_if anstelle von std::vector für das Ergebnis und verwende set gefolgt von std::sort , um das Endergebnis zu erzeugen. In einem solchen Fall würde ich wahrscheinlich auch die std::unique_copy innerhalb von std::set durch eine show_copies ersetzen:

Dies ist geringfügig komplexer (eine ganze Zeile länger!), aber wahrscheinlich wesentlich schneller, wenn / wenn die Anzahl der Wörter sehr groß wird. Beachten Sie auch, dass ich std::unordered_set hauptsächlich verwende, um sichtbare Ausgaben zu erzeugen. Wenn Sie das Ergebnis nur in einer Sammlung haben möchten, können Sie das standardmäßige Unique / Erase-Idiom verwenden, um eindeutige Elemente in std::unique_copy zu erhalten.

In 3 Zeilen (ohne die Vektor- und Listenerstellung oder die überflüssigen Zeilenumbrüche im Namen der Lesbarkeit):

BEARBEITEN

Erklärung der Lösung:

1. Das Sortieren des Vektors wird benötigt, um später set_difference() zu verwenden.

2. Der uvec satz wird Elemente automatisch sortiert halten und Dubletten eliminieren.

3. Die output Liste wird mit den Elementen von vec - uvec gefüllt.

An Ort und Stelle (kein zusätzlicher Speicher). Kein String-Kopieren (außer zur Ergebnisliste). Eine Sorte + ein Pass:

Sie können eine ziemlich saubere Implementierung mit einer std :: map erhalten, um die Vorkommen zu zählen und sich dann auf std :: list :: sort zu verlassen, um die resultierende Liste von Wörtern zu sortieren. Zum Beispiel:

Mit einer std :: map scheint es ein wenig verschwenderisch zu sein, aber es erledigt den Job.

Hier ist ein besserer Algorithmus als die, die andere Leute vorgeschlagen haben:

Es ist besser, weil es nur swap mit keinem zusätzlichen vector für den Speicher benötigt, was bedeutet, dass es sich für frühere Versionen von C ++ optimal verhält und keine Elemente kopierbar sein müssen.

Wenn Sie schlauer sind, denke ich, dass Sie vermeiden können, den Vektor doppelt so gut zu sortieren.