C++ 向量插入实现崩溃

Question

我正在尝试重现 vector 的行为，但当我尝试使用 vector::insert(iterator, size_type, const T &) 时发生了奇怪的崩溃，我的代码如下所示：

iterator    insert(iterator pos, size_type count, const T &value) {
    return _M_insert_size(pos, count, value);
}

//with
iterator    _M_insert_size(iterator pos, size_type count, const T &value) {
    const size_type size = _size + count; // get the new size

    if (_capacity < size) reserve(size); // reserve if larger than capacity
    // here `end()` is still using old size
    std::copy(pos, end(), pos + count); // move [pos;end()[ to (pos + count)
    std::fill(pos, pos + count, value); // fill [pos;(pos + count)[ with value
    _size = size; // set the new size
    return pos;
}

//and
void        reserve(size_type new_cap) {
    if (new_cap > max_size()) throw std::length_error(std::string("vector::") + __func__);

    if (new_cap > _capacity) {
        T   *ptr = _allocator.allocate(new_cap);
        std::copy(begin(), end(), ptr);
        _allocator.deallocate(_array, _capacity);
        _capacity = new_cap;
        _array = ptr;
    }
}

//and
iterator                begin(void) { return _array; }
iterator                end(void) { return _array + _size; }

我的代码似乎是合法的，但我却崩溃了

munmap_chunk(): invalid pointer
[1]    3440 abort (core dumped)  ./build/test

使用 valgrind，我在 std::copy 处读取无效，但我在过去的四个小时里苦苦挣扎，但没有发现哪个值或参数是错误的。此次测试发生崩溃：

            ft::vector< int >   v(10, 42);
            std::vector< int >  r(10, 42);

            v.insert(v.begin(), 5UL, 1);
            r.insert(r.begin(), 5UL, 1);

Answer 1

    if (_capacity < size) reserve(size); // reserve if larger than capacity
    // here `end()` is still using old size
    std::copy(pos, end(), pos + count); // move [pos;end()[ to (pos + count)

如果你正在调试这个，你应该知道你是否在这里调用了reserve()，对吧？因为您正在单步执行该函数。
- 如果您还没有知道这一点，那么您在调试时应该注意这一点。如果你这样做了，它应该在问题中。
并且由于您正在编写自己的 std::vector::reserve，您知道它使包括 pos 在内的所有迭代器都无效，因为您的实现总是分配新的存储空间。
- 如果您想添加调试模式来检测此类问题，您可以向容器和迭代器添加生成计数器，并在每次无效操作时增加容器的生成计数器。
如果你在valgrind中得到一个无效读取，它应该也会告诉你内存最初分配到哪里，又从哪里释放。
- 如果没有，请检查其选项。如果是这样，该信息也应该在问题中。

因此，最接近的解决方法是在（可能）调用 reserve() 之前编写 const auto pos_offset = pos - begin();，然后使用 pos_offset 恢复正确的迭代器。

其他问题是：

带有前导下划线后跟大写字母的标识符（如 _M）保留用于实现。您的标准库中提供的 std::vector 是实现的一部分，但您的代码不是。

_allocator.deallocate不破坏数组元素，_allocator.allocate不构造数组元素。请参阅 std::construct_at 和 std::destroy_n 在 std::allocator example code 中的用法：

    S* s = allocator.allocate(n); // may throw
    for (std::size_t i{}; i != n; ++i) {
    //  allocator.construct(&s[i], i+42); // removed in C++20
        std::construct_at(&s[i], i+42);   // since C++20
    }
    std::destroy_n(s, n);
    // or loop over allocator.destroy(&s[i]); before C++17
    allocator.deallocate(s, n);

C++ 向量插入实现崩溃

C++ vector insert implementation crash

c++

vector

iterator