1 Introduction

P2786 is currently making progress through EWG and LEWG. In Poland, LEWG expressed a strong desire for that language feature to come with a proper user-facing library interface. This paper proposes such an interface. That interface is heavily influenced by the uninitialized algorithms that were originally proposed in P1144 which, after implementation experience in libc++, seem to be almost exactly what we need.

This paper aims to provide the high-level algorithms that all programmers will want to use, while purposefully not touching on some of the more contentious design points of P2786/P1144. The high-level algorithms proposed in this paper are compatible with essentially any definition of “trivial relocation” we might introduce in the language in C++26 or later.

2 Motivation

Today, many algorithms and containers use some flavor of assignment, either as an implementation detail or as part of their API promise. In cases where the use of assignment is merely an implementation detail, writing the code in terms of relocation can often result in cleaner code and improved performance (since move-construction is often faster than move-assignment).

Furthermore, in a future where the language itself provides a definition of relocation (and in particular trivial relocation), algorithms and containers written in terms of relocation today would benefit from a massive speedup for trivially relocatable types without requiring any change. Indeed, the algorithms introduced in this paper boil down to memmove (or memcpy if we can prove the absence of overlap) in trivial cases, which are fairly common.

3 Proposal

We propose adding algorithms std::uninitialized_relocate, std::uninitialized_relocate_n, and std::uninitialized_relocate_backward. We also add the equivalent ranges:: functions and the parallel algorithm overloads. At a high level, these algorithms relocate a range of objects from one memory location to another, which is a very useful primitive when writing containers and algorithms.

However, the library interface proposed here is intentionally independent of the details of the underlying language feature.

Design points:

• These functions behave similarly to the other uninitialized algorithms like std::uninitialized_copy, with the difference that the new proposed relocation algorithms support overlapping input/output ranges like std::move and std::move_backward. That is necessary in order to support most use cases where one is relocating a range a bit “to the right” or a bit “to the left” of its current location.
• Unlike P2786 which talks of trivial relocation, these algorithms talk of relocation in the general sense. This is because it’s generally more useful (and easier!) to write an algorithm or data structure operation in terms of general relocation, even if it is not trivial (in which case it is move + destroy). Even non-trivial relocation is usually faster than the equivalent assignment-based algorithm. By encouraging users to write their code in terms of general relocation today, we are preparing the terrain for when the language gets a notion of trivial relocation, and in the meantime we let implementations optimize under the as-if rule.
• The algorithms provide an exception guarantee that in case of an exception, the whole source range is destroyed and the whole destination range as well. Otherwise, the ranges would contain an unknown number of alive objects, making it impossible for the caller to perform a clean up. This turns out to work well with what e.g. std::vector::insert requires in order to provide the basic exception safety guarantee (see the examples below).
• The algorithms accept input_iterators (or bidirectional_iterators for the backward variant) for the input range. This iterator category is sufficient to implement these algorithms properly. However, it does mean that the range overlap precondition cannot be checked at runtime for some iterator categories. In practice, we would expect an implementation that wishes to check this precondition to do so whenever the input range is at least random access, which should be the vast majority of use cases.
• The algorithms accept forward_iterators for the output range, which is necessary to perform cleanup if an exception is thrown.
• The proposed API facilities are intended to be as consistent as possible with existing uninitialized algorithms, with the few differences being a direct consequence of the fact that the source range does not contain any elements after performing the operation.

4 Usage examples

In these examples, we ignore allocator support for simplicity, and we use iterator instead of const_iterator as the parameter types to lighten the code. The “real” code for implementing these functions does not look meaningfully different.

4.1 vector::emplace / vector::insert

template <class ...Args>
constexpr iterator
vector<T>::emplace(iterator position, Args&&... args) {
  if [[unlikely]] (size() == capacity()) {
    // slow path where we grow the vector
  }

  if (position == end()) {
    std::construct_at(std::to_address(position),
                      std::forward<Args>(args)...);
    ++end_;
  } else {
    T tmp(std::forward<Args>(args)...);

    // Create a gap at the end by moving the last
    // element into the "new last position".
    std::construct_at(std::to_address(end()),
                      std::move(back()));
    ++end_;

    // The element before the last one is moved-from:
    // shift everything else by one position to the
    // right to open a gap at the insert location.
    std::move_backward(position, end() - 2, end() - 1);

    // Now there's a gap at the insert location, move the
    // new element into it.
    *position = std::move(tmp);
  }
  return position;
}

