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

### 2998. Requirements on function objects passed to `{forward_,}list`-specific algorithms

Section: 22.3.10.5 [list.ops], 99 [forwardlist.ops] Status: C++20 Submitter: Tim Song Opened: 2017-07-07 Last modified: 2021-02-25

Priority: 0

View all other issues in [list.ops].

View all issues with C++20 status.

Discussion:

Some specialized algorithms for `forward_list` and `list` take template parameters named `Predicate`, `BinaryPredicate`, or `Compare`. However, there's no wording importing the full requirements for template type parameters with such names from 25.2 [algorithms.requirements] and 25.8 [alg.sorting], which means, for instance, that there appears to be no rule prohibiting `Compare` from modifying its arguments, because we only refer to 25.8 [alg.sorting] for the definition of strict weak ordering. Is that intended?

[2017-07 Toronto Tuesday PM issue prioritization]

Priority 0; status to Ready

Proposed resolution:

This wording is relative to N4659.

1. Edit 22.3.10.5 [list.ops] as indicated:

   > -1- Since lists allow fast insertion and erasing from the middle of a list, certain operations are provided specifically for them.259) In this subclause, arguments for a template parameter named `Predicate` or `BinaryPredicate` shall meet the corresponding requirements in 25.2 [algorithms.requirements]. For `merge` and `sort`, the definitions and requirements in 25.8 [alg.sorting] apply.

2. Edit 22.3.10.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);

   > > -22- Requires: `comp` shall define a strict weak ordering (25.8 [alg.sorting]), and b Both the list and the argument list shall be sorted according to this ordering with respect to the comparator `operator<` (for the first two overloads) or `comp` (for the last two overloads).

3. Delete 22.3.10.5 [list.ops]/28 as redundant:

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

   > > -28- Requires: `operator<` (for the first version) or `comp` (for the second version) shall define a strict weak ordering (25.8 [alg.sorting]).

4. Insert a new paragraph at the beginning of 99 [forwardlist.ops]:

   > -?- In this subclause, arguments for a template parameter named `Predicate` or `BinaryPredicate` shall meet the corresponding requirements in 25.2 [algorithms.requirements]. For `merge` and `sort`, the definitions and requirements in 25.8 [alg.sorting] apply.

   >     void splice_after(const_iterator position, forward_list& x);
   >     void splice_after(const_iterator position, forward_list&& x);

   > […]

5. Edit 99 [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);

   > > -22- Requires: `comp` defines a strict weak ordering (25.8 [alg.sorting]), and `*this` and `x` are both sorted according to this ordering with respect to the comparator `operator<` (for the first two overloads) or `comp` (for the last two overloads). `get_allocator() == x.get_allocator()`.

6. Delete 99 [forwardlist.ops]/23 as redundant:

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

   > > -23- Requires: `operator<` (for the version with no arguments) or `comp` (for the version with a comparison argument) defines a strict weak ordering (25.8 [alg.sorting]).