Mehrfacheinträge entfernen

Mizar

Es gibt einen STL-Algorythmus der fast das macht was du möchtest: std::unique
std::unique "schiebt" aufeinanderfolgende, sich wiederholende Elemente eines Containers hinter das letzte eindeutige Element des Containers. Wenn z.B. ein Vektor die folgenden Elemente hätte:

1 2 2 3 3 4

Dann würde std::unique die Elemente folgendermaßen "umordnen":

1 2 3 4 2 3

Aber wie oben erwähnt müssen die sich wiederholenden Elemente aufeinanderfolgend sein, weshalb std::unique an einem Vektor mit den folgenden Elementen nichts umsortieren würde:

1 2 3 2 3 4

Allerdings kannst du ja mit std::sort die Elemente des Containers so sortieren, dass diese dann hintereinander stehen würden. Anschließend könntest du dann die sich wiederholenden und nun auch aufeinanderfolgenden Elemente mit std::unique an das Ende des Containers "schieben" und diese dann mit Hilfe des zurückgegebenen Iterators, der auf das Element hinter dem letzten eindeutigen Element des Containers zeigt, löschen.

Puh, falls das jetzt zu kompliziert war, habe ich hier noch ein kleines Beispiel:

//main.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using std::cout;
using std::endl;
using std::vector;
using std::sort;
using std::unique;

int main()
{
	vector<int> ivec;
	// Vector mit 2 Werten füllen
	ivec.push_back(2);
	ivec.push_back(5);
	// Füllt den Vector mit weiteren Werten
	for(int i = 0; i != 10; ++i)
		ivec.push_back(i);
	// und zusätzlich noch ein paar bereits enthaltene Werte hinzufügen
	ivec.push_back(3);
	ivec.push_back(7);
	ivec.push_back(9);
	// Alle Elemente des Vectors ausgeben
	cout << "Alle Werte des Vectors:" << endl;
	for(vector<int>::iterator it = ivec.begin(); it != ivec.end(); ++it)
		cout << *it << " ";
	cout << endl;
	// Die Elemente des Vectors sortieren, damit Elemente mit gleichen Werten
	// hintereinander stehen
	sort(ivec.begin(), ivec.end());
	// 'unique' "schiebt" aufeinanderfolgende, sich wiederholende Elemente hinter
	// das letzte eindeutige Element des Vectors und gibt einen Iterator auf das
	// erste nach hinten "geschobene" Element zurück
	vector<int>::iterator unique_iter = unique(ivec.begin(), ivec.end());
	// Und jetzt noch die Elemente, die sich wiederholten, löschen
	ivec.erase(unique_iter, ivec.end());
	// Nun alle noch übrigen, eindeutigen Elemente ausgeben
	cout << "Eindeutige Elemente:" << endl;
	for(vector<int>::iterator it = ivec.begin(); it != ivec.end(); ++it)
		cout << *it << " ";
	cout << endl;

	return 0;
}

Die erste Ausgabe des Beispiels würde lauten:

Alle Werte des Vectors:
2 5 0 1 2 3 4 5 6 7 8 9 3 7 9

Und die Ausgabe nach std::sort und std::unique und std::vector::erase() würde lauten:

Eindeutige Elemente:
0 1 2 3 4 5 6 7 8 9

So, das war hoffentlich hilfreich

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.