Stroustroup: free(): double free detected in tcache 2 when implementing vector::reserve()

Question

The code given in Bjarne Stroustrup - Programming Principles and Practice - Chapter 19.5.6 "RAII for vector" doesn't work when calling push_back() then reserve(). Separately they work fine.

I get this error "free(): double free detected in tcache 2"
With debugging I see that after calling swap() inside reserve() the variable b.elem[0] has <error: Cannot access memory at address 0x55555556d>

The uninitialized_copy is written wrong in the book so maybe there's something else missing? Or am I doing something wrong?

Update 17.08: I added constructors, destructors, copy and move operations for vector_base and vector (inspired from C++ Programming Language) and now it works. Thanks for the replies!

I have a question: "Programing Principles and Practice" makes vector class a derivate of vector_base class while "C++ Programming Language" makes a vector_base object a data member of class vector. I wonder which option is better? They seem equivalent though.

#include <iostream>
#include <stdexcept>
#include <string>
#include <algorithm>

template <typename T>
class allocator
{
public:
    T *allocate(int n) { return (T *)malloc(n * sizeof(T)); } // allocate space for n objects of type T
    void construct(T *p, const T &v) { new (p) T{v}; }        // construct a T with the value v in p
    void destroy(T *p) { p->~T(); }                           // destroy the T in p
    void deallocate(T *p, int n) { free(p); }                 // deallocate n objects of type T starting at p
};

template <typename T, typename A = allocator<T>>
struct vector_base
{
    A alloc;   // allocator,
    T *elem;   // start of allocation
    int sz;    // number of elements
    int space; // amount of allocated space

    vector_base()
        : sz{0}, elem{nullptr}, space{0} {}
    vector_base(const A &a, int n)
        : alloc{a}, elem{alloc.allocate(n)}, sz{0}, space{n} 
    {
    }
    ~vector_base() { alloc.deallocate(elem, space); }

    vector_base(const vector_base &) = delete; // no copy operations
    vector_base &operator=(const vector_base &) = delete;
    vector_base(vector_base &&); // move operations
    vector_base &operator=(vector_base &&);
};

template <class T, class A>
vector_base<T, A>::vector_base(vector_base &&a)              // move constructor
    : alloc{a.alloc}, elem{a.elem}, sz{a.sz}, space{a.space} // no free space if space{a.sz}
{
    a.elem = nullptr;
    a.sz = a.space = 0;
}
template <class T, class A>
vector_base<T, A> &vector_base<T, A>::operator=(vector_base &&a) // move assignment
{
    elem = a.elem;
    sz = a.sz;
    space = a.space; // also move space
    a.elem = nullptr;
    a.sz = a.space = 0;
    return *this;
    // swap(*this, a); // also works
    // return *this;
}

template <typename T, typename A = allocator<T>>
class vector : private vector_base<T, A>
{
public:
    vector()
        : vector_base<T, A>() {}

    explicit vector(int s);
    vector(std::initializer_list<T> lst); // 18.2 initializer-list constructor
    vector(const vector &);               // copy constructor
    vector &operator=(const vector &);    // copy assignment

    vector(vector &&);            // move constructor
    vector &operator=(vector &&); // move assignment

    ~vector(); // destructor

    T &operator[](int n) { return this->elem[n]; }
    const T &operator[](int n) const { return this->elem[n]; }
    int size() const { return this->sz; }
    int capacity() const { return this->space; }
    T *get_elem() const { return this->elem; }  
    A get_alloc() const { return this->alloc; } 
    void reserve(int newalloc);
    void push_back(const T &d);
    void resize(int newsize, T val = T());
};

template <typename T, typename A>
vector<T, A>::vector(int s)
    : vector_base<T, A>(this->alloc, s)
{
    for (int i = 0; i < s; ++i)                     
        this->alloc.construct(&this->elem[i], T()); 
}
template <typename T, typename A>
vector<T, A>::vector(std::initializer_list<T> lst) 
    : vector_base<T, A>(this->alloc, lst.size())   
{
    std::copy(lst.begin(), lst.end(), this->elem); 
    this->sz = lst.size();                         
}
template <typename T, typename A>
vector<T, A>::vector(const vector &a) // copy constructor
    : vector_base<T, A>(a.alloc, a.size())
{
    uninitialized_copy(a.elem, a.elem + a.sz, this->elem); 
    this->sz = a.sz;
}
template <typename T, typename A>
vector<T, A> &vector<T, A>::operator=(const vector &a) // copy assignment
{
    if (this == &a) // self-assignment, no work needed
        return *this;
    if (a.sz <= this->space) // enough space, no need for new allocation 
    {
        uninitialized_copy(a.get_elem(), &a.get_elem()[a.size()], this->elem);
        this->sz = a.sz;
    }
    // took it from C++ Programming Language
    vector temp{a}; // copy allocator
    std::swap(*this, temp);
    return *this;
}

