Was ist der Unterschied zwischen eindeutigen Formularalgorithmen und eindeutigen Listencontainern?

Question

Kann ich den eindeutigen Algorithmus auf einer Liste ausführen? Und wenn ja, wo ist der Unterschied zur eindeutigen Funktion des Listencontainers?

Entspricht der folgende Code?

std::list<int> l; 
//add some values to list 
l.unique(); 

und

std::list<int> l; 
//add some value to list 
std::unique(l.begin(), l.end()); 

Answer 1

They're not the same.

std::list::unique entfernt alle aufeinanderfolgenden doppelten Elemente aus dem Container.
Dies ist, was Sie wahrscheinlich wollen.

std::unique ... gut ...

Entfernen durch Verschieben der Elemente in dem Bereich in der Weise, dass die Elemente gelöscht werden, überschrieben werden. Die relative Reihenfolge der verbleibenden Elemente bleibt erhalten und die physische Größe des Containers bleibt unverändert. Iteratoren, die auf ein Element zwischen dem neuen logischen Ende und dem physikalischen Ende des Bereichs zeigen, sind immer noch dereferenzierbar, aber die Elemente selbst haben nicht spezifizierte Werte. Ein Aufruf von unique wird normalerweise von einem Aufruf der Löschmethode eines Containers gefolgt, der die nicht angegebenen Werte löscht und die physische Größe des Containers auf die neue logische Größe reduziert.

Answer 2

standardmäßig die Algorithmen in <algorithm>, sind generische Algorithmen, die auf Iteratoren arbeitet. Zusammenfassend können diese Algorithmen keinen Vorteil aus dem Aufbau des Containers ziehen.

Die STL fügt ihren Containern jedoch auch Memberfunktionen hinzu, die zwar weniger allgemein sind, aber von der Containerstruktur profitieren können. Ein Beispiel: std::find(map.cbegin(), map.cend(), element) wird über alle Elemente gehen, um das gegebene Element zu finden, während map.find(element) die Baumstruktur verwenden kann. Dies reduziert einen linear Algorithmus auf einen log(n).

Die gleiche Strategie wird std::list hinzugefügt, wie 'Verschieben' ein Element ist eine Std :: Liste ist nicht mehr als das Ändern der Links in der Liste, dies kann viel mehr performant als Verschieben/Kopieren des Inhalts der Elemente.

Also, für std::list<int>, erwarte ich nicht viel anders, obwohl wenn Sie teure Klassen in der Liste speichern, werden Sie den Unterschied bemerken.

PS: std :: einzigartig keine Elemente entfernen, bewegt er sich nach hinten und gibt ein neues 'Ende', std :: entfernen (oder std :: list :: remove), um die Elemente zu entfernen

Answer 3

Entspricht der folgende Code?

Nein, ist es nicht. std::list::unique entfernt alle aufeinanderfolgenden Duplikate, aber std::unique hat keine Möglichkeit, dies für alle Container generisch zu tun. Der Algorithmus ordnet den Container so an, dass die nicht entfernten am Anfang stehen und Ihnen einen Iterator zurückgeben, von dem Sie löschen sollten.

Diese beiden sind äquivalent (zumindest im Hinblick darauf, was die resultierende Liste aussieht, wenn auch nicht in den Schritte unternommen, um dorthin zu gelangen, die Anforderungen an die Art, oder die Auswirkungen auf Iterator Validierung):

l.unique(); 
l.erase(
    std::unique(l.begin(), l.end()), 
    l.end()); 

Letzteres wird auch als das Erase-Remove-Idiom bezeichnet (obwohl in diesem Fall verwenden wir eindeutig und nicht entfernen)