Proposed resolution:

This wording is relative to the N3485.

1. Change [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 ([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 ([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 ([algorithm.stable]).

   […]

3. Change [list.ops] as indicated:

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

   […]

   -17- Remarks: Stable ([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 ([algorithm.stable]). […]

   […]

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

   […]

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

   […]

4. Change [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 ([algorithm.stable]).

5. Change [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 ([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 ([algorithm.stable]).

6. Change [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 ([algorithm.stable]).

7. Change [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 ([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 ([algorithm.stable]).

[ 2013-04-18, Bristol ]

Original wording saved here:

This wording is relative to the FDIS.

1. Change [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.

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

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

Step 2: [defns.stable] and [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 [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 [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 [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 [algorithm.stable]'s "first range" and "second range".

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

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 [list.ops], p24 as follows:

Remarks: Stable.

Note that in general we define "stable" only for algorithms (see [defns.stable] and [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

• we first have all element of *this (in the same order as on entry)
• and then all elements of the passed argument (in the same order as on entry).