2122. merge() stability for lists versus forward lists

Section: 23.3.9.5 [list.ops], 23.3.7.6 [forward.list.ops] Status: C++14 Submitter: Nicolai Josuttis Opened: 2012-01-15 Last modified: 2023-02-07

Priority: Not Prioritized

View all other issues in [list.ops].

View all issues with C++14 status.

Discussion:

forward_list::merge() is specified in [forwardlist.ops], p19 as follows:

This operation shall be stable: for equivalent elements in the two lists, the elements from *this shall always precede the elements from x.

But list::merge() is only specified in 23.3.9.5 [list.ops], p24 as follows:

Remarks: Stable.

Note that in general we define "stable" only for algorithms (see 3.58 [defns.stable] and 16.4.6.8 [algorithm.stable]) so for member function we should explain it everywhere we use it.

Thus for lists we have to add:

Stable: for equivalent elements in the two lists, the elements from the list always precede the elements from the argument list.

This, BTW, was the specification we had with C++03.

In addition, I wonder whether we also have some guarantees regarding stability saying that the order of equivalent elements of each list merged remains stable (which would be my interpretation of just saying "stable", BTW).

Thus, I'd expect that for equivalent elements we guarantee that

[2012, Kona]

Move to Open.

STL says we need to fix up 17.6.5.7 to be stronger, and then the remarks for merge should just say "Remarks: Stable (see 17.6.5.7)"

Assigned to STL for word-smithing.

[ 2013-04-14 STL provides rationale and improved wording ]

Step 1: Centralize all specifications of stability to 16.4.6.8 [algorithm.stable].

Step 2: 3.58 [defns.stable] and 16.4.6.8 [algorithm.stable] talk about "algorithms", without mentioning "container member functions". There's almost no potential for confusion here, but there's a simple way to increase clarity without increasing verbosity: make the container member functions explicitly cite 16.4.6.8 [algorithm.stable]. For consistency, we can also update the non-member functions.

Step 3: Fix the "so obvious, we forgot to say it" bug in 16.4.6.8 [algorithm.stable]: a "stable" merge of equivalent elements A B C D and W X Y Z produces A B C D W X Y Z, never D C B A X W Z Y.

Step 3.1: Say "(preserving their original order)" to be consistent with "the relative order [...] is preserved" in 16.4.6.8 [algorithm.stable]'s other bullet points.

Step 4: Copy part of list::merge()'s wording to forward_list::merge(), in order to properly connect with 16.4.6.8 [algorithm.stable]'s "first range" and "second range".

[2013-04-18, Bristol]

Original wording saved here:

This wording is relative to the FDIS.

  1. Change 23.3.9.5 [list.ops] as indicated:

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

    […]

    -24- Remarks: StableThis operation shall be stable: for equivalent elements in the two lists, the elements from *this shall always precede the elements from x and the order of equivalent elements of *this and x remains 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().

  2. Change [forwardlist.ops] as indicated:

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

    […]

    -19- Effects: Merges x into *this. This operation shall be stable: for equivalent elements in the two lists, the elements from *this shall always precede the elements from x and the order of equivalent elements of *this and x remains stable. 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.

Proposed resolution:

This wording is relative to the N3485.

  1. Change 16.4.6.8 [algorithm.stable]/1 as indicated:

    When the requirements for an algorithm state that it is “stable” without further elaboration, it means:

    […]

    • For the merge algorithms, for equivalent elements in the original two ranges, the elements from the first range (preserving their original order) precede the elements from the second range (preserving their original order).

  2. Change [forwardlist.ops] as indicated:

    void remove(const T& value);
template <class Predicate> void remove_if(Predicate pred);

    -12- Effects: Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value (for remove()), pred(*i) is true (for remove_if()). This operation shall be stable: the relative order of the elements that are not removed is the same as their relative order in the original list. Invalidates only the iterators and references to the erased elements.

    -13- Throws: Nothing unless an exception is thrown by the equality comparison or the predicate.

    -??- Remarks: Stable (16.4.6.8 [algorithm.stable]).

    […] 

    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)

    […]

    -19- Effects: Merges x into *thisthe two sorted ranges [begin(), end()) and [x.begin(), x.end()). This operation shall be stable: for equivalent elements in the two lists, the elements from *this shall always precede the elements from x. 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.

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

    […] 

    void sort();
template <class Compare> void sort(Compare comp);

    […]

    -23- Effects: Sorts the list according to the operator< or the comp function object. This operation shall be stable: the relative order of the equivalent elements is preserved. If an exception is thrown the order of the elements in *this is unspecified. Does not affect the validity of iterators and references.

    -??- Remarks: Stable (16.4.6.8 [algorithm.stable]).

    […]

  3. Change 23.3.9.5 [list.ops] as indicated:

    void remove(const T& value);
template <class Predicate> void remove_if(Predicate pred);

    […]

    -17- Remarks: Stable (16.4.6.8 [algorithm.stable]).

    […]

    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)

    […]

    -24- Remarks: Stable (16.4.6.8 [algorithm.stable]). […]

    […] 

    void sort();
template <class Compare> void sort(Compare comp);

    […]

    -30- Remarks: Stable (16.4.6.8 [algorithm.stable]).

    […]

  4. Change 26.7.1 [alg.copy]/12 as indicated:

    template<class InputIterator, class OutputIterator, class Predicate>
OutputIterator 
copy_if(InputIterator first, InputIterator last,
        OutputIterator result, Predicate pred);

    […]

    -12- Remarks: Stable (16.4.6.8 [algorithm.stable]).

  5. Change 26.7.8 [alg.remove] as indicated:

    template<class ForwardIterator, class T>
ForwardIterator 
remove(ForwardIterator first, ForwardIterator last, const T& value);
template<class ForwardIterator, class Predicate>
ForwardIterator 
remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);

    […]

    -4- Remarks: Stable (16.4.6.8 [algorithm.stable]).

    […] 

    template<class InputIterator, class OutputIterator, class T>
OutputIterator
remove_copy(InputIterator first, InputIterator last,
            OutputIterator result, const T& value);
template<class InputIterator, class OutputIterator, class Predicate>
OutputIterator
remove_copy_if(InputIterator first, InputIterator last,
               OutputIterator result, Predicate pred);

    […]

    -11- Remarks: Stable (16.4.6.8 [algorithm.stable]).

  6. Change 26.8.2.2 [stable.sort]/4 as indicated:

    template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

    […]

    -4- Remarks: Stable (16.4.6.8 [algorithm.stable]).

  7. Change 26.8.6 [alg.merge] as indicated:

    template<class InputIterator1, class InputIterator2,
         class OutputIterator>
OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2,
      OutputIterator result);
template<class InputIterator1, class InputIterator2,
         class OutputIterator, class Compare>
OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2,
      OutputIterator result, Compare comp);

    […]

    -5- Remarks: Stable (16.4.6.8 [algorithm.stable]).

    […] 

    template<class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
                   BidirectionalIterator middle,
                   BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
                   BidirectionalIterator middle,
                   BidirectionalIterator last, Compare comp);

    […]

    -9- Remarks: Stable (16.4.6.8 [algorithm.stable]).