1215. list::merge with unequal allocators

Section: 23.3.9.5 [list.ops] Status: C++11 Submitter: Pablo Halpern Opened: 2009-09-24 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [list.ops].

View all issues with C++11 status.

Discussion:

In Bellevue (I think), we passed N2525, which, among other things, specifies that the behavior of list::splice is undefined if the allocators of the two lists being spliced do not compare equal. The same rationale should apply to list::merge. The intent of list::merge (AFAIK) is to move nodes from one sorted list into another sorted list without copying the elements. This is possible only if the allocators compare equal.

Proposed resolution:

Relative to the August 2009 WP, N2857, change 23.3.9.5 [list.ops], paragraphs 22-25 as follows:

void merge(list&& x);
template <class Compare> void merge(list&& x, Compare comp);

Requires: both the list and the argument list shall be sorted according to operator< or comp.

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.

Remarks: Stable. If (&x != this) the range [x.begin(), x.end()) is empty after the merge. No elements are copied by this operation. The behavior is undefined if this->get_allocator() != x.get_allocator().

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.