list::merge() specification incomplete
John Pedretti

Created on 2001-01-23.00:00:00, last changed 2010-10-21.18:28:33.


Date: 2010-10-21.18:28:33

[ Post-CuraƧao: Robert Klarer provided new wording. ]

Date: 2010-10-21.18:28:33

[ Copenhagen: The original proposed resolution did not fix all of the problems in [list.ops], p22-25. Three different paragraphs (23, 24, 25) describe the effects of merge. Changing p23, without changing the other two, appears to introduce contradictions. Additionally, "merges the argument list into the list" is excessively vague. ]

Date: 2010-10-21.18:28:33

Proposed resolution:

In [list.ops], replace paragraps 23-25 with:

23 Effects: if (&x == this) does nothing; otherwise, merges the two sorted ranges [begin(), end()) and [x.begin(), x.end()). The result is a range in which the elements will be sorted in non-decreasing order according to the ordering defined by comp; that is, for every iterator i in the range other than the first, the condition comp(*i, *(i - 1)) will be false.

24 Notes: Stable: if (&x != this), then for equivalent elements in the two original ranges, the elements from the original range [begin(), end()) always precede the elements from the original range [x.begin(), x.end()). If (&x != this) the range [x.begin(), x.end()) is empty after the merge.

25 Complexity: At most size() + x.size() - 1 applications of comp if (&x ! = this); otherwise, no applications of comp are performed. If an exception is thrown other than by a comparison there are no effects.

Date: 2001-01-23.00:00:00

The "Effects" clause for list::merge() ([list.ops], p23) appears to be incomplete: it doesn't cover the case where the argument list is identical to *this (i.e., this == &x). The requirement in the note in p24 (below) is that x be empty after the merge which is surely unintended in this case.

Date User Action Args
2010-10-21 18:28:33adminsetmessages: + msg2167
2010-10-21 18:28:33adminsetmessages: + msg2166
2010-10-21 18:28:33adminsetmessages: + msg2165
2001-01-23 00:00:00admincreate