19 General utilities library [utilities]

19.10 Memory [memory]

19.10.11 Specialized algorithms [specialized.algorithms]

1
#
Throughout this subclause, the names of template parameters are used to express type requirements for those algorithms defined directly in namespace std.
  • (1.1)
    If an algorithm's template parameter is named InputIterator, the template argument shall meet the Cpp17InputIterator requirements ([input.iterators]).
  • (1.2)
    If an algorithm's template parameter is named ForwardIterator, the template argument shall meet the Cpp17ForwardIterator requirements ([forward.iterators]), and is required to have the property that no exceptions are thrown from increment, assignment, comparison, or indirection through valid iterators.
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
#
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.
4
#
The following additional requirements apply for those algorithms defined in namespace std::ranges:
  • (4.1)
    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.
  • (4.2)
    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.
  • (4.3)
    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
     ]
5
#
[ 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
 ]
6
#
Some algorithms defined in this clause make use of the exposition-only function voidify: 
template<class T>
  void* voidify(T& ptr) noexcept {
    return const_cast<void*>(static_cast<const volatile void*>(addressof(ptr)));
  }

19.10.11.1 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 InputIterator<I> && is_lvalue_reference_v<iter_reference_t<I>> && Same<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
:
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
4
#
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.
5
#
[ 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>>;
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> && ForwardIterator<I> && no-throw-sentinel<I, I>;
7
#
[ 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>>;

19.10.11.2 addressof [specialized.addressof]

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

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

🔗
template<class ForwardIterator> void uninitialized_default_construct(ForwardIterator first, ForwardIterator last);
1
#
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); }
2
#
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);
3
#
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); }
4
#
Effects: Equivalent to: 
return uninitialized_default_construct(counted_iterator(first, n),
                                       default_sentinel).base();

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

🔗
template<class ForwardIterator> void uninitialized_value_construct(ForwardIterator first, ForwardIterator last);
1
#
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); }
2
#
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);
3
#
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); }
4
#
Effects: Equivalent to: 
return uninitialized_value_construct(counted_iterator(first, n),
                                     default_sentinel).base();

19.10.11.5 uninitialized_­copy [uninitialized.copy]

🔗
template<class InputIterator, class ForwardIterator> ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);
1
#
Expects: [result, (last - first)) shall not overlap with [first, last).
2
#
Effects: Equivalent to: 
for (; first != last; ++result, (void) ++first)
  ::new (voidify(*result))
    typename iterator_traits<ForwardIterator>::value_type(*first);
3
#
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); }
4
#
Expects: [ofirst, olast) shall 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 {ifirst, ofirst};
🔗
template<class InputIterator, class Size, class ForwardIterator> ForwardIterator uninitialized_copy_n(InputIterator first, Size n, ForwardIterator result);
6
#
Expects: [result, n) shall not overlap with [first, n).
7
#
Effects: Equivalent to: 
for ( ; n > 0; ++result, (void) ++first, --n) {
  ::new (voidify(*result))
    typename iterator_traits<ForwardIterator>::value_type(*first);
}
8
#
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); }
9
#
Expects: [ofirst, olast) shall not overlap with [ifirst, n).
10
#
Effects: Equivalent to: 
auto t = uninitialized_copy(counted_iterator(ifirst, n),
                            default_sentinel, ofirst, olast);
return {t.in.base(), t.out};

19.10.11.6 uninitialized_­move [uninitialized.move]

🔗
template<class InputIterator, class ForwardIterator> ForwardIterator uninitialized_move(InputIterator first, InputIterator last, ForwardIterator result);
1
#
Expects: [result, (last - first)) shall not overlap with [first, last).
2
#
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); }
3
#
Expects: [ofirst, olast) shall 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 {ifirst, ofirst};
5
#
[ 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);
6
#
Expects: [result, n) shall not overlap with [first, n).
7
#
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); }
8
#
Expects: [ofirst, olast) shall not overlap with [ifirst, n).
9
#
Effects: Equivalent to: 
auto t = uninitialized_move(counted_iterator(ifirst, n),
                            default_sentinel, ofirst, olast);
return {t.in.base(), t.out};
10
#
[ Note
:
If an exception is thrown, some objects in the range [first, n) are left in a valid but unspecified state.
— end note
 ]

19.10.11.7 uninitialized_­fill [uninitialized.fill]

🔗
template<class ForwardIterator, class T> void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);
1
#
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);
2
#
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); }
3
#
Effects: Equivalent to: 
return uninitialized_fill(counted_iterator(first, n), default_sentinel, x).base();

19.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; }
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 ForwardIterator> void destroy(ForwardIterator first, ForwardIterator last);
2
#
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; }
3
#
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);
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>> I destroy_n(I first, iter_difference_t<I> n) noexcept; }
5
#
Effects: Equivalent to: 
return destroy(counted_iterator(first, n), default_sentinel).base();