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

Section: 26.3.10.5 [list.ops], 26.3.9.6 [forwardlist.ops] Status: WP Submitter: Tim Song Opened: 2017-07-07 Last modified: 2017-11-13

Priority: 0

View all other issues in [list.ops].

View all issues with WP 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 28.3 [algorithms.requirements] and 28.7 [alg.sorting], which means, for instance, that there appears to be no rule prohibiting Compare from modifying its arguments, because we only refer to 28.7 [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 26.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 28.3 [algorithms.requirements]. For merge and sort, the definitions and requirements in 28.7 [alg.sorting] apply.

  2. Edit 26.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 (28.7 [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 26.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 (28.7 [alg.sorting]).

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

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

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

    […]

  5. Edit 26.3.9.6 [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 (28.7 [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 26.3.9.6 [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 (28.7 [alg.sorting]).