25 Algorithms library [algorithms]

25.11 Specialized <memory> algorithms [specialized.algorithms]

25.11.1 General [specialized.algorithms.general]

1
#
The contents specified in [specialized.algorithms] are declared in the header <memory>.
2
#
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.
3
#
[Note 1:
When invoked on ranges of potentially-overlapping subobjects ([intro.object]), the algorithms specified in [specialized.algorithms] result in undefined behavior.
— end note]
4
#
Some algorithms specified in [specialized.algorithms] make use of the exposition-only function voidify: template<class T> constexpr void* voidify(T& obj) noexcept { return const_cast<void*>(static_cast<const volatile void*>(addressof(obj))); }

25.11.2 Special memory concepts [special.mem.concepts]

1
#
Some algorithms in this subclause are constrained with the following exposition-only concepts:
🔗
template<class I> concept no-throw-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>>;
2
#
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.
3
#
[Note 1:
This concept allows some input_­iterator ([iterator.concept.input]) operations to throw exceptions.
— end note]
🔗
template<class S, class I> concept no-throw-sentinel-for = sentinel_for<S, I>; // exposition only
4
#
Types S and I model no-throw-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.
5
#
[Note 2:
This concept allows some sentinel_­for ([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-for<sentinel_t<R>, iterator_t<R>>;
6
#
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> && forward_iterator<I> && no-throw-sentinel-for<I, I>;
7
#
[Note 3:
This concept allows some forward_­iterator ([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>>;

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

🔗
template<class NoThrowForwardIterator> void uninitialized_default_construct(NoThrowForwardIterator first, NoThrowForwardIterator last);
1
#
Effects: Equivalent to: for (; first != last; ++first) ::new (voidify(*first)) typename iterator_traits<NoThrowForwardIterator>::value_type;
🔗
namespace ranges { template<no-throw-forward-iterator I, no-throw-sentinel-for<I> S> requires default_initializable<iter_value_t<I>> I uninitialized_default_construct(I first, S last); template<no-throw-forward-range R> requires default_initializable<range_value_t<R>> borrowed_iterator_t<R> uninitialized_default_construct(R&& r); }
2
#
Effects: Equivalent to: for (; first != last; ++first) ::new (voidify(*first)) remove_reference_t<iter_reference_t<I>>; return first;
🔗
template<class NoThrowForwardIterator, class Size> NoThrowForwardIterator uninitialized_default_construct_n(NoThrowForwardIterator first, Size n);
3
#
Effects: Equivalent to: for (; n > 0; (void)++first, --n) ::new (voidify(*first)) typename iterator_traits<NoThrowForwardIterator>::value_type; return first;
🔗
namespace ranges { template<no-throw-forward-iterator I> requires default_initializable<iter_value_t<I>> I uninitialized_default_construct_n(I first, iter_difference_t<I> n); }
4
#
Effects: Equivalent to: return uninitialized_default_construct(counted_iterator(first, n), default_sentinel).base();

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

🔗
template<class NoThrowForwardIterator> void uninitialized_value_construct(NoThrowForwardIterator first, NoThrowForwardIterator last);
1
#
Effects: Equivalent to: for (; first != last; ++first) ::new (voidify(*first)) typename iterator_traits<NoThrowForwardIterator>::value_type();
🔗
namespace ranges { template<no-throw-forward-iterator I, no-throw-sentinel-for<I> S> requires default_initializable<iter_value_t<I>> I uninitialized_value_construct(I first, S last); template<no-throw-forward-range R> requires default_initializable<range_value_t<R>> borrowed_iterator_t<R> uninitialized_value_construct(R&& r); }
2
#
Effects: Equivalent to: for (; first != last; ++first) ::new (voidify(*first)) remove_reference_t<iter_reference_t<I>>(); return first;
🔗
template<class NoThrowForwardIterator, class Size> NoThrowForwardIterator uninitialized_value_construct_n(NoThrowForwardIterator first, Size n);
3
#
Effects: Equivalent to: for (; n > 0; (void)++first, --n) ::new (voidify(*first)) typename iterator_traits<NoThrowForwardIterator>::value_type(); return first;
🔗
namespace ranges { template<no-throw-forward-iterator I> requires default_initializable<iter_value_t<I>> I uninitialized_value_construct_n(I first, iter_difference_t<I> n); }
4
#
Effects: Equivalent to: return uninitialized_value_construct(counted_iterator(first, n), default_sentinel).base();

25.11.5 uninitialized_­copy [uninitialized.copy]

🔗
template<class InputIterator, class NoThrowForwardIterator> NoThrowForwardIterator uninitialized_copy(InputIterator first, InputIterator last, NoThrowForwardIterator result);
1
#
Preconditions: does not overlap with [first, last).
2
#
Effects: Equivalent to: for (; first != last; ++result, (void) ++first) ::new (voidify(*result)) typename iterator_traits<NoThrowForwardIterator>::value_type(*first);
3
#
Returns: result.
🔗
namespace ranges { template<input_iterator I, sentinel_for<I> S1, no-throw-forward-iterator O, no-throw-sentinel-for<O> S2> requires constructible_from<iter_value_t<O>, iter_reference_t<I>> uninitialized_copy_result<I, O> uninitialized_copy(I ifirst, S1 ilast, O ofirst, S2 olast); template<input_­range IR, no-throw-forward-range OR> requires constructible_from<range_value_t<OR>, range_reference_t<IR>> uninitialized_copy_result<borrowed_iterator_t<IR>, borrowed_iterator_t<OR>> uninitialized_copy(IR&& in_range, OR&& out_range); }
4
#
Preconditions: [ofirst, olast) does not overlap with [ifirst, ilast).
5
#
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> NoThrowForwardIterator uninitialized_copy_n(InputIterator first, Size n, NoThrowForwardIterator result);
6
#
Preconditions: does not overlap with .
7
#
Effects: Equivalent to: for ( ; n > 0; ++result, (void) ++first, --n) ::new (voidify(*result)) typename iterator_traits<NoThrowForwardIterator>::value_type(*first);
8
#
Returns: result.
🔗
namespace ranges { template<input_iterator I, no-throw-forward-iterator O, no-throw-sentinel-for<O> S> requires constructible_from<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); }
9
#
Preconditions: [ofirst, olast) does not overlap with .
10
#
Effects: Equivalent to: auto t = uninitialized_copy(counted_iterator(ifirst, n), default_sentinel, ofirst, olast); return {std::move(t.in).base(), t.out};

25.11.6 uninitialized_­move [uninitialized.move]

🔗
template<class InputIterator, class NoThrowForwardIterator> NoThrowForwardIterator uninitialized_move(InputIterator first, InputIterator last, NoThrowForwardIterator result);
1
#
Preconditions: does not overlap with [first, last).
2
#
Effects: Equivalent to: for (; first != last; (void)++result, ++first) ::new (voidify(*result)) typename iterator_traits<NoThrowForwardIterator>::value_type(std::move(*first)); return result;
🔗
namespace ranges { template<input_iterator I, sentinel_for<I> S1, no-throw-forward-iterator O, no-throw-sentinel-for<O> S2> requires constructible_from<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<input_­range IR, no-throw-forward-range OR> requires constructible_from<range_value_t<OR>, range_rvalue_reference_t<IR>> uninitialized_move_result<borrowed_iterator_t<IR>, borrowed_iterator_t<OR>> uninitialized_move(IR&& in_range, OR&& out_range); }
3
#
Preconditions: [ofirst, olast) does not overlap with [ifirst, ilast).
4
#
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};
5
#
[Note 1:
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 NoThrowForwardIterator> pair<InputIterator, NoThrowForwardIterator> uninitialized_move_n(InputIterator first, Size n, NoThrowForwardIterator result);
6
#
Preconditions: does not overlap with .
7
#
Effects: Equivalent to: for (; n > 0; ++result, (void) ++first, --n) ::new (voidify(*result)) typename iterator_traits<NoThrowForwardIterator>::value_type(std::move(*first)); return {first, result};
🔗
namespace ranges { template<input_iterator I, no-throw-forward-iterator O, no-throw-sentinel-for<O> S> requires constructible_from<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); }
8
#
Preconditions: [ofirst, olast) does not overlap with .
9
#
Effects: Equivalent to: auto t = uninitialized_move(counted_iterator(ifirst, n), default_sentinel, ofirst, olast); return {std::move(t.in).base(), t.out};
10
#
[Note 2:
If an exception is thrown, some objects in the range are left in a valid but unspecified state.
— end note]

25.11.7 uninitialized_­fill [uninitialized.fill]

🔗
template<class NoThrowForwardIterator, class T> void uninitialized_fill(NoThrowForwardIterator first, NoThrowForwardIterator last, const T& x);
1
#
Effects: Equivalent to: for (; first != last; ++first) ::new (voidify(*first)) typename iterator_traits<NoThrowForwardIterator>::value_type(x);
🔗
namespace ranges { template<no-throw-forward-iterator I, no-throw-sentinel-for<I> S, class T> requires constructible_from<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_from<range_value_t<R>, const T&> borrowed_iterator_t<R> uninitialized_fill(R&& r, const T& x); }
2
#
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> NoThrowForwardIterator uninitialized_fill_n(NoThrowForwardIterator first, Size n, const T& x);
3
#
Effects: Equivalent to: for (; n--; ++first) ::new (voidify(*first)) typename iterator_traits<NoThrowForwardIterator>::value_type(x); return first;
🔗
namespace ranges { template<no-throw-forward-iterator I, class T> requires constructible_from<iter_value_t<I>, const T&> I uninitialized_fill_n(I first, iter_difference_t<I> n, const T& x); }
4
#
Effects: Equivalent to: return uninitialized_fill(counted_iterator(first, n), default_sentinel, x).base();

25.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); }
1
#
Constraints: The expression ​::​new (declval<void*>()) T(declval<Args>()...) is well-formed when treated as an unevaluated operand.
2
#
Effects: Equivalent to: return ::new (voidify(*location)) T(std::forward<Args>(args)...);

25.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; }
1
#
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);
2
#
Effects: Equivalent to: for (; first != last; ++first) destroy_at(addressof(*first));
🔗
namespace ranges { template<no-throw-input-iterator I, no-throw-sentinel-for<I> S> requires destructible<iter_value_t<I>> constexpr I destroy(I first, S last) noexcept; template<no-throw-input-range R> requires destructible<range_value_t<R>> constexpr borrowed_iterator_t<R> destroy(R&& r) noexcept; }
3
#
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);
4
#
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>> constexpr I destroy_n(I first, iter_difference_t<I> n) noexcept; }
5
#
Effects: Equivalent to: return destroy(counted_iterator(first, n), default_sentinel).base();