Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I've implemented a simple vector like STL C++.

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

I would appreciate all criticism relevant to code, style, flow, camelCase vs underscore, and so forth.


Edit (reflects some of the suggestions provided below)

template <class T>
class  Vector {
public:

    typedef T* iterator;

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

    Vector<T> & operator = (const Vector<T> &);

    size_t capacity() const;
    size_t size() const;
    bool empty() const;

    const iterator begin() const;
    iterator begin();

    const iterator end() const;
    iterator end();

    // both form should be implemented otherwise some STL functions won't work
    const T& front() const;
    T& front();

    const T& back() const;
    T& back();

    void push_back(const T& value);
    void pop_back();

    void reserve(size_t capacity);
    void resize(size_t size);

    T & operator[](size_t index) const;

    void clear();
private:
    size_t _size;
    size_t _capacity;
    T* buffer;
};

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

template<class T>
Vector<T>::Vector(const Vector<T> & v) {
    _size = v._size;
    _capacity = v._capacity;
    buffer = new T[_size];
    copy(v.buffer, v.buffer + _size, buffer);
}

template<class T>
Vector<T>::Vector(size_t size) {
    _size = size;
    _capacity = size;
    buffer = new T[_capacity];
}

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

template<class T>
Vector<T>::Vector(size_t size, const T& initial) {
    _size = size;
    _capacity = size;
    buffer = new T [_capacity];
    fill(buffer, buffer + _size, initial);
}

template<class T>
Vector<T>& Vector<T>::operator = (const Vector<T> & v) {
    free(buffer);
    _size = v._size;
    _capacity = v._capacity;
    buffer = new T [_capacity];
    copy(v.buffer, v.buffer + _size, buffer);
    return *this;
}

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

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

template<class T>
const typename Vector<T>::iterator Vector<T>::end() const {
    return buffer + _size;
}

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

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


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

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

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) {
        if(_capacity == 0)
            reserve(_capacity + 1);
        else
            reserve(_capacity * 2);
    }
    buffer [_size++] = v;
}

template<class T>
void Vector<T>::pop_back() {
    (reinterpret_cast<T*>(buffer)[_size - 1]).~T();
    _size--;
}

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

    copy(buffer, buffer + _size, newBuffer);

    _capacity = capacity;
    free(buffer);
    buffer = newBuffer;
}

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

template<class T>
void Vector<T>::resize(size_t size) {
    reserve(size);
    _size = size;
}

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

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

template<class T>
Vector<T>::~Vector() {
    free(buffer);
}
share|improve this question

3 Answers 3

up vote 10 down vote accepted

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;

log(2.0) is 0.3 so dividing by that is equivalent to multiplying by 3.3. That seems a bit large. I believe the standard uses a constant value of 1.6 (I could be totally wrong on that its just a number that pops into my head), but I don;t believe it is bigger than 2. Also 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;
}
share|improve this answer
    
It looks like Visual Studio 2012 attempts to increase the capacity by max (capacity + 50%, minimum capacity needed). But then again, Microsoft has been known to ignore standards. –  jliv902 Aug 19 at 20:19
    
@jliv902: That looks like 1.5x to me then (so not far off a 1.6x I suggested). But I don't think the standard actually specifies. It just defines the insertion (and some others) characteristics which should amortized constant time –  Loki Astari Aug 19 at 20:26
    
@LokiAstari: The logic behind a growth factor of 1.5x is that whenever the growth factor is less than the golden ratio, the vector should (in theory) be able to (in the long run) reuse previously allocated memory, while if the ratio is larger than the golden ratio, the new allocation will always request more memory than the sum of all previous allocations. See for example this blog post for further explanation. –  Mankarse Aug 20 at 3:07
    
@Mankarse: I am (somewhat) aware of golden ratio connection. That is why I said 1.6 golden ratio –  Loki Astari Aug 20 at 3:08
    
@LokiAstari: I suppose my comment should have been directed at OP then. –  Mankarse Aug 20 at 3:09
  • 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.

share|improve this answer
1  
+1 for some great points you've mentioned. I corrected everything you've recommended except the log stuff as STL vector regrows vector in the same manner cplusplus.com/reference/vector/vector . Should I reconsider it, Sir? –  Kaidul Islam Aug 19 at 17:14
1  
Yes, the vector should grow exponentially, but it is not a reason to summon math library. It is more than enough to have a reasonable default capacity, and double it as needed. A very important guideline is to not force a client to pay for he's not asked for. I think you should reconsider. –  vnp Aug 19 at 17:31
    
Okay Sir :) Another question is I am returning front and back like int& front() const and int& back() const. Can I use int front() and int back() there? Will it violate the convention? if so, why? –  Kaidul Islam Aug 19 at 17:34
1  
Note sure about: clear() must delete [] buffer. It must delete all the members of the vector. But you do not need to deallocate the buffer. –  Loki Astari Aug 19 at 18:09
1  
@LokiAstari The standard doesn't specify how large the expansion should be. –  Yuushi Aug 20 at 2:02
  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.

share|improve this answer
    
+1 for a very informative answer. Now I am in a pos N dilemma whose answer I should accept? :P –  Kaidul Islam Aug 19 at 17:53
1  
@KaidulIslam You just posted this question an hour ago. I usually wait a week before accepting an answer (on Code Review only), but that's just me. I would upvote any answer you felt was helpful and accept the one that helped you the most. –  jliv902 Aug 19 at 17:56
    
Yes. Pending accepting a answer is a good idea as more opinion will come as codereview has no EXACT answer. But this snippet is very small and there are few scope to dig it. I will wait :) –  Kaidul Islam Aug 19 at 18:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.