D4102R0
Container insertion and erasure should be allowed to relocate

1. Changelog

• R0

  • First submission

2. Motivation and scope

2.1. How erasure and insertion currently work

The sequence containers vector, inplace_vector and deque store their elements in contiguous storage (or, in the case of deque, in blocks of contiguous storage). When an element is erased from the middle of such a container, the elements after the erased position must be shifted to fill the gap. Similarly, when an element is inserted in the middle, the existing elements must be shifted to make room.

The C++ Standard does not explicitly specify how these shifting operations are performed. The semantics of vector::erase are given by [sequence.reqmts] simply as "Erases the element pointed to by q", and [vector.modifiers] does not elaborate on the mechanism.

However, the Complexity clause in [vector.modifiers] states that:

Complexity: The destructor of T is called the number of times equal to the number of the elements erased, but the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements.

This, combined with the requirement that T must be Cpp17MoveAssignable (but not necessarily Cpp17MoveInsertable), imposes a specific implementation strategy: the elements after the erased range are moved to fill the gap by using move assignment, and then the trailing moved-from elements are destroyed. In pseudocode:

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

    // Step 1: move-assign leftward
    auto new_end = std::move(last, end(), first); 

    // Step 2: destroy the tail
    std::destroy(new_end, end());

    // ... update bookkeeping ...

    return first;
}

The insert operation (when no reallocation is needed and the insertion point is not at the end) is slightly more involved.

The last element must be move-constructed into the uninitialized storage past the end (since there is no existing object there to assign to). Then the remaining elements between the insertion point and the (former) last element are shifted rightward by move assignment. Finally, the new value is assigned over the moved-from element at the insertion point:

template <typename T>
constexpr auto vector<T>::insert(iterator pos, const T& value)
{
    if (size() == capacity()) { /* reallocate */ }
    else if (pos == end()) { /* insertion at the end */ }
    else {
        // Step 1: move-construct last element into uninitialized storage
        std::construct_at(std::to_address(end()), std::move(*(end() - 1)));

        // Step 2: move-assign the rest of the tail one position to the right
        std::move_backward(pos, end() - 1, end());

        // Step 3: assign the new value into the gap
        *pos = value;

        // ... update bookkeeping ...
    }
}

Because these operations are specified in terms of assignment, the type requirements reflect this: erase requires Cpp17MoveAssignable but does not require Cpp17MoveInsertable (that is, move constructibility via the allocator). insert requires both Cpp17MoveAssignable and Cpp17MoveInsertable.

The same pattern applies to deque ([deque.modifiers]) and inplace_vector ([inplace.vector.modifiers]), as well as to related operations like emplace (in the cases where existing elements need to be shifted).

2.2. The relocation alternative

There is a different implementation strategy for shifting elements: instead of move-assigning each element to its new position, the implementation can relocate each element. A relocation consists of move-constructing the element at its new position and then destroying the original. In pseudocode:

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

    // Step 1: destroy erased elements
    std::destroy(first, last);

    // Step 2: relocate tail leftward
    std::uninitialized_relocate(last, end(), first);

    // Where uninitialized_relocate does, for each element (see P3516R2):
    //   std::construct_at(dst, std::move(*src));
    //   std::destroy_at(src);

    // ... update bookkeeping ...

    return first;
}

For the insert case:

template <typename T>
constexpr auto vector<T>::insert(iterator pos, const T& value)
{
    if (size() == capacity()) { /* reallocate */ }
    else if (pos == end()) { /* insertion at the end */ }
    else {
        // Step 1: relocate rightward
        std::uninitialized_relocate_backward(pos, end(), end() + 1);

        // Step 2: construct new element
        std::construct_at(std::to_address(pos), value);

        // ... update bookkeeping ...
    }
}

The relocation strategy is attractive for performance reasons. For trivially relocatable types -- types for which relocation is equivalent to a bytewise copy -- the entire shifting loop can be replaced by a single call to a trivial relocation primitive (such as the std::trivially_relocate proposed by [P2786R13]), which the implementation can carry out as an efficient low-level memory operation (such as memmove).

