stl map, lower_bound and upper_bound

[Diego Martins]

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.

In your example, lower_bound(beg,end,"foo") will return an iterator
pointing to the first element starting with "foo". Can anyone give me
some advice how to use lower_bound() or upper_bound() to return an
iterator pointing to the next element after the ones started with "foo"
?

Diego Martins

 

[Mark P]

In your example, lower_bound(beg,end,"foo") will return an iterator
pointing to the first element starting with "foo". Can anyone give me
some advice how to use lower_bound() or upper_bound() to return an
iterator pointing to the next element after the ones started with "foo"
?

First of all, if you're using a map you should be using the map member
functions lower_bound and upper_bound, not the template functions
defined in <algorithm>.

As to your question, I think Andrew pretty much said all that can be
said on the subject: upper_bound("foo") will return an iterator one past
the last occurrence of "foo", if any. Otherwise it will return an
iterator one past where, loosely speaking, "foo" would have been (see
Andrew's last paragraph for the precise definition). In any event, be
aware the the returned iterator may be one past the end so you must
check this before dereferencing it.

 

[Jerry Coffin]

[ ... ]

In your example, lower_bound(beg,end,"foo") will return an iterator
pointing to the first element starting with "foo". Can anyone give me
some advice how to use lower_bound() or upper_bound() to return an
iterator pointing to the next element after the ones started with "foo"
?

That's that upper_bound will normally give you. Remember that the norm
with iterators is that the lower bound points AT the first item in a
sequence, and the upper bound points one BEYOND the end of the sequence.
Therefore, upper_bound returns an iterator to the first item after the
end of all the items that match what you ask for.

 

[Diego Martins]

[ ... ]

In your example, lower_bound(beg,end,"foo") will return an iterator
pointing to the first element starting with "foo". Can anyone give me
some advice how to use lower_bound() or upper_bound() to return an
iterator pointing to the next element after the ones started with "foo"
?

That's that upper_bound will normally give you. Remember that the norm
with iterators is that the lower bound points AT the first item in a
sequence, and the upper bound points one BEYOND the end of the sequence.
Therefore, upper_bound returns an iterator to the first item after the
end of all the items that match what you ask for.

--
Later,
Jerry.

The universe is a figment of its own imagination.

I disagree. lower_bound() and upper_bound() will return the same
iterator if "foo" is not in the container

Try this in your updated compiler:

{
using namespace std;
map<string,int> m;
m["a"] = 1;
m["foo1"] = 2;
m["foo2"] = 20;
m["foo333"] = -783;
m["zombie"] = 0;

assert(m.lower_bound("foo") == m.upper_bound("foo"));
assert(m.lower_bound("foo")->first == "foo1");
assert(m.upper_bound("foo")->first == "foo1");
}

Can you see now? :-(

lower_bound() is doing fine for my purposes
but what I really need is a function that returns an iterator pointing
to m["zombie"]


Diego Martins
HP