CODEWITHSUNDEEP
c++c++11vectorstl
Kemal
Kemal

Reputation: 889

reserve() Implementation for std::vector in STL

Consider this implementation of std::vector::reserve() from the book "The C++ Programming Language, 4th ed., Bjarne Stroustrup:

template<class T, class A>
void vector<T,A>::reserve(size_type newalloc)
{
    if (newalloc<=capacity()) return;
    vector_base<T,A> b {vb.alloc,newalloc};          // get new storage
                                                     // (see PS of question for details on vb data member)

    T* src  = elem;                                  // ptr to the start of old storage
    T* dest = b.elem;                                // ptr to the start of new storage       
    T* end  = elem+size();                           // past-the-end ptr to old storage
    for (; src!=end; ++src, ++dest) {
        new(static_cast<void*>(dest)) T{move(*src)}; // move construct
        src–>~T();                                   // destroy
    }

    swap(vb,b);                                      // install new base (see PS if needed)
} // implicitly release old space(when b goes out of scope)

Note that in the loop, for each element in vector, at least one call is made to a ctor and a dtor(possibly triggering more such calls if the element's class has bases, or if the class or its bases have data members with ctors). (In the book, for-loop is actually a separate function, but I injected it into the reserve() here for simplicity.)

Now consider my suggested alternative:

template<class T, class A>
void vector<T,A>::reserve(size_type newalloc)
{
    if (newalloc<=capacity()) return;
    vector_base<T,A> b {vb.alloc,newalloc};    // get new space

    memcpy(b.elem, elem, sz);                  // copy raw memory
                                               // (no calls to ctors or dtors)

    swap(vb,b);                                // install new base
} // implicitly release old space(when b goes out of scope)

To me, it seems like the end result is the same, minus the calls to ctors/dtors.

Is there a situation where this alternative would fail, and if so, where is the flaw?

P.S. I don't think it is much relevant, but here are the data members of vector and vector_base classes:

// used as a data member in std::vector
template<class T, class A = allocator<T> >
struct vector_base {                    // memory structure for vector
     A alloc;       // allocator
     T* elem;       // start of allocation
     T* space;      // end of element sequence, start of space allocated for possible expansion
     T* last;       // end of allocated space

     vector_base(const A& a, typename A::size_type n)
         : alloc{a}, elem{alloc.allocate(n)}, space{elem+n}, last{elem+n} { }
     ~vector_base() { alloc.deallocate(elem,last–elem); } // releases storage only, no calls 
                                                          // to dtors: vector's responsibility        
     //...
};

// std::vector
template<class T, class A = allocator<T> >
class vector {
     vector_base<T,A> vb;            // the data is here
     void destroy_elements();
public:
     //...
};

Upvotes: 3

Views: 2008

Answers (1)

Christophe
Christophe

Reputation: 73542

This might fail:

  • memcpy() will work only if you have a vector of POD.

  • It will fail for all other kind of objects as it doesn't respect the semantic of the objects it copies (copy construction).

Example of issues:

  • If the constructor of the object sets some internal pointers to internal members, your memcpy() will copy the value of the original pointer, which will not be updated correctly and continue to point to a memory region that will be released.
  • If the object contains a shared_ptr, the object count will become inconsistent (memcpy() will duplicate the pointer without incrementing its reference count, then swap() will make sure that the original shared pointer will be in b, which will be released, so that the shared pointer reference count will be decremented).

As pointed out by T.C in the comments, as soon as your vector stores non-POD data the memcpy() results in UB (undefined behaviour).

Upvotes: 3

Related Questions