The overwhelming majority of types used in practice are trivially relocatable: scalar types, certain implementations of std::string, std::vector<T>, std::unique_ptr<T>, std::shared_ptr<T>, and most user-defined types composed of these. Trivial relocation instead of element-by-element move assignment and destruction provides order-of-magnitude performance improvements, especially for large containers.

The relocation-based algorithms (std::uninitialized_relocate, etc.) are the subject of [P3516R2]; they provide the building blocks that container implementations would use.

2.3. Why the current specification blocks relocation

The current specification prevents implementations from using the relocation strategy for two reasons.

First, the type requirements differ. The relocation strategy requires move constructibility (that is, Cpp17MoveInsertable for allocator-aware containers), but erase currently only requires Cpp17MoveAssignable. A type that is move-assignable but not move-constructible could legally be stored in a vector and erased, but the relocation strategy would fail to compile for such a type.

In practice, this is not a real concern. A type with a working move assignment operator but a deleted move constructor is pathological. All common types satisfy both requirements, and it is hard to come up with a realistic use case for a container holding a type that is move-assignable but not move-constructible.

Second, and more importantly, for certain types the two strategies produce different observable results. This is the core issue that this paper addresses.

2.4. When the two strategies diverge

The two strategies -- assignment-based and relocation-based -- produce different results for types where move assignment has different semantics from destroy-then-move-construct. Following the terminology introduced by [P2786R13], we call such types non-replaceable: a type is replaceable if destroying an object and move-constructing a new one in its place is equivalent to move-assigning to it.

It is important to note that replaceability is a more specific property than reference semantics. A type can have reference semantics and still be replaceable. For example, std::string_view refers to external storage and does not own its data, but its move assignment simply copies the pointer and length -- exactly what destroy-then-move-construct would do. string_view is replaceable, and the two shifting strategies produce identical results for it.

The types where the strategies diverge are the non-replaceable ones. There are two notable families.

2.4.1. Types with write-through assignment

The canonical example is std::tuple<int &>, whose move assignment operator has write-through semantics: it assigns through the reference rather than rebinding it.

Consider the following example:

int a = 1, b = 2, c = 3;
std::vector<std::tuple<int &>> v = { {a}, {b}, {c} };

v.erase(v.begin());  // erase the first element

Under the assignment strategy (current specification), the following happens:

1. v[1] is move-assigned to v[0]. Because tuple<int &>’s move assignment has write-through semantics, this assigns the value of b (2) into the int referenced by v[0], which is a. Now a == 2. v[0] still references a.

2. v[2] is move-assigned to v[1]. By the same logic, b gets the value of c (3). Now b == 3. v[1] still references b.

3. v[2] is destroyed (a no-op for references).

Result: v has two elements, v[0] references a and v[1] references b. The values of the external variables have been mutated: a == 2, b == 3, c == 3.

Under the relocation strategy, the following happens:

1. v[0] (referencing a) is destroyed (no-op).

2. v[1] is move-constructed into v[0]’s storage. The reference is copied, not written through: v[0] now references b. The original v[1] is then destroyed.

3. v[2] is move-constructed into v[1]’s storage. v[1] now references c. The original v[2] is then destroyed.

Result: v has two elements, v[0] references b and v[1] references c. The external variables are unchanged: a == 1, b == 2, c == 3.

The relocation strategy produces what most programmers would consider the "correct" result: erasing the first element should leave the remaining elements (references to b and c) intact, without mutating the referenced objects as a side effect.

The assignment strategy’s behavior -- silently overwriting a -- is surprising and arguably a design defect in how these types interact with container operations. Nevertheless, it is what the current Standard specifies.

Other types in this family include std::pair containing references, and user-defined types with analogous write-through assignment.

2.4.2. PMR containers

A more practically significant family of non-replaceable types is PMR containers: std::pmr::vector<T>, std::pmr::string, and other containers using std::pmr::polymorphic_allocator.

