STL vector implementation

Question

I've implemented a simple vector-like structure. I would appreciate all criticism relevant to code, style, flow, camelCase vs underscore, and so forth.

template <class T>
class  Vector {
public:

    typedef T* Iterator;

    Vector();
    Vector(unsigned int size);
    Vector(unsigned int size, const T & initial);
    Vector(const Vector<T>& v);
    ~Vector();

    unsigned int capacity() const;
    unsigned int size() const;
    bool empty() const;
    Iterator begin();
    Iterator end();
    T& front();
    T& back();
    void push_back(const T& value);
    void pop_back();

    void reserve(unsigned int capacity);
    void resize(unsigned int size);

    T & operator[](unsigned int index);
    Vector<T> & operator = (const Vector<T> &);
    void clear();
private:
    unsigned int _size;
    unsigned int _capacity;
    unsigned int Log;
    T* buffer;
};

template<class T>
Vector<T>::Vector() {
    _capacity = 0;
    _size = 0;
    buffer = 0;
    Log = 0;
}

template<class T>
Vector<T>::Vector(const Vector<T> & v) {
    _size = v._size;
    Log = v.Log;
    _capacity = v._capacity;
    buffer = new T[_size];
    for (unsigned int i = 0; i < _size; i++)
        buffer[i] = v.buffer[i];
}

template<class T>
Vector<T>::Vector(unsigned int size) {
    _size = size;
    Log = ceil(log((double) size) / log(2.0));
    _capacity = 1 << Log;
    buffer = new T[_capacity];
}

template <class T>
bool Vector<T>:: empty() const {
    return _size == 0;
}

template<class T>
Vector<T>::Vector(unsigned int size, const T& initial) {
    _size = size;
    Log = ceil(log((double) size) / log(2.0));
    _capacity = 1 << Log;
    buffer = new T [_capacity];
    for (unsigned int i = 0; i < size; i++)
        buffer[i] = initial;
}

template<class T>
Vector<T>& Vector<T>::operator = (const Vector<T> & v) {
    delete[] buffer;
    _size = v._size;
    Log = v.Log;
    _capacity = v._capacity;
    buffer = new T [_capacity];
    for (unsigned int i = 0; i < _size; i++)
        buffer[i] = v.buffer[i];
    return *this;
}

template<class T>
typename Vector<T>::Iterator Vector<T>::begin() {
    return buffer;
}

template<class T>
typename Vector<T>::Iterator Vector<T>::end() {
    return buffer + size();
}

template<class T>
T& Vector<T>::front() {
    return buffer[0];
}

template<class T>
T& Vector<T>::back() {
    return buffer[_size - 1];
}

template<class T>
void Vector<T>::push_back(const T & v) {
    /*
        Incidentally, one common way of regrowing an array is to double the size as needed.
        This is so that if you are inserting n items at most only O(log n) regrowths are performed
        and at most O(n) space is wasted.
    */
    if (_size >= _capacity) {
        reserve(1 << Log);
        Log++;
    }
    buffer [_size++] = v;
}

template<class T>
void Vector<T>::pop_back() {
    _size--;
}

template<class T>
void Vector<T>::reserve(unsigned int capacity) {
    T * newBuffer = new T[capacity];

    for (unsigned int i = 0; i < _size; i++)
        newBuffer[i] = buffer[i];

    _capacity = capacity;
    delete[] buffer;
    buffer = newBuffer;
}

template<class T>
unsigned int Vector<T>::size() const {
    return _size;
}

template<class T>
void Vector<T>::resize(unsigned int size) {
    Log = ceil(log((double) size) / log(2.0));
    reserve(1 << Log);
    _size = size;
}

template<class T>
T& Vector<T>::operator[](unsigned int index) {
    return buffer[index];
}

template<class T>
unsigned int Vector<T>::capacity()const {
    return _capacity;
}

template<class T>
Vector<T>::~Vector() {
    delete[] buffer;
}

template <class T>
void Vector<T>::clear() {
    _capacity = 0;
    _size = 0;
    buffer = 0;
    Log = 0;
}

Answer 1

Your code is C++03 like (ie there are no move constructors or move assignment operators). You should definitely think about updating your class to be move aware.

The first thing about the interface is that the assignment operator is not close to the constructors. Since these are highly linked I like to place the assignment operators very close to the constructors (see rule of three/five).

