3. map::lower_bound

map::lower_bound

  • K

    Vielleicht mal die Erklärung, wieso mich das interessiert:

    Ich baue gerade einen standardkonformen sortierten, assoziativen Container auf Basis einer Skip List (Boost hat noch keine … hint, hint ^^). Die Klasse besitzt dieselbe Schnittstelle wie eine std::map. Und bei den Bound-Funktionen verzage ich gerade an der Implementierung, weil die vom Standard vorgeschriebenen Rückgabewerte einfach keinen Sinn ergeben.

    0
  • J

    Stell Dir vor, Du wolltest eine Range mit allen Elementen zwischen 8 und 17 haben. Dann kriegste mit lower_bound(8) das untere Ende der Range und mit upperbound(17) das obere Ende. Prima Namensgebung oder? 😉

    0
  • L

    Zum Misverständnis führt hier wohl, dass du lower_bound so aufgefasst hast, dass du der Methode einen beliebigen Wert gibst und es einen Wert aus der Map sucht der als untere Grenze geeignet ist.
    Aber das Verhalten ist so zu verstehen wie Jester bereits erklärt hat.

    0
  • W

    Mal angenommen der set hat die Elemente

    idx:  0   1   2   3   4   5   6
val:  1   5   9  11  15  20  22

    dann liefern Dir die Aufrufe lower_bound(8) und upper_bound(17) die Iteratoren bei den Indizes
    2 und 5 - also das halboffene Intervall [a_2, a_5)
    Jetzt kannst Du dies durch einen set ersetzen, dessen kleinstes Element den Wert 8 und dessen größtes Element den Wert 17 hat. Beachte, dass das Intervall halboffen ist und der obere Wert nicht verändert wird.
    Also aus

    [..........)
idx:  0   1  2   3   4   5   6
val:  1   5  9  11  15  20  22

    wird

    val:  1   5  [ 8 ... 17 ] 20  22

    unter Einhaltung der Ordnung des sets

    Gruß
    Werner

    0
  • K

    Okay, mit Mengen gibt das Sinn. Danke.

    0
  • P

    wo sowas auch evtl sinn geben könnte, ist mit einer map<double, X> - da double-werte dazu neigen, dass man sie verfehlt wenn man sie berechnet, bringen hier die bounds vielleicht was.

    std::map<double, std::string> mymap;
double a = 1.0/6.0 + 1.0/3.0; //mit etwas pech gibt das eben nicht 0.5

mymap[a] = "Hier steht 0.5, oder?". //vermutlich mymap[0.49999999999997] oder sowas
cout << mymap[0.5] << endl; // gibt wohl n leeren string.
for(/*...*/iterator it = mymap.lower_bound(0.5-epsilon); it != mymap.upper_bound(0.5+epsilon)) cout << *it.second << endl;
    0
  • ?

    @Konrad Rudolph: Mir hat das auch mal schlimme Kopfschmerzen bereitet ...

    0
  • F

    Man sollte dabei natürlich beachten das es entegen dem was Werner Salomon schreibt sicht auf die Keys bezieht und nicht auf die Values. Da die Values ja nicht sortiert sind, macht es keinen Sinn dies auf second anzuwenden.

    0
  • K

    Fellhuhn schrieb:

    Man sollte dabei natürlich beachten das es entegen dem was Werner Salomon schreibt sicht auf die Keys bezieht und nicht auf die Values. Da die Values ja nicht sortiert sind, macht es keinen Sinn dies auf second anzuwenden.

    Ich glaube, Werner meint schon das richtige und die Indizes sind nur zur Veranschaulichung der Position. Mein Beispiel war ja auch mit std::set, da gibt's keine Werte, nur Schlüssel.

    0
  • F

    Mit set kommt es hin, sein Beispiel sieht aber eben mehr nach einer Map aus. Deswegen wollte ich das noch einmal erwähnen. 😉

    0
  • L

    Fellhuhn schrieb:

    Mit set kommt es hin, sein Beispiel sieht aber eben mehr nach einer Map aus. Deswegen wollte ich das noch einmal erwähnen. 😉

    Er erwähnt aber explizit "set". Und das im ersten Satz. 😉

    0
  • F

    Kleinigkeiten! 😛

    0
  • K

    Hallo,

    mir fällt gerade auf: Eure Erklärung ist fein, aber leider „versagt“ sie, sobald man zu 'equal_range' kommt. Der Standard definiert den Rückgabewert von equal_range(k) als make_pair(lower_bound(k), upper_bound(k)) .

    Für Multi-Map-Container mag das sinnvoll sein, aber wieso ist die Methode auch in Unique-Map-Containers vorhanden, und nimmt nur einen Parameter an (wenn sie zwei annähme, wäre sie sinnvoller)?

    0
  • J

    was versagt denn da? Du kriegst alle Elemente, x für die weder x<k noch k<x gilt. Die also bezüglich Deiner Ordnung in etwa als "gleich k" einzustufen sind.

    0
  • K

    Jester schrieb:

    was versagt denn da? Du kriegst alle Elemente, x für die weder x<k noch k<x gilt. Die also bezüglich Deiner Ordnung in etwa als "gleich k" einzustufen sind.

    Eben. 😉 Da kann ich auch gleich 'find' aufrufen.

    0
  • C
    Mod

    Konrad Rudolph schrieb:

    Jester schrieb:

    was versagt denn da? Du kriegst alle Elemente, x für die weder x<k noch k<x gilt. Die also bezüglich Deiner Ordnung in etwa als "gleich k" einzustufen sind.

    Eben. 😉 Da kann ich auch gleich 'find' aufrufen.

    Allerdings mit dem Unterschied, dass du mit lower_bound gleich einen Iterator hast, den du zum Einfügen verwenden kannst, falls das Element fehlt.

    0
  • P

    für map und set ist find und equal_range recht ähnlich, ja, bzw. letzteres erscheint wenig sinnvoll. Das gibts wohl hauptsächlich aus Kompatibilitätsgründen zu multimap/multiset bzw. weils schneller ist (ca. doppelt so schnell) wie wenn man lower_bound(k) und upper_bound(k) per hand aufrufen muss.

    0
  • K

    Okay, vielen Dank. Ich denke, dann ist alles klar. Die Implementierung dieser Funktionen ist ja sowieso trivial.

    Mir zickt nur gerade meine Iterator-Klasse rum. Sieht wohl doch so aus, als müsste ich sie zweimal identisch implementieren: als 'iterator' und 'const_iterator'. Ba.

    0
Anmelden zum Antworten