3088. forward_list::merge behavior unclear when passed *this

Section: 23.3.7.6 [forward.list.ops] Status: C++23 Submitter: Tim Song Opened: 2018-03-19 Last modified: 2023-11-22

Priority: 3

View all other issues in [forward.list.ops].

View all issues with C++23 status.

Discussion:

LWG 300 changed list::merge to be a no-op when passed *this, but there's no equivalent rule for forward_list::merge. Presumably the forward_list proposal predated the adoption of LWG 300's PR and was never updated for the change. Everything in the discussion of that issue applies mutatis mutandis to the current specification of forward_list::merge.

[2018-06-18 after reflector discussion]

Priority set to 3

[2019-07-30 Tim provides updated PR]

Per the comments during issue prioritization, the new PR tries to synchronize the wording between list::merge and forward_list::merge.

Previous resolution [SUPERSEDED]:

This wording is relative to N4727.

1. Edit [forwardlist.ops] as indicated:

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

   -20- Requires: *this and x are both sorted with respect to the comparator operator< (for the first two overloads) or comp (for the last two overloads), and get_allocator() == x.get_allocator() is true.

   -21- Effects: If addressof(x) == this, does nothing. Otherwise, mMerges the two sorted ranges [begin(), end()) and [x.begin(), x.end()). The result is a range that is sorted with respect to the comparator operator< (for the first two overloads) or comp (for the last two overloads). x is empty after the merge. If an exception is thrown other than by a comparison there are no effects. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.

   -22- Remarks: Stable (16.4.6.8 [algorithm.stable]). The behavior is undefined if get_allocator() != x.get_allocator().

   -23- Complexity: At most distance(begin(), end()) + distance(x.begin(), x.end()) - 1 comparisons if addressof(x) != this; otherwise, no comparisons are performed.

[2021-05-22 Tim syncs wording to the current working draft]

[2022-01-31; Reflector poll]

Set status to Tentatively Ready after six votes in favour during reflector poll.

[2022-02-10 Approved at February 2022 virtual plenary. Status changed: Tentatively Ready → WP.]

Proposed resolution:

This wording is relative to N4901.

1. Edit 23.3.7.6 [forward.list.ops] as indicated:

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

   -?- Let comp be less<>{} for the first two overloads.

   -24- Preconditions: *this and x are both sorted with respect to the comparator operator< (for the first two overloads) or comp (for the last two overloads), and get_allocator() == x.get_allocator() is true.

   -25- Effects: If addressof(x) == this, there are no effects. Otherwise, mMerges the two sorted ranges [begin(), end()) and [x.begin(), x.end()). The result is a range that is sorted with respect to the comparator comp. x is empty after the merge. If an exception is thrown other than by a comparison there are no effects. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.

   -26- Complexity: At most distance(begin(), end()) + distance(x.begin(), x.end()) - 1 comparisons if addressof(x) != this; otherwise, no comparisons are performed.

   -27- Remarks: Stable (16.4.6.8 [algorithm.stable]). If addressof(x) != this, x is empty after the merge. No elements are copied by this operation. If an exception is thrown other than by a comparison there are no effects.

2. Edit 23.3.11.5 [list.ops] as indicated:

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

   -?- Let comp be less<>{} for the first two overloads.

   -26- Preconditions: Both the list and the argument list shall be*this and x are both sorted with respect to the comparator operator< (for the first two overloads) or comp (for the last two overloads), and get_allocator() == x.get_allocator() is true.

   -27- Effects: If addressof(x) == this, does nothing; othere are no effects. 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 falsethat is sorted with respect to the comparator comp. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.

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

   -29- Remarks: Stable (16.4.6.8 [algorithm.stable]). If addressof(x) != this, the range [x.begin(), x.end())x is empty after the merge. No elements are copied by this operation. If an exception is thrown other than by a comparison there are no effects.