pmr::polymorphic_allocator does not provide a propagate_on_container_move_assignment member type, which causes allocator_traits<pmr::polymorphic_allocator> to report propagate_on_container_move_assignment as false_type. This means that when a PMR container is move-assigned, the target retains its own allocator. If the source and target use different memory resources, the move assignment cannot simply transfer ownership of the source’s storage; instead, it must perform an element-wise move into the target’s allocation. By contrast, move-constructing a PMR container from a source creates a fresh object that takes the source’s memory resource and can take direct ownership of the source’s storage.

This means that move assignment and destroy-then-move-construct are not equivalent for PMR containers: the allocator association of the resulting object may differ. PMR containers are therefore formally non-replaceable.

However, whether this non-replaceability actually matters in the context of container shifting depends on whether the elements within the vector share the same memory resource.

When all elements share the same memory resource -- which is the common case, especially when using a pmr::vector that propagates its allocator to its elements via uses_allocator construction (e.g. a pmr::vector<pmr::string>) -- the allocators of all elements compare equal. In this scenario, move assignment can transfer ownership of the source’s buffer (since the target’s allocator can deallocate it), producing the same result as move construction. The two shifting strategies are effectively equivalent, even though the type is formally non-replaceable.

When elements use different memory resources -- which requires deliberate setup, for instance by explicitly constructing elements with different memory resources -- the strategies diverge. Under the assignment strategy, each element retains the memory resource it was originally constructed with; the string data is moved (or copied) into the target’s own allocation. Under the relocation strategy, the element is destroyed and a new one is move-constructed in its place; the new object takes the source’s memory resource.

The key question is whether this difference in allocator association matters to the program. From a value semantics perspective, both strategies preserve the string’s content: after erasing position 0, the string at position 0 holds the data that was previously at position 1, regardless of which memory resource backs it. The difference is only in which allocator the resulting object uses -- an implementation detail that programs should not depend on during element shifting.

2.5. Affected containers

The containers affected by this proposal are:

• std::vector -- the primary target, as it is the most commonly used contiguous container.

• std::inplace_vector -- same storage model as vector, same shifting operations.

• std::deque -- uses blocks of contiguous storage; its insert and erase operations shift elements within blocks.

Node-based containers (std::list, std::forward_list) are not affected, as they do not shift elements. Associative and unordered containers are similarly unaffected (they are also node-based).

std::basic_string is not affected in practice, as its element type (charT) is always trivially relocatable, so the two strategies are indistinguishable.

3. Design decisions

3.1. Allow, do not mandate

This paper proposes that implementations be allowed to use either the assignment strategy or the relocation strategy for shifting elements in erase, insert, emplace, and related operations. The choice of strategy is left to the implementation.

This is a pure relaxation of the current specification: existing implementations that use assignment remain conforming. Implementations that want to use relocation are also conforming under this proposal. As a quality-of-implementation matter, an implementation that knows that relocation is more efficient than move assignment for a given type is now free to use it.

We do not propose to mandate the relocation strategy, as that would break existing code that depends on the assignment-based behavior (however exotic that code may be) and would prevent implementations from choosing the most appropriate strategy for their platform and use case.

This approach is analogous to how copy elision was handled before C++17: the Standard allowed implementations to elide copies, but did not require it. Programmers could not rely on copies being elided, and they could not rely on copies not being elided. This served the community well for many years.

3.2. The is_replaceable trait is not needed

The "Trivial Relocation for C++26" proposal ([P2786R13]) introduced the "replaceable" type property to capture exactly the property relevant here: whether destroying an object and constructing a new one in its place is equivalent to assigning to it. The trait was introduced out of concern that the library needed an explicit opt-in -- a language-level property -- before implementations could be allowed to use relocation (and, transitively, trivial relocation) for container operations such as insertion and erasure.

This paper takes a different stance. The reason implementations could not use relocation for these operations is not a missing trait, but an over-specification of their behavior. The current wording constrains implementations to use assignment by specifying complexity in terms of calls to the assignment operator. By relaxing this over-specification, we give implementations the freedom to use relocation -- and, in the future, trivial relocation -- without requiring any new language-level machinery.

