On Thu, 24 Mar 2005 02:01:06 GMT, Mark P <no*@my.real.email> wrote:

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?

--

Best wishes,

Bob