[specialized.algorithms] (original) (raw)

26 Algorithms library [algorithms]

26.11.1 General [specialized.algorithms.general]

26.11.2 Special memory concepts [special.mem.concepts]

26.11.3 uninitialized_default_construct [uninitialized.construct.default]

26.11.4 uninitialized_value_construct [uninitialized.construct.value]

26.11.5 uninitialized_copy [uninitialized.copy]

26.11.6 uninitialized_move [uninitialized.move]

26.11.7 uninitialized_fill [uninitialized.fill]

26.11.8 construct_at [specialized.construct]

26.11.9 destroy [specialized.destroy]

26.11.1 General [specialized.algorithms.general]

The contents specified in [specialized.algorithms] are declared in the header .

Unless otherwise specified, if an exception is thrown in the following algorithms, objects constructed by a placement new-expression ([expr.new]) are destroyed in an unspecified order before allowing the exception to propagate.

[Note 1:

When new objects are created by the algorithms specified in [specialized.algorithms], the lifetime ends for any existing objects (including potentially-overlapping subobjects [intro.object]) in storage that is reused [basic.life].

— _end note_]

Some algorithms specified in [specialized.algorithms] make use of the following exposition-only function templates:template<class T> constexpr void* voidify(T& obj) noexcept { return addressof(obj);} template<class I> decltype(auto) deref-move(I& it) { if constexpr (is_lvalue_reference_v<decltype(*it)>) return std::move(*it);else return *it;}

26.11.2 Special memory concepts [special.mem.concepts]

Some algorithms in this subclause are constrained with the following exposition-only concepts:

