no upper_bound() for unordered_multimap

Discussion in 'C++' started by Ralf Goertz, Oct 18, 2010.

  1. Ralf Goertz

    Ralf Goertz Guest

    Hi,

    why is there no upper_bound() (or lower_bound()) for unordered_multimap
    like there is for normal multimap? I think this is odd since there is
    equal_range() for unordered_multimap and the interators in the returned
    pair is what I would lower_bound() and upper_bound() expect to return.

    BTW, what iterator is returned by multimap::find()? Is it
    multimap::lower_bound() or is it not specified? What about
    unordered_multimap::find()?

    Thanks,

    Ralf
    Ralf Goertz, Oct 18, 2010
    #1
    1. Advertising

  2. Ralf Goertz

    SG Guest

    On 18 Okt., 14:38, Pete Becker <> wrote:
    > On 2010-10-18 07:52:33 -0400, Ralf Goertz said:
    >
    > > Hi,

    >
    > > why is there no upper_bound() (or lower_bound()) for unordered_multimap
    > > like there is for normal multimap? I think this is odd since there is
    > > equal_range() for unordered_multimap and the interators in the returned
    > > pair is what I would lower_bound() and upper_bound() expect to return.

    >
    > As the name suggests, unordered_multimap isn't required to store its
    > elements in any particular order. This makes upper_bount and
    > lower_bound much more expensive than they are for multimap. The
    > expensive versions are, however, available in namespace std through the
    > <algorithms> header.


    But std::upper_bound expects iterators referring to an ordered
    sequence which -- as you pointed out already -- unordered_multimap
    does /not/ provide. So, std::upper_bound cannot be used with iterators
    from an unordered_multimap.
    SG, Oct 18, 2010
    #2
    1. Advertising

  3. Ralf Goertz

    Ralf Goertz Guest

    Pete Becker wrote:

    > On 2010-10-18 07:52:33 -0400, Ralf Goertz said:
    >
    >> Hi,
    >>
    >> why is there no upper_bound() (or lower_bound()) for unordered_multimap
    >> like there is for normal multimap? I think this is odd since there is
    >> equal_range() for unordered_multimap and the interators in the returned
    >> pair is what I would lower_bound() and upper_bound() expect to return.

    >
    > As the name suggests, unordered_multimap isn't required to store its
    > elements in any particular order. This makes upper_bount and
    > lower_bound much more expensive than they are for multimap.


    Hm, pairs with equal keys must be contiguously stored also in an
    unordered map so that when you start with m.equal_range(key).first and
    increment it until you reach m.equal_range(key).second you have visited
    *all* elements with key "key" and *no* *other*. At least that is my
    understanding. Why then should it be much more expensive to find the
    upper bound? You only need to find an appropriate element's iterator and
    increment it until you get an iterator which points to an element with a
    different key. So this shouldn't be more expensive then traversing the
    map, right?


    > The expensive versions are, however, available in namespace std
    > through the <algorithms> header.


    Could you tell me how to use them? I thought std::upper_bound only works
    for ordered containers?
    Ralf Goertz, Oct 18, 2010
    #3
  4. Ralf Goertz

    SG Guest

    On 18 Okt., 15:20, Ralf Goertz wrote:
    >
    > Hm, pairs with equal keys must be contiguously stored also in an
    > unordered map so that when you start with m.equal_range(key).first and
    > increment it until you reach m.equal_range(key).second you have visited
    > *all* elements with key "key" and *no* *other*. At least that is my
    > understanding. Why then should it be much more expensive to find the
    > upper bound?


    Equal keys are stored adjacently but other than that there is no
    order. So, from what I can tell, an upper_bound function doesn't
    really make any sense in this case. Suppose an
    unordered_multimap<int,something> contains the following keys in that
    order:

    4 4 1 8 7 7 5 3

    What iterator is upper_bound(7) supposed to return? I have no idea.
    Tell me.

    Cheers!
    SG
    SG, Oct 18, 2010
    #4
  5. Ralf Goertz

    Ralf Goertz Guest

    Pete Becker wrote:

    > On 2010-10-18 09:20:47 -0400, Ralf Goertz said:
    >
    >> Pete Becker wrote:
    >>
    >>> On 2010-10-18 07:52:33 -0400, Ralf Goertz said:
    >>>
    >>>> Hi,
    >>>>
    >>>> why is there no upper_bound() (or lower_bound()) for unordered_multimap
    >>>> like there is for normal multimap? I think this is odd since there is
    >>>> equal_range() for unordered_multimap and the interators in the returned
    >>>> pair is what I would lower_bound() and upper_bound() expect to return.
    >>>
    >>> As the name suggests, unordered_multimap isn't required to store its
    >>> elements in any particular order. This makes upper_bount and
    >>> lower_bound much more expensive than they are for multimap.

    >>
    >> Hm, pairs with equal keys must be contiguously stored also in an
    >> unordered map so that when you start with m.equal_range(key).first and
    >> increment it until you reach m.equal_range(key).second you have visited
    >> *all* elements with key "key" and *no* *other*. At least that is my
    >> understanding. Why then should it be much more expensive to find the
    >> upper bound? You only need to find an appropriate element's iterator and
    >> increment it until you get an iterator which points to an element with a
    >> different key. So this shouldn't be more expensive then traversing the
    >> map, right?

    >
    > upper_bound gives you an iterator that guarantees that every element
    > that comes before the key is in front of that iterator. While that can
    > be done, for an unsorted sequence it's not particularly useful:
    >
    > { 1, 4, 3, 2 };
    >
    > What should upper_bound return for a key of 3? Yes, it could return an
    > iterator pointing to the first element, but what can you sensibly do
    > with that iterator?


    It should return the iterator that comes after the iterator for "3".
    That is the iterator that I get when I traverse the whole unordered
    multimap. I think that is the one I get with equal_range(3).second. As I
    said in my OP I don't see why there is equal_range() for
    unordered_multimap but no upper/lower_bound().

    As to why I need upper bound: I use equal_range to visit all elements in
    a multithreaded program. There will be no inserts into the
    unordered_multimap (which could invalidate iterators) during the
    multithreading. There are only erases. And that is the problem. I can't
    be sure that the upper_bound-element still exists. Another thread might
    have erased the element. That's why I want to check if my just
    incremented iterator is equal to the upper_bound for that key. Maybe this
    example explains it:

    typedef unordered_multimap<int,int> UM;
    UM m;
    //m is filled and then multithreading begins
    pair<UM::iterator,UM::iterator> itp=m.equal_range(thread_specifik key);
    for(;itp.first!=itp.second;++itp.first) // does itp.second still exist?
    {
    //possibly erase(itp.first)
    }
    Ralf Goertz, Oct 18, 2010
    #5
  6. Ralf Goertz

    SG Guest

    On 18 Okt., 18:33, Pete Becker wrote:
    >
    > [...] Rephrasing what I said earlier, [upper_bound] returns
    > an iterator that points to the first element for which every
    > preceding value is less than or equal to the target key.


    That doesn't sound right. You probably meant to say "that points to
    the /last/ element for which...". Also, this doesn't cover the case
    where the returned iterator equals the second parameter (which doesn't
    necessarily point to anything).

    Looking at a very early C++0x draft which contains almost no C++0x
    feature (N1804.pdf):

    std::upper_bound(first,last,value,comp)

    returns the furthermost iterator i in the range [first,last) such
    that for any iterator j in the range [first,i) the following
    corresponding conditions hold: !(value<*j) or comp(value,*j)==false.

    But even this definition contains a bug. It rules out i==last which I
    think is not intentional. So, it should be "...furthermost iterator i
    in the range [first,last] such that..." (including last).

    So, on my example, 4 4 1 8 7 7 5 3, upper_bound(7), this could return
    an iterator pointing to the element with the key 8. That is, ignoring
    the requirement for ordered sequences...

    Cheers!
    SG
    SG, Oct 18, 2010
    #6
  7. SG <> wrote:
    > On 18 Okt., 18:33, Pete Becker wrote:
    >>
    >> [...] Rephrasing what I said earlier, [upper_bound] returns
    >> an iterator that points to the first element for which every
    >> preceding value is less than or equal to the target key.

    >
    > That doesn't sound right. You probably meant to say "that points to
    > the /last/ element for which...". Also, this doesn't cover the case
    > where the returned iterator equals the second parameter (which doesn't
    > necessarily point to anything).


    Both are wrong. upper_bound() returns an iterator to the first element
    that is greater than the value. (In other words, even if the searched
    element exists in the search range, the returned iterator won't point
    to it; it will point to the next value that is greater than it.)

    The reasoning is simple: upper_bound() returns an "end()" iterator
    to the range of equal values in the (ordered) container. In other words,
    "one past" the last equal value. Togetether with lower_bound() you can
    get the range of equal values (in the same way as equal_range()).

    Another property of both lower_bound() and upper_bound() is that if
    you insert the searched value at the iterator position returned by
    either function, the container will remain ordered. The difference is
    that in the first case the element will be inserted as the first element
    in the range of equal elements, while in the last case it will be
    inserted as the last one.
    Juha Nieminen, Oct 18, 2010
    #7
  8. Ralf Goertz

    SG Guest

    On 18 Okt., 19:16, Juha Nieminen wrote:
    > SG <> wrote:
    > > On 18 Okt., 18:33, Pete Becker wrote:

    >
    > >> [...] Rephrasing what I said earlier, [upper_bound] returns
    > >> an iterator that points to the first element for which every
    > >> preceding value is less than or equal to the target key.

    >
    > > That doesn't sound right. You probably meant to say "that points to
    > > the /last/ element for which...". Also, this doesn't cover the case
    > > where the returned iterator equals the second parameter (which doesn't
    > > necessarily point to anything).

    >
    >   Both are wrong. upper_bound() returns an iterator to the first element
    > that is greater than the value. (In other words, even if the searched
    > element exists in the search range, the returned iterator won't point
    > to it; it will point to the next value that is greater than it.)


    Your wording isn't any better. It suffers from the same problem I
    already pointed out in the above paragraph. Why you snipped my quote
    from the standard library is beyond me... Here is it again, just for
    your enjoyement. I took the liberty to fix the other issue I pointed
    out earlier:

    std::upper_bound(first,last,value[,comp])

    returns the furthermost iterator i in the range [first,last] such
    that for any iterator j in the range [first,i) the following
    corresponding conditions hold: !(value<*j) or !comp(value,*j).

    The closing ] for the first range is intentional, btw.

    Cheers!
    SG
    SG, Oct 18, 2010
    #8
  9. Ralf Goertz

    Ralf Goertz Guest

    Pete Becker wrote:

    > On 2010-10-18 11:45:49 -0400, Ralf Goertz said:
    >
    >> Pete Becker wrote:
    >>
    >>> What should upper_bound return for a key of 3? Yes, it could return
    >>> an iterator pointing to the first element, but what can you sensibly
    >>> do with that iterator?

    >>
    >> It should return the iterator that comes after the iterator for "3".
    >> That is the iterator that I get when I traverse the whole unordered
    >> multimap.

    >
    > That's a different definition of upper_bound than the current one,


    I know that upper_bound might be a misleading name, it is just
    convenient to have an interface to unordered_multimap that is as similar
    to multimap as possible. In fact the problem arose when I changed a
    multimap to unordered_multimap in a working program. I am not
    particularly interested in the iterator ub returned by upper_bound. I
    just use it to make sure I haven't left the equal_range. Therefore I
    don't care whether the key of ub is greater or less than the key I am
    currently working on. I just want ub to be the same iterator that comes
    *after* the last interesting iterator so that comparison i!=ub returns
    false.

    >>
    >> typedef unordered_multimap<int,int> UM;
    >> UM m;
    >> //m is filled and then multithreading begins
    >> pair<UM::iterator,UM::iterator> itp=m.equal_range(thread_specifik key);
    >> for(;itp.first!=itp.second;++itp.first) // does itp.second still exist?
    >> {
    >> //possibly erase(itp.first)
    >> }

    >
    > Even if you could use upper_bound to get the value you want, this code
    > formally has data races. Erasing from the container in one thread while
    > another thread is incrementing an iterator into the same container is a
    > data race, and results in undefined behavior. For example, suppose one
    > thread is inside the call to equal_range, and happens to hold an
    > iterator to element X when a context switch occurs, and the new thread
    > erases element X; now there's serious trouble.


    I know that. That's why (using OMP for multithreading) every change of
    the map is guarded by a

    #pragma omp critical

    directive.
    Ralf Goertz, Oct 19, 2010
    #9
  10. Ralf Goertz

    Ralf Goertz Guest

    Pete Becker wrote:

    > On 2010-10-18 11:45:49 -0400, Ralf Goertz said:
    >
    >>
    >> typedef unordered_multimap<int,int> UM;
    >> UM m;
    >> //m is filled and then multithreading begins
    >> pair<UM::iterator,UM::iterator> itp=m.equal_range(thread_specifik key);
    >> for(;itp.first!=itp.second;++itp.first) // does itp.second still exist?
    >> {
    >> //possibly erase(itp.first)
    >> }

    >
    > Seems to me that the solution is one less level of abstraction:
    >
    > UM::iterator current = m.lower_bound(key);
    > while (current->first == key)
    > {
    > UM::iterator temp = current++;
    > maybe_delete(temp);
    > }


    Yes, I came up with the same solution this morning, thanks.

    Would you be so nice and comment on my second question in the OP: Is it
    specified which iterator (if there are more than one) is returned by
    find(key) for (unordered)_multimaps? Is it the same as lower_bound()?

    Ralf
    Ralf Goertz, Oct 19, 2010
    #10
  11. Ralf Goertz

    Joe Gottman Guest

    On 10/19/2010 9:53 AM, Pete Becker wrote:
    > On 2010-10-18 11:45:49 -0400, Ralf Goertz said:
    >
    >>
    >> typedef unordered_multimap<int,int> UM;
    >> UM m;
    >> //m is filled and then multithreading begins
    >> pair<UM::iterator,UM::iterator> itp=m.equal_range(thread_specifik key);
    >> for(;itp.first!=itp.second;++itp.first) // does itp.second still exist?
    >> {
    >> //possibly erase(itp.first)
    >> }

    >
    > Seems to me that the solution is one less level of abstraction:
    >
    > UM::iterator current = m.lower_bound(key);
    > while (current->first == key)
    > {
    > UM::iterator temp = current++;
    > maybe_delete(temp);
    > }
    >


    Actually, the unordered containers don't provide lower_bound either.
    They just provide equal_range, I assume on the logic that you need
    both lower_bound and upper_bound to do any useful work.

    Joe Gottman
    Joe Gottman, Oct 20, 2010
    #11
    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,301
    Erik Arner
    Nov 2, 2004
  2. upper_bound

    , Feb 15, 2006, in forum: C++
    Replies:
    2
    Views:
    381
  3. asdf

    std::set::upper_bound

    asdf, Apr 12, 2006, in forum: C++
    Replies:
    3
    Views:
    361
    Mark P
    Apr 13, 2006
  4. asdf

    std::set::upper_bound

    asdf, Apr 12, 2006, in forum: C++
    Replies:
    0
    Views:
    283
  5. Ralf Goertz

    g++ unordered_multimap buggy?

    Ralf Goertz, May 13, 2011, in forum: C++
    Replies:
    8
    Views:
    820
    Ruben Safir
    Jun 9, 2011
Loading...

Share This Page