# STL Vector Implementation

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.

-

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


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

-
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 '14 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 '14 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 '14 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 '14 at 3:08
@LokiAstari: I suppose my comment should have been directed at OP then. –  Mankarse Aug 20 '14 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.

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.

-
+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 '14 at 17:14
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 '14 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 '14 at 17:34
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 '14 at 18:09
@LokiAstari The standard doesn't specify how large the expansion should be. –  Yuushi Aug 20 '14 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.

-
+1 for a very informative answer. Now I am in a pos N dilemma whose answer I should accept? :P –  Kaidul Islam Aug 19 '14 at 17:53
@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 '14 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 '14 at 18:02