Using _ as a prefix is a bad idea. You don't break any rules (but was this on purpose or just an accident?). The rules are sufficiently complex that prefix _ on identifiers is a bad idea for user space code. Others have suggested a prefix like m_ personally I think that is old school advice. As long as the naming is clear there should be no issues.

My personal convention with identifiers is that anything that can be an object starts with a lowercase letter. Anything that is a type begins with an uppercase letter. Others will disagree with this convention as the standard does not follow it and this can lead to other conflicts.

Here is one of those exceptions to my rules.

    typedef T* Iterator;

You should probably have iterator with a lowercase i. This is because a lot of the algorithms will use the type.

Good start.

    Iterator begin();
    Iterator end();
    T& front();
    T& back();
    T & operator[](unsigned int index);

But you will need const versions of all these (and a const_iterator type) to be a fully compliant container.

You are going to have a hard time making this work if the buffer is of type T. Every time you expand the buffer all the elements in the buffer will be initialized with T constructor. For int this is not a problem. But if T has a non trivial constructor then you are going to pay a heavy price initializing elements that may never be used.

T* buffer;

Really the buffer should be something that does not have a constructor.

char* buffer;

Prefer the initializer list.

template<class T>
Vector<T>::Vector() {
    _capacity = 0;
    _size = 0;
    buffer = 0;
    Log = 0;
}

// This will also warn about out of order initialization.
// Not a big thing but it keeps your thinking logical.

template<class T>
Vector<T>::Vector()
    : _size(0)
    , _capacity(0)
    , Log(0)
    // Personally I would always allocate some space for the buffer
    // even if the size is zero. This way I do not have to worry about
    // the special case of buffer ever being a NULL pointer.
    //
    // Having a special case of NULL will affect all the methods and make
    // the code much more complex. Reduce code complexity means easier to
    // maintain code.
    //
    , buffer(new char[sizeof(T) * capacity])
    // Note this assumes buffer is (char* as described above)
{}

Again. Use an initializer list.

template<class T>
Vector<T>::Vector(const Vector<T> & v) {
    _size = v._size;
    Log = v.Log;
    _capacity = v._capacity;

Do you really mean to allocate _size memebers to the buffer. Should this not be _capacity?

    buffer = new T[_size];

    for (unsigned int i = 0; i < _size; i++)
        buffer[i] = v.buffer[i];
}

Also use the internal algorithms to help you.

template<class T>
Vector<T>::Vector(Vector<T> const& v)
 // Note. I put cost here   ^^^^^   most of the time it does not matter.
 // There is one corner case where it does.
    : _size(v._size)
    , _capacity(v._capacity)
    , Log(v.Log)
    , buffer(new char[sizeof(T) * _capacity])
{
    for (unsigned int i = 0; i < _size; i++)
    {
        // Now you can use placement new to copy the elements from
        // source into the current vector.
        new (buffer + sizeof(T) * i) T(v[i]);
    }
}

Again use initializer list.

template<class T>
Vector<T>::Vector(unsigned int size) {
    _size = size;

This seems to be a constant. I would just make this a constant of the class and calculate it once by hand. The use of these maths functions seems a bit like overkill to me.

    Log = ceil(log((double) size) / log(2.0));
    _capacity = 1 << Log;
    buffer = new T[_capacity];
}

Personally one liners like this.

template <class T>
bool Vector<T>:: empty() const {
    return _size == 0;
}

I just put inline into the class.

The assignment operator problem has been covered by @liv902

template<class T>
Vector<T>& Vector<T>::operator = (const Vector<T> & v) {
    delete[] buffer;
    _size = v._size;
    Log = v.Log;
    _capacity = v._capacity;
    buffer = new T [_capacity];
    for (unsigned int i = 0; i < _size; i++)
        buffer[i] = v.buffer[i];
    return *this;
}

Basically you should not change the state of your object until you have guranteed that there are no expceptions can be thrown and leave your object in an incosistent state. This means your assignemnt should proceed in three stages.

1. Copy the state of the src class into temporary objects.
   This is because making the copy can throw an exception and thus you should not put your object into a state wheere it can be invalid.
2. Swap the state of you object with the temporary values.
   Swapping is an exception safe operation.
3. Now you can destroy the old state (which is in the temporary values).
   This can also throw an exception, but your object will be in a consistent state.

