stl map, lower_bound and upper_bound

[Fred Zwarts]

I have an application which uses maps.
I need to find elements in the map, without knowing the exact key value.
I thought I could use the lower_bound, or upper_bound function for this purpose.
However, after searching the internet and after some experiments with a few compilers
I am completely confused.
I find several contradictory descriptions of these functions. Also the results from test
programs are not clear to me.
So, maybe someone can help me, with the following example.
Suppose I have a map with keys of type int.
This map is populated with three elements, with key values 1, 3 and 7.
Which values should be returned by lower_bound and upper_bound when these are called
with parameter values 0, 1, 2, 3, 4, 5, 6, 7, 8?
Can someone fill in this table:

Parameter value 0 1 2 3 4 5 6 7 8
result of lower_bound
result of upper_bound

Thanks,
Fred.Zwarts.

 

[Peter Jansson]

I have an application which uses maps.
I need to find elements in the map, without knowing the exact key value.
I thought I could use the lower_bound, or upper_bound function for this purpose.
However, after searching the internet and after some experiments with a few compilers
I am completely confused.
I find several contradictory descriptions of these functions. Also the

results from test programs are not clear to me.

So, maybe someone can help me, with the following example.
Suppose I have a map with keys of type int.
This map is populated with three elements, with key values 1, 3 and 7.

Are you sure it is a std::map you want to use and not a std::set?
A map is a map between key<->value pairs.
A set is just a set of (unique) keys.

Regards,

Peter Jansson
http://www.p-jansson.com/
http://www.jansson.net/

 

[mlody277]

Hello,
Look at this page
http://www.sgi.com/tech/stl/upper_bound.html#1

 

[Rolf Magnus]

I have an application which uses maps.
I need to find elements in the map, without knowing the exact key value.
I thought I could use the lower_bound, or upper_bound function for this
purpose.

They are not designed for that.

However, after searching the internet and after some experiments
with a few compilers I am completely confused.

lower_bound gives you the first element with the specified key. If there is
none, the first element with a key greater than the specified one is
returned. If there is none of those either, the 'last' argument is
returned.
upper_bound gives you the first element that has a key greater than the one
you specified or 'last' if none is found.

I find several contradictory descriptions of these functions. Also the
results from test programs are not clear to me.
So, maybe someone can help me, with the following example.
Suppose I have a map with keys of type int.
This map is populated with three elements, with key values 1, 3 and 7.
Which values should be returned by lower_bound and upper_bound when these
are called with parameter values 0, 1, 2, 3, 4, 5, 6, 7, 8?
Can someone fill in this table:

Parameter value 0 1 2 3 4 5 6 7 8
result of lower_bound 1 1 3 3 7 7 7 7 last
result of upper_bound 3 3 3 7 7 7 7 last last

 

[Rolf Magnus]

I have an application which uses maps.
I need to find elements in the map, without knowing the exact key value.
I thought I could use the lower_bound, or upper_bound function for this
purpose.

They are not designed for that.

However, after searching the internet and after some experiments
with a few compilers I am completely confused.

lower_bound gives you the first element with the specified key. If there is
none, the first element with a key greater than the specified one is
returned. If there is none of those either, end() is returned.
upper_bound gives you the first element that has a key greater than the one
you specified or end() if none is found.

I find several contradictory descriptions of these functions. Also the
results from test programs are not clear to me.
So, maybe someone can help me, with the following example.
Suppose I have a map with keys of type int.
This map is populated with three elements, with key values 1, 3 and 7.
Which values should be returned by lower_bound and upper_bound when these
are called with parameter values 0, 1, 2, 3, 4, 5, 6, 7, 8?
Can someone fill in this table:

Parameter value 0 1 2 3 4 5 6 7 8
result of lower_bound 1 1 3 3 7 7 7 7 end()
result of upper_bound 3 3 3 7 7 7 7 end() end()

 

[Andrew Koenig]

I have an application which uses maps.
I need to find elements in the map, without knowing the exact key value.
I thought I could use the lower_bound, or upper_bound function for this
purpose.
However, after searching the internet and after some experiments with a
few compilers
I am completely confused.
I find several contradictory descriptions of these functions. Also the
results from test
programs are not clear to me.
So, maybe someone can help me, with the following example.

I don't think your example will help you solve your problem.

Here's a capsule summary of what happens.

If the element you seek is in the container, then lower_bound returns an
iterator that refers to that element, and upper_bound returns an iterator
that refers to the next element (or one past the end if there is no such
element).

If the element is not in the container, then lower_bound and upper_bound
both return the same value, namely an iterator referring to the first
element *after* the one you seek (or one past the end if there is no such
element).

So if the map keys are strings, and you know the first few characters of the
string, you could use lower_bound to look for the given key.

If the result is one past the end of the container, you know that no element
begins with your key. Otherwise, the iterator gives you a place to start
looking.

For example, if your key is "foo", lower_bound will return the first element
that starts with "foo", if such an element exists. If not, it will return
either the first element that is > "foo" or one past the end if no such
element exists.