We therefore argue that the is_replaceable trait is unnecessary for this purpose. The following arguments further support this position.

• The set of types where this matters in practice is small. The types for which the two strategies produce observably different results are non-replaceable types: those where move assignment is not equivalent to destroy-then-move-construct. This includes types with write-through assignment semantics (like tuple<int &>) and, formally, PMR containers. However, as discussed in the Motivation section, the tuple<int &> case is exotic and already problematic in containers, while the PMR case only diverges when elements use different memory resources -- an uncommon configuration. In the typical PMR setup (all elements sharing one resource), the strategies are equivalent.

• Containers already assume value semantics. The Standard’s container requirements have always been designed around types with value semantics. For instance, the Cpp17MoveConstructible requirement states that after move construction, "the value of u is equivalent to the value of rv before the construction" (emphasis ours). The concept of equivalence in terms of values -- rather than identity or resource association -- pervades the container requirements. Allowing relocation is consistent with this assumption.

• No new machinery is required. If we do not gate the optimization on a trait, no new type traits, no new concepts, and no new language features are needed. The change is purely a relaxation of the existing wording. This makes the proposal simpler to specify, simpler to implement, and simpler to teach.

• Laying the groundwork for trivial relocation in the language. P2786 was voted into C++26 but was subsequently removed and deferred. One lesson from that experience is that attempting to solve the entire trivial relocation problem in a single proposal -- the language trait, the library algorithms, the container optimizations -- makes the design space too large and the consensus too difficult to achieve.

  This paper takes a more incremental approach, similar to [P3516R2] (uninitialized relocation algorithms). P3516 proposes relocation algorithms that are useful today on their own merits, but that will be further optimized once trivial relocation is standardized. Similarly, this paper proposes relaxing container operations so that they can use relocation today, and will benefit from trivial relocation in the future.

  By adopting these proposals independently, we lay the groundwork so that when trivial relocation is discussed again, there will be no need to re-litigate questions like "should containers be allowed to use relocation?" or "do we need relocation algorithms?" -- those pieces will already be in place, and the discussion can focus on the core language feature.

3.3. Fallback: an opt-out mechanism

If SG9/LEWG finds the blanket permission proposed above to be too aggressive, a fallback position is available: an opt-out mechanism similar to what [P2959R0] proposed with its container_replace_with_assignment trait.

Under this approach, the library is allowed to use the relocation strategy by default for all types, but a type author can explicitly opt out by specializing a trait:

// Hypothetical opt-out mechanism:
template<>
struct std::use_assignment_for_container_shift<MyNonReplaceableType>
    : std::true_type {};

Types that specialize this trait to true_type would be guaranteed to always use the assignment strategy.

An opt-out (rather than opt-in) is the correct default here: the vast majority of types benefit from the optimization and do not care which strategy is used. Only the rare non-replaceable type would need to opt out.

This fallback adds complexity -- a new trait, a new concept for users to learn, a new specialization point -- and we believe it is unnecessary. But it is available as a compromise if the blanket permission does not achieve consensus.

3.4. Requirements changes

Under this proposal, the requirements for erase would effectively become: the element type must be either Cpp17MoveAssignable or Cpp17MoveInsertable (or both). The implementation may use either strategy, and the type must support whichever strategy the implementation chooses.

In practice, this is not a meaningful change. While types that are move-assignable but not move-constructible can exist (for instance, a type that requires address stability and therefore deletes its move constructor, but allows its contents to be updated via assignment), such types would not be used in a data-shifting container like vector in the first place.

For insert, there is no change in requirements: insert already requires both Cpp17MoveAssignable and Cpp17MoveInsertable.

3.5. Interaction with allocators

For allocator-aware containers (vector and deque), the relocation strategy must use allocator_traits::construct and allocator_traits::destroy rather than placement new and direct destructor calls.