template <class ...Args>
constexpr iterator
vector<T>::emplace(iterator position, Args&&... args) {
  if [[unlikely]] (size() == capacity()) {
    // slow path where we grow the vector
  }

  if (position == end()) {
    std::construct_at(std::to_address(position),
                      std::forward<Args>(args)...);
    ++end_;
  } else {
    T tmp(std::forward<Args>(args)...);

    // Create a gap inside the vector by relocating
    // everything to the right.
    try {
      std::uninitialized_relocate_backward(position, end(),
                                           end() + 1);
    } catch (...) {
      // basic guarantee: vector lost its tail
      end_ = std::to_address(position);
      throw;
    }

    // Move-construct the new value into the gap created above.
    try {
      std::construct_at(std::to_address(position), std::move(tmp));
    } catch (...) {
      // basic guarantee: vector lost its tail
      std::destroy(position + 1, end() + 1);
      end_ = std::to_address(position);
      throw;
    }

    ++end_;
  }
  return position;
}

A few things are worth noting:

• The relocation-based implementation looks more complicated than the assignment-based one, but in reality the complexity only stems from exception handling. The algorithm is conceptually simpler because we just relocate things around instead of creating artificial gaps that contain moved-from objects, like in the assignment-based one.
• Both implementations provide the basic exception safety guarantee, but they provide it differently. After an exception, the assignment-based implementation may leave elements in the [position, end()) range in a moved-from state, and the vector size may or may not have been incremented by 1. Whether this is actually the case or not depends on which operation exactly throws. Either way, the user has no direct means to know which elements have been left in a moved-from state. The relocation-based implementation instead ends up with the elements in [position, end()) being erased from the vector. It’s unclear whether one behavior is really superior over the other, but both are conforming.
• There is no mention of trivial relocation in the implementation. We relocate elements even when that is not equivalent to std::memcpy (or whatever the language definition would be).
• An implementation that considers the usage of move-assignment to be part of the function’s API may want to preserve that behavior, in which case the relocating code path may be guarded by something like P2786’s is_replaceable_v<T> (and otherwise fallback to move-assignment). In the absence of is_replaceable, a conservative implementation could use std::is_trivially_copyable as a guard.

4.2 vector::erase

constexpr iterator
vector<T>::erase(iterator first, iterator last) {
  if (first == last)
    return last;

  auto new_end = std::move(last, end(), first);
  std::destroy(new_end, end());

  end_ -= (last - first);
  return first;
}

constexpr iterator
vector<T>::erase(iterator first, iterator last) {
  if (first == last)
    return last;

  // Destroy the range being erased and relocate the
  // tail of the vector into the created gap.
  std::destroy(first, last);
  std::uninitialized_relocate(last, end(), first);

  end_ -= (last - first);
  return first;
}

Things worth noting:

• Again, there is no mention of trivial relocation above, since we write the algorithm in term of general relocation.
• Like for vector::emplace, an implementation that considers the usage of move-assignment to be part of the function’s API may want to preserve that behavior by further constraining the usage of relocation.
• Pedantically, the relocation-based implementation violates an exception constraint on std::vector::erase. The current specification requires vector::erase not to throw an exception unless T’s move-assignment operator throws. The implementation above can also throw if the move-constructor throws. We view this as an overspecification in the Standard that could be relaxed – this is probably an artifact of the fact that implementations were assumed to use assignment. To make the definition above pedantically correct, we should only use relocation when is_nothrow_move_constructible<T> is satisfied, and otherwise use assignment.

4.3 vector::emplace_back / vector::push_back

Note that the vector growth policy presented here is more naive than what std::vector typically does. Also keep in mind that we must provide the strong exception safety guarantee here.

