lower_bound - close, but no cigar

[Jaap]

Hi all,

I'm looking for functionality very similar to std::map::lower_bound:
I'd like to find the first element whose key is equal to or smaller
than the key I pass.

In a map filled like this:

map[10] = 10;
map[20] = 20;
map[30] = 30;

foo being a function yielding an iterator to an element from map, I'd
like foo to do the following:

foo(map, 10)->first == 10
foo(map, 15)->first == 10
foo(map, 22)->first == 20

Obviously, I'd like foo() to have performance similar to lower_bound,
if at all possible.

Does anyone here know of such a beast ?

Thanks a lot,

JJ

 

[Shezan Baig]

Hi all,

I'm looking for functionality very similar to std::map::lower_bound:
I'd like to find the first element whose key is equal to or smaller
than the key I pass.

In a map filled like this:

map[10] = 10;
map[20] = 20;
map[30] = 30;

foo being a function yielding an iterator to an element from map, I'd
like foo to do the following:

foo(map, 10)->first == 10
foo(map, 15)->first == 10
foo(map, 22)->first == 20

Obviously, I'd like foo() to have performance similar to lower_bound,
if at all possible.

Does anyone here know of such a beast ?

Thanks a lot,

JJ

How about calling lower_bound and doing a '--' on the iterator if the
keys are different.

Hope this helps,
-shez-

 

[Andrew Koenig]

I'm looking for functionality very similar to std::map::lower_bound:
I'd like to find the first element whose key is equal to or smaller
than the key I pass.

I doubt it. If such an element exists, it will always be the first element
in the map.

Could you mean the *last* element with a key equal to or smaller than a
given key? If so, that's the element (if any) immediately before the
*first* element with a key strictly greater than the given key. That
element, in turn, is what upper_bound returns.

So you could do this:

Call upper_bound.
If the result is equal to the result of begin, the key you seek does not
exist.
Otherwise decrement the result of upper_bound, and you're done.

If that's not what you want, you'll have to be more precise about what you
want.

 

[Jaap]

I doubt it. If such an element exists, it will always be the first element
in the map.

Could you mean the *last* element with a key equal to or smaller than a
given key? If so, that's the element (if any) immediately before the
*first* element with a key strictly greater than the given key. That
element, in turn, is what upper_bound returns.

So you could do this:

Call upper_bound.
If the result is equal to the result of begin, the key you seek does not
exist.
Otherwise decrement the result of upper_bound, and you're done.

If that's not what you want, you'll have to be more precise about what you
want.

Of course you are right, I do want the last element with a key smaller
than or equal to my key. I've even read through my post three times
before sending it, and still managed to screw it up...

Thanks a lot !

JJ