26 Algorithms library [algorithms]

26.11 Specialized <memory> algorithms [specialized.algorithms]

26.11.1 General [specialized.algorithms.general]

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

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 = // exposition only
  input_iterator<I> &&
  is_lvalue_reference_v<iter_reference_t<I>> &&
  same_as<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.

[Note 1:

This concept allows some input_iterator ([iterator.concept.input]) operations to throw exceptions.

— end note]

🔗

template<class S, class I>
concept nothrow-sentinel-for = sentinel_for<S, I>; // exposition only

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

[Note 2:

This concept allows some sentinel_for ([iterator.concept.sentinel]) operations to throw exceptions.

— end note]

🔗

template<class R>
concept nothrow-input-range = // exposition only
  range<R> &&
  nothrow-input-iterator<iterator_t<R>> &&
  nothrow-sentinel-for<sentinel_t<R>, iterator_t<R>>;

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

🔗

template<class I>
concept nothrow-forward-iterator = // exposition only
  nothrow-input-iterator<I> &&
  forward_iterator<I> &&
  nothrow-sentinel-for<I, I>;

[Note 3:

This concept allows some forward_iterator ([iterator.concept.forward]) operations to throw exceptions.

— end note]

🔗

template<class R>
concept nothrow-forward-range = // exposition only
  nothrow-input-range<R> &&
  nothrow-forward-iterator<iterator_t<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)) typename iterator_traits<NoThrowForwardIterator>::value_type;

🔗

namespace ranges {
  template<nothrow-forward-iterator I, nothrow-sentinel-for<I> S>
    requires default_initializable<iter_value_t<I>>
    constexpr I uninitialized_default_construct(I first, S last);
  template<nothrow-forward-range R>
    requires default_initializable<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)) typename iterator_traits<NoThrowForwardIterator>::value_type; return first;

🔗

namespace ranges {
  template<nothrow-forward-iterator I>
    requires default_initializable<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)) typename iterator_traits<NoThrowForwardIterator>::value_type();

🔗

namespace ranges {
  template<nothrow-forward-iterator I, nothrow-sentinel-for<I> S>
    requires default_initializable<iter_value_t<I>>
    constexpr I uninitialized_value_construct(I first, S last);
  template<nothrow-forward-range R>
    requires default_initializable<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)) typename iterator_traits<NoThrowForwardIterator>::value_type(); return first;

🔗

namespace ranges {
  template<nothrow-forward-iterator I>
    requires default_initializable<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:

result + [0, (last - first))

does not overlap with [first, last).

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

Returns: result.

🔗

namespace ranges {
  template<input_iterator I, sentinel_for<I> S1,
           nothrow-forward-iterator O, nothrow-sentinel-for<O> S2>
    requires constructible_from<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 IR, nothrow-forward-range OR>
    requires constructible_from<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:

result + [0, n)

does not overlap with

first + [0, n)

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

Returns: result.

🔗

namespace ranges {
  template<input_iterator I, nothrow-forward-iterator O, nothrow-sentinel-for<O> S>
    requires constructible_from<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

ifirst + [0, n)

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:

result + [0, (last - first))

does not overlap with [first, last).

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

🔗

namespace ranges {
  template<input_iterator I, sentinel_for<I> S1,
           nothrow-forward-iterator O, nothrow-sentinel-for<O> S2>
    requires constructible_from<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 IR, nothrow-forward-range OR>
    requires constructible_from<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:

result + [0, n)

does not overlap with

first + [0, n)

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

🔗

namespace ranges {
  template<input_iterator I, nothrow-forward-iterator O, nothrow-sentinel-for<O> S>
    requires constructible_from<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

ifirst + [0, n)

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 range

ifirst + [0, n)

are 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)) typename iterator_traits<NoThrowForwardIterator>::value_type(x);

🔗

namespace ranges {
  template<nothrow-forward-iterator I, nothrow-sentinel-for<I> S, class T>
    requires constructible_from<iter_value_t<I>, const T&>
    constexpr I uninitialized_fill(I first, S last, const T& x);
  template<nothrow-forward-range R, class T>
    requires constructible_from<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)) typename iterator_traits<NoThrowForwardIterator>::value_type(x); return first;

🔗

namespace ranges {
  template<nothrow-forward-iterator I, class T>
    requires constructible_from<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 T>
    constexpr void destroy_at(T* location) noexcept;
}

Effects:

(1.1)
If T is an array type, equivalent to destroy(begin(*location), end(*location)).
(1.2)
Otherwise, equivalent to location->~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 I, nothrow-sentinel-for<I> S>
    requires destructible<iter_value_t<I>>
    constexpr I destroy(I first, S last) noexcept;
  template<nothrow-input-range R>
    requires 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 I>
    requires 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();