std::list, wie funktioniert der vergleich?
-
ihr habt recht, ich meine std::set. ansonsten bleibt die frage gleich
-
Vielleicht ein Schreibfehler.
Einer std::list ist es sch****egal ob ein Objekt bereits in der Liste
vorhanden ist. Der < operator wird verwendet wenn du list.sort() ohne
eine Sort-Funktion aufrufst.
-
Ooops, was für ein Gedrängel.
-
Wenn ein op< keinen Sinn macht musst du std::set eine andere Möglichkeit geben die Element sortiert zu halten um den gewünschten Speed durch ein std::set auch zu haben.
Du kannst bei der Erstellung als zweiten Template-Parameter ein Prädikat angeben, dass die Sortierung vornimmt.
Standardmäßig wird std::less verwendet, welches intern den op< benützt.
MfG SideWinder
-
An STL set is:
- An associative container, which a variable size container that supports the efficient retrieval of element values based on an associated key value. Further, it is a simple associative container because its element values are its key values.
- Reversible, because it provides a bidirectional iterator to access its elements.
- Sorted, because its elements are ordered by key values within the container in accordance with a specified comparison function.
- Unique in the sense that each of its elements must have a unique key. Since set is also a simple associative container, its elements are also unique.Punkt 3 erfordert, dass deine Elemente in irgendeinerweise sortiert werden können. Wenn das nicht der Fall ist, ist std::set nicht der richtige Container.
MfG SideWinder
-
wegen des speedups hab ich auf std::set zurückgegriffen. ich muss aus meiner objektmenge alle duplikate entfernen und jede eigene implementation wäre unter garantie langsamer als das, was in der stl vorhanden ist
werd mir dann wohl ne schnelle ordnungsrelation ausdenken müssen.
-
std::setlist schrieb:
wegen des speedups hab ich auf std::set zurückgegriffen. ich muss aus meiner objektmenge alle duplikate entfernen und jede eigene implementation wäre unter garantie langsamer als das, was in der stl vorhanden ist
werd mir dann wohl ne schnelle ordnungsrelation ausdenken müssen.
Wie erkennst du Duplikate wenn du die einzelnen Elemente nicht untereinander unterschieden kannst? Wenn sie unterscheidbar sind kannst du im schlechtesten Fall ja immer von "größer" reden wenn sie unterschiedlich sind und ansonsten von "gleich".
MfG SideWinder
-
Nein, das geht nicht, das wäre keine (totale?) Ordnungsrelation. Das verursacht höchstens Abstürze und Endlosschleifen.
Bye, TGGC (Fakten)
-
SideWinder schrieb:
Wenn sie unterscheidbar sind kannst du im schlechtesten Fall ja immer von "größer" reden wenn sie unterschiedlich sind und ansonsten von "gleich".
Meines Wissens führt das zu einem undefinierten Verhalten beim Einfügen in einen std::set. In der Praxis ergibt sich u.U. eine Endlosschleife.
Die Elemente müssen eindeutig sortierbar sein.Gruß
Werner
-
Nein, das geht nicht, das wäre keine (totale?) Ordnungsrelation. Das verursacht höchstens Abstürze und Endlosschleifen.
ich nehme an, da std::set den < operator verwendet, wird es eine totale ordnungsrelation verwenden. partielle ordnungen würden zudem "duplikate" zulassen.
-
Meines Wissens führt das zu einem undefinierten Verhalten beim Einfügen in einen std::set. In der Praxis ergibt sich u.U. eine Endlosschleife.
Die Elemente müssen eindeutig sortierbar sein.mein erster versuch war tatsächlich einfach der, dass ich den op< als "op!=" implementiert hatte. mehrere testdurchläufe mit 2 mio. objekten mit vielen duplikaten sind auch recht fix durchgelaufen. es wurden aber erstaunlich wenig objekte entfernt, was mich auf die frage nach der art des vergleichs brachte.
-
Wenn ich nicht ganz falsch liege testet set auf (!(value<*it) && !(*it<value)).
Wie wäre es mit ner std::map die als Schlüssel die Speicheradresse der konkreten Objekte nutzt?MfG Spacelord
-
hey, die idee ist gut. ich werds mal damit versuchen.
-
Naja,eigentlich ist die Idee ziemlicher Käse
,aber ich frag mich auch warum du unbedingt nen sortierten Container für nicht sortierbare Objekte brauchst !?
Wie willst du denn jemals irgendwelche konkreten Objekte in der map wiederfinden?MfG Spacelord
-
die idee ist kein käse, denn so erspar ich mir das generieren eines keys.
map vergleicht aber offenbar auch nicht alle objekte. also im endeffekt doch käse
ich brauch die objekte eigentlich nicht sortiert, ich brauch nur nen schnelle methode, duplikate zu entfernen. duplikate sind all jene objekte, bei denen bestimmte member variablen gleich sind.
dachte halt, vielleicht hätte irgendne stl klasse ne schweinegeile methode eingebaut, auf duplikate zu überprüfen. aber es ist wohl doch bloss ne striktordnung.
aber immerhin erspar ich es mir so, den ganzen krams komplett selbst implementieren zu müssen
ich muss mir halt nur noch ne striktordnung für meine objekte ausdenken.
-
Eventuell ist dann sowas in der Art für dich von Interesse http://www.sgi.com/tech/stl/hash_set.html.
Ansonsten kommst du in nem unsortierten Container immer auf O(n).Also wäre vielleicht auch std::unique ne Alternative.
Oder schau mal ob boost dir was in der Richtung bietet...MfG Spacelord
-
Eigentlich ist es doch ziemlich simpel 'ne Vergleichsfunktion zu schreiben. Du betrachtest einfach beide Daten als ByteArray (oder int.. egal), wenn eins länger ist mit Nullen auffüllen. Und dann vergleichst du die ersten Einträge beider Arrays, ist einer größer, hast du das Ergebnis. Bei Gleichheit gehts mit dem nächsten weiter. Entweder findest du irgendwann einen Unterschied, oder die Objekte sind halt gleich.
Bye, TGGC (Fakten)
-
-
doch nicht. macht nur nur aufeinanderfolgende duplikate weg.
