Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Stroustrup: C++ implementation of reserve()

Tags:

c++

I dont understand the code given in Bjarne Stroustrup - Programming Chapter 19.5.6 RAII for vector:

template<typename T, typename A>
struct vector_base {
  A alloc;
  T* elem;
  int sz;
  int space;
  vector_base(const A& a, int n) : alloc{a}, elem{alloc.allocate(n)}, sz{n}, space{n}{}
  ~vector_base() {alloc.deallocate(elem,space);}
}

//--------- vector class ------------
template<typename T, typename A = allocator<T>>
class vector : private vector_base<T,A> {
   // ...
};

//--------- vector reserve ------------
template<typename T, typename A>
void vector<T,A>::reserve(int newalloc)
{
  if (newalloc <= this->space) return;
  vector_base<T,A> b(this->alloc,newalloc);
  uninitialized_copy(b.elem, &b.elem[this->sz], this->elem);
  for(int i=0; i<this->sz; ++i)
     this->alloc.destroy(&this->elem[i]);
  swap<vector_base<T,A>>(*this,b);
}

1) I don't understand what is the need to pass the allocator along to the new vector_base object b. The vector_base has its own allocator, why does the constructor need this->alloc?

2) I don't understand the uninitialized_copy line. It looks like we copy from b to this->elem. It should be the other way around. Is that just a mistake in the book, or am I getting it wrong?

like image 434
Arthur Spooner Avatar asked Aug 16 '18 22:08

Arthur Spooner


1 Answers

The new vector needs to use the same allocator as the existing vector, i.e., this->alloc to make sure the reallocated memory comes from the same allocation area. If different allocators were used swap() on the last line would exchange the memory in the vector to point to memory allocated from a different allocator than that used to release the memory later.

The use of std::uninitialized_copy() is indeed wrong: it would copy from the newly created, uninitialised memory to the original values. Assuming the source and destination are appropriately put in place there is another error: if the memory of the existing vector is fully used, the expression &this->elem[this->sz] forms a reference to an object past the last element. The expression should rather read this->elem + this->sz. That is, the initialisation should be

uninitialized_copy(this->elem, this->elem + this->sz,
                   b.elem);
like image 182
Dietmar Kühl Avatar answered Sep 18 '22 13:09

Dietmar Kühl