Is there an STL algorithm for this?

[Mark P]

I'm working with a std::multiset and I want to efficiently select a
(continuous) range of elements in the set. What I know is that the
desired range is exactly those elements which compare equal to any of 3
"test elements" which I can easily construct (but which are not in the
multiset).

What makes this somewhat tricky is that if, say, no element compares
equal to the smallest test element, then there may be other subsequent
elements in the set (greater than the smallest test element and less
than the middle test element) which I do not want. So I can't just use
a lower_bound with the smallest test element and an upper_bound with the
largest test element. However, if there are elements in the set that
compare equal to one or more test elements, then I can be certain that
there are no intervening unwanted elements.

Presently I accomplish this by using equal_range for each test element,
and combining all non-empty output ranges. But this fails to exploit
the fact that all non-empty ranges must be consecutive. Is there an
algorithm in the STL which could make this more efficient?

If you're wondering, this is related to a scanline algorithm in
computational geometry.

Thanks for your help,
Mark

 

[Robert W Hand]

I'm working with a std::multiset and I want to efficiently select a
(continuous) range of elements in the set. What I know is that the
desired range is exactly those elements which compare equal to any of 3
"test elements" which I can easily construct (but which are not in the
multiset).

What makes this somewhat tricky is that if, say, no element compares
equal to the smallest test element, then there may be other subsequent
elements in the set (greater than the smallest test element and less
than the middle test element) which I do not want. So I can't just use
a lower_bound with the smallest test element and an upper_bound with the
largest test element. However, if there are elements in the set that
compare equal to one or more test elements, then I can be certain that
there are no intervening unwanted elements.

Presently I accomplish this by using equal_range for each test element,
and combining all non-empty output ranges. But this fails to exploit
the fact that all non-empty ranges must be consecutive. Is there an
algorithm in the STL which could make this more efficient?

equal_range() is defined in terms of upper_bound() and lower_bound().

I'm at a loss to see how three unequal test elements are guaranteed to
make all non-empty ranges consecutive. Consider these integers in a
multiset:

{1, 3, 4, 4, 5, 5, 7, 9, 9, 9, 10}.

equal_range(2) returns the iterator pair (3, 3). equal_range(5)
returns iterator pair (5, 6), and equal_range(9) returns iterator pair
(9, 10). The first range is empty. The second contains the two 5's
and the third contains the three 9's. This behavior depends on the
test elements and the structure of the set. Can you place the ranges
into a new multi-set or where do you put them - the original
multi-set?

 

[Chris Theis]

I'm working with a std::multiset and I want to efficiently select a
(continuous) range of elements in the set. What I know is that the
desired range is exactly those elements which compare equal to any of 3
"test elements" which I can easily construct (but which are not in the
multiset).

What makes this somewhat tricky is that if, say, no element compares
equal to the smallest test element, then there may be other subsequent
elements in the set (greater than the smallest test element and less
than the middle test element) which I do not want. So I can't just use
a lower_bound with the smallest test element and an upper_bound with the
largest test element. However, if there are elements in the set that
compare equal to one or more test elements, then I can be certain that
there are no intervening unwanted elements.

Presently I accomplish this by using equal_range for each test element,
and combining all non-empty output ranges. But this fails to exploit
the fact that all non-empty ranges must be consecutive. Is there an
algorithm in the STL which could make this more efficient?

[SNIP]

Associative containers like set/multiset provide the function equal_range as
a member function because they are optimized versions of the generic
implementations. They actually make use of the fact that the elements are
already sorted, and thus in consecutive order.

Cheers
Chris

 

[Mark P]

equal_range() is defined in terms of upper_bound() and lower_bound().

I'm at a loss to see how three unequal test elements are guaranteed to
make all non-empty ranges consecutive. Consider these integers in a
multiset:

Of course you're correct that this is not true in general. This is a
particular feature, invariant if you like, of the data I'm working with.

{1, 3, 4, 4, 5, 5, 7, 9, 9, 9, 10}.

equal_range(2) returns the iterator pair (3, 3). equal_range(5)
returns iterator pair (5, 6), and equal_range(9) returns iterator pair
(9, 10). The first range is empty. The second contains the two 5's
and the third contains the three 9's. This behavior depends on the
test elements and the structure of the set. Can you place the ranges
into a new multi-set or where do you put them - the original
multi-set?

Nothing is done with the range at this point. I simply seek a pair of
iterators that delimit the range.

Thanks,
Mark