Movatterモバイル変換

This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofC++11 status.

498. Requirements for partition() and stable_partition() too strong

Section: 26.8.5[alg.partitions]Status:C++11Submitter: Sean Parent, Joe GottmanOpened: 2005-05-04Last modified: 2025-03-13

Priority:Not Prioritized

View all otherissues in [alg.partitions].

View all issues withC++11 status.

Discussion:

Problem:The iterator requirements for partition() and stable_partition() [25.2.12]are listed as BidirectionalIterator, however, there are efficient algorithmsfor these functions that only require ForwardIterator that have been knownsince before the standard existed. The SGI implementation includes these (seehttps://www.boost.org/sgi/stl/partition.htmlandhttps://www.boost.org/sgi/stl/stable_partition.html).

[2009-04-30 Alisdair adds:]

Now we have concepts this is easier to express!

Proposed resolution:

Add the following signature to:

Header<algorithm> synopsis [algorithms.syn]
p3 Partitions 26.8.5[alg.partitions]

 template<ForwardIterator Iter, Predicate<auto, Iter::value_type> Pred>   requires ShuffleIterator<Iter>         && CopyConstructible<Pred>   Iter partition(Iter first, Iter last, Pred pred);

Update p3 Partitions 26.8.5[alg.partitions]:

Complexity:At most(last - first)/2 swaps. Exactlylast - firstapplications of the predicateare done.IfIter satisfiesBidirectionalIterator, at most(last -first)/2 swaps. Exactlylast - first applications of the predicateare done.

IfIter merely satisfiedForwardIterator at most(last - first) swapsare done. Exactly(last - first) applications of the predicate are done.

[Editorial note: I looked for existing precedent in how we might call outdistinct overloads overloads from a set of constrained templates, but thereis not much existing practice to lean on. advance/distance were the onlyalgorithms I could find, and that wording is no clearer.]

[2009-07 Frankfurt]

Hinnant: if you want to partition your std::forward_list, you'll needpartition() to accept ForwardIterators.

No objection to Ready.

Move to Ready.

Proposed resolution:

Change 25.2.12 from

template<class BidirectionalIterator, class Predicate> BidirectionalIterator partition(BidirectionalIterato r first,                                 BidirectionalIterator last,                                 Predicate pred);

to

template<class ForwardIterator, class Predicate> ForwardIterator partition(ForwardIterator first,                           ForwardIterator last,                           Predicate pred);

Change the complexity from

At most (last - first)/2 swaps are done. Exactly (last - first) applications of the predicate are done.

to

If ForwardIterator is a bidirectional_iterator, at most (last - first)/2 swaps are done; otherwise at most (last - first) swaps are done. Exactly (last - first) applications of the predicate are done.

Rationale:

Partition is a "foundation" algorithm useful in many contexts (like sortingas just one example) - my motivation for extending it to include forwarditerators is foward_list - without this extension you can't partition an foward_list(without writing your own partition). Holes like this in the standardlibrary weaken the argument for generic programming (ideally I'd be ableto provide a library that would refine std::partition() to other conceptswithout fear of conflicting with other libraries doing the same - butthat is a digression). I consider the fact that partition isn't definedto work for ForwardIterator a minor embarrassment.

[Mont Tremblant: Moved to Open, request motivation and use cases by next meeting. Sean provided further rationale by post-meeting mailing.]