This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++14 status.

### 2122. `merge()` stability for lists versus forward lists

Section: 22.3.10.5 [list.ops], 99 [forwardlist.ops] Status: C++14 Submitter: Nicolai Josuttis Opened: 2012-01-15 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [list.ops].

View all issues with C++14 status.

Discussion:

`forward_list::merge()` is specified in 99 [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 22.3.10.5 [list.ops], p24 as follows:

> Remarks: Stable.

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

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

[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.59 [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 22.3.10.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: Stable 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. 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 99 [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 99 [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 `*this` the 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 22.3.10.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 25.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 25.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 25.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 25.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]).