template <class ...Args>
constexpr reference
vector<T>::emplace_back(Args&& ...args) {
  if [[likely]] (size() < capacity()) {
    std::construct_at(std::to_address(end()),
                      std::forward<Args>(args)...);
    ++end_;
    return back();
  }

  // Move or copy all the elements into a large
  // enough vector.
  vector<T> tmp;
  tmp.reserve((size() + 1) * 2);
  for (auto& element : *this) {
    [[assume(tmp.size() < tmp.capacity())]];
    tmp.emplace_back(std::move_if_noexcept(element));
  }

  [[assume(tmp.size() < tmp.capacity())]];
  tmp.emplace_back(std::forward<Args>(args)...);

  swap(tmp);
  return back();
}

template <class ...Args>
constexpr reference
vector<T>::emplace_back(Args&& ...args) {
  if [[likely]] (size() < capacity()) {
    std::construct_at(std::to_address(end()),
                      std::forward<Args>(args)...);
    ++end_;
    return back();
  }

  // Relocate all the elements into a large enough vector,
  // or copy if moving might throw.
  vector<T> tmp;
  tmp.reserve((size() + 1) * 2);
  if constexpr (is_nothrow_move_constructible_v<T>) {
    tmp.end_ = std::uninitialized_relocate(begin(), end(), tmp.begin_);
  } else {
    for (auto& element : *this) {
      [[assume(tmp.size() < tmp.capacity())]];
      tmp.emplace_back(element);
    }
  }

  // At this point, the original contents of the vector are in tmp, which is large enough.
  // Construct the new last element.
  try {
    [[assume(tmp.size() < tmp.capacity())]];
    tmp.emplace_back(std::forward<Args>(args)...);
  } catch (...) {
    swap(tmp);
    throw;
  }

  swap(tmp);
  return back();
}

Things worth noting:

• Again, there is no mention of trivial relocation: we write the algorithm based on general relocation.
• The above implementation omits to support the case where args... is in fact a single object located inside the vector we’re inserting in. Supporting that essentially requires creating a temporary value or constructing the new element before we start moving from the current vector, but does not meaningfully change the code.

5 Compatibility with trivial relocation proposals

If we had trivial relocation in the language, these algorithms would not need to change significantly, assuming that trivial relocation is equivalent to move + destroy when both are valid. We can’t imagine a trivial relocation design where that wouldn’t be the case.

If C++ gets a notion of trivial relocation that increases the expressive power over move + destroy (like P2786), then these uninitialized algorithms should be slightly generalized to support types that are not movable but that are still trivially relocatable. Thus, these algorithms would be able to operate either on types that are movable, or on types that are not movable but trivially relocatable instead. That would be a small backwards compatible change.

6 Wording

6.1 [algorithms.requirements]

Modify 26.2 [algorithms.requirements] as shown:

• (4.?) If an algorithm’s template parameter is named InputIterator, InputIterator1, or InputIterator2, or NoThrowInputIterator, the template argument shall meet the Cpp17InputIterator requirements ([input.iterators]).
• (4.?) If an algorithm’s template parameter is named OutputIterator, OutputIterator1, or OutputIterator2, the template argument shall meet the Cpp17OutputIterator requirements ([output.iterators]).
• (4.?) If an algorithm’s template parameter is named ForwardIterator, ForwardIterator1, ForwardIterator2, or NoThrowForwardIterator, NoThrowForwardIterator1, or NoThrowForwardIterator2, the template argument shall meet the Cpp17ForwardIterator requirements ([forward.iterators]) if it is required to be a mutable iterator, or model forward_iterator ([iterator.concept.forward]) otherwise.
• (4.?) If an algorithm’s template parameter is named NoThrowForwardIterator, the template argument is also required to have the property that no exceptions are thrown from increment, assignment, or comparison of, or indirection through, valid iterators.
• (4.?) If an algorithm’s template parameter is named BidirectionalIterator, BidirectionalIterator1, or BidirectionalIterator2, NoThrowBidirectionalIterator1, or NoThrowBidirectionalIterator2, the template argument shall meet the Cpp17BidirectionalIterator requirements ([bidirectional.iterators]) if it is required to be a mutable iterator, or model bidirectional_iterator ([iterator.concept.bidir]) otherwise.
• (4.?) If an algorithm’s template parameter is named RandomAccessIterator, RandomAccessIterator1, or RandomAccessIterator2, the template argument shall meet the Cpp17RandomAccessIterator requirements ([random.access.iterators]) if it is required to be a mutable iterator, or model random_access_iterator ([iterator.concept.random.access]) otherwise.
• (4.?) If an algorithm’s template parameter is named NoThrowInputIterator, NoThrowForwardIterator, NoThrowForwardIterator1, NoThrowForwardIterator2, NoThrowBidirectionalIterator1, or NoThrowBidirectionalIterator2, the template argument is also required to have the property that no exceptions are thrown from increment, assignment, or comparison of, or indirection through, valid iterators.

