Find next element in multimap not matching current element Key, How to?

[Victor Bazarov]

What is the neatest way to find the next element in a multimap or
multiset whose key is different from the current element?

E.g., if I have a multi set whose elements are like so:
1.0, 1.0, 1.0, 2.0, 3.0
and I am at the beginning (0th element). How do I get to the 3rd
element?

I suppose I could write a functor that implements the negation of the
multiset's predicate/comparator and call find_if, but I think there
should be a better way (like a member function on the container).

'std::equal_range' returns a pair of iterators. If the second one is
not 'end', it will point to the element that isn't in range. RTFM on
'equal_range'.

HTH

V

 

[Victor Bazarov]

'std::equal_range' returns a pair of iterators. If the second one is
not 'end', it will point to the element that isn't in range. RTFM on
'equal_range'.

Actually, 'std::multimap' has a member called 'equal_range'. Does
basically the same thing. Forget I mentioned the stand-alone function.

V

 

[Anand Hariharan]

What is the neatest way to find the next element in a multimap or
multiset whose key is different from the current element?

E.g., if I have a multi set whose elements are like so:
1.0, 1.0, 1.0, 2.0, 3.0
and I am at the beginning (0th element). How do I get to the 3rd
element?

I suppose I could write a functor that implements the negation of the
multiset's predicate/comparator and call find_if, but I think there
should be a better way (like a member function on the container).

- Anand

 

[Jerry Coffin]

[ ... ]

'std::equal_range' returns a pair of iterators. If the second one
is not 'end', it will point to the element that isn't in range.
RTFM on 'equal_range'.

Since it returns both the lower bound and the upper bound,
equal_range does roughly double the work needed in this case...

 

[Joshua Maurice]

[ ... ]

'std::equal_range' returns a pair of iterators.  If the second one
is not 'end', it will point to the element that isn't in range.
RTFM on 'equal_range'.

Since it returns both the lower bound and the upper bound,
equal_range does roughly double the work needed in this case...

Actually less than 2x if we're being anal. It's guaranteed to
"effectively" perform a lower_bound, then do an upper bound on the
subrange [lower_bound_result, end).

But yeah Anand, use the multimap's member function upper_bound.
cplusplus.com, cppreference.com, and sgi's site are good places to
start for such questions.

 

[Joshua Maurice]

Actually less than 2x if we're being anal. It's guaranteed to
"effectively" perform a lower_bound, then do an upper bound on the
subrange [lower_bound_result, end).

I retract. Clicked the post button early. I'm sorry. Just verified
that there are similar guarantees, but not this guarantee, at least
not in the references I can find. I'd hope at least as QoI that an
implementation would do it that way.

 

[James Kanze]

[ ... ]

'std::equal_range' returns a pair of iterators. If the second one
is not 'end', it will point to the element that isn't in range.
RTFM on 'equal_range'.

Since it returns both the lower bound and the upper bound,
equal_range does roughly double the work needed in this
case...

Does it? I would expect something cleverer, since it's only
when you reach the lower nodes that you need to follow two
different paths.

Anyway, there's also an upper_bound function, which returns an
iterator to the first element for which key < element.

 

[Seungbeom Kim]

What is the neatest way to find the next element in a multimap or
multiset whose key is different from the current element?

E.g., if I have a multi set whose elements are like so:
1.0, 1.0, 1.0, 2.0, 3.0
and I am at the beginning (0th element). How do I get to the 3rd
element?

I suppose I could write a functor that implements the negation of the
multiset's predicate/comparator and call find_if, but I think there
should be a better way (like a member function on the container).

Suppose your container is c of type C, and you have

C::iterator i = c.begin();

then you can use

i = c.upper_bound(i->first);

to advance i to the last position where you can insert the same key
without violating the order, i.e. the position of 2.0 in the above case.

 

[Anand Hariharan]

What is the neatest way to find the next element in a multimap or
multiset whose key is different from the current element?

E.g., if I have a multi set whose elements are like so:
1.0, 1.0, 1.0, 2.0, 3.0
and I am at the beginning (0th element). How do I get to the 3rd
element?

I suppose I could write a functor that implements the negation of the
multiset's predicate/comparator and call find_if, but I think there
should be a better way (like a member function on the container).

- Anand

Seems like multiset::upper_bound does what I want.

- Anand

 

[Mateusz Adamczyk]

E.g., if I have a multi set whose elements are like so:
1.0, 1.0, 1.0, 2.0, 3.0
and I am at the beginning (0th element). How do I get to the 3rd
element?

Take a look at multimap::upper_bound. The lower_bound(k1) and
upper_bound(k1)
give a range [first element with key=k1, first element with key=k2),
where
k2 is the 'smallest' key that: k1 < k2 (in terms of multimap's
predicate).
The multimap::equal_range gives pair of iterators, which is
"logically"
the same as std::make_pair(lower_bound, upper_bound).

Regards,
Mateusz

 

[Jerry Coffin]

(e-mail address removed)>, (e-mail address removed)
says...

[ ... ]

Does it? I would expect something cleverer, since it's only
when you reach the lower nodes that you need to follow two
different paths.

True -- that's why I said "roughly". The reason is fairly simple:
with a tree structure, most of the data is very close to the leaf
nodes. As such, even traversing back up a couple of levels and then
traversing back down a couple of levels to find the next node with a
larger key is still often very close to as much work as traversing
from the base of the tree to the right point. It will usually save a
little, but not nearly as much as might initially seem obvious.

 

[Jerry Coffin]

@c14g2000yqm.googlegroups.com>, (e-mail address removed)
says...

What is the neatest way to find the next element in a multimap or
multiset whose key is different from the current element?

E.g., if I have a multi set whose elements are like so:
1.0, 1.0, 1.0, 2.0, 3.0
and I am at the beginning (0th element). How do I get to the 3rd
element?

I suppose I could write a functor that implements the negation of the
multiset's predicate/comparator and call find_if, but I think there
should be a better way (like a member function on the container).

std::mismatch is intended for that purpose. If you expect to have a
_lot_ of items with identical keys, you might prefer to use
std::upper_bound instead. The difference is that std::mismatch will
do a linear search from the current spot to the first item with a
different key. std::upper_bound will use a binary search instead.

--
Later,
Jerry.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 

[McNepp]

What is the neatest way to find the next element in a multimap or
multiset whose key is different from the current element?

E.g., if I have a multi set whose elements are like so:
1.0, 1.0, 1.0, 2.0, 3.0
and I am at the beginning (0th element). How do I get to the 3rd
element?

multiset's member function "upper_bound(1.0)" will do the trick.

 

[Seungbeom Kim]

@c14g2000yqm.googlegroups.com>, (e-mail address removed)
says...

std::mismatch is intended for that purpose.

std::mismatch takes two ranges. What are they in this case?

 

[Jerry Coffin]

std::mismatch takes two ranges. What are they in this case?

Thinking about things a bit more, mismatch() is definitely _not_ the
right algorithm to use. My apologies for mistakenly suggesting it.

--
Later,
Jerry.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 

[Vaclav Haisman]

Anand Hariharan wrote, On 11.8.2009 20:24:

What is the neatest way to find the next element in a multimap or
multiset whose key is different from the current element?

E.g., if I have a multi set whose elements are like so:
1.0, 1.0, 1.0, 2.0, 3.0
and I am at the beginning (0th element). How do I get to the 3rd
element?

I suppose I could write a functor that implements the negation of the
multiset's predicate/comparator and call find_if, but I think there
should be a better way (like a member function on the container).

You can get the whole range at once by using equal_range() member function.
If you already have the lower bound then using .upper_bound() is what you want.