P1144R9
std::is_trivially_relocatable

1. Changelog

• R9 (pre-Kona 2023):

  • Added feature-test macros __cpp_impl_trivially_relocatable and __cpp_lib_trivially_relocatable.

  • Added §3.1 "Design non-goals" and comparison to [P2785R3].

  • Replaced Appendix C "Examples of non-trivially relocatable class types" with a shorter summary.

  • Removed Appendix E "Open questions" as basically redundant with §5.2 "Confusing interactions with std::pmr". See "P1144 PMR koans" (June 2023).

• R8 (pre-Varna 2023):

  • dcl.attr.trivreloc: Removed "If a type T is declared trivially_relocatable, and T is either not move-constructible or not destructible, the program is ill-formed." This should have been removed in R7 along with "move-constructible, destructible."

  • meta.unary.prop: Adjusted the precondition of is_trivially_relocatable_v to match is_trivially_copyable_v. Removed is_relocatable_v, is_nothrow_relocatable_v for insufficient motivation (but kept concept relocatable because it expresses semantic requirements).

  • Marked std::relocate as [[nodiscard]]; changed its return type to remove_cv_t<T>.

  • Resolved the Appendix E question about potentially overlapping subobjects; we have implementation experience now that proves this is not a problem. Expanded discussion of pmr types.

  • Replaced §3 "Design goals" with a shorter summary.

• R7 (post-Issaquah 2023):

  • Added std::uninitialized_relocate_backward, the building block of vector::insert.

  • Removed "move-constructible, destructible" from the requirements in basic.types.general. Now trivially relocatable types, like trivially copyable types, can be non-relocatable.

  • Added table §2.1 directly comparing this proposal to Folly, BSL, and Qt.

  • Added straw poll results from Issaquah; removed much background and discussion (leaving only notes for the interested reader to consult [P1144R6]).

  • Removed mentions of EASTL.

  • Added Appendix E "Open questions."

• R6:

  • Added T std::relocate(T *source).

  • Changed the exception guarantee of uninitialized_relocate and uninitialized_relocate_n in accord with feedback from David Stone.

  • Removed std::ranges::relocate_at (but kept std::relocate_at).

2. Introduction and motivation

Given an object type T and memory addresses src and dst, the phrase "relocate a T from src to dst" means "move-construct dst from src, and then immediately destroy the object at src."

Any type which is both move-constructible and destructible is relocatable. A type is nothrow relocatable if its relocation operation is noexcept, and a type is trivially relocatable if its relocation operation is trivial (which, just like trivial move-construction and trivial copy-construction, means "tantamount to memcpy").

In practice, almost all relocatable types are trivially relocatable: std::unique_ptr<int>, std::vector<int>, std::string (on libc++ and MSVC), std::list<int> (on MSVC). Examples of non-trivially relocatable types include std::list<int> (on libstdc++ and libc++) and std::string (on libstdc++). See Appendix C: Examples of non-trivially relocatable class types and [InPractice].

P1144 allows the library programmer to warrant to the compiler that a resource-management type is trivially relocatable. Explicit warrants are rarely needed because the compiler can infer trivial relocatability for Rule-of-Zero types. See § 4.4 Trivially relocatable type [basic.types.general].

The most important thing about P1144 relocation is that it is backward compatible and does not break either API or ABI. P1144 intends simply to legalize the well-understood tricks that many industry codebases already do (see [BSL], [Folly], [Deque]), not to change the behavior of any existing source code (except to speed it up), nor to require major work from standard library vendors.

2.1. Optimizations enabled by trivial relocatability

The following optimizations are possible according to P1144R9’s notion of trivial relocatability. Here’s who does these optimizations in practice:

2.1.1. Contiguous reallocation

Trivial relocation helps anywhere we do the moral equivalent of realloc, such as in vector<R>::reserve.

[Bench] (presented at C++Now 2018) shows a 3x speedup on vector<unique_ptr<int>>::resize. This Reddit thread demonstrates a similar 3x speedup using the online tool Quick-Bench.

2.1.2. Moving in-place/SBO type-erased types like any and function

