I am trying to familiarize myself with maps in C++, and I am also trying to understand some basic operations that can be used on them. The only two I do not understand, however, are lower_bound(), and upper_bound(). I have looked them up multiple times but do not understand what they are doing. Can somebody please clarify this?
2 Answers
Lower bound and upper bound are probably easier to understand as equal_range.
equal_range returns a pair of iterators which, when treated as a half-open interval, are the values that are equivalent (under <) to the key you passed in.
Once you grasp that, lower_bound returns the first "starting" iterator of equal_range and upper_bound returns the last "one past the end" ending iterator of equal_range.
Specifying them directly leads to the awkward reading you are probably confused by: "the first element not less than" etc. Nobody in their right mind thinks of them that way, except in narrow circumstances.
answered Sep 21, 2018 at 0:03
Yakk - Adam Nevraumont
280k31 gold badges367 silver badges585 bronze badges
Comments
To understand lower_bound/upper_bound you have to remember that a map isn't just a container that maps keys to values, but, like a real-world vocabulary, it also enforces that elements are sorted by key, so you can be interested not only in finding a specific item, but in quickly locating the "surroundings" of some key that may not actually be present.
Imagine you have a map<string, T>, which maps dictionary words to something else. If you want a prefix match (say, all words starting with "dange"), use lower_bound, which will return you the first item greater or equal to the given value; all words starting with that prefix, compared lexicographically, will satisfy this criterion (so you may get an iterator pointing to "danger"). You can now iterate forward as long as the prefix matches ("danger", "dangerous", ...).
Another example: you have a map from a timestamp to events, and you want to look up what happened between two timestamps. You can use lower_bound to locate the first element >= than the initial timestamp, even if such timestamp doesn't actually correspond to any stored event (so find won't do), and then go forward as long as you are in the range of your interest.
Similar examples can be done with upper_bound - although honestly I think I use it way more rarely.
3 Comments
Amir
This is actually not accurate. lower_bound in contrast to its use of wording, doesn't give you the largest key that is smaller than the current key. It's actually a bummer, as that's a very useful feature. But it's not doing that.
Matteo Italia
@Amir: while what you say is true (and what you describe is often a useful operation I've often implemented myself, based on
lower_bound), I re-read my answer several times, and I don't see where I said that lower_bound returns the largest key smaller than the requested one, I think I always said that it returns the first key >=... Could you point exactly to where I wrote the incorrect wording? BTW for the upper/lower bound terminology, it's actually coherent with the general usage of [, ) intervals in C++.Amir
You're correct. I think I might have misunderstood some of the points you mentioned when I was quickly reading it. You correctly mentioned that lower_bound will give the value equal to or larger than the key we're searching for.
std::lower_bound, but forstd::map. the doc from algorithm gives some example.