"unique stack" Container

[icarus2]

Auf keinen Fall einen std::vector. Da du ja bei jedem Einfügen onehin alle Elemente durchlaufen musst um zu prüfen, ob das Element bereits vorkommt, kannst du genauso gut eine linked list nehmen. Diese ist dann sowiso performanter wenn es darum geht ein Element aus der Mitte vorne anzuhängen.

[FrEEzE2046]

Also wenn ich es sowieso selbst schreiben müsste, würde ich eher eine Hash und BTree Variante bevorzugen, um festzustellen, ob ein Eintrag schon existiert. Die weitere stack Reihenfolge könnte ja parallel dazu festgehalten werden.

[icarus2]

FrEEzE2046 schrieb:

Also wenn ich es sowieso selbst schreiben müsste, würde ich eher eine Hash und BTree Variante bevorzugen, um festzustellen, ob ein Eintrag schon existiert. Die weitere stack Reihenfolge könnte ja parallel dazu festgehalten werden.

Wenn man den zusätzlichen Speicherplatz verkraften kann, kann man das so machen. Könnte allerdings etwas mühsam werden. Vor allem weil dir normale BTrees auch nur lineare worst-case Garantie geben.
Hast du sehr viele Einfügeoperationen auf dem Stack? Wel wenn der Stack nicht allzu intensiv gebraucht wird, dann könnte eine linked list reichen.

Was möchtest du den überhaupt genau machen?

[FrEEzE2046]

Also std::vector wäre denkbar unangebracht, da er ja auch immer am Stück allokiert, was sehr inperformant werden kann.

Die Einfüge-Operationen halten sich in Grenzen. Das was intensiv passieren wird, sind beim push eines bereits existierenden Werte, das Umhängen dieser Elemente. Der std::queue ist eigentlich recht fein, jedoch hat er keine splice Funktionalität. Mit der std::list (oder diese selbst) ihn zu nutzen ist wieder schlecht, weil hier jedes Element einzeln allokiert wird ...

[icarus2]

FrEEzE2046 schrieb:

Also std::vector wäre denkbar unangebracht, da er ja auch immer am Stück allokiert, was sehr inperformant werden kann.

Nun ja, man allokiert dann halt einen std::vector mit einer bestimmten Grösse. Diese muss dann halt gegebenenfalls verändert werden. Wenn man es aber richtig implementiert, so bleibendie Kosten trotzdem konstant. Die teurern Operationen, also das vergrössern des vectors, wird amortisiert.
Das Problem in deinem Fall wären eher die Verschiebungen von der Mitte nach vorne, die teuer werden können. Die Lücken aufzufüllen ist sehr mühsam. Könnte man allerdings vielleicht sogar performant implementieren, bin ich mir jetzt nicht sicher. Hab ich nie ausprobiert.

FrEEzE2046 schrieb:

Die Einfüge-Operationen halten sich in Grenzen. Das was intensiv passieren wird, sind beim push eines bereits existierenden Werte, das Umhängen dieser Elemente.

Das umhängen ist mit einer linked list kein Problem. Aber die Suche ist ziemlich teuer. O(n) Laufzeit.

Was hast du den überhaupt vor? Wofür muss der Stack unique sein?

[FrEEzE2046]

icarus2 schrieb:

Das umhängen ist mit einer linked list kein Problem. Aber die Suche ist ziemlich teuer. O(n) Laufzeit.

Sagen wir mal ich möchte Objekte nach der letzten Verwendung speichern (Pointer). Das zuletzt verwendete Objekt steht immer "vorne".

[icarus2]

FrEEzE2046 schrieb:

icarus2 schrieb:

Das umhängen ist mit einer linked list kein Problem. Aber die Suche ist ziemlich teuer. O(n) Laufzeit.

Sagen wir mal ich möchte Objekte nach der letzten Verwendung speichern (Pointer). Das zuletzt verwendete Objekt steht immer "vorne".