This techniques means you provide the "Strong (Transaction) Exception Guarantee" (You can look it up in google).

The easiest way to implement the above is to use the "Copy and Swap Idiom".

When you remove something from a std::vector.

template<class T>
void Vector<T>::pop_back() {
    _size--;
}

The destructor for that object is also called. This allows you free resources for non trivial resources (say T was a std::shared_ptr<int>) not calling the destructor means you are effectively retaining a reference to an object that could be freed.

It is perfectly valid to manually call the destructor of an object (In fact this is very normal when pared with placement new operation).

template<class T>
void Vector<T>::pop_back() {

    // You way want to do a check for empty() before calling the destructor.

    // Call the destructor.
    (reinterpret_cast<T*>(buffer)[_size-1]).~T();

    // It is usual to prefer the pre decrement (and pre increment).
    --_size;
}

Just like a pop.
When you clear a vector you generally expect the destructor to all the members to be called.

template <class T>
void Vector<T>::clear() {
    _capacity = 0;
    _size = 0;
    buffer = 0;
    Log = 0;
}

Answer 2

• Using log to calculate capacity is very questionable. It forces a client to link the executable with -lm. I would not bother with Log at all: just double the capacity as needed.

• A repeated code in the constructors should be factored out.

• It is OK (and in fact preferable) to use std::copy() instead of loops.

• pop_back() must destroy a buffer[size - 1] object.

• clear() must delete [] buffer. Edit: it must destroy everything in the buffer. The buffer itself may stay. Thanks to Loki Astari

• All accessors (begin, end, front, back, operator[]) must have const versions as well.

• A choice of unsigned int for size parameters is questionable. A natural type for size is size_t.

PS: addressing the comment:

The spec says

const T& front() const;
      T& front();

Both must be implemented. It is not the matter of convention: you want your class to be useful, that is, std algorithms should work with it - and they expect those methods.

Answer 3

1. Use a size_type.

   What if one day, instead of an unsigned int, you wanted to use an unsigned long, or a size_t, or a unsigned long long for some reason. You would have to change multiple lines in your code. If anybody was using your Vector class then they would have to change their code as well.

   Defining a size_type would make it so that you only have to change one line of code and anyone using your Vector class would (hypothetically) not have to change any of their code at all.

   You can define a size_type like this:

   typedef unsigned int size_type ;
   

   Or if you have C++11:

   using size_type = unsigned int ; // C++11 only
   

2. Be mindful of exception safety.

   For example, let's take a look at your copy-assignment operator.

   template<class T>
   Vector<T>& Vector<T>::operator = (const Vector<T> & v) {
       delete[] buffer; // no throw (can cause undefined behavior)
       _size = v._size; // no throw
       Log = v.Log; // no throw
       _capacity = v._capacity; // no throw
       buffer = new T [_capacity]; // CAN THROW!!
       for (unsigned int i = 0; i < _size; i++) // no throw
           buffer[i] = v.buffer[i]; // no throw
       return *this; // no throw
   }
   

   Let's say I was using your Vector like this:

   Vector <int> v ;
   // Initialize v and add some elements
   // some other code...
   
   try {
       // copy-assignment operator
       // let's pretend it throws std::bad_alloc()
       v = someOtherVector ;
   
       // some other code...
   }
   
   // some other code...
   

   Assuming I handle the exception, v will now have an incorrect _size, Log, and _capacity.

3. Your copy-assignment operator does not check for self-assignment.

   Your program will invoke undefined behavior when you get to this part of your code:

   for (unsigned int i = 0; i < _size; i++)
       buffer[i] = v.buffer[i];
   

   Check out the copy and swap idiom for a good way to tackle this problem.

4. Your member-variable names are inconsistent.

   You should follow a single convention.

   One way to do it:

   size_type _size;
   size_type _capacity;
   size_type _log;
   T* _buffer;
   

   Another way to do it:

   size_type m_size;
   size_type m_capacity;
   size_type m_log;
   T* m_buffer;
   

   There are a few other conventions. Just pick one and stick to it, and make sure you don't use any reserved names.

Answer 4

Every time you are deleting buffer first, you have to check if _size > 1. If so, then you are using delete[], otherwise just delete.

if(m_size >1)
        delete [] buffor;
        delete buffor;