C++ vector insert implementation crash

Question

I'm trying to reproduce the behavior of vector and a weird crash occurs when I try to use vector::insert(iterator, size_type, const T &), my code looks like this:

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; }

My code seems legit but I get this crash

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

and with valgrind I get an invalid read at std::copy, but I struggled for the past four hours but didn't find which value or parameter was wrong. The crash occured at this test:

            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)

• If you're debugging this, you should know whether you called reserve() here, right? Because you're single-stepping through the function.

  • If you didn't already know this, that's something you should look out for when debugging. If you did, it should have been in the question.

• And since you're writing your own own std::vector::reserve you know it invalidated all iterators including pos, because your implementation always allocates new storage.

  • If you want to add a debug mode to detect this kind of stuff, you can add a generation counter to the container and to your iterator, and increment the container's generation counter on every invalidating operation.

• If you get an invalid read in valgrind, it should also tell you where the memory was originally allocated and where it was released.

  • If it didn't, check its options. If it did, that information should also be in the question.

So, the proximate fix is to write const auto pos_offset = pos - begin(); before (maybe) calling reserve(), and then use pos_offset to recover the correct iterator.

Other issues are:

• identifiers with a leading underscore followed by an upper-case letter (like _M) are reserved for the implementation. The std::vector provided in your standard library is part of the implementation, but your code is not.
• _allocator.deallocate does not destroy the array elements, and _allocator.allocate does not construct them. See the use of std::construct_at and std::destroy_n in the 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);