Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

partition

partition

Prototype

template<
    class ForwardRange,
    class UnaryPredicate
    >
typename range_iterator<ForwardRange>::type
partition(ForwardRange& rng, UnaryPredicate pred);

template<
    class ForwardRange,
    class UnaryPredicate
    >
typename range_iterator<const ForwardRange>::type
partition(const ForwardRange& rng, UnaryPredicate pred);

template<
    range_return_value re,
    class ForwardRange,
    class UnaryPredicate
    >
typename range_return<ForwardRange, re>::type
partition(ForwardRange& rng, UnaryPredicate pred);

template<
    range_return_value re,
    class ForwardRange,
    class UnaryPredicate
    >
typename range_return<const ForwardRange, re>::type
partition(const ForwardRange& rng, UnaryPredicate pred);

Description

partition orders the elements in rng based on pred, such that the elements that satisfy pred precede the elements that do not. In the versions that return a single iterator, the return value is the middle iterator. In the versions that have a configurable range_return, found corresponds to the middle iterator.

Definition

Defined in the header file boost/range/algorithm/partition.hpp

Requirements

ForwardRange is a model of the Forward Range Concept. For C++ versions prior to C++11 the underlying std::partition requires Bidirectional Iterators, hence the requirement for older library versions is for a Bidirectional Range.
UnaryPredicate is a model of the PredicateConcept.
ForwardRange's value type is convertible to UnaryPredicate's argument type.

Complexity

Linear. Exactly distance(rng) applications of pred, and at most distance(rng) / 2 swaps.