Trivial relocation can de-duplicate the code generated by type-erasing wrappers like any, function, and move_only_function. For these types, a move of the wrapper object is implemented in terms of a relocation of the contained object. (E.g., libc++'s std::any.) In general, the relocate operation must have a different instantiation for each different contained type C, leading to code bloat. But every trivially relocatable C of a given size can share the same instantiation.

2.1.3. Moving fixed-capacity containers like static_vector and small_vector

The move-constructor of fixed_capacity_vector<R,N> can be implemented naïvely as an element-by-element move (leaving the source vector’s elements in their moved-from state), or efficiently as an element-by-element relocate (leaving the source vector empty). For detailed analysis, see [FixedCapacityVector].

boost::container::static_vector<R,N> currently implements the naïve element-by-element-move strategy, but after LEWG feedback, [P0843R5] static_vector does permit the faster relocation strategy.

2.1.4. Contiguous insert and erase

Trivial relocation can be used anywhere we shift a contiguous range left or right, such as in vector::erase (i.e., destroy the erased elements and "close the window" by memmoving left) and vector::insert (i.e., "make a window" by memmoving right and then construct the new elements in place). [Folly]'s fbvector does this optimization; see fbvector::make_window. Bloomberg’s [BSL] also does this optimization.

But § 5.2 Confusing interactions with std::pmr determines whether this optimization will be possible for certain types.

2.1.5. Swap

Given a reliable way of detecting trivial relocatability, we can optimize any routine that uses the moral equivalent of std::swap, such as std::rotate, std::partition, or std::sort.

Optimizing std::swap produces massive code-size improvements for all swap-based algorithms, including std::sort and std::rotate. See [CppNow] @19:56–21:22, and see this Godbolt. This Quick-Bench shows a 25% speedup in std::rotate when it is allowed to use bitwise swap on a Rule-of-Zero type.

But § 5.2 Confusing interactions with std::pmr determines whether this optimization will be possible for certain types.

2.2. Assertions, not assumptions

Some data structures might reasonably assert the trivial relocatability of their elements, just as they sometimes assert the stronger property of trivial copyability today. This might help them guarantee reasonable performance, or guarantee exception-safety.

2.3. Eliminate manual warrants, improve safety

Many real-world codebases contain templates which require trivial relocatability of their template parameters, but cannot today verify trivial relocatability. For example, until 2012 [Folly] required the programmer to warrant the trivial relocatability of any type stored in a folly::fbvector:

class Widget {
    std::vector<int> lst_;
};

folly::fbvector<Widget> vec;  // FAIL AT COMPILE TIME for lack of warrant

This merely encouraged the programmer to add the warrant and continue. An incorrect warrant was discovered only at runtime, via undefined behavior. See [FollyIssue889] and (most importantly) [CppNow] @27:26–31:47.

class Gadget {
    std::list<int> lst_;
};
// sigh, add the warrant on autopilot
template<> struct folly::IsRelocatable<Gadget> : std::true_type {};

folly::fbvector<Gadget> vec;  // CRASH AT RUNTIME due to fraudulent warrant

Note: Folly’s fbvector was patched in December 2012 to accept both trivially relocatable and non-trivially relocatable types, in line with std::vector. Since then, the effect of an incorrect warrant remains the same — UB and crash — but a missing warrant simply disables the optimization.

If this proposal is adopted, then Folly can start using static_assert(std::is_trivially_relocatable_v<T>) resp. if constexpr (std::is_trivially_relocatable_v<T>) in the implementation of fbvector, and the programmer can stop writing explicit warrants. Finally, the programmer can start writing assertions of correctness, which aids maintainability and can even find real bugs. Example:

class Widget {
    std::vector<int> lst_;
};
static_assert(std::is_trivially_relocatable_v<Widget>);  // correctly SUCCEEDS

class Gadget {
    std::list<int> lst_;
};
static_assert(std::is_trivially_relocatable_v<Gadget>);  // correctly ERRORS

The improvement in user experience and safety in real-world codebases ([Folly], [BSL], [Qt], [HPX], etc.) is the most important benefit to be gained by this proposal.

3. Design goals

For the former, longer, contents of this section, see P1144R7 §3.

Briefly: We want to support all five of the following use-cases (Godbolt).

static_assert(std::is_trivially_relocatable_v<std::unique_ptr<int>>); // #1

struct RuleOfZero { std::unique_ptr<int> p_; };
static_assert(std::is_trivially_relocatable_v<RuleOfZero>); // #2

struct [[trivially_relocatable]] RuleOf3 {
    RuleOf3(RuleOf3&&);
    RuleOf3& operator=(RuleOf3&&);
    ~RuleOf3();
};
static_assert(std::is_trivially_relocatable_v<RuleOf3>); // #3

struct [[trivially_relocatable]] Wrap0 {
    boost::movelib::unique_ptr<int> p_;
    static_assert(!std::is_trivially_relocatable_v<decltype(p_)>);
        // it’s not annotated, but we know it’s actually trivial
};
static_assert(std::is_trivially_relocatable_v<Wrap0>); // #4

struct [[trivially_relocatable]] Wrap3 {
    Wrap3(Wrap3&&);
    Wrap3& operator=(Wrap3&&);
    ~Wrap3();
    int i_;
    boost::interprocess::offset_ptr<int> p_ = &i_;
    static_assert(!std::is_trivially_relocatable_v<decltype(p_)>);
        // it’s not trivial, but we preserve our invariant correctly
};
static_assert(std::is_trivially_relocatable_v<Wrap3>); // #5

3.1. Non-goals

Note: This section is new in P1144R9.

We propose special support for trivially relocatable types, but no particular support for types that are relocatable in other ways. The two most-frequently-asked scenarios are:

• "Never-empty types," e.g. gsl::not_null<unique_ptr<int>>. Such types are not movable (because by design they never enter a moved-from state), but they are swappable and could in theory be relocatable (but not via move-and-destroy, since they cannot be moved). P1144 supports the physical possibility that is_trivially_relocatable_v<T> && !is_relocatable_v<T>, but keeps the status quo w.r.t. library support for such types; e.g. you can’t resize, insert, or erase a vector of such types. P1144’s std::relocate_at rejects such types.

• Types that are "efficiently but non-trivially relocatable," e.g. libc++'s tuple<string, list<int>>, where the ideal relocation operation would trivially relocate the string and move-and-destroy the list; this is not trivial, but still faster than move-and-destroy’ing the whole tuple. P1144 keeps the status quo w.r.t. such types, and doesn’t provide any way to optimize their relocation. See "Cheaply relocatable, but not trivially relocatable" (October 2018).

The most promising active proposal for "non-trivial relocation" is [P2785R3]. It proposes a "relocation constructor" like this:

struct A {
    A(A) = default;
};

which the compiler deduces is trivial iff all of A’s members are trivially relocatable. This solves both of the above "non-goal" scenarios. However, [P2785R3] fails to support our positive goals Wrap0 and Wrap3, which are trivially relocatable despite having some non-trivial members. In other words, P1144 is forward-compatible with (does not close the door to) [P2785R3]; and vice versa, adopting [P2785R3] would not solve two of P1144’s five advertised use-cases. WG21 might well want to adopt both proposals. But P1144 solves "the 99% problem"; P1144 might not leave enough performance on the table to motivate the further adoption of [P2785R3].

Notably, P1144R9 is almost entirely a subset of [P2785R3]; the only significant difference is that [P2785R3] doesn’t propose the [[trivially_relocatable]] warrant itself. (P2785 proposes that to make a type trivially relocatable, you =default its relocation constructor. P1144 can’t do that, and anyway wants to support Wrap0 and Wrap3.)

4. Proposed wording for C++26

The wording in this section is relative to the current working draft ([N4958]).

Note: There is no difficulty in changing the attribute syntax to a contextual-keyword syntax; the only downsides are aesthetic. We can defer that decision to the last minute, according to CWG’s feedback on the final wording.

Note: Our feature-test macros follow the pattern set by __cpp_impl_coroutine+__cpp_lib_coroutine and __cpp_impl_three_way_comparison+__cpp_lib_three_way_comparison.

4.1. Predefined macro names [cpp.predefined]

Add a feature-test macro to the table in [cpp.predefined]:

__cpp_impl_three_way_comparison   201907L
__cpp_impl_trivially_relocatable  YYYYMML
__cpp_inheriting_constructors     201511L

4.2. Header <version> synopsis [version.syn]

Add a feature-test macro to [version.syn]/2:

#define __cpp_lib_transparent_operators   201510L // also in <memory>, <functional>
#define __cpp_lib_trivially_relocatable   YYYYMML // also in <memory>, <type_traits>
#define __cpp_lib_tuple_element_t         201402L // also in <tuple>

4.3. Relocation operation [defns.relocation]

Add a new section in [intro.defs]:

relocation operation

the homogeneous binary operation performed by std::relocate_at, consisting of a move construction immediately followed by a destruction of the source object

4.4. Trivially relocatable type [basic.types.general]

Add a new section in [basic.types.general]:

An object type T is a trivially relocatable type if it is:

• a trivially copyable type, or

• an array of trivially relocatable type, or

• a (possibly cv-qualified) class type declared with a trivially_relocatable attribute with value true [dcl.attr.trivreloc], or

• a (possibly cv-qualified) class type which:

  • has no user-provided move constructors or move assignment operators,

  • has no user-provided copy constructors or copy assignment operators,

  • has no user-provided destructors,

  • has no virtual member functions,

  • has no virtual base classes,

  • all of whose members are either of reference type or of trivially relocatable type, and

  • all of whose base classes are of trivially relocatable type.

[Note: For a trivially relocatable type, the relocation operation (as performed by, for example, std::swap_ranges or std::vector::reserve) is tantamount to a simple copy of the underlying bytes. —end note]

[Note: It is intended that most standard library types be trivially relocatable types. —end note]

Note: Polymorphic types are disallowed from "natural" trivial relocatability (see [Polymorphic]). Volatile members are not disallowed (see [Subobjects]).

4.5. Trivially relocatable attribute [dcl.attr.trivreloc]

Add a new section after [dcl.attr.nouniqueaddr]:

The attribute-token trivially_relocatable specifies that a class type’s relocation operation has no visible side-effects other than a copy of the underlying bytes, as if by the library function std::memcpy. It may be applied to the definition of a class. It shall appear at most once in each attribute-list. An attribute-argument-clause may be present and, if present, shall have the form

( constant-expression )

The constant-expression shall be an integral constant expression of type bool. If no attribute-argument-clause is present, it has the same effect as an attribute-argument-clause of (true).

If any definition of a class type has a trivially_relocatable attribute with value V, then each definition of the same class type shall have a trivially_relocatable attribute with value V. No diagnostic is required if definitions in different translation units have mismatched trivially_relocatable attributes.

If a class type is declared with the trivially_relocatable attribute, and the program relies on observable side-effects of its relocation other than a copy of the underlying bytes, the behavior is undefined.

4.5.1. __has_cpp_attribute entry [cpp.cond]

Add a new entry to the table of supported attributes in [cpp.cond]:

noreturn              200809L
trivially_relocatable YYYYMML
unlikely              201803L

4.6. relocatable concept [concept.relocatable]

Add a new section after [concept.copyconstructible]:

template<class T>
  concept relocatable = move_constructible<T>;

If T is an object type, then let rv be an rvalue of type T, lv an lvalue of type T equal to rv, and u2 a distinct object of type T equal to rv. T models relocatable only if

• After the definition T u = rv;, u is equal to u2.

• T(rv) is equal to u2.

• If the expression u2 = rv is well-formed, then the expression has the same semantics as u2.~T(); ::new ((void*)std::addressof(u2)) T(rv);

• If the definition T u = lv; is well-formed, then after the definition u is equal to u2.

• If the expression T(lv) is well-formed, then the expression’s result is equal to u2.

• If the expression u2 = lv is well-formed, then the expression has the same semantics as u2.~T(); ::new ((void*)std::addressof(u2)) T(lv);

Note: We intend that a type may be relocatable regardless of whether it is copy-constructible; but, if it is copy-constructible then copy-and-destroy must have the same semantics as move-and-destroy. We intend that a type may be relocatable regardless of whether it is assignable; but, if it is assignable then assignment must have the same semantics as destroy-and-copy or destroy-and-move. The semantic requirements on assignment help us optimize vector::insert and vector::erase. pmr::forward_list<int> satisfies relocatable, but it models relocatable only when all relevant objects have equal allocators.

4.7. Type trait is_trivially_relocatable [meta.unary.prop]

Add a new entry to Table 47 in [meta.unary.prop]:

Template	Condition	Preconditions
template<class T> struct is_trivially_relocatable;	T is a trivially relocatable type.	remove_all_extents_t<T> shall be a complete type or cv void.

4.8. relocate_at and relocate [specialized.relocate]

Add a new section after [specialized.destroy]:

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

Mandates: T is a complete non-array object type.

Effects: Equivalent to:

struct guard { T *t; ~guard() { destroy_at(t); } } g(source);
return ::new (voidify(*dest)) T(std::move(*source));

except that if T is trivially relocatable [basic.types], side effects associated with the relocation of the value of *source might not happen.

template<class T>
[[nodiscard]] remove_cv_t<T> relocate(T* source);

Mandates: T is a complete non-array object type.

Effects: Equivalent to:

remove_cv_t<T> t = std::move(source);
destroy_at(source);
return t;

except that if T is trivially relocatable [basic.types], side effects associated with the relocation of the object’s value might not happen.

Note: These functions have both been implemented in my libc++ fork; for relocate, see godbolt.org/z/cqPP4oeE9 and [StdRelocateIsCute]. My implementation of their "as-if-by-memcpy" codepaths relies on Clang’s __builtin_memmove; vendors can use any vendor-specific means to implement them. The wording also deliberately permits a low-quality implementation with no such codepath at all. See [CppNow] @45:23–48:39.

4.9. Nothrow bidirectional iterator [algorithms.requirements]

Modify [algorithms.requirements] as follows:

• If an algorithm’s template parameter is named ForwardIterator, ForwardIterator1, ForwardIterator2, or NoThrowForwardIterator, 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.

• 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.

• If an algorithm’s template parameter is named BidirectionalIterator, BidirectionalIterator1, or BidirectionalIterator2, or NoThrowBidirectionalIterator, 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.

• If an algorithm’s template parameter is named NoThrowBidirectionalIterator, the template argument is also required to have the property that no exceptions are thrown from increment, decrement, assignment, or comparison of, or indirection through, valid iterators.

4.10. uninitialized_relocate, uninitialized_relocate_n, uninitialized_relocate_backward [uninitialized.relocate]

Add a new section after [uninitialized.move]:

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

Effects: Equivalent to:

try {
  for (; first != last; ++result, (void)++first) {
    ::new (voidify(*result))
      typename iterator_traits<NoThrowForwardIterator>::value_type(std::move(*first));
    destroy_at(addressof(*first));
  }
  return result;
} catch (...) {
  destroy(++first, last);
  throw;
}

except that if the iterators' common value type is trivially relocatable, side effects associated with the relocation of the object’s value might not happen.

Remarks: If an exception is thrown, all objects in both the source and destination ranges are destroyed.

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

Effects: Equivalent to:

try {
  for (; n > 0; ++result, (void)++first, --n) {
    ::new (voidify(*result))
      typename iterator_traits<NoThrowForwardIterator>::value_type(std::move(*first));
    destroy_at(addressof(*first));
  }
  return {first, result};
} catch (...) {
  destroy_n(++first, --n);
  throw;
}

except that if the iterators' common value type is trivially relocatable, side effects associated with the relocation of the object’s value might not happen.

Remarks: If an exception is thrown, all objects in both the source and destination ranges are destroyed.

template<class BidirectionalIterator, class NoThrowBidirectionalIterator>
  NoThrowBidirectionalIterator
    uninitialized_relocate_backward(BidirectionalIterator first, BidirectionalIterator last,
                                    NoThrowBidirectionalIterator result);

Effects: Equivalent to:

try {
  for (; last != first; ) {
    --last;
    --result;
    ::new (voidify(*result))
      typename iterator_traits<NoThrowBidirectionalIterator>::value_type(std::move(*last));
    destroy_at(addressof(*last));
  }
  return result;
} catch (...) {
  destroy(first, ++last);
  throw;
}

except that if the iterators' common value type is trivially relocatable, side effects associated with the relocation of the object’s value might not happen.

Remarks: If an exception is thrown, all objects in both the source and destination ranges are destroyed.

Note: The Remarks allude to blanket wording in [specialized.algorithms.general]/2.

5. Rationale and alternatives

5.1. Attribute [[maybe_trivially_relocatable]]

My Clang implementation, currently available on Godbolt, supports both [[clang::trivially_relocatable]] and another attribute called [[clang::maybe_trivially_relocatable]], which John McCall requested that I explore.

In Issaquah (February 2023), P2786R0 suggested a very similar design to [[clang::maybe_trivially_relocatable]]. EWGI took a three-way straw poll on [[trivially_relocatable]] versus [[maybe_trivially_relocatable]], with an inconclusive 7–5–6 vote (the author of P1144 voting "For" and the three representatives of P2786 presumably voting "Against").

For discussion of [[maybe_trivially_relocatable]] and why I don’t think it’s the right thing to standardize, see

• [[maybe_trivially_relocatable]] by itself cannot support § 3 Design goals examples #4 and #5

• P1144R4 section 6.2

• "Should the compiler sometimes reject a [[trivially_relocatable]] warrant?" (2023-03-10)

5.2. Confusing interactions with std::pmr

Note: See "P1144 PMR koans" (June 2023) for additional analysis of the problem cases.

Note: This section was added in P1144R5, revised in P1144R7, and again in P1144R8. Here I assume libc++, where std::string is trivially relocatable. Feel free to substitute your favorite trivially relocatable container type; I’m sticking with string for these examples because it is short and easy to spell.

P1144 proposes a "trivial relocatability" very similar to "trivial copyability": if the user provides any special member, we assume that the user wants control over this type’s value semantics, and we won’t implicitly infer triviality. This includes the assignment operator.

struct A {
    A(A&&) = default;
    A& operator=(A&&);
    ~A() = default;
};
static_assert(!std::is_trivially_relocatable_v<A>);
  // P2786 would say the opposite here

P1144 treats move as an optimization of copy; thus we assume that it always ought to be safe to replace "copy and destroy" with "move and destroy" (and thus with "relocate"). This is informed by Arthur’s experience standardizing "implicit move" in P1155 (C++20) and P2266 (C++23). "Implicit move" affects pmr types because their copy differs from their move. Example:

struct ByValueSink {
    ByValueSink(std::pmr::vector<int> v) : v_(std::move(v)) {}
    std::pmr::vector<int> v_;
};

ByValueSink f(std::pmr::memory_resource *mr) {
    auto v = std::pmr::vector<int>(mr);
    return v;
      // C++17, Clang 12-: Copies (changes allocator)
      // C++20, GCC, Clang 13+: Moves (preserves allocator)
}

We didn’t care about this when fiddling with implicit move; P1144 implicitly believes we shouldn’t care about it now. (This position might be debatable, but it’s definitely part of the worldview that led to P1144’s specific proposed semantics, so it’s good to have this background in mind.)

P1144 wants to be able to optimize not just vector reserve, but also vector insert and erase (see table §2.1). Today, vector insert and erase use move-assignment, not relocation. (In fact, [vector.modifiers]/5 specifies the exact number of times "the assignment operator of T is called." We might want to fix that, but that’s out of scope for this paper.) We can optimize vector insert to use (trivial) relocation for element types that model relocatable ([concept.relocatable]).

Some types invariably model relocatable; that is, their assignment is naturally tantamount to construct-and-destroy. But for pmr types and polymorphic types, assignment is not tantamount to construct-and-destroy, except under certain conditions. For pmr types, the condition is "both objects have the same allocator." For polymorphic types, the condition is "both objects have the same dynamic type."

std::vector<Derived> dv = { ~~~ };
dv.erase(dv.begin());
  // Every object in the vector certainly has the same dynamic type.

std::pmr::vector<std::pmr::string> pv = { ~~~ };
pv.erase(pv.begin());
  // Every string in the vector certainly has the same allocator.

Derived da[5] = { ~~~ };
std::rotate(da, da+2, da+5);
  // Every object in the contiguous range certainly has the same dynamic type.

std::pmr::string pa[5] = { ~~~ };
std::rotate(pa, pa+2, pa+5);
  // Objects in the contiguous range might have different allocators?

P1144 aims to permit efficient insertion and erasure in std::vector. Example:

std::vector<std::string> vs(501);
vs.erase(vs.begin());

This erase requires us to shift down 500 std::string objects. We can do this by 500 calls to string::operator= followed by one call to ~string, or by one call to ~string followed by a memmove (as in [Folly] and BSL; see table §2.1). We want to permit BSL’s implementation. That’s why since P1144R5, the definition of concept relocatable in §4.8 places semantic requirements on T’s assignment operators (if they exist) as well as on T’s constructors and destructors.

If pmr::string is considered trivially relocatable, this will trickle down into all Rule-of-Zero types with a pmr::string member. (Godbolt.)

static_assert(std::is_trivially_relocatable_v<std::pmr::string>);
  // Before: not true, of course
  // After: suppose this is true
struct A {
  std::pmr::string ps;
};
static_assert(std::is_trivially_relocatable_v<A>);
  // After: then this will also be true, by the Rule of Zero
std::vector<A> v;
v.push_back({std::pmr::string("one", &mr1)});
v.push_back({std::pmr::string("two", &mr2)});
v.erase(v.begin());
  // Before: Well-defined behavior, acts as-if by assignment
  // After: Do we somehow make this a precondition violation?
assert(v[0].ps.get_allocator().resource() == &mr1);
  // Before: Succeeds
  // After: Might fail (and on a quality implementation, *will* fail)

If we (1) advertise pmr::string as is_trivially_relocatable; (2) propagate trivial relocatability in the core language as both P1144 and P2786 propose to do; and (3) optimize vector insert and erase for trivially relocatable types; then we inevitably arrive here. Arthur’s solution is to impose preconditions on user-defined types used within certain parts of the STL: Just as their destructors are forbidden to (dynamically) throw exceptions, and their copy constructors are forbidden to (dynamically) make things that aren’t copies, their assignment operators ought to be forbidden to (dynamically) violate concept relocatable’s semantic requirements.

What new wording is needed to achieve this?

6. Acknowledgements

Thanks to Pablo Halpern for [N4158], to which this paper bears a striking resemblance —including the meaning assigned to the word "trivial," and the library-algorithm approach to avoiding the problems with "lame duck objects" discussed in the final section of [N1377]. See discussion of N4034 at Rapperswil (June 2014) and discussion of N4158 at Urbana (November 2014).

Significantly different approaches to this problem have previously appeared in Rodrigo Castro Campos’s [N2754], Denis Bider’s [P0023R0] (introducing a core-language "relocation" operator), and Niall Douglas’s [P1029R3] (treating trivial relocatability as an aspect of move-construction in isolation, rather than an aspect of the class type as a whole).

A less different approach is taken by Mungo Gill & Alisdair Meredith’s [P2786R2]. [P2814R1] compares P2786R0 against P1144R8.

Thanks to Elias Kosunen, Niall Douglas, John Bandela, and Nicolas Lesser for their feedback on early drafts of P1144R0. Thanks to Jens Maurer for his feedback on P1144R3 at Kona 2019, and to Corentin Jabot for championing P1144R4 at Prague 2020.

Thanks to Nicolas Lesser and John McCall for their review comments on the Clang implementation [D50119].

Many thanks to Matt Godbolt for allowing me to install my Clang fork on Compiler Explorer (godbolt.org). See also [Announcing].

Thanks to Howard Hinnant for appearing with me on [CppChat], and to Jon Kalb and Phil Nash for hosting us.

Thanks to Marc Glisse for his work integrating a "trivially relocatable" trait into GNU libstdc++ (see [Deque]) and for answering my questions on GCC bug 87106.

Thanks to Dana Jansens for her contributions re overlapping and non-standard-layout types (see [Subspace]), to Alisdair Meredith for our extensive discussions during the February 2023 drafting of P2786R0, to Giuseppe D’Angelo and Thiago Maceira for contributing the Qt entries in table §2.1, and to Giuseppe D’Angelo for extensive review comments and discussion.

Appendix A: Straw polls

Polls taken at EWGI at Issaquah on 2023-02-10

Arthur O’Dwyer presented [P1144R6]. Alisdair Meredith presented P2786R0 (which proposed a [[maybe_trivially_relocatable]]-style facility, and expressed it as a contextual keyword instead of an attribute). EWGI took the following straw polls (as well as polls on attribute syntax and on both papers' readiness for EWG).

Polls taken at EWGI at Prague on 2020-02-13

Corentin Jabot championed P1144R4. EWGI discussed P1144R4 and Niall Douglas’s [P1029R3] consecutively, then took the following straw polls (as well as a poll on the attribute syntax).

For polls taken September–November 2018, see [P1144R6].

Appendix B: Sample code

See [P1144R6]'s Appendix B for reference implementations of relocate, relocate_at, and P1144R6’s version of the uninitialized_relocate library algorithm, plus a conditionally trivially relocatable std::optional<T>.

Appendix C: Examples of non-trivially relocatable class types

See [P1144R6]'s Appendix C for compilable examples of types that are not trivially relocatable, for each of the following reasons:

• Class contains pointer to self (e.g. libstdc++'s std::string)

• Allocated memory contains pointer to self (e.g. libstdc++'s std::list)

• Class invariant depends on this (e.g. boost::interprocess::offset_ptr)

• Program invariant depends on this (e.g. a global registry of Widget addresses)

• Polymorphic object effectively relies on offset-into-self (see also [Polymorphic])

Appendix D: Implementation experience

Core-language implementations

Clang trunk provides a compiler builtin __is_trivially_relocatable(T) (see [D114732]), which is largely the same as the trait proposed in this paper. (There are slight differences; e.g., Clang incorrectly reports function types and reference types as trivially relocatable. This is Clang bug 67498.) Clang trunk has no equivalent of the [[trivially_relocatable]] attribute, so __is_trivially_relocatable(T) is true only when T is trivially copyable or marked with the [[clang::trivial_abi]] attribute. As of October 2023, Clang trunk has no conception of a type which is non-trivial for purposes of calls yet is trivially relocatable. But Clang’s current status is compatible with P1144 (modulo the few unintentional differences in __is_trivially_relocatable mentioned above).

Arthur’s fork of Clang implements all of P1144 (since 2018), and has been kept up-to-date with the latest P1144. See it in action on godbolt.org, under the name "x86-64 clang (experimental P1144)."

Library implementations

Arthur’s fork of libc++ implements all of P1144 (since 2018), and has been kept up-to-date with the latest P1144. See it in action on godbolt.org, under the name "x86-64 clang (experimental P1144)." (Here is another example showing P1144’s interaction with fancy allocators.)

Since September 2023, Stellar HPX implements relocate_at and uninitialized_relocate{,_n} in the hpx::experimental namespace. This was a GSoC project. See [HPX].

[Qt] implements q_uninitialized_relocate_n in the QtPrivate namespace, but (unlike P1144’s std::uninitialized_relocate_n) does not support overlap; it optimizes to memcpy. Qt also provides q_relocate_overlap_n, which optimizes to memmove.

Since November 2018, libstdc++ optimizes vector::reserve for types that manually specialize std::__is_bitwise_relocatable. (Godbolt.) As of October 2023, the only libstdc++ library type for which __is_bitwise_relocatable has been specialized is deque. See [Deque].

[HPX], [Qt], [Folly], and [BSL] all provide "type traits" that are intended to be manually specialized by the client programmer.

See table §2.1 for more details on [Qt], [Folly], and [BSL].