template <typename T, typename A> // move constructor
vector<T, A>::vector(vector &&a)
    : vector_base<T, A>(a.alloc, a.size()) // get a's data members (alloc, elem, space)
{
    this->sz = a.sz; // also get a's size
    a.elem = nullptr;
    a.sz = a.space = 0;
}
template <typename T, typename A>
vector<T, A> &vector<T, A>::operator=(vector<T, A> &&a) // move assignment
//: vector_base<T, A>(a.alloc, a.size())
{
    for (int i = 0; i < this->sz; ++i)
        this->alloc.destroy(&this->elem[i]);
    this->alloc.deallocate(this->elem, this->space);

    this->elem = a.elem;
    this->sz = a.sz;
    this->space = a.space;
    a.elem = nullptr;
    a.sz = a.space = 0;
    return *this;
}

template <typename T, typename A>
vector<T, A>::~vector() // destructor
{
    for (int i = 0; i < this->sz; ++i)
        this->alloc.destroy(&this->elem[i]); 
}

template <typename T, typename A>
void print(const vector<T, A> &v, const std::string &s)
{
    std::cout << '\n';
    std::cout << s << ' ' << "size: " << v.size() << ' ' << "capacity: " << v.capacity() << ' ';
    std::cout << "elements: ";
    for (int i = 0; i < v.size(); ++i)
        std::cout << v[i] << ' ';
    std::cout << '\n';
}

template <typename T, typename A>
void vector<T, A>::reserve(int newalloc)
{
    if (newalloc <= this->space)
        return;                                 // never decrease allocation
    vector_base<T, A> b(this->alloc, newalloc); // allocate new space
    uninitialized_copy(this->elem, &this->elem[size()], b.elem); // copy from caller of reserve() to b
    b.sz = this->sz;                                             // vector_base b has size = 0 because of the constructor so you have to change it
    for (int i = 0; i < this->sz; ++i)
        this->alloc.destroy(&this->elem[i]); // destroy old
    std::swap<vector_base<T, A>>(*this, b); // swap representations
} // at exit ~vector_base will deallocate b

template <typename T, typename A> // 19.3.7
void vector<T, A>::push_back(const T &val)
{
    if (this->space == 0)
        reserve(8);
    else if (this->sz == this->space)
        reserve(2 * this->space);
    this->alloc.construct(&this->elem[this->sz], val); // add val to position sz
    ++this->sz;
}
template <typename T, typename A>
void vector<T, A>::resize(int newsize, T val) //  deleted =T() from here
{
    reserve(newsize);
    for (int i = this->sz; i < newsize; ++i)  // if newsize is bigger than currect size construct default values
        this->alloc.construct(&this->elem[i], val); // construct
    for (int i = newsize; i < this->sz; ++i)   // if newsize is smaller than currenct size destroy the elements
        this->alloc.destroy(&this->elem[i]); // destroy
    this->sz = this->space= newsize; // reset space - like in C++PL

}

int main()
try
{
   vector<std::string> vs;
    vs.push_back("test");
    print(vs, "vs.push_back():");
    vs.reserve(10);
    print(vs, "vs.reserve(10):");
}
catch (std::exception &e)
{
    std::cerr << "exception: " << e.what() << '\n';
    return 1;
}
catch (...)
{
    std::cerr << "exception\n";
    return 2;
}

Answer 1

The problem is that vector_base in the example fails to follow the rule of 5 (previously, of 3). It implements a destructor where it releases a resource, but doesn't implement copy / move constructors nor assignment operators to handle that. When reserve calls swap with vector_base arguments, it will move (previously copy) the instance, then do two move (previously copy) assignments after which the intermediate object is destroyed... and that destructor frees the same pointer that is still owned by one of the arguments which results in undefined behaviour when the pointer is freed again in the destructor of that object.

One correct C++03 implementation would be to remove ~vector_base() and instead deallocate at the end of vector::reserve and vector::~vector (which needs to be added). Or maybe you could use std::auto_ptr in vector_base. You also need to define copy constructor and assignment operator of the vector.

In C++11 and later, you would define the move constructor and assignment operator for vector_base.