There are many open source implementations of STL. However it is difficult to read the STL code because it is meant to be practically usable than readable.
STLHow is an implementation of C++ Standard Template Library (STL) written in easy to understand and human readable code.
A series of articles here on codefreakr will discuss the STLHow to demonstrate “How the STL is implemented”.
Implementing STL Vector
Constructors and Destructor
Vector is implemented as a dynamically allocated array. The memory for this array is allocated in the constructor. As more elements are inserted the array is dynamically increased in size. A constructor without parameter creates an array with a default size. Another constructor with integer parameter creates an array of the specified size. The destructor deletes the memory allocated for the array.
const int _DEFAULT_VECTOR_SIZE = 4;
template <typename T>
class vector
{
public :
// constructors
vector()
: array_( new T[_DEFAULT_VECTOR_SIZE] ),
reserved_size_( _DEFAULT_VECTOR_SIZE ),
size_( 0 )
{ }
vector(int n) // create vector with n default elements
: array_( new T[n] ),
reserved_size_( n ),
size_( 0 )
{ }
// destructor
~vector()
{ delete[] array_; }
private :
T *array_;
int size_;
int reserved_size_;
};
Adding elements
The most frequently used function to add elements to vector is push_back. The function adds the element at the end of the vector ie. after the current last element. This is accomplished by putting the element at the size_th position. However that is not sufficient because vector is a dynamically increasing container hence if the currently allocated memory is not sufficient to hold the element then more memory should be allocated. So, see that there is sufficient memory to hold the element, if not allocate more memory and then insert the element.
template <typename T>
void vector<T>::push_back(const T &t)
{
// if we've run out of space, allocate more memory
if(size_ == reserved_size_)
resize(reserved_size_ + _DEFAULT_VECTOR_SIZE);
// size_ when used as an index, points to the next position after
// the last element in the vector
array_[size_] = t;
// now there is one more element in the vector, so increase the size
size_++;
}
The resize function is used to set the size of the reserved memory. Although this function is public and can be called by client code to change the actual size of the memory held by the vector it is used internally for the same purpose. Here is the implementation of the function.
template <typename T>
void vector<T>::resize(int n) // make the size of the internal array exactly n
{
if(n > reserved_size_) // if requested size is more than the current size
{
// allocate a new array of larger capacity
// copy the old array to new array
// destroy old array
auto_array<T> new_array( new T[n] );
for(int i=0; i<size_; i++)
{
new_array[i] = array_[i];
}
delete[] array_;
array_ = new_array.release();
reserved_size_ = n;
}
}
In the above snippet of code, auto_array is an auto_ptr like class. The standard auto_ptr has a destructor which performs delete on the pointer it holds. Hence it is unable to delete an array of objects which requires delete[] instead of delete to free them. The custom auto_ptr class is discussed here.
Forward Iterator
The forward iterator iterates through the vector elements starting from index zero and in increasing index order. Because the elements of the vector are stored in an contiguous array, a pointer of element type can function as a forward iterator. This shows that a simple pointer can work as an iterator hence it is often said that anything that behaves like an iterator is an iterator.
// iterator typedef T* iterator;
The begin function returns the pointer to the first element in the array and the end function returns pointer to an element past the last element of the array. The end really refers to a memory location that should not be accessed as it is outside the limit of the array. This is the reason why it is advised to not to de-reference the end iterator.
// iterator functions
iterator begin()
{ return array_; }
iterator end()
{ return array_ + size_; }
There is no need to write any special iterator de-reference or access to member operator, as the pointer already has those operators defined.
Reverse Iterator
The reverse iterator iterates through the vector elements starting from the very last element and in decreasing index order. A wrapper class to the plain pointer can do the job of the reverse iterator. The operator++ should perform — and operator– should perform ++ on the plain pointer.
class reverse_iterator
{
public:
reverse_iterator(T *p)
: pos(p) { }
reverse_iterator()
: pos(0) { }
T &operator*()
{ return *pos; }
T *operator->()
{ return pos; }
reverse_iterator operator++(int)
{ pos--; return *this; }
reverse_iterator operator--(int)
{ pos++; return *this; }
bool operator!=(const reverse_iterator &rhs)
{ return this->pos != rhs.pos; }
private:
T *pos;
};
The rbegin function returns an object of reverse_iterator that holds pointer to the last element of the array and the rend function returns an object of reverse_iterator that holds pointer to an element before the first element of the array. The location pointed to by the rend is invalid and hence should not be de-referenced.
This article shows the internal implementation of the C++ STL vector container. Not all but only the commonly used features of the vector are described here. Rest of the features can easily be implemented based on this description.
In the next article in the series STLHow describes the implementation of C++ STL List container.