6.2 [specialized.algorithms.general]

Modify 26.11.1 [specialized.algorithms.general] as shown:

• 4 Some algorithms specified in [specialized.algorithms] make use of the exposition-only function template voidify following exposition-only entities:

template<class T>
  constexpr void* voidify(T& obj) noexcept {
    return addressof(obj);
  }

+template<class Source, class Dest>
+ concept relocatable-from =
+   same_as<Source, Dest> &&
+   move_constructible<Dest>;
+
+template<class T>
+ requires relocatable-from<T, T>
+  constexpr T* relocate-at(T* dest, T* source) {
+      struct guard { T *t; ~guard() { destroy_at(t); } } g(source);
+      return ::new (voidify(*dest)) T(std::move(*source));
+  }

6.3 [special.mem.concepts]

Add at the end of 26.11.2 [special.mem.concepts]:

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

• ? [Note: This concept allows some bidirectional_iterator ([iterator.concept.bidir]) operations to throw exceptions. — end note]

template<class R>
concept nothrow-bidirectional-range = // exposition only
  nothrow-forward-range<R> &&
  nothrow-bidirectional-iterator<iterator_t<R>>;

6.4 [memory.syn]

In 20.2.2 [memory.syn], add to the <memory> header synopsis (before [unique.ptr]):

template<class NoThrowInputIterator, class NoThrowForwardIterator>
  constexpr NoThrowForwardIterator
    uninitialized_relocate(NoThrowInputIterator first,    // freestanding
                           NoThrowInputIterator last,
                           NoThrowForwardIterator result);

template<class ExecutionPolicy, class NoThrowForwardIterator1, class NoThrowForwardIterator2>
  constexpr NoThrowForwardIterator2
    uninitialized_relocate(ExecutionPolicy&& exec,    // see [algorithms.parallel.overloads]
                           NoThrowForwardIterator1 first,
                           NoThrowForwardIterator1 last,
                           NoThrowForwardIterator2 result);

template<class NoThrowInputIterator, class Size, class NoThrowForwardIterator>
  constexpr NoThrowForwardIterator
    uninitialized_relocate_n(NoThrowInputIterator first,    // freestanding
                             Size n,
                             NoThrowForwardIterator result);

template<class ExecutionPolicy, class NoThrowForwardIterator1, class Size, class NoThrowForwardIterator2>
  constexpr NoThrowForwardIterator2
    uninitialized_relocate_n(ExecutionPolicy&& exec,    // see [algorithms.parallel.overloads]
                             NoThrowForwardIterator1 first,
                             Size n,
                             NoThrowForwardIterator2 result);

template<class NoThrowBidirectionalIterator1, class NoThrowBidirectionalIterator2>
  constexpr NoThrowBidirectionalIterator2
    uninitialized_relocate_backward(NoThrowBidirectionalIterator1 first,    // freestanding
                                    NoThrowBidirectionalIterator1 last,
                                    NoThrowBidirectionalIterator2 result);

template<class ExecutionPolicy, class NoThrowBidirectionalIterator1, class NoThrowBidirectionalIterator2>
  constexpr NoThrowBidirectionalIterator2
    uninitialized_relocate_backward(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
                                    NoThrowBidirectionalIterator1 first,
                                    NoThrowBidirectionalIterator1 last,
                                    NoThrowBidirectionalIterator2 result);

namespace ranges {
  template<class I, class O>
    using uninitialized_relocate_result = in_out_result<I, O>;    // freestanding

  template<nothrow-input-iterator I, nothrow-sentinel-for<I> S1,
           nothrow-forward-iterator O, nothrow-sentinel-for<O> S2>
    requires relocatable-from<iter_value_t<I>, iter_value_t<O>>
      constexpr uninitialized_relocate_result<I, O>
        uninitialized_relocate(I ifirst, S1 ilast, O ofirst, S2 olast);    // freestanding

  template<nothrow-input-range IR, nothrow-forward_range<I> OR>,
    requires relocatable-from<range_value_t<IR>, range_value_t<OR>>
      constexpr uninitialized_relocate_result<borrowed_iterator_t<IR>, borrowed_iterator_t<OR>>
        uninitialized_relocate(IR&& in_range, OR&& out_range);    // freestanding

  template<class I, class O>
    using uninitialized_relocate_n_result = in_out_result<I, O>;    // freestanding

  template<nothrow-input-iterator I,
           nothrow-forward-iterator O, nothrow-sentinel-for<O> S>
    requires relocatable-from<iter_value_t<I>, iter_value_t<O>>
      constexpr uninitialized_relocate_n_result<I, O>
        uninitialized_relocate_n(I ifirst, iter_difference_t<I> n, O ofirst, S olast);    // freestanding

  template<class I, class O>
    using uninitialized_relocate_backward_result = in_out_result<I, O>;    // freestanding

  template<nothrow-bidirectional-iterator I, nothrow-sentinel-for<I> S1,
           nothrow-bidirectional-iterator O, nothrow-sentinel-for<O> S2>
    requires relocatable-from<iter_value_t<I>, iter_value_t<O>>
      constexpr uninitialized_relocate_backward_result<I, O>
        uninitialized_relocate_backward(I ifirst, S1 ilast, O ofirst, S2 olast);    // freestanding

  template<nothrow-bidirectional-range IR, nothrow-bidirectional-range OR>
    requires relocatable-from<range_value_t<IR>, range_value_t<OR>>
      constexpr uninitialized_relocate_backward_result<borrowed_iterator_t<IR>, borrowed_iterator_t<OR>>
        uninitialized_relocate_backward(IR&& in_range, OR&& out_range);    // freestanding
}

6.5 [specialized.algorithms]

6.5.1 [special.relocate]

Append to 26.11 [specialized.algorithms] a new subclause, uninitialized_relocate [special.relocate], with these contents:

template<class NoThrowInputIterator, class NoThrowForwardIterator>
  constexpr NoThrowForwardIterator
    uninitialized_relocate(NoThrowInputIterator first,
                           NoThrowInputIterator last,
                           NoThrowForwardIterator result);

• ? Preconditions: result is not in the range [first, last).

• ? Effects: Equivalent to:

NoThrowForwardIterator first_result = result;
try {
  while (first != last) {
    relocate-at(addressof(*result), addressof(*first));
    ++first;
    ++result;
  }
} catch (...) {
  destroy(++first, last);
  destroy(first_result, result);
  throw;
}

return result;

namespace ranges {
  template<nothrow-input-iterator I, nothrow-sentinel-for<I> S1,
           nothrow-forward-iterator O, nothrow-sentinel-for<O> S2>
    requires relocatable-from<iter_value_t<I>, iter_value_t<O>>
      constexpr uninitialized_relocate_result<I, O>
        uninitialized_relocate(I ifirst, S1 ilast, O ofirst, O2 olast);

  template<nothrow-input-range IR, nothrow-forward_range<I> OR>,
    requires relocatable-from<range_value_t<IR>, range_value_t<OR>>
      constexpr uninitialized_relocate_result<borrowed_iterator_t<IR>, borrowed_iterator_t<OR>>
        uninitialized_relocate(IR&& in_range, OR&& out_range);
}

• ? Preconditions: ofirst is not in the range [ifirst, ilast).

• ? Effects: Equivalent to:

O first_result = ofirst;
try {
  while (ifirst != ilast && ofirst != olast) {
    relocate-at(addressof(*ofirst), addressof(*ifirst));
    ++ifirst;
    ++ofirst;
  }
} catch (...) {
  destroy(++ifirst, ilast);
  destroy(first_result, ofirst);
  throw;
}

return {std::move(ifirst), ofirst};

6.5.2 [special.relocate_n]

Append to 26.11 [specialized.algorithms] a new subclause, uninitialized_relocate_n [special.relocate_n], with these contents:

template<class NoThrowInputIterator, class Size, class NoThrowForwardIterator>
  constexpr NoThrowForwardIterator
    uninitialized_relocate_n(NoThrowInputIterator first,
                             Size n,
                             NoThrowForwardIterator result);

• ? Preconditions: result is not in the range [first, first + n).

• ? Effects: Equivalent to:

NoThrowForwardIterator first_result = result;
try {
  while (n > 0) {
    relocate-at(addressof(*result), addressof(*first));
    ++first;
    ++result;
    --n;
  }
} catch (...) {
  destroy_n(++first, --n);
  destroy(first_result, result);
  throw;
}

return result;

namespace ranges {
  template<nothrow-input-iterator I,
           nothrow-forward-iterator O, nothrow-sentinel-for<O> S>
    requires relocatable-from<iter_value_t<I>, iter_value_t<O>>
      constexpr uninitialized_relocate_n_result<I, O>
        uninitialized_relocate_n(I ifirst, iter_difference_t<I> n, O ofirst, S olast);
}

• ? Preconditions: ofirst is not in the range [ifirst, ifirst + n).

• ? Effects: Equivalent to:

O first_result = ofirst;
try {
  while (n > 0 && ofirst != olast) {
    relocate-at(addressof(*ofirst), addressof(*ifirst));
    ++ifirst;
    ++ofirst;
    --n;
  }
} catch (...) {
  destroy_n(++ifirst, --n);
  destroy(first_result, ofirst);
  throw;
}

return {std::move(ifirst), ofirst};

6.5.3 [special.relocate_backward]

Append to 26.11 [specialized.algorithms] a new subclause, uninitialized_relocate_backward [special.relocate_backward], with these contents:

template<class NoThrowBidirectionalIterator1, class NoThrowBidirectionalIterator2>
  constexpr NoThrowBidirectionalIterator2
    uninitialized_relocate_backward(NoThrowBidirectionalIterator1 first,
                                    NoThrowBidirectionalIterator1 last,
                                    NoThrowBidirectionalIterator2 result);

• ? Preconditions: result is not in the range (first, last].

• ? Effects: Equivalent to:

NoThrowBidirectionalIterator2 result_last = result;
try {
  while (last != first) {
    --last;
    --result;
    relocate-at(addressof(*result), addressof(*last));
  }
} catch (...) {
  destroy(first, last);
  destroy(++result, result_last);
  throw;
}

return {last, result};

namespace ranges {
  template<nothrow-bidirectional-iterator I, nothrow-sentinel-for<I> S1,
           nothrow-bidirectional-iterator O, nothrow-sentinel-for<O> S2>
    requires relocatable-from<iter_value_t<I>, iter_value_t<O>>
      constexpr uninitialized_relocate_backward_result<I, O>
        uninitialized_relocate_backward(I ifirst, S1 ilast, O ofirst, S2 olast);

  template<nothrow-bidirectional-range IR, nothrow-bidirectional-range OR>
    requires relocatable-from<range_value_t<IR>, range_value_t<OR>>
      constexpr uninitialized_relocate_backward_result<borrowed_iterator_t<IR>, borrowed_iterator_t<OR>>
        uninitialized_relocate_backward(IR&& in_range, OR&& out_range);
}

• ? Preconditions: olast is not in the range (ifirst, ilast].

• ? Effects: Equivalent to:

O result_last = olast;
try {
  while (ilast != ifirst && olast != ofirst) {
    --ilast;
    --olast;
    relocate-at(addressof(*olast), addressof(*ilast));
  }
} catch (...) {
  destroy(ifirst, ilast);
  destroy(++olast, result_last);
  throw;
}

return {ilast, olast};