20 General utilities library [utilities]

20.10 Memory [memory]

20.10.11 Specialized algorithms [specialized.algorithms]

Throughout this subclause, the names of template parameters are used to express type requirements for those algorithms defined directly in namespace std.
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.
In the description of the algorithms, operator - is used for some of the iterator categories for which it need not be defined.
In these cases, the value of the expression b - a is the number of increments of a needed to make bool(a == b) be true.
The following additional requirements apply for those algorithms defined in namespace std::ranges:
  • The entities defined in the std::ranges namespace in this subclause are not found by argument-dependent name lookup ([basic.lookup.argdep]). When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a function call ([expr.call]), they inhibit argument-dependent name lookup.
  • Overloads of algorithms that take Range arguments ([range.range]) behave as if they are implemented by calling ranges::begin and ranges::end on the Range(s) and dispatching to the overload that takes separate iterator and sentinel arguments.
  • The number and order of deducible template parameters for algorithm declarations is unspecified, except where explicitly stated otherwise.
    [Note
    : Consequently, these algorithms may not be called with explicitly-specified template argument lists. —end note
    ]
[Note
:
When invoked on ranges of potentially overlapping subobjects ([intro.object]), the algorithms specified in this subclause [specialized.algorithms] result in undefined behavior.
end note
]
Some algorithms defined in this clause make use of the exposition-only function voidify:
template<class T>
  void* voidify(T& obj) noexcept {
    return const_cast<void*>(static_cast<const volatile void*>(addressof(obj)));
  }

20.10.11.1 Special memory concepts [special.mem.concepts]

Some algorithms in this subclause are constrained with the following exposition-only concepts:
template<class I> concept no-throw-input-iterator = // exposition only InputIterator<I> && is_lvalue_reference_v<iter_reference_t<I>> && Same<remove_cvref_t<iter_reference_t<I>>, iter_value_t<I>>;
A type I models no-throw-input-iterator only if no exceptions are thrown from increment, copy construction, move construction, copy assignment, move assignment, or indirection through valid iterators.
[Note
:
This concept allows some InputIterator ([iterator.concept.input]) operations to throw exceptions.
end note
]
template<class S, class I> concept no-throw-sentinel = Sentinel<S, I>; // exposition only
Types S and I model no-throw-sentinel 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
:
This concept allows some Sentinel ([iterator.concept.sentinel]) operations to throw exceptions.
end note
]
template<class R> concept no-throw-input-range = // exposition only Range<R> && no-throw-input-iterator<iterator_t<R>> && no-throw-sentinel<sentinel_t<R>, iterator_t<R>>;
A type R models no-throw-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 no-throw-forward-iterator = // exposition only no-throw-input-iterator<I> && ForwardIterator<I> && no-throw-sentinel<I, I>;
[Note
:
This concept allows some ForwardIterator ([iterator.concept.forward]) operations to throw exceptions.
end note
]
template<class R> concept no-throw-forward-range = // exposition only no-throw-input-range<R> && no-throw-forward-iterator<iterator_t<R>>;

20.10.11.2 addressof [specialized.addressof]

template<class T> constexpr T* addressof(T& r) noexcept;
Returns: The actual address of the object or function referenced by r, even in the presence of an overloaded operator&.
Remarks: An expression addressof(E) is a constant subexpression if E is an lvalue constant subexpression.

20.10.11.3 uninitialized_­default_­construct [uninitialized.construct.default]

template<class ForwardIterator> void uninitialized_default_construct(ForwardIterator first, ForwardIterator last);
Effects: Equivalent to:
for (; first != last; ++first)
  ::new (voidify(*first))
    typename iterator_traits<ForwardIterator>::value_type;
