stl map, lower_bound and upper_bound

Discussion in 'C++' started by Diego Martins, Aug 14, 2006.

  1. Andrew Koenig wrote:
    > "Fred Zwarts" <> wrote in message
    > news:e27bop$62n$...


    > > 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.


    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
     
    Diego Martins, Aug 14, 2006
    #1
    1. Advertising

  2. Diego Martins

    Mark P Guest

    Diego Martins wrote:
    > Andrew Koenig wrote:
    >> "Fred Zwarts" <> wrote in message
    >> news:e27bop$62n$...

    >
    >>> 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.

    >
    > 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.
     
    Mark P, Aug 14, 2006
    #2
    1. Advertising

  3. Diego Martins

    Jerry Coffin Guest

    In article <>,
    says...

    [ ... ]

    > 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.
     
    Jerry Coffin, Aug 14, 2006
    #3
  4. Jerry Coffin wrote:
    > In article <>,
    > says...
    >
    > [ ... ]
    >
    > > 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
     
    Diego Martins, Aug 15, 2006
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Erik Arner
    Replies:
    0
    Views:
    1,330
    Erik Arner
    Nov 2, 2004
  2. Fred Zwarts
    Replies:
    5
    Views:
    1,562
    Andrew Koenig
    Apr 23, 2006
  3. Replies:
    3
    Views:
    400
  4. Henrik Goldman

    Problem with map upper_bound

    Henrik Goldman, Jul 5, 2007, in forum: C++
    Replies:
    3
    Views:
    393
    James Kanze
    Jul 6, 2007
  5. Replies:
    3
    Views:
    1,024
    Andrew Koenig
    Apr 7, 2008
Loading...

Share This Page