This is not a new pattern for these containers. Vector already uses allocator_traits::construct and allocator_traits::destroy when it reallocates: elements are move-constructed into the new buffer and destroyed in the old one, all through the allocator. The relocation strategy for insert/erase is the same operation, except that the source and destination are within the same buffer rather than across two different buffers.

In fact, the relocation strategy is more consistent with how allocator-aware containers work than the assignment strategy. Under the current specification, construction and destruction go through allocator_traits, but assignment (operator=) is called directly, bypassing the allocator entirely. The relocation strategy replaces that direct assignment call with construction and destruction, both of which go through the allocator.

Note that the relocation algorithms proposed in [P3516R2] (std::uninitialized_relocate, etc.) are not allocator-aware: they use std::construct_at and std::destroy_at directly. An allocator-aware container implementation using the relocation strategy would need to perform the construction and destruction steps through allocator_traits::construct and allocator_traits::destroy itself, rather than delegating to the P3516 algorithms.

For inplace_vector, which does not use an allocator, the P3516 algorithms can be used directly.

3.6. Exception safety

The current specification of vector::erase provides a nothrow guarantee when T’s move assignment operator does not throw, and the basic exception safety guarantee otherwise. The wording in [vector.modifiers] states:

Throws: Nothing unless an exception is thrown by the assignment operator or move assignment operator of T.

Under the relocation strategy, exceptions during the shifting phase would come from the move constructor rather than the move assignment operator. The exception safety wording must therefore be generalized to cover both cases.

Importantly, the shape of the basic exception safety guarantee differs between the two strategies, even though both provide the basic guarantee (the container is left in a valid state).

Under the assignment strategy, if an exception is thrown mid-shift, the vector retains its original size. Some elements in the range [pos, end()) are in a moved-from (but valid) state. The caller is left with a vector containing an unknown number of moved-from elements whose values are indeterminate.

Under the relocation strategy, the erase operation first destroys the elements to be erased, leaving a window of uninitialized storage in the middle of the vector. Then then the tail elements are relocated to close the window. If an exception is thrown during this relocation, the vector cannot be left with a window of uninitialized storage in the middle. At a minimum, all the elements that still need to be relocated must be destroyed (the already-relocated elements in their new positions could be kept). The P3516 algorithms go one step further and destroy everything -- including the elements that were already successfully relocated -- because the caller of the algorithm has no way to know how many elements were transferred before the exception. Either way, the net result is that the vector’s size has decreased.

One can argue that the relocation-based postcondition is actually preferable: the vector is shorter, but all of its remaining elements are fully determinate. The assignment-based postcondition preserves the vector’s size but leaves the caller with moved-from elements in an unspecified state, which in practice are likely to be discarded anyway.

There is, however, a subtler issue. Consider a type T that is nothrow move-assignable but has a potentially throwing move constructor. A concrete example is std::list on some implementations (e.g. MSVC), where the move constructor may allocate a sentinel node and can therefore throw. Under the current specification, vector<std::list<int>>::erase is guaranteed not to throw during the shifting phase, because the shifting is done by noexcept move assignment. If an implementation switches to the relocation strategy, the shifting would use the potentially-throwing move constructor, and the erase could throw mid-shift -- leaving the vector in a partially-relocated state with a gap of destroyed objects in the middle. This would be a regression in exception safety.

We must address this issue. We propose the following rule: if is_nothrow_move_assignable_v<T> is true but the relocation strategy would involve a potentially-throwing operation (currently, this means is_nothrow_move_constructible_v<T> is false), the implementation must use the assignment strategy for shifting. This ensures no regression in exception safety for types like std::list where move assignment is noexcept but move construction is not.

If both move assignment and move construction are potentially throwing, then the current specification already permits exceptions during shifting, and neither strategy offers a stronger guarantee. In this case, the implementation is free to use either strategy.

For the common situation where T is both nothrow move-assignable and nothrow move-constructible -- which covers the vast majority of types in practice -- the implementation is of course free to use whichever strategy it prefers.