namespace ranges { template<no-throw-forward-iterator I, no-throw-sentinel<I> S> requires DefaultConstructible<iter_value_t<I>> I uninitialized_default_construct(I first, S last); template<no-throw-forward-range R> requires DefaultConstructible<iter_value_t<iterator_t<R>>> safe_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 ForwardIterator, class Size> ForwardIterator uninitialized_default_construct_n(ForwardIterator first, Size n);
Effects: Equivalent to:
for (; n > 0; (void)++first, --n)
  ::new (voidify(*first))
    typename iterator_traits<ForwardIterator>::value_type;
return first;
namespace ranges { template<no-throw-forward-iterator I> requires DefaultConstructible<iter_value_t<I>> 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();

20.10.11.4 uninitialized_­value_­construct [uninitialized.construct.value]

template<class ForwardIterator> void uninitialized_value_construct(ForwardIterator first, ForwardIterator last);
Effects: Equivalent to:
for (; first != last; ++first)
  ::new (voidify(*first))
    typename iterator_traits<ForwardIterator>::value_type();
namespace ranges { template<no-throw-forward-iterator I, no-throw-sentinel<I> S> requires DefaultConstructible<iter_value_t<I>> I uninitialized_value_construct(I first, S last); template<no-throw-forward-range R> requires DefaultConstructible<iter_value_t<iterator_t<R>>> safe_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 ForwardIterator, class Size> ForwardIterator uninitialized_value_construct_n(ForwardIterator first, Size n);
Effects: Equivalent to:
for (; n > 0; (void)++first, --n)
  ::new (voidify(*first))
    typename iterator_traits<ForwardIterator>::value_type();
return first;
namespace ranges { template<no-throw-forward-iterator I> requires DefaultConstructible<iter_value_t<I>> 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();

20.10.11.5 uninitialized_­copy [uninitialized.copy]

template<class InputIterator, class ForwardIterator> ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);
Expects: [result, (last - first)) shall not overlap with [first, last).
Effects: Equivalent to:
for (; first != last; ++result, (void) ++first)
  ::new (voidify(*result))
    typename iterator_traits<ForwardIterator>::value_type(*first);
Returns: result.
namespace ranges { template<InputIterator I, Sentinel<I> S1, no-throw-forward-iterator O, no-throw-sentinel<O> S2> requires Constructible<iter_value_t<O>, iter_reference_t<I>> uninitialized_copy_result<I, O> uninitialized_copy(I ifirst, S1 ilast, O ofirst, S2 olast); template<InputRange IR, no-throw-forward-range OR> requires Constructible<iter_value_t<iterator_t<OR>>, iter_reference_t<iterator_t<IR>>> uninitialized_copy_result<safe_iterator_t<IR>, safe_iterator_t<OR>> uninitialized_copy(IR&& input_range, OR&& output_range); }
Expects: [ofirst, olast) shall 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 {ifirst, ofirst};
template<class InputIterator, class Size, class ForwardIterator> ForwardIterator uninitialized_copy_n(InputIterator first, Size n, ForwardIterator result);
Expects: [result, n) shall not overlap with [first, n).
Effects: Equivalent to:
for ( ; n > 0; ++result, (void) ++first, --n) {
  ::new (voidify(*result))
    typename iterator_traits<ForwardIterator>::value_type(*first);
}
Returns: result.
namespace ranges { template<InputIterator I, no-throw-forward-iterator O, no-throw-sentinel<O> S> requires Constructible<iter_value_t<O>, iter_reference_t<I>> uninitialized_copy_n_result<I, O> uninitialized_copy_n(I ifirst, iter_difference_t<I> n, O ofirst, S olast); }
Expects: [ofirst, olast) shall not overlap with [ifirst, n).
Effects: Equivalent to:
auto t = uninitialized_copy(counted_iterator(ifirst, n),
                            default_sentinel, ofirst, olast);
return {t.in.base(), t.out};

20.10.11.6 uninitialized_­move [uninitialized.move]

template<class InputIterator, class ForwardIterator> ForwardIterator uninitialized_move(InputIterator first, InputIterator last, ForwardIterator result);
Expects: [result, (last - first)) shall not overlap with [first, last).
Effects: Equivalent to:
for (; first != last; (void)++result, ++first)
  ::new (voidify(*result))
    typename iterator_traits<ForwardIterator>::value_type(std::move(*first));
return result;
namespace ranges { template<InputIterator I, Sentinel<I> S1, no-throw-forward-iterator O, no-throw-sentinel<O> S2> requires Constructible<iter_value_t<O>, iter_rvalue_reference_t<I>> uninitialized_move_result<I, O> uninitialized_move(I ifirst, S1 ilast, O ofirst, S2 olast); template<InputRange IR, no-throw-forward-range OR> requires Constructible<iter_value_t<iterator_t<OR>>, iter_rvalue_reference_t<iterator_t<IR>>> uninitialized_move_result<safe_iterator_t<IR>, safe_iterator_t<OR>> uninitialized_move(IR&& input_range, OR&& output_range); }
Expects: [ofirst, olast) shall 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 {ifirst, ofirst};
[Note
:
If an exception is thrown, some objects in the range [first, last) are left in a valid, but unspecified state.
end note
]
template<class InputIterator, class Size, class ForwardIterator> pair<InputIterator, ForwardIterator> uninitialized_move_n(InputIterator first, Size n, ForwardIterator result);
Expects: [result, n) shall not overlap with [first, n).
Effects: Equivalent to:
for (; n > 0; ++result, (void) ++first, --n)
  ::new (voidify(*result))
    typename iterator_traits<ForwardIterator>::value_type(std::move(*first));
return {first,result};
namespace ranges { template<InputIterator I, no-throw-forward-iterator O, no-throw-sentinel<O> S> requires Constructible<iter_value_t<O>, iter_rvalue_reference_t<I>> uninitialized_move_n_result<I, O> uninitialized_move_n(I ifirst, iter_difference_t<I> n, O ofirst, S olast); }
Expects: [ofirst, olast) shall not overlap with [ifirst, n).
Effects: Equivalent to:
auto t = uninitialized_move(counted_iterator(ifirst, n),
                            default_sentinel, ofirst, olast);
return {t.in.base(), t.out};
[Note
:
If an exception is thrown, some objects in the range [first, n) are left in a valid but unspecified state.
end note
]

20.10.11.7 uninitialized_­fill [uninitialized.fill]

template<class ForwardIterator, class T> void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);
Effects: Equivalent to:
for (; first != last; ++first)
  ::new (voidify(*first))
    typename iterator_traits<ForwardIterator>::value_type(x);
namespace ranges { template<no-throw-forward-iterator I, no-throw-sentinel<I> S, class T> requires Constructible<iter_value_t<I>, const T&> I uninitialized_fill(I first, S last, const T& x); template<no-throw-forward-range R, class T> requires Constructible<iter_value_t<iterator_t<R>>, const T&> safe_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 ForwardIterator, class Size, class T> ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T& x);
Effects: Equivalent to:
for (; n--; ++first)
  ::new (voidify(*first))
    typename iterator_traits<ForwardIterator>::value_type(x);
return first;
namespace ranges { template<no-throw-forward-iterator I, class T> requires Constructible<iter_value_t<I>, const T&> 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();

20.10.11.8 destroy [specialized.destroy]

template<class T> void destroy_at(T* location); namespace ranges { template<Destructible T> void destroy_at(T* location) noexcept; }
Effects:
  • If T is an array type, equivalent to destroy(begin(*location), end(*location)).
  • Otherwise, equivalent to location->~T().
template<class ForwardIterator> void destroy(ForwardIterator first, ForwardIterator last);
Effects: Equivalent to:
for (; first!=last; ++first)
  destroy_at(addressof(*first));
namespace ranges { template<no-throw-input-iterator I, no-throw-sentinel<I> S> requires Destructible<iter_value_t<I>> I destroy(I first, S last) noexcept; template<no-throw-input-range R> requires Destructible<iter_value_t<iterator_t<R>>> safe_iterator_t<R> destroy(R&& r) noexcept; }
Effects: Equivalent to:
for (; first != last; ++first)
  destroy_at(addressof(*first));
return first;
template<class ForwardIterator, class Size> ForwardIterator destroy_n(ForwardIterator first, Size n);
Effects: Equivalent to:
for (; n > 0; (void)++first, --n)
  destroy_at(addressof(*first));
return first;
namespace ranges { template<no-throw-input-iterator I> requires Destructible<iter_value_t<I>> I destroy_n(I first, iter_difference_t<I> n) noexcept; }
Effects: Equivalent to:
return destroy(counted_iterator(first, n), default_sentinel).base();