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

Section: 23.3.9.5 [list.ops], 23.3.7.6 [forward.list.ops] Status: C++20 Submitter: Tim Song Opened: 2017-07-07 Last modified: 2023-02-07

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 26.2 [algorithms.requirements] and 26.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 26.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 23.3.9.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 26.2 [algorithms.requirements]. For merge and sort, the definitions and requirements in 26.8 [alg.sorting] apply.

  2. Edit 23.3.9.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 (26.8 [alg.sorting]), and bBoth the list and the argument list shall be sorted according to this orderingwith respect to the comparator operator< (for the first two overloads) or comp (for the last two overloads).

  3. Delete 23.3.9.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 (26.8 [alg.sorting]).

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

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

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

    […]

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

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

  6. Delete [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 (26.8 [alg.sorting]).