Note: we phrase the constraint in terms of whether the relocation strategy would throw, rather than directly in terms of is_nothrow_move_constructible_v, in order to leave room for future developments. If trivial relocation is added to the language, a type could be nothrow trivially relocatable despite having a potentially-throwing move constructor. In that case, the relocation strategy would still be nothrow (via trivial relocation), and the implementation should be free to use it. Phrasing the constraint in terms of the nothrow-ness of the relocation operation itself, rather than of the individual sub-operations, avoids the need to revisit this specification when trivial relocation is standardized.

4. Impact on the Standard

4.1. Wording changes

The proposed change would affect the following areas:

• [container.reqmts.general] / [sequence.reqmts]: the container requirements tables, which specify the type requirements for operations like erase and insert. Currently, erase requires Cpp17MoveAssignable; this would need to be relaxed to allow Cpp17MoveInsertable as an alternative (or the requirement would become implementation-defined).

• [vector.modifiers], [deque.modifiers], [inplace.vector.modifiers]: the Effects, Complexity, and Throws clauses for erase, insert, and emplace. The Effects modifications would state that elements may be shifted either by move assignment or by relocation (move construction followed by destruction), at the implementation’s discretion. The Complexity clauses currently count operations in terms of assignments and destructor calls (e.g., "the assignment operator of T is called the number of times equal to the number of elements after the erased elements"); these would need to be generalized to count either assignments or move constructions plus destructions. The Throws clauses currently reference exceptions thrown by assignment; these would need to be generalized to also cover exceptions thrown by move construction (see the exception safety discussion below).

4.2. ABI impact

This proposal has no ABI impact. The choice of shifting strategy is an implementation detail that does not affect the binary interface of any container.

4.3. Relationship to other proposals

This proposal is independent of, but complementary to, the ongoing efforts to add trivial relocation support to C++ ([P2786R13], [P1144R13]).

This paper addresses a prerequisite question: whether the specification of insertion and erasure operations allows implementations to use relocation (move construction followed by destruction) instead of assignment for shifting elements. Without this relaxation, even if trivial relocation were standardized, implementations could not use it for these operations, because the operations are currently specified in terms of assignment.

If both this proposal and a trivial relocation proposal are adopted, implementations would be able to use trivial relocation for shifting elements during insertion and erasure when the element type is trivially relocatable.

5. Future work

5.1. Trivial relocation

Once trivial relocation support is standardized (whether through a revival of P2786 or through another mechanism), this proposal’s relaxation would automatically enable implementations to use trivial relocation for shifting elements of trivially relocatable types, without any further wording changes.

5.2. Algorithms

The same argument applies to algorithms that shift elements within a range, such as std::remove and std::unique. These algorithms are currently specified in terms of move assignment (and require MoveAssignable). Allowing them to use relocation instead would enable the same class of optimizations. Note that std::rotate, while superficially similar, is specified in terms of swaps and therefore does not have the same issue. However, std::rotate could still benefit from optimization: when operating on iterators over contiguous storage of a trivially relocatable type, iter_swap could be specialized to perform a bytewise swap of the underlying storage. This is left to a future paper.

5.3. Value semantics requirement for elements stored in containers

This paper touches on a broader question: should the Standard formally require that container element types have value semantics? Such a requirement would resolve not only the issue addressed here, but also related issues with swap, sort, and other operations that behave surprisingly for types with reference semantics. This is a larger discussion that deserves its own paper.

6. Proposed Wording

Wording will be provided once a direction is chosen.

As a sketch, the wording change would modify the Effects clauses of vector::erase, vector::insert, deque::erase, deque::insert, inplace_vector::erase, and inplace_vector::insert to state that elements may be shifted either by move assignment or by relocation (move construction followed by destruction of the source element), at the implementation’s discretion. The complexity clauses would be updated accordingly.

7. Acknowledgements

Thanks to KDAB for supporting this work.

Thanks to Alisdair Meredith for [P2959R0], which explored the interaction between relocation and container operations. Thanks to Louis Dionne for the collaboration on [P3516R2].

All remaining errors are ours and ours only.