Container wie multiset, der aber operator== nutzt



  • Hi,

    ich benötige einen Container, der einen functor less nutzt, um schnell Objekte innerhalb eines Baumes zu lokalisieren. Bzgl. less soll es jedoch Buckets geben, bei denen das richtige Element eben trotzdem erst noch gefunden werden muss.

    Bei einer hashmap funktioniert das ja beispielsweise genau so. Der Hash muss nicht eindeutig sein, aber man gelangt dadurch erstmal zum Bucket. Dort muss man dann alle Objekte mit operator== angehen.

    Hashs sind bei mir unpraktisch, das Erstellen dauert ewig. Ich kann aber schnell less durchführen, kann also den Suchbereich sehr schnell eingrenzen.

    Dennoch gibt es viele Elemente, die dann eben nach dieser Ordnung genau so sind. Die sind aber nicht identisch und ich benötige die Identitätsprüfung.

    Eigentlich hätte ich das von multiset erwartet. Das führt ganz am Ende aber nicht den operator==-Vergleich durch, sondern gibt mir bei find einfach nur einen iterator zum erstbesten Element...

    Ich kann jetzt equal_range nutzen, selbst über die Ergebnismenge iterieren und operator== nutzen. Aber gibt es nicht einen Container, der bereits genau das macht?

    Viele Grüße
    Eisflamme



  • Deine "unabhängige" Definition von gleich und kleiner ist schon speziell, das wird wohl kein Container implementieren.



  • Eisflamme schrieb:

    Dennoch gibt es viele Elemente, die dann eben nach dieser Ordnung genau so sind. Die sind aber nicht identisch und ich benötige die Identitätsprüfung.

    Und die Identitätsprüfung doch miAlso doch hashes erstellen?
    also map<hash_map<T>> oder map<vector<T>>.



  • Wärs nicht ein sortierter vector + binary_search? Also evtl. boost::flat_map, wenn man das gekapselt haben will.



  • Hi,

    manni66:
    Wieso ist das speziell? Es reicht ja:

    template<typename T, typename Compare = std::less<t>, typename Equal = std::equal_to<T>>
    

    Der Vorteil dieses Containers bei mir liegt darin, dass ich große Objekte im Baum habe, die sich aber anhand einer gewissen Ordnung sehr schnell miteinander vergleichen lassen (fastLess). Wenn es ein Objekt also nicht gibt (und auch kein Bucket dafür), kriege ich diese Information sehr schnell.

    Wenn operator== genutzt werden muss, weil fastLess noch keinen Unterschied fest gestellt hat, ist das natürlich leider langsam... das passiert nicht häufig, aber kann halt passieren. Trotzdem habe ich den Bereich, den ich langsam vergleichen muss dann stark eingegrenzt.

    Aus diesem Grund ergibt hash bei mir auch keinen Sinn. Wenn ich ein Objekt vergleichen möchte, muss ich immer den gesamten Hash erzeugen, man kann ja unordered_map keinen gecacheten Hash übergeben. Den gesamten Hash zu erzeugen und dann einen Vergleich durch den Container zu machen, dauert aber fast immer länger, als einfach einen operator< zu machen, der sehr schnell das Element direkt findet.

    flat_map und volkards Ansatz muss ich noch überdenken.

    Danke für den Input!



  • Eisflamme schrieb:

    Aus diesem Grund ergibt hash bei mir auch keinen Sinn. Wenn ich ein Objekt vergleichen möchte, muss ich immer den gesamten Hash erzeugen, man kann ja unordered_map keinen gecacheten Hash übergeben.

    Doch, klar.
    Du sagst uns leider nur WIE DU es machen willst, nicht WAS DU machen willst, fürchte ich. Das ist für die Kommunikation suboptimal, weil Du beim WIE schon Fehlentscheidungen getroffen hast, die wir nur erraten können.



  • Und du kannst nicht wissen, dass ich beim "wie" schon Fehlentscheidungen getroffen habe. Das Standardargument, dass ich das "was" nicht erkläre, kenne ich zur genüge. Ich fordere aber niemanden auf, die Glaskugel zu bedienen. Wer meint, das zu müssen, hat die Frage falsch gelesen. Und falls nicht, kann man gezielte Infos nachfragen, die ich für irrelevant hielt.

    Ich will aber einen bestimmten Aspekt hier diskutieren, nicht immer das Rad neu erfinden und bei null anfangen, das ist nicht wirtschaftlich.

    In multiset fand ich in meinen Augen eine Schwäche, weil es operator== einfach nicht selbst ausführt, somit also Gleichheit unter allen mehrfach gelisteten Elementen annimmt. Eine Annahme, die ich für ziemlich sinnfrei halte, wofür sollte man multiset da einsetzen?

    Und wieso sollte operator< eine vollständige Ordnung schaffen, wenn eine teilweise Ordnung völlig reicht? Das ist doch bei einem Hash genau so, der muss nicht zwangsläufig komplett kollisionsfrei sein, wenn der Aufwand diese Freiheit zu erreichen eben sehr groß ist und man mit geringem Aufwand auch schon einen hohen Nutzen durch den Hash erzielt. In meinen Augen absolut valide Gedanken, weswegen ich die Annahme von multiset eben schlecht finde.

    In einem Punkt hast du jedoch recht, den Hash könnte man tatsächlich auch durch den functor cachen, das bringt an der Stelle wieder Speed. Muss ich mal neu benchmarken.



  • Eisflamme schrieb:

    Und du kannst nicht wissen, dass ich beim "wie" schon Fehlentscheidungen getroffen habe.

    Doch, diesmal schon.



  • 1. Es gibt wenn ich mich recht erinnere einen boost hash container, der einen "compatible" Typ bekommen kann. Also du speicherst Typ T im Container, suchst aber nach einem hash<U>. Das könnte man evtl. benutzen.

    2. Es hört sich etwas komisch an, dass man < viel schneller implementieren kann, als ==. Wenn du bei < schnell entscheiden kannst, ob ein Objekt kleiner ist, weißt du ja auch, dass die nicht gleich sind. Wenn du also die Vergleiche beim == entsprechend anordnest, kannst du in den meisten Fällen schnell sagen, die Objekte sind nicht gleich. Mag aber sein, dass es bei dir tatsächlich nicht geht.



  • Hi,

    volkard:
    Ich kann jdf. sagen, dass bei dem Beitrag:

    Und die Identitätsprüfung doch miAlso doch hashes erstellen?
    also map<hash_map<T>> oder map<vector<T>>.

    wohl irgendwas schief gelaufen ist. Was ist dein Vorschlag, was ist Key und Value bei deiner Map, was soll dein erster Satz sagen?

    Mechanics:
    Da habe ich wohl leider den falschen Eindruck erweckt. operator== könnte ich genau so schnell implementieren, jedoch gibt operator< ja zusätzlich eine Richtung an, die praktisch ist. vector + binary_search wäre natürlich möglich, da muss ich halt selbst ein korrekt platziertes insert usw. implementieren, was ich gerne vermeiden würde (weil das Rad doch bestimmt bereits erfunden wurde). Bei flat_map verstehe ich jedoch nicht, was der Key sein sollte oder soll das hier der Hash sein?

    Mein Argument gegen Hashs kann schnell verfallen, wenn ich übersehe, wie man schöne Hashs erstellen kann. Meine Objekte haben ein paar Zahlen, ein paar Strings und dann komplexere Strukturen. operator!= (oder operator<) finden Ungleichheit bei Strings maximal schnell raus. Würde ich einen Hash generieren, müssten bei der Erstellung alle Strings durchlaufen werden. Gut, die könnte ich im Objekt selbst cachen mit einem hash-Functor für flat_map, welcher einfach das Objekt fragt, wie der aktuelle Hash ist. Das wäre dann legitim, ich muss halt das Caching im Objekt einbauen... wenn das einen klaren Performance-Benefit bringt, wär das gut, ich sehe jedoch noch nicht genau, ob der dann da ist. Und man muss sich erstmal Gedanken für eine sehr gute Hashfunktion machen, fällt mir auch schwer (<- an dem Punkt kann man sagen, mein Argument verfällt schnell, wenn man superschnell tolle Hashes erstellen kann, was ich noch nicht sehe).

    Viele Grüße
    Eisflamme



  • Eisflamme schrieb:

    Bei flat_map verstehe ich jedoch nicht, was der Key sein sollte oder soll das hier der Hash sein?

    Der Key wäre dein Objekt und das value nichts. Bzw., brauchst dann ein flat_set.


Log in to reply