Jap, der Zurgriff auf das oberste Element des Stacks ist konstant. Aber du musst ja bei jedem push den ganzen Stack durchsuchen um herauszufinden, ob das Element bereits vorkommt.

Oder habe ich deine Aussage falsch verstanden? Ich weiss nämlich nicht genau was du mit Verwendung meinst? push?

[hustbaer]

FrEEzE2046 schrieb:

icarus2 schrieb:

Das umhängen ist mit einer linked list kein Problem. Aber die Suche ist ziemlich teuer. O(n) Laufzeit.

Sagen wir mal ich möchte Objekte nach der letzten Verwendung speichern (Pointer). Das zuletzt verwendete Objekt steht immer "vorne".

Dann sag gleich dass du einen LRU-Cache implementieren willst.

Fertigen Container kenne ich dazu keinen.
Aber du kannst z.B. Boost.Multiindex verwenden und eine Liste mit einer Map bzw. einem Set paaren.
Den "gibt's schon?" Lookup machst du das Set/die Map, dann holst du dir über den Map/Set Iterator den Listen-Iterator und schiebst das Element in der Liste ganz nach vorne.

Kann man natürlich auch ohne Boost.Multiindex mit ner std::list + std::set/map machen, nur muss man da beim Einfügen aufpassen dass es auch Exception-safe ist.
(Da es weder bei list noch bei map/set ein "reserve" gibt, bleibt eigentlich nur die Möglichkeit dass man, falls beim 2. insert eine Exception fliegt, das 1. insert mit erase wieder rückgängig macht.)

BTW: falls es um recht wenige Elemente geht (10-20), und der Vergleich zweier Elemente billig ist (z.B. einfach nen Integer oder Zeiger vergleichen), dann ist es vermutlich den Aufwand nicht wert. Eine einfache Implementierung mit std::vector kann da sogar schneller sein.

[icarus2]

hustbaer schrieb:

Dann sag gleich dass du einen LRU-Cache implementieren willst.

Achsoo, jetzt ist klar was er meint
Habe gar nicht daran gedacht und habe mich die ganze Zeit gefragt wofür man denn so etwas brauchen könnte ^^

[hustbaer]

Naja, ist auch nur geraten. Ist aber der einzige Anwendungsfall der mir jetzt auf die Schnelle einfällt.

[volkard]

FrEEzE2046 schrieb:

Der Begriff "unique stack" beschreibt es nicht ganz.
Ich suche einen STL konformen Container, welcher folgende Funktionalität bietet:

- Elemente sind unique (keine doppelten Werte)
- was zuletzt gepushed wurde steht an oberster Stelle
- Wird ein Werte gepushed, der bereits existiert, wird er aus seiner bestehenden Position entfernt und oben angefügt

Gibt es so etwas bereits oder muss ich mir da selbst einen Container schreiben?

Sorry, aber wieder einmal muß ich fragen, wozu Du ihn brauchst.
Klinkt mir nämlich nach eine Move-To-Front-List.

Die nehme ich oft. Allerdings passend zu Algos, wo ich sinnvoll von vorne nach hinten laufe und bei Fund den Fund nach vorne ziehe.
Die mache ich gewöhlich als intrusive double linked list als ring mit Pseudoknoten als Wurzel.
Zur Zeit habe ich eine als vector laufen, das Suchprädikat ist so teuer, daß es gar nicht weh tut, den Fund dann schrittweise nach vorne zu swappen, und ich habe störend viele Daten, die möchte ich besammen halten.

[FrEEzE2046]

Es ist im Endeffekt ein Last-Recently-Used Cache. Bisher habe ich das so gelöst:

Ich habe eine std::list, welche die Objekte enthält. Dann habe ich ein dynamisch allokiertes array mit Pointern auf die Iteratoren. Der Index auf dieses array ist auch gleichzeitig eine ID für die Objekte. Sieht ungefähr so aus:

