Title
forward_list::merge behavior unclear when passed *this
Status
new
Section
[forwardlist.ops]
Submitter
Tim Song

Created on 2018-03-19.00:00:00 last changed 3 weeks ago

Messages

Date: 2021-05-22.14:52:08

Proposed resolution:

This wording is relative to N4885.

  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);
    

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

    -22- 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.

    -23- 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.

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

    -25- Remarks: Stable ([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 [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.

    -24- 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.

    -25- 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.

    -26- 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.

    -27- Remarks: Stable ([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.

Date: 2021-05-22.00:00:00

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

Date: 2019-07-30.00:00:00

[ 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 ([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.

Date: 2018-06-18.00:00:00

[ 2018-06-18 after reflector discussion ]

Priority set to 3

Date: 2018-03-19.00:00:00

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.

History
Date User Action Args
2021-05-22 14:52:08adminsetmessages: + msg11836
2019-07-30 12:00:34adminsetmessages: + msg10525
2018-06-19 05:49:11adminsetmessages: + msg9936
2018-03-25 13:18:26adminsetmessages: + msg9783
2018-03-19 00:00:00admincreate