template<class I> concept [_nothrow-input-iterator_](#concept:nothrow-input-iterator "26.11.2 Special memory concepts [special.mem.concepts]") = // _exposition only_ [input_iterator](iterator.concept.input#concept:input%5Fiterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]")<I> && is_lvalue_reference_v<iter_reference_t<I>> && [same_as](concept.same#concept:same%5Fas "18.4.2 Concept same_­as [concept.same]")<remove_cvref_t<iter_reference_t<I>>, iter_value_t<I>>;

A type I models nothrow-input-iterator only if no exceptions are thrown from increment, copy construction, move construction, copy assignment, move assignment, or indirection through valid iterators.

template<class S, class I> concept [_nothrow-sentinel-for_](#concept:nothrow-sentinel-for "26.11.2 Special memory concepts [special.mem.concepts]") = [sentinel_for](iterator.concept.sentinel#concept:sentinel%5Ffor "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<S, I>; // _exposition only_

Types S and I model nothrow-sentinel-foronly if no exceptions are thrown from copy construction, move construction, copy assignment, move assignment, or comparisons between valid values of type I and S.

Types S and I model nothrow-sized-sentinel-foronly if no exceptions are thrown from the - operator for valid values of type I and S.

template<class R> concept [_nothrow-input-range_](#concept:nothrow-input-range "26.11.2 Special memory concepts [special.mem.concepts]") = // _exposition only_ [range](range.range#concept:range "25.4.2 Ranges [range.range]")<R> && [_nothrow-input-iterator_](#concept:nothrow-input-iterator "26.11.2 Special memory concepts [special.mem.concepts]")<iterator_t<R>> && [_nothrow-sentinel-for_](#concept:nothrow-sentinel-for "26.11.2 Special memory concepts [special.mem.concepts]")<sentinel_t<R>, iterator_t<R>>;

A type R models nothrow-input-range only if no exceptions are thrown from calls to ranges​::​begin andranges​::​end on an object of type R.

template<class R> concept [_nothrow-forward-range_](#concept:nothrow-forward-range "26.11.2 Special memory concepts [special.mem.concepts]") = // _exposition only_ [_nothrow-input-range_](#concept:nothrow-input-range "26.11.2 Special memory concepts [special.mem.concepts]")<R> && [_nothrow-forward-iterator_](#concept:nothrow-forward-iterator "26.11.2 Special memory concepts [special.mem.concepts]")<iterator_t<R>>;

A type I models nothrow-bidirectional-iteratoronly if no exceptions are thrown from decrementing valid iterators.

template<class R> concept [_nothrow-bidirectional-range_](#concept:nothrow-bidirectional-range "26.11.2 Special memory concepts [special.mem.concepts]") = // _exposition only_ [_nothrow-forward-range_](#concept:nothrow-forward-range "26.11.2 Special memory concepts [special.mem.concepts]")<R> && [_nothrow-bidirectional-iterator_](#concept:nothrow-bidirectional-iterator "26.11.2 Special memory concepts [special.mem.concepts]")<iterator_t<R>>;

A type I models nothrow-random-access-iteratoronly if no exceptions are thrown from comparisons of valid iterators, or the -, +, -=, +=, [] operators on valid values of type I and iter_difference_t<I>.

template<class R> concept [_nothrow-random-access-range_](#concept:nothrow-random-access-range "26.11.2 Special memory concepts [special.mem.concepts]") = // _exposition only_ [_nothrow-bidirectional-range_](#concept:nothrow-bidirectional-range "26.11.2 Special memory concepts [special.mem.concepts]")<R> && [_nothrow-random-access-iterator_](#concept:nothrow-random-access-iterator "26.11.2 Special memory concepts [special.mem.concepts]")<iterator_t<R>>;template<class R> concept [_nothrow-sized-random-access-range_](#concept:nothrow-sized-random-access-range "26.11.2 Special memory concepts [special.mem.concepts]") = // _exposition only_ [_nothrow-random-access-range_](#concept:nothrow-random-access-range "26.11.2 Special memory concepts [special.mem.concepts]")<R> && [sized_range](range.sized#concept:sized%5Frange "25.4.4 Sized ranges [range.sized]")<R>;

A type R models nothrow-sized-random-access-rangeonly if no exceptions are thrown from the call to ranges​::​sizeon an object of type R.

26.11.3 uninitialized_default_construct [uninitialized.construct.default]

template<class NoThrowForwardIterator> constexpr void uninitialized_default_construct(NoThrowForwardIterator first, NoThrowForwardIterator last);

Effects: Equivalent to:for (; first != last; ++first) ::new (voidify(*first)) iterator_traits<NoThrowForwardIterator>::value_type;

namespace ranges { template<[_nothrow-forward-iterator_](#concept:nothrow-forward-iterator "26.11.2 Special memory concepts [special.mem.concepts]") I, [_nothrow-sentinel-for_](#concept:nothrow-sentinel-for "26.11.2 Special memory concepts [special.mem.concepts]")<I> S> requires [default_initializable](concept.default.init#concept:default%5Finitializable "18.4.12 Concept default_­initializable [concept.default.init]")<iter_value_t<I>> constexpr I uninitialized_default_construct(I first, S last);template<[_nothrow-forward-range_](#concept:nothrow-forward-range "26.11.2 Special memory concepts [special.mem.concepts]") R> requires [default_initializable](concept.default.init#concept:default%5Finitializable "18.4.12 Concept default_­initializable [concept.default.init]")<range_value_t<R>> constexpr borrowed_iterator_t<R> uninitialized_default_construct(R&& r);}

Effects: Equivalent to:for (; first != last; ++first) ::new (voidify(*first)) remove_reference_t<iter_reference_t<I>>;return first;

template<class NoThrowForwardIterator, class Size> constexpr NoThrowForwardIterator uninitialized_default_construct_n(NoThrowForwardIterator first, Size n);

Effects: Equivalent to:for (; n > 0; (void)++first, --n) ::new (voidify(*first)) iterator_traits<NoThrowForwardIterator>::value_type;return first;

namespace ranges { template<[_nothrow-forward-iterator_](#concept:nothrow-forward-iterator "26.11.2 Special memory concepts [special.mem.concepts]") I> requires [default_initializable](concept.default.init#concept:default%5Finitializable "18.4.12 Concept default_­initializable [concept.default.init]")<iter_value_t<I>> constexpr I uninitialized_default_construct_n(I first, iter_difference_t<I> n);}

Effects: Equivalent to:return uninitialized_default_construct(counted_iterator(first, n), default_sentinel).base();

26.11.4 uninitialized_value_construct [uninitialized.construct.value]

template<class NoThrowForwardIterator> constexpr void uninitialized_value_construct(NoThrowForwardIterator first, NoThrowForwardIterator last);

Effects: Equivalent to:for (; first != last; ++first) ::new (voidify(*first)) iterator_traits<NoThrowForwardIterator>::value_type();

namespace ranges { template<[_nothrow-forward-iterator_](#concept:nothrow-forward-iterator "26.11.2 Special memory concepts [special.mem.concepts]") I, [_nothrow-sentinel-for_](#concept:nothrow-sentinel-for "26.11.2 Special memory concepts [special.mem.concepts]")<I> S> requires [default_initializable](concept.default.init#concept:default%5Finitializable "18.4.12 Concept default_­initializable [concept.default.init]")<iter_value_t<I>> constexpr I uninitialized_value_construct(I first, S last);template<[_nothrow-forward-range_](#concept:nothrow-forward-range "26.11.2 Special memory concepts [special.mem.concepts]") R> requires [default_initializable](concept.default.init#concept:default%5Finitializable "18.4.12 Concept default_­initializable [concept.default.init]")<range_value_t<R>> constexpr borrowed_iterator_t<R> uninitialized_value_construct(R&& r);}

Effects: Equivalent to:for (; first != last; ++first) ::new (voidify(*first)) remove_reference_t<iter_reference_t<I>>();return first;

template<class NoThrowForwardIterator, class Size> constexpr NoThrowForwardIterator uninitialized_value_construct_n(NoThrowForwardIterator first, Size n);

Effects: Equivalent to:for (; n > 0; (void)++first, --n) ::new (voidify(*first)) iterator_traits<NoThrowForwardIterator>::value_type();return first;

namespace ranges { template<[_nothrow-forward-iterator_](#concept:nothrow-forward-iterator "26.11.2 Special memory concepts [special.mem.concepts]") I> requires [default_initializable](concept.default.init#concept:default%5Finitializable "18.4.12 Concept default_­initializable [concept.default.init]")<iter_value_t<I>> constexpr I uninitialized_value_construct_n(I first, iter_difference_t<I> n);}

Effects: Equivalent to:return uninitialized_value_construct(counted_iterator(first, n), default_sentinel).base();

26.11.5 uninitialized_copy [uninitialized.copy]

template<class InputIterator, class NoThrowForwardIterator> constexpr NoThrowForwardIterator uninitialized_copy(InputIterator first, InputIterator last, NoThrowForwardIterator result);

Preconditions: does not overlap with [first, last).

Effects: Equivalent to:for (; first != last; ++result, (void)++first) ::new (voidify(*result)) iterator_traits<NoThrowForwardIterator>::value_type(*first);

namespace ranges { template<[input_iterator](iterator.concept.input#concept:input%5Fiterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel%5Ffor "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S1,[_nothrow-forward-iterator_](#concept:nothrow-forward-iterator "26.11.2 Special memory concepts [special.mem.concepts]") O, [_nothrow-sentinel-for_](#concept:nothrow-sentinel-for "26.11.2 Special memory concepts [special.mem.concepts]")<O> S2> requires [constructible_from](concept.constructible#concept:constructible%5Ffrom "18.4.11 Concept constructible_­from [concept.constructible]")<iter_value_t<O>, iter_reference_t<I>> constexpr uninitialized_copy_result<I, O> uninitialized_copy(I ifirst, S1 ilast, O ofirst, S2 olast);template<[input_range](range.refinements#concept:input%5Frange "25.4.6 Other range refinements [range.refinements]") IR, [_nothrow-forward-range_](#concept:nothrow-forward-range "26.11.2 Special memory concepts [special.mem.concepts]") OR> requires [constructible_from](concept.constructible#concept:constructible%5Ffrom "18.4.11 Concept constructible_­from [concept.constructible]")<range_value_t<OR>, range_reference_t<IR>> constexpr uninitialized_copy_result<borrowed_iterator_t<IR>, borrowed_iterator_t<OR>> uninitialized_copy(IR&& in_range, OR&& out_range);}

Preconditions: [ofirst, olast) does not overlap with [ifirst, ilast).

Effects: Equivalent to:for (; ifirst != ilast && ofirst != olast; ++ofirst, (void)++ifirst) ::new (voidify(*ofirst)) remove_reference_t<iter_reference_t<O>>(*ifirst);return {std::move(ifirst), ofirst};

template<class InputIterator, class Size, class NoThrowForwardIterator> constexpr NoThrowForwardIterator uninitialized_copy_n(InputIterator first, Size n, NoThrowForwardIterator result);

Preconditions: does not overlap with .

Effects: Equivalent to:for (; n > 0; ++result, (void)++first, --n) ::new (voidify(*result)) iterator_traits<NoThrowForwardIterator>::value_type(*first);

namespace ranges { template<[input_iterator](iterator.concept.input#concept:input%5Fiterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I, [_nothrow-forward-iterator_](#concept:nothrow-forward-iterator "26.11.2 Special memory concepts [special.mem.concepts]") O, [_nothrow-sentinel-for_](#concept:nothrow-sentinel-for "26.11.2 Special memory concepts [special.mem.concepts]")<O> S> requires [constructible_from](concept.constructible#concept:constructible%5Ffrom "18.4.11 Concept constructible_­from [concept.constructible]")<iter_value_t<O>, iter_reference_t<I>> constexpr uninitialized_copy_n_result<I, O> uninitialized_copy_n(I ifirst, iter_difference_t<I> n, O ofirst, S olast);}

Preconditions: [ofirst, olast) does not overlap with.

Effects: Equivalent to:auto t = uninitialized_copy(counted_iterator(std::move(ifirst), n), default_sentinel, ofirst, olast);return {std::move(t.in).base(), t.out};

26.11.6 uninitialized_move [uninitialized.move]

template<class InputIterator, class NoThrowForwardIterator> constexpr NoThrowForwardIterator uninitialized_move(InputIterator first, InputIterator last, NoThrowForwardIterator result);

Preconditions: does not overlap with [first, last).

Effects: Equivalent to:for (; first != last; (void)++result, ++first) ::new (voidify(*result)) iterator_traits<NoThrowForwardIterator>::value_type(deref-move(first));return result;

namespace ranges { template<[input_iterator](iterator.concept.input#concept:input%5Fiterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel%5Ffor "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S1,[_nothrow-forward-iterator_](#concept:nothrow-forward-iterator "26.11.2 Special memory concepts [special.mem.concepts]") O, [_nothrow-sentinel-for_](#concept:nothrow-sentinel-for "26.11.2 Special memory concepts [special.mem.concepts]")<O> S2> requires [constructible_from](concept.constructible#concept:constructible%5Ffrom "18.4.11 Concept constructible_­from [concept.constructible]")<iter_value_t<O>, iter_rvalue_reference_t<I>> constexpr uninitialized_move_result<I, O> uninitialized_move(I ifirst, S1 ilast, O ofirst, S2 olast);template<[input_range](range.refinements#concept:input%5Frange "25.4.6 Other range refinements [range.refinements]") IR, [_nothrow-forward-range_](#concept:nothrow-forward-range "26.11.2 Special memory concepts [special.mem.concepts]") OR> requires [constructible_from](concept.constructible#concept:constructible%5Ffrom "18.4.11 Concept constructible_­from [concept.constructible]")<range_value_t<OR>, range_rvalue_reference_t<IR>> constexpr uninitialized_move_result<borrowed_iterator_t<IR>, borrowed_iterator_t<OR>> uninitialized_move(IR&& in_range, OR&& out_range);}

Preconditions: [ofirst, olast) does not overlap with [ifirst, ilast).

Effects: Equivalent to:for (; ifirst != ilast && ofirst != olast; ++ofirst, (void)++ifirst) ::new (voidify(*ofirst)) remove_reference_t<iter_reference_t<O>>(ranges::iter_move(ifirst));return {std::move(ifirst), ofirst};

[Note 1:

If an exception is thrown, some objects in the range [ifirst, ilast) are left in a valid, but unspecified state.

— _end note_]

template<class InputIterator, class Size, class NoThrowForwardIterator> constexpr pair<InputIterator, NoThrowForwardIterator> uninitialized_move_n(InputIterator first, Size n, NoThrowForwardIterator result);

Preconditions: does not overlap with .

Effects: Equivalent to:for (; n > 0; ++result, (void)++first, --n) ::new (voidify(*result)) iterator_traits<NoThrowForwardIterator>::value_type(deref-move(first));return {first, result};

namespace ranges { template<[input_iterator](iterator.concept.input#concept:input%5Fiterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I, [_nothrow-forward-iterator_](#concept:nothrow-forward-iterator "26.11.2 Special memory concepts [special.mem.concepts]") O, [_nothrow-sentinel-for_](#concept:nothrow-sentinel-for "26.11.2 Special memory concepts [special.mem.concepts]")<O> S> requires [constructible_from](concept.constructible#concept:constructible%5Ffrom "18.4.11 Concept constructible_­from [concept.constructible]")<iter_value_t<O>, iter_rvalue_reference_t<I>> constexpr uninitialized_move_n_result<I, O> uninitialized_move_n(I ifirst, iter_difference_t<I> n, O ofirst, S olast);}

Preconditions: [ofirst, olast) does not overlap with .

Effects: Equivalent to:auto t = uninitialized_move(counted_iterator(std::move(ifirst), n), default_sentinel, ofirst, olast);return {std::move(t.in).base(), t.out};

[Note 2:

If an exception is thrown, some objects in the rangeare left in a valid but unspecified state.

— _end note_]

26.11.7 uninitialized_fill [uninitialized.fill]

template<class NoThrowForwardIterator, class T> constexpr void uninitialized_fill(NoThrowForwardIterator first, NoThrowForwardIterator last, const T& x);

Effects: Equivalent to:for (; first != last; ++first) ::new (voidify(*first)) iterator_traits<NoThrowForwardIterator>::value_type(x);

namespace ranges { template<[_nothrow-forward-iterator_](#concept:nothrow-forward-iterator "26.11.2 Special memory concepts [special.mem.concepts]") I, [_nothrow-sentinel-for_](#concept:nothrow-sentinel-for "26.11.2 Special memory concepts [special.mem.concepts]")<I> S, class T> requires [constructible_from](concept.constructible#concept:constructible%5Ffrom "18.4.11 Concept constructible_­from [concept.constructible]")<iter_value_t<I>, const T&> constexpr I uninitialized_fill(I first, S last, const T& x);template<[_nothrow-forward-range_](#concept:nothrow-forward-range "26.11.2 Special memory concepts [special.mem.concepts]") R, class T> requires [constructible_from](concept.constructible#concept:constructible%5Ffrom "18.4.11 Concept constructible_­from [concept.constructible]")<range_value_t<R>, const T&> constexpr borrowed_iterator_t<R> uninitialized_fill(R&& r, const T& x);}

Effects: Equivalent to:for (; first != last; ++first) ::new (voidify(*first)) remove_reference_t<iter_reference_t<I>>(x);return first;

template<class NoThrowForwardIterator, class Size, class T> constexpr NoThrowForwardIterator uninitialized_fill_n(NoThrowForwardIterator first, Size n, const T& x);

Effects: Equivalent to:for (; n--; ++first) ::new (voidify(*first)) iterator_traits<NoThrowForwardIterator>::value_type(x);return first;

namespace ranges { template<[_nothrow-forward-iterator_](#concept:nothrow-forward-iterator "26.11.2 Special memory concepts [special.mem.concepts]") I, class T> requires [constructible_from](concept.constructible#concept:constructible%5Ffrom "18.4.11 Concept constructible_­from [concept.constructible]")<iter_value_t<I>, const T&> constexpr I uninitialized_fill_n(I first, iter_difference_t<I> n, const T& x);}

Effects: Equivalent to:return uninitialized_fill(counted_iterator(first, n), default_sentinel, x).base();

26.11.8 construct_at [specialized.construct]

template<class T, class... Args> constexpr T* construct_at(T* location, Args&&... args);namespace ranges { template<class T, class... Args> constexpr T* construct_at(T* location, Args&&... args);}

Constraints: is_unbounded_array_v<T> is false.

The expression ​::​new (declval<void*>()) T(declval<Args>()...)is well-formed when treated as an unevaluated operand ([expr.context]).

Mandates: If is_array_v<T> is true, sizeof...(Args) is zero.

Effects: Equivalent to:if constexpr (is_array_v<T>) return ::new (voidify(*location)) T[1]();else return ::new (voidify(*location)) T(std::forward<Args>(args)...);

26.11.9 destroy [specialized.destroy]

template<class T> constexpr void destroy_at(T* location);namespace ranges { template<[destructible](concept.destructible#concept:destructible "18.4.10 Concept destructible [concept.destructible]") T> constexpr void destroy_at(T* location) noexcept;}

Effects:

• If T is an array type, equivalent todestroy(begin(*location), end(*location)).
• Otherwise, equivalent tolocation->~T().

template<class NoThrowForwardIterator> constexpr void destroy(NoThrowForwardIterator first, NoThrowForwardIterator last);

Effects: Equivalent to:for (; first != last; ++first) destroy_at(addressof(*first));

namespace ranges { template<[_nothrow-input-iterator_](#concept:nothrow-input-iterator "26.11.2 Special memory concepts [special.mem.concepts]") I, [_nothrow-sentinel-for_](#concept:nothrow-sentinel-for "26.11.2 Special memory concepts [special.mem.concepts]")<I> S> requires [destructible](concept.destructible#concept:destructible "18.4.10 Concept destructible [concept.destructible]")<iter_value_t<I>> constexpr I destroy(I first, S last) noexcept;template<[_nothrow-input-range_](#concept:nothrow-input-range "26.11.2 Special memory concepts [special.mem.concepts]") R> requires [destructible](concept.destructible#concept:destructible "18.4.10 Concept destructible [concept.destructible]")<range_value_t<R>> constexpr borrowed_iterator_t<R> destroy(R&& r) noexcept;}

Effects: Equivalent to:for (; first != last; ++first) destroy_at(addressof(*first));return first;

template<class NoThrowForwardIterator, class Size> constexpr NoThrowForwardIterator destroy_n(NoThrowForwardIterator first, Size n);

Effects: Equivalent to:for (; n > 0; (void)++first, --n) destroy_at(addressof(*first));return first;

namespace ranges { template<[_nothrow-input-iterator_](#concept:nothrow-input-iterator "26.11.2 Special memory concepts [special.mem.concepts]") I> requires [destructible](concept.destructible#concept:destructible "18.4.10 Concept destructible [concept.destructible]")<iter_value_t<I>> constexpr I destroy_n(I first, iter_difference_t<I> n) noexcept;}

Effects: Equivalent to:return destroy(counted_iterator(std::move(first), n), default_sentinel).base();