Home | Libraries | People | FAQ | More |
template<class BidirectionalRange> BidirectionalRange& inplace_merge( BidirectionalRange& rng, typename range_iterator<BidirectionalRange>::type middle ); template<class BidirectionalRange> const BidirectionalRange& inplace_merge( const BidirectionalRange& rng, typename range_iterator<const BidirectionalRange>::type middle ); template<class BidirectionalRange, class BinaryPredicate> BidirectionalRange& inplace_merge( BidirectionalRange& rng, typename range_iterator<BidirectionalRange>::type middle, BinaryPredicate pred ); template<class BidirectionalRange, class BinaryPredicate> const BidirectionalRange& inplace_merge( const BidirectionalRange& rng, typename range_iterator<const BidirectionalRange>::type middle, BinaryPredicate pred );
inplace_merge
combines
two consecutive sorted ranges [begin(rng), middle)
and [middle, end(rng))
into a single sorted range [begin(rng), end(rng))
. That is, it starts with a range [begin(rng), end(rng))
that consists of two pieces each of
which is in ascending order, and rearranges it so that the entire range
is in ascending order. inplace_merge
is stable, meaning both that the relative order of elements within each
input range is preserved.
Defined in the header file boost/range/algorithm/inplace_merge.hpp
For the non-predicate version:
BidirectionalRange
is a model of the Bidirectional
Range Concept.
BidirectionalRange
is mutable.
range_value<BidirectionalRange>::type
is a model of LessThanComparableConcept
range_type<BidirectionalRange>::type
is a strict weak ordering,
as defined in the LessThanComparableConcept
requirements.
For the predicate version: * BidirectionalRange
is a model of the
Bidirectional Range
Concept. * BidirectionalRange
is mutable. * BinaryPredicate
is a model of the StrictWeakOrderingConcept
.
* BidirectionalRange
's
value type is convertible to both BinaryPredicate
's
argument types.
middle
is in the range
rng
.
[begin(rng), middle)
is in ascending order. That is for
each pair of adjacent elements [x,y]
,
y <
x
is false
.
[middle, end(rng))
is in ascending order. That is for
each pair of adjacent elements [x,y]
,
y <
x
is false
.
middle
is in the range
rng
.
[begin(rng), middle)
is in ascending order. That is for
each pair of adjacent elements [x,y]
,
pred(y,x) == false
.
[middle, end(rng))
is in ascending order. That is for
each pair of adjacent elements [x,y]
,
pred(y,x) == false
.
Worst case: O(N log(N))