This is the second in a series of at least three weekly blog posts. Each post (I, II, III, IV) will explain one of the problems facing P1144 “std::is_trivially_relocatable” and P2786R0 “Trivial relocatability options” as we try to (1) resolve their technical differences and (2) convince the rest of the C++ Committee that these resolutions are actually okay to ship.

Today’s topic is new library algorithms for relocation.

What is relocation used for, in practice?

Relocation (trivial or otherwise) tends to be used in the following ways:

• On single objects that are (at least conceptually) member subobjects; e.g. the move-constructors of SBO-optimized any and function

• On non-overlapping arrays of objects; e.g. Vector reallocation and the move-constructor of static_vector

• On an array that overlaps itself; e.g. vector::insert (which needs to shift elements rightward before inserting the new element) and vector::erase (which needs to shift elements leftward after destroying the old element)

You might say, “Wait, I don’t think that’s how vector::erase works!” For ordinary (non-trivial) types, you’re right: erasure works by move-assigning elements to the left, and then destroying the last (moved-from) element. But for trivially copyable types, this is tantamount to memmove; it is also tantamount to memmove for trivially relocatable types. Facebook’s folly::fbvector already works that way for types that are folly::IsRelocatable, and Bloomberg’s bsl::vector does too for types that are bslmf::IsBitwiseMoveable.

Finally, a use-case that remains hypothetical as far as I know:

• On a single object, producing a return value. This is the idea I explored two days ago in “Making priority_queue and flat_set work with move-only types” (2023-03-01); it’s used inside vector::displace_back, although it doesn’t need to be.

Now, the “implementor” (the STL vendor) doesn’t need any help to implement these use-cases. The implementor can use their intimacy with the compiler to do things that are, on paper, undefined behavior; or they can rely on non-portable compiler intrinsics. But when you, the ordinary programmer of something like BSL or Folly or Qt, want to implement your own Vector, Function, or StaticVector type, it’ll help if the STL provides portable APIs that you can use in each of these cases.

Can’t I just use memmove?

In practice, yes, that’s the state of the art in BSL, Folly, and Qt. But on paper, no, it’s undefined behavior for at least two reasons.

• If I have two objects, it’s defined behavior to memmove between them (and then inspect the value of the destination object) only if the object’s type is trivially copyable ([basic.types.general]/3).

• If I have only one object, and memmove from it into some storage where there is no object yet, and then treat that storage as if it now held an object, that’s defined behavior only if the object’s type is implicit-lifetime ([intro.object]/10). (The storage must also have been properly acquired, but that part is hard to screw up in practice. See [intro.object]/13.)

Both P1144 and P2786 agree that it’s important for the STL to provide a public API that relocates objects (trivially or otherwise) in a well-defined way. Neither paper is trying to “bless” the current use of raw memmove as seen in BSL, Folly, and Qt; we’re trying to provide a blessed alternative.

Overview of existing algorithms

Three major libraries provide “prior art” for P1144: BSL, Folly, and Qt. We can imagine what the STL API should look like, by looking at what these libraries define for their own internal purposes.

Folly

Folly provides no generic algorithms, as far as I can tell. fbvector defines a member function M_relocate which calls relocate_move(T* d_first, T* first, T* last) followed by relocate_done(T*, T* first, T* last). relocate_move calls either D_uninitialized_move_a or memcpy; relocate_done calls either D_destroy_range_a or nothing.

That same division of labor is seen in libc++’s vector, by the way.

Qt

Qt’s approach to relocation semantics is the cleanest. It provides these two algorithms:

template<class T, class N>
  void q_uninitialized_relocate_n(T* first, N n, T* d_first);

template<class T, class N>
  void q_relocate_overlap_n(T* first, N n, T* d_first)

q_uninitialized_relocate_n relocates a non-overlapping array. This is the building block for Vector::reserve and StaticVector. Qt’s version of static_vector is called QVarLengthArray, and its move constructor relocates using q_uninitialized_relocate_n.

q_relocate_overlap_n relocates an overlapping array left or right, handling overlap “by magic” just like memmove does. This could be the building block for Vector::insert and Vector::erase. However, as of this post, Qt’s QList::erase uses QMovableArrayOps::erase which doesn’t use q_relocate_overlap_n; it uses raw memmove instead.

The naming roughly reflects the analogies that Qt’s authors see with the STL: q_uninitialized_relocate_n, like std::uninitialized_copy, writes into uninitialized memory, and like std::copy_n does not document whether the data is copied front-to-back or back-to-front. q_relocate_overlap_n writes into a destination buffer that might initially hold objects, so its name doesn’t involve the word uninitialized.

Qt doesn’t provide a single-argument relocation function. Its equivalent of std::any, named QVariant, is SBO-optimized but simply refuses to store anything non-trivially relocatable in its SBO buffer. So QVariant’s move constructor can simply copy the bits.

BSL

BSL has the largest zoo of helper algorithms by far: “bslalg_arrayprimitives.h” is 4800 lines long. But BSL has only one primitive relocation algorithm.

template<class T, class Alloc>
  void ArrayPrimitives_Imp::destructiveMove(
           T* d_first, T* first, T* last, Alloc a);

destructiveMove relocates a non-overlapping array, just like q_uninitialized_relocate_n; this is the building block for Vector::reserve and StaticVector. In fact, BSL’s documentation shows an example of using this algorithm in vector::reserve.

