Is this a bug?

[Jonathan Wakely]

On Sun, Apr 13, 2003 at 07:23:27PM -0700, S. Loisel wrote:

> The following code
> 
> #include <map>
> #include <stdio.h>
> 
> int main()
> {
>  std::map<int,int, std::less<int> > foo;
>  foo[0]=0;
>  foo[2]=2;
>  printf("%i %i\n",(*foo.lower_bound(1)).first,
>     (*foo.upper_bound(1)).first);
>  return 0;
> }
> 
> produces this:
> 
> $ g++ bug.C -o bug
> $ ./bug
> 2 2
> 
> What am I misunderstanding?

The semantics of map::lower_bound() and map::upper_bound(), I believe.

Conceptually...
Both functions find the position at which the argument could be inserted
without changing the ordering. One finds the earliest position, one the
latest, but they're the same in this case as the interval between the 0
and 2 keys is empty, so the upper and lower bounds of the interval are
at the same place.
This empty range is described by two equal iterators that point just past
the end of the range, i.e. at the element with key 2.
c.f. http://gcc.gnu.org/onlinedocs/libstdc++/24_iterators/howto.html#2

Technically...
map::lower_bound(n) returns an iterator to the first element X for which
map::key_comp()(X.first, n) is false. In your case this boils down to
the first element X for which (X.first < 1) is false.
0 < 1 is true, 2 < 1 is false, therefore an iterator pointing to the
second element is returned.

map::upper_bound(n) returns an iterator to the first element X for which
map::key_comp()(n, X.first) is _true_.
1 < 0 is false, 1 < 2 is true, therefore an iterator pointing to the
second element is returned.

Hope that helps,

jon

-- 
"There are books in which the footnotes, or the comments scrawled by some 
 reader's hand in the margin, are more interesting than the text. The world 
 is one of those books."
	- George Santayana