如何处理将初始化值的一部分移动到分配中重叠的部分初始化和部分未初始化的空间？

Question

背景

上下文，我正在尝试在自定义向量类型上实现 std::vector 插入。这适用于

vector::insert

的所有重载，我试图与 C++ 的 std::vector 保持奇偶校验。

在我被迫重新分配内存的情况下，插入实际上是微不足道的。当我不需要需要重新分配时，当我的容量> =插入元素所需的新大小时，我很困惑。我在这里使用列表https://en.cppreference.com/w/cpp/container/vector/insert

如果我可能没有可平凡复制的类型，并且我可能没有默认的可构造类型，并且我可能没有可移动类型，那么我不太确定如何正确初始化数据。

例如下面的原型

constexpr iterator insert(const_iterator pos, const T &value);

如果插入

value

不会触发分配大小的调整，那么这意味着我可以只使用已经进行的分配。

我通常会选择像

copy_backwards

这样的东西，但问题是，如果我这样做，我不知道该类型是否是廉价可移动的，如果可用的话我应该选择。虽然这对于输入

value

没有任何意义，仍然应该被复制，但我很困惑这里需要发生什么，例如，假设我有

pointer_type m_ptr; 
size_type m_size; 
size_type m_capacity;
allocator_type m_allocator; 

我将尝试类似的操作来移动已经有效的数据。

if constexpr (std::is_move_constructible_v<T>) {
    auto pos_idx = static_cast<size_type>(std::distance(cbegin(), pos));
    std::move_backward(m_ptr + pos_idx, m_ptr + m_size, m_ptr + pos_idx + 1);
    ...
}

但问题是我正在进入带有最后一个元素的未初始化内存。所以我可以先对最后一个元素进行未初始化的移动。

if constexpr (std::is_move_constructible_v<T>) {
    std::uninitialized_move(m_ptr + m_size - 1, m_ptr + size, m_ptr + size); 
    auto pos_idx = static_cast<size_type>(std::distance(cbegin(), pos));
    std::move_backward(m_ptr + pos_idx, m_ptr + m_size - 1, m_ptr + pos_idx + 1);
    ...
}

但是现在最后一个元素的空间假设尚未初始化？所以我不能再向后移动了。

这意味着我需要对插入点之后的每个值进行未初始化的移动，对吗？但我不仅需要这样做，我还需要为每个值手动调用未初始化的移动函数，因为我需要有效地执行一个

std::uninitalized_move_backward(...)

（希望任何看到这个的人都会意识到它不存在），因为uninit std 函数都不是重叠安全的吗？即：

if constexpr (std::is_move_constructible_v<T>) {
    auto pos_idx = static_cast<size_type>(std::distance(cbegin(), pos));
    auto pos_end_reverse = pos != begin() ? (std::reverse_iterator(pos - 1) : rend()); 
    for(auto pos_r = rbegin(); pos_r != pos_end_reverse; ++pos_r){
        //subtract, because this is a reverse iterator and we are trying to look *forward*. 
        std::uninitialized_move_n(pos_r, 1, pos_r - 1); 
    } 
} 

问题

对于我有一些初始化值需要移动到分配中重叠的初始化和未初始化空间的情况，是否有任何方法可以为每个元素向后手动调用未初始化移动，或者是否有处理这种情况的 stdlib 方法？

Answer 1

更好地理解这里的要求使得所需的语义比看起来简单得多：只需提醒自己，移动会使移出的对象处于“有效但未指定的状态”。这意味着移出的对象不是处于“未初始化”状态（如您所说）。

这意味着在插入期间，只有重新定位到最后一个有效（初始化）值之后的新值才会移动到未初始化的空间。

使用一个简单的示例：现有向量有六个值，从

vector[0]

到

vector[5]

，并且您要在向量的开头插入两个新值。

这意味着

vector[5]

到

vector[7]

和

vector[4]

到

vector[6]

是进入未初始化空间的移动。所有其他动作，

vector[3]

到

vector[5]

都是不是。它们实际上是一个移动分配（自

vector[5]

起，其前任被留在“有效但未指定的空间中）。

总而言之，在没有重新分配的情况下进行的插入最终会执行三部分操作：1）未初始化的移动到向量增长到的所有保留的未初始化空间，2）对所有其他移动值的移动分配，3）移动分配向量中插入的新值的数量。

并且，不，没有标准库算法可以为您处理所有这些，所有这些逻辑都必须实现。但其实没那么复杂。