ranged Container

kartoffelsack

Ich habe Objekte, die haben einen Gültigkeitsbereich (z.B. beginn und Ende-Zeitpunkt).

Die möchte ich in einen Container speichern. Abfragen möchte ich die Objekte, indem ich einen Wert (z.B. Zeitpunkt) angebe, der Container sollte mir dann alle Objekte, in deren Gültigkeitsbereich dieser Wert liegt, geben.

Also z.B. Objekt1 gültig von 15:00 bis 16:00, Objet2 von 15:45 bis 16:00.

getObjekt( 15:30) würde dann Objekt1, getObjekt( 15:50) Objekt1 und Objekt2 liefern.

Kennt vielleicht jemand was fertiges, am besten template-mäßiges, das vernünftig skaliert und noch dazu ausnahmefest ist?

Ganz so einfach ist das ja nicht von hand zu machen, oder?

eine sehr dumme frage -.-
schonmal mit selber nachdenken versucht?!?
stichwort: std::copy_if()

HumeSikkins

Hört sich für mich so an als könne man da was mit lower_bound bzw. upper_bound machen. Vorher musst du den Container natürlich entsprechend sortieren. Z.B. nach dem Startwert.
In diesem Fall suchst du mit lower_bound das erste Intervall, dessen Startwert nicht kleiner als der Testwert ist. Von diesem Intervall kannst du dann rückwärts alle Intervalle nehmen, dessen Endwert nicht kleiner dem Testwert ist.
In PseudoCode:

pair<iterator, iterator> getObject(Zeitpunkt p)
{
    if (container_.empty()) 
        return pair<iterator, iterator>(container_.end(), container_.end());
    iterator pastP = lower_bound(container_.begin(),conatiner_.end(), p);
    if (pastP == container_.begin())
         return pair<iterator, iterator>(container_.end(), container_.end());
    iterator start = pastP;
    --start;
    while (!(start->endPoint < p) && start != container_.begin())
        --start;
    return pair<iterator, iterator>(start, pastP);
}

kartoffelsack

hm, naja.
copy_if macht wohl ne lineare Suche über alle Elemente des Containers.
Ähnlich, wenn ich mit upper und lower_bound arbeite.
Die Elemente, deren Beginn in den Grenzen liegt, finden sich noch schnell. Aber dann muss ich diese linear durchwühlen. Und wenn das ein paar sind und ich das ein paarmal machen muss, dann bricht mir die Performance weg.

Meine eigene Idee geht dahin, zwei std::maps zu haben, die einmal nach Beginn und einmal nach Ende sortiert ist und dann die Schnittmenge zu nehmen. Aber auch das läuft ja wieder auf ne lineare Suche raus

Irgnendwelche Ideen?
Vielleicht sowas:
std::map< std::map<Object, SortByEnd>, SortByBegin>
???
Bringt ja auch nix, muss ich bei jedem suchen alle innerne Maps angucken.

Oder seh ich Probleme wo keine sind

Shade Of Mine

kartoffelsack schrieb:

Aber auch das läuft ja wieder auf ne lineare Suche raus

Dein Problem ist: du hast unendlich viele Keys und willst die in eine Map packen (unendlich, weil es unendlich viele Kombinationen aus Start und Endwert gibt. OK, vielleicht ist die Menge auch endlich, aber trotzdem viel zu groß).

Das klappt natürlich nicht vernüenftig. Du wirst also mit reinem Lookup nicht weit kommen.

Die Idee mit der Schnittmenge klingt doch vernünftig, auch wenn ein std::map< std::map<Object, SortByEnd>, SortByBegin> vermutlich nicht das richtige ist.

vielleicht ist ein vector mit den Elementen und 2 sortierte container mit den keys eine gute idee.

du hantierst im speicher somit nur mit ints, was ja schön schnell ist wenn es sortierte vectoren sind, schnappst du dir erstmal alle mit der richtigen startzeit und dann alle mit der richtigen endzeit. und da die schnittmenge bilden ist zwar auch linear aber ziemlich schnell
O(N) ist ja nicht zwangsläufig schlecht.

Oder seh ich Probleme wo keine sind

Wieviele Elemente hast du denn?
Wenn es nur um ein paar Tausend geht, dann verschwendest du deine Zeit und wenn es signifikant mehr sind, hast du vermutlich ein größeres Problem mit dem Speicherverbrauch...

finix

Ich find Shades Idee eigentlich ganz vernünftig. Wenn du die Zeitpunkte von den eigentlichen Objekten getrennt hast könntest du vielleicht auch den Wertebereich noch mal in Segmente aufteilen, z.B. eins pro Stunde.

Viel mehr Gedanken solltest du dir darüber machen wie du deine Ergebnismenge zurückgibst. Wenn sowas wie

Objektintervalle = {(13:00, 13:45), (13:05, 13:20), (13:30, 14:42)}

möglich ist und du nach z.B. 13:33 suchst kannst du nicht einfach zwei Iteratoren liefern.

Nebenbei: Beginn- und Endzeitpunkt sind Eigenschaften der Klasse oder nicht?

kartoffelsack

Nebenbei: Beginn- und Endzeitpunkt sind Eigenschaften der Klasse oder nicht?

ja. Ich kann die Werte aber auch kopieren und seperat als keys speichern.

Wieviele Elemente hast du denn?
Wenn es nur um ein paar Tausend geht, dann verschwendest du deine Zeit und wenn es signifikant mehr sind, hast du vermutlich ein größeres Problem mit dem Speicherverbrauch...

ok, wahrscheinlich ist die Performance aufgrund der Anzahl der Daten nicht das Problem. D.h. wenns nix gibt, ist es schon ok. Dache aber, dass es für solche Prolbeme auch ne Standard-Struktur (k.a. ein 'zweidimensionaler Binärbaum' oder wie das auch immer heißen könnte) gibt.

Werds dann entweder mit humes Vorschlag oder mit ner Schnittmenge probieren.

Vielen Dank!