Mehrfacheinträge entfernen

dixidix

Danke, so richtig blicke ich da noch nicht durch aber mal sehen. Von array_unique() in PHP habe ich mal was gehört. Evtl. kann man sowas nachbauen

pumuckl

dixidix schrieb:

Evtl. kann man sowas nachbauen

Wozu nachbauen was es schon gibt? Eine Referenz für std::unique findest du übrigens hier:
http://www.cplusplus.com/reference/algorithm/unique.html

Das zeigt auch, dass Mizar's Ausführungen nicht ganz richtig waren: die mehrfach vorkommenden Elemente werden NICHT nach hinten kopiert.

Wenn du viele mehrfache Elemente hast ist es unter Umständen auch sinnvoll, den vector anschließend "zu schrumpfen":

std::vector<MyType> vec;
//füllen...

std::vector<MyType>::iterator begin = vec.begin(), end = vec.end();
std::sort(begin, end);
std::vector(begin, std::unique(begin,end)).swap(vec);
//temporärer vector wird mit dem ergebnis von unique copy-initialisiert
//swap sorgt dafür, dass in vec dieses ergebnis steht und der komplette alte Inhalt im temporären vector
//der temporäre vector wird zerstört und nimmt den ganzen "müll" mit

Der Vollständigkeit halber für (dynamische) Arrays, inklusive "Schrumpfung":

MyType *myArr = new MyType[wievielauchimmer];
//myArr füllen

std::sort(myArr, myArr+wievielauchimmer);
std::size_t newlen = std::unique(myArr, myArr+wievielauchimmer) - myArr;
MyType *tmp = new MyType[newlen];
std::copy(myArr, myArr+newlen, tmp);
delete[] myArr; //alten Müll löschen
myArr = tmp; //myArr zeigt jetzt auf das neue Array mit den "einzigartigen" Elementen

dixidix

Wozu nachbauen was es schon gibt?

Danke für den Tipp, soweit bin ich noch nicht vorgedrungen. Werd's mal probieren, sobald ich dazu komme.

Mizar

pumuckl schrieb:

Das zeigt auch, dass Mizar's Ausführungen nicht ganz richtig waren: die mehrfach vorkommenden Elemente werden NICHT nach hinten kopiert.

Das verstehe ich ehrlich gesagt nicht. In der Referenz heißt es doch auch:

Removes the duplicate consecutive elements from the range [first,last). This is done by removing all the elements that compare equal to the element right preceding them (only the first element in each group of consecutive equal elements is kept).

Also, mehrfach vorkommende, aufeinanderfolgende Elemente wandern hinter das letzte eindeutige Element.

Vielleicht hatte ich in meinem Post das ganze auch etwas zu ausufernd geschrieben. Das Prinzip ist eigentlich ganz einfach:

vector<int> ivec;
//füllen
std::sort(ivec.begin(), ivec.end()) // Elemente mit gleichem Wert stehen hintereinander
ivec.erase(std::unique(ivec.begin(), ivec.end()), ivec.end());

std::unique "vertauscht" sich gleichende, aufeinanderfolgende Elemente, so dass am Ende sich wiederholende Elemente hinter dem letzten eindeutigen Element stehen. Der zurückgegebene Iterator zeigt auf das Element hinter dem letzten eindeutigen Element und kann dann z. B. dazu benutzt werden, den Anfang eines zu löschenden Bereiches anzugeben.

Wie wär's mit std::set ?

Fellhuhn

unique vertauscht nicht, es geht etwas anders vor.

Beispiel:
122345 wird zu 123455

Die zweite 2 wird gelöscht indem alle Elemte dahinter (bis auf das letzte) einen "aufrücken".

1222345 wird zu 1234545

Das Ergebnis ist also so als wenn du das eigentliche Ergebnis in seiner neuen Länge über das alte rüberkopierst.

Übrigens geht auch folgendes:

myVec.resize(std::unique(myVec.begin(), myVec.end()) - myVec.begin());

Mizar

Fellhuhn schrieb:

Beispiel:
122345 wird zu 123455

Die zweite 2 wird gelöscht indem alle Elemte dahinter (bis auf das letzte) einen "aufrücken".

1222345 wird zu 1234545

Das Ergebnis ist also so als wenn du das eigentliche Ergebnis in seiner neuen Länge über das alte rüberkopierst.

Ok, ich habe deine Beispiele mal schnell getestet und musste dabei feststellen, das ich die Vorgehensweise von std::unique bisher doch etwas falsch verstanden hatte.
Naja, zumindest lag ich damit richtig, dass man std::unique dazu nutzen kann Mehrfacheinträge zu entfernen.

pumuckl

Fellhuhn schrieb:

Übrigens geht auch folgendes:

myVec.resize(std::unique(myVec.begin(), myVec.end()) - myVec.begin());

Jup. Im Vergleich dazu war mein Vorschlag weniger performant (da das Ergebnis einmal komplett kopiert wird), aber platzsparender (weil der Speicher der überflüssigen Elemente freigegeben wird). Außerdem werden bei dem Kopiervorgang Iteratoren ungültig, beim resize() nicht (aber auch nur, weil der Vector nicht vergrößert wird)
Ist also ein wenig Geschmackssache und ein wenig Profilersache.

dixidix

also so hat es was gebracht:

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

	v.resize(unique(v.begin(), v.end()) - v.begin());
...

Fellhuhn

pumuckl schrieb:

...aber platzsparender (weil der Speicher der überflüssigen Elemente freigegeben wird)...

Kommt dabei natürlich immer drauf an, was man weiterhin mit dem Vector vor hat. Wenn kurz darauf eh wieder neue Elemente angehängt werden, ist es von Vorteil den Platz nicht freizugeben. Ansonsten natürlich anders herum.