This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofCD1 status.
Section: 26.8.7[alg.set.operations]Status:CD1Submitter: Matt AusternOpened: 2001-01-03Last modified: 2016-01-28
Priority:Not Prioritized
View all otherissues in [alg.set.operations].
View all issues withCD1 status.
Discussion:
The standard library contains four algorithms that compute setoperations on sorted ranges:set_union,set_intersection,set_difference, andset_symmetric_difference. Eachof these algorithms takes two sorted ranges as inputs, and writes theoutput of the appropriate set operation to an output range. The elementsin the output range are sorted.
The ordinary mathematical definitions are generalized so that theyapply to ranges containing multiple copies of a given element. Twoelements are considered to be "the same" if, according to anordering relation provided by the user, neither one is less than theother. So, for example, if one input range contains five copies of anelement and another contains three, the output range ofset_unionwill contain five copies, the output range ofset_intersection will contain three, the output range ofset_difference will contain two, and the output range ofset_symmetric_difference will contain two.
Because two elements can be "the same" for the purposesof these set algorithms, without being identical in other respects(consider, for example, strings under case-insensitive comparison),this raises a number of unanswered questions:
The standard should either answer these questions, or explicitlysay that the answers are unspecified. I prefer the former option,since, as far as I know, all existing implementations behave thesame way.
Proposed resolution:
Add the following to the end of 26.8.7.3[set.union] paragraph 5:
If [first1, last1) containsm elements that are equivalent toeach other and [first2, last2) containsn elements that areequivalent to them, then max(m,n) of these elementswill be copied to the output range: allm of these elementsfrom [first1, last1), and the last max(n-m, 0) of them from[first2, last2), in that order.
Add the following to the end of 26.8.7.4[set.intersection] paragraph 5:
If [first1, last1) containsm elements that are equivalent to eachother and [first2, last2) containsn elements that areequivalent to them, the first min(m,n) of those elements from [first1, last1) are copied to the output range.
Add a new paragraph,Notes, after 26.8.7.5[set.difference]paragraph 4:
If [first1, last1) containsm elements that are equivalent to eachother and [first2, last2) containsn elements that areequivalent to them, the last max(m-n, 0) elements from [first1, last1) are copied to the output range.
Add a new paragraph,Notes, after 26.8.7.6[set.symmetric.difference]paragraph 4:
If [first1, last1) containsm elements that are equivalent toeach other and [first2, last2) containsn elements that areequivalent to them, then |m - n| of those elements will becopied to the output range: the lastm - n of these elementsfrom [first1, last1) ifm >n, and the lastn -m of these elements from [first2, last2) ifm <n.
[Santa Cruz: it's believed that this language is clearer than what's in the Standard. However, it's also believed that the Standard may already make these guarantees (although not quite in these words). Bill and Howard will check and see whether they think that some or all of these changes may be redundant. If so, we may close this issue as NAD.]
Rationale:
For simple cases, these descriptions are equivalent to what's already in the Standard. For more complicated cases, they describe the behavior of existing implementations.