446,389 Members | 1,844 Online
Need help? Post your question and get tips & solutions from a community of 446,389 IT Pros & Developers. It's quick & easy.

# Is there an STL algorithm for this?

 P: n/a 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 Jul 23 '05 #1
3 Replies

 P: n/a On Thu, 24 Mar 2005 02:01:06 GMT, Mark P 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 thedesired range is exactly those elements which compare equal to any of 3"test elements" which I can easily construct (but which are not in themultiset).What makes this somewhat tricky is that if, say, no element comparesequal to the smallest test element, then there may be other subsequentelements in the set (greater than the smallest test element and lessthan the middle test element) which I do not want. So I can't just usea lower_bound with the smallest test element and an upper_bound with thelargest test element. However, if there are elements in the set thatcompare equal to one or more test elements, then I can be certain thatthere 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 exploitthe fact that all non-empty ranges must be consecutive. Is there analgorithm 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 Jul 23 '05 #2

 P: n/a "Mark P" wrote in message news:Cb**************@newssvr13.news.prodigy.com.. . 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 Jul 23 '05 #3

 P: n/a Robert W Hand wrote: On Thu, 24 Mar 2005 02:01:06 GMT, Mark P 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 thedesired range is exactly those elements which compare equal to any of 3"test elements" which I can easily construct (but which are not in themultiset).What makes this somewhat tricky is that if, say, no element comparesequal to the smallest test element, then there may be other subsequentelements in the set (greater than the smallest test element and lessthan the middle test element) which I do not want. So I can't just usea lower_bound with the smallest test element and an upper_bound with thelargest test element. However, if there are elements in the set thatcompare equal to one or more test elements, then I can be certain thatthere 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 exploitthe fact that all non-empty ranges must be consecutive. Is there analgorithm 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: 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 Jul 23 '05 #4

### This discussion thread is closed

Replies have been disabled for this discussion.