std::list<my_type>            m_list;
std::list<my_type>::iterator* m_iter;

my_type& get(std::ptrdiff_t i)
{
	if( iter >= this->m_list.size() )
		throw throw std::out_of_range();	
	this->m_list.splice(this->m_list.begin(), this->m_list, this->m_iter[i]);
	return *this->m_iter[i];
}

[Shade Of Mine]

volkard schrieb:

Sorry, aber wieder einmal muß ich fragen, wozu Du ihn brauchst.

Ich habe sowas für einen LRU-Cache.
Eine map die den Wert als Key hat und als Value einen iterator auf eine double linked list die als value wiederum einen iterator auf das Element in der map hat.

[FrEEzE2046]

Ich habe noch einen weiteren Anwendungsfall, bei dem ich eine ergänzende Funktionalität benötige. Hier möchte ich LRU-Objekte bis zu einem gewissen Grad der Verdrängung betrachten; beispielsweiße eine Art Top 10. Sobald Objekte diese Top 10 durch Benutzung betreten (egal ob als "Neueinsteiger" oder aus einem der hinteren Plätze) oder durch längere nicht Benutzung verlassen, soll mich ein Event über diesen Eintritt / Austritt informieren. Ich benötige das, weil diese Objekte Resourcen allokieren, welche sie bei längerer Benutzung freigeben sollen.

Da beide Anwendungsfälle recht ähnlich sind und nur wenig zutun zu vorhandenen containern benötigen, würde ich diese gerne in einer Klasse kapseln. Möglichst so dynamisch, dass auch der darunter liegende container, per template, austauschbar ist.

Natürlich könnte ich die Funktionalität auch redundant an beiden Stellen implementieren (einmal mit den angesprochenen Events und einmal ohne). Jedoch sieht man schon hier, dass man das durchaus öfter benötigen kann und zum anderen möchte ich, dass der Sinn dieser Implementation möglichst deutlich wird, was bei einer Kapselung in einer eigenen Klasse, aus meiner Sicht der Fall wäre.

[hustbaer]

@FrEEzE2046:
Na dann mach das so.
Die "Durchnummerierung" ist, wenn es nicht 10 Elemente sind sondern eher 100 oder 1000, nicht ganz trivial. Wenn es wirklich 10 sind, dann kannst du in dem Fall dass ein "nicht Top 10" Element vorgereiht wird einfach die ersten 10 durchzählen und das 11. (das gerade rausgeflogen ist) dann mit "nicht mehr top 10" markieren.

Bzw. mir fallen da gerade die Intrusive Container von Boost ein. Die sind einfacher zu verwenden als Boost.Multiindex und bieten eigentlich alles was du dafür brauchst. Dazu packst du einfach die beiden benötigten Hooks (Liste & Set), nen "is top 10" bool und das zu speichernde Element in eine struct, und verwaltest diese struct dann in einem intrusive-set + einer intrusive-list.
Da ein insert bei der intrusive list nicht schief gehen kann (und beim set nur wenn es ein element mit dem selben key bereits gibt), ist das auch automatisch exception safe. Und du brauchst nur eine dynamische Allokation pro Element (inklusvie insert in die Liste und das Set), also auch relativ performant.

Im Prinzip kannst du sogar beim Insert eines Elements erst das ermitteln was dann rausfliegt, und die "Node" dieses Elements recyclen. Dann hast du amortisiert 0 dynamische Allokationen pro insert. Besser geht net

[FrEEzE2046]

@hustbar
Das mit den "Top 10" möchte ich nochmal relativieren. Der Wert soll natürlich konfigurierbar sein. Die "10" hatte ich jetzt nur mal als Beispiel genommen. Ist es nicht angebrachter einfach mein inserten bzw. umhängen von Knoten für diesen das "Eingangs-Event" (er kommt ja dann immer an Position 1) und für den n-ten (auch dieser steht ja immer fest) das "Ausgangs-Event" zu werfen?