BSL has some other helpers, but (as in Folly) they divide the labor in ways unclearly related to relocation. For example, bsl::vector::erase calls ArrayPrimitives::erase, which calls ArrayPrimitives_Imp::erase, which uses memmove to do the trivial relocation. (It can’t use BSL’s own destructiveMove, because destructiveMove works only on non-overlapping arrays.)

P2786R0

Bloomberg’s P2786R0 “Trivial relocatability options” (Gill & Meredith, February 2023) proposes the following library algorithms:

template<class T>
  requires (is_trivially_relocatable_v<T> && !is_const_v<T>)
void trivially_relocate(T* first, T* last, T* d_first) noexcept;

template<class T>
  requires ((is_trivially_relocatable_v<T> && !is_const_v<T>) ||
            is_nothrow_move_constructible_v<T>)
T* relocate(T* first, T* last, T* d_first) noexcept;

template<class InputIterator, class NoThrowForwardIterator>
  requires is_nothrow_move_constructible_v<iter_value_t<NoThrowForwardIterator>>
NoThrowForwardIterator
  move_and_destroy(InputIterator first, InputIterator last,
                   NoThrowForwardIterator d_first);

trivially_relocate is specified to always trivially relocate. It handles overlapping arrays “by magic,” just like memmove and q_relocate_overlap_n. So it could be the building block for both Vector::insert and Vector::erase… except that it cannot handle arbitrary types! It SFINAEs away when trivial relocation isn’t possible.

relocate also handles overlapping arrays “by magic,” like memmove. It can almost handle arbitrary types; it relocates trivially if possible, falling back to move+destroy. But it cannot handle types with throwing move constructors, such as MSVC’s std::list, unless they happen to be trivially relocatable. (Instead of cleaning up after an exception, the way std::uninitialized_move does, relocate is specified to SFINAE away when relocation might throw an exception. Thus it never throws. P2786R0 missed marking it noexcept, but I’ve fixed that above.)

Finally, move_and_destroy relocates by relatively underspecified means. P2786R0 says “We do not support overlapping ranges in this function,” which I think means it’s UB to pass overlapping ranges to this function at all — as in BSL’s destructiveMove, Qt’s q_uninitialized_relocate_n, and std::copy_n. Alternatively, it might mean that the order of traversal is fixed, making move_and_destroy a suitable building block for Vector::erase but not Vector::insert. std::copy and P1144R6’s uninitialized_relocate follow that approach.

Since all of these algorithms are constrained, none of them can accurately be described as a “building block” for any of our use-cases. For example, StaticVector’s move-constructor can’t be implemented in terms of move_and_destroy because move_and_destroy fails to compile at all for C++03-era types such as

struct Widget {
    std::string s_;
    Widget(const Widget& w) : s_(w.s_) {}
    void operator=(const Widget& w) { s_ = w.s_; }
};

and of course StaticVector needs to be able to work with such types.

P1144R6

My P1144R6 “Object relocation…” (O’Dwyer, June 2022) proposed the following library algorithms:

template<class T>
T* relocate_at(T* source, T* dest);

template<class T>
T relocate(T* source);

template<class InputIterator, class NoThrowForwardIterator>
  NoThrowForwardIterator
    uninitialized_relocate(InputIterator first, InputIterator last,
                           NoThrowForwardIterator d_first);

template<class InputIterator, class Size, class NoThrowForwardIterator>
  pair<InputIterator, NoThrowForwardIterator>
    uninitialized_relocate_n(InputIterator first, Size n, NoThrowForwardIterator result);

relocate_at relocates an object (by any means possible) from source to dest. This is the building block for Function and Any.

relocate relocates an object from source into the return slot. See “std::relocate’s implementation is cute” (2022-05-18). This is the building block for our hypothetical Vector::displace_back.

uninitialized_relocate relocates by any means possible, and invariably from left to right, like std::copy. This makes it a suitable building block for Vector::reallocate and Vector::erase, but not Vector::insert.

uninitialized_relocate_n is exactly the same: relocate by any means possible, from left to right, like std::copy (and not like std::copy_n).

If you want to relocate from right to left, as in Vector::insert, then (under P1144R6) you must write something like this:

template<class BidirIterator, class NoThrowBidirIterator>
NoThrowBidirIterator
uninitialized_relocate_backward(BidirIterator first, BidirIterator last,
                                NoThrowBidirIterator d_last)
{
  std::uninitialized_relocate(
    std::make_reverse_iterator(last),
    std::make_reverse_iterator(first),
    std::make_reverse_iterator(d_last));
}

As usual, Alexander Stepanov was here 30 years ago. Instead of calling the C++98 STL’s std::copy_backward, you could have written:

std::copy(
  std::make_reverse_iterator(last),
  std::make_reverse_iterator(first),
  std::make_reverse_iterator(d_last));

But that requires your STL vendor’s std::copy to have special-case memmove’ing codepaths not only for TriviallyCopyable* but also for std::reverse_iterator<TriviallyCopyable*>. No vendor does that. Instead, they provide std::copy and std::copy_backward, each with a single special-case codepath for TriviallyCopyable*. That’s much easier to implement.

Therefore, P1144R7 will propose to add uninitialized_relocate_backward, too.

Comparison table

In the table below, ✓ means “does what you’d expect”; UB means “undefined or unpredictable/wrong behavior”; SFINAE means “the call fails to compile, in a SFINAE-friendly way”; and “N/A” means “not applicable/don’t care.” q_uninitialized_relocate_n supports types with non-noexcept move constructors, but at least fails to say (and possibly fails to consider) what happens at runtime were a move constructor actually to throw.