HOW ARE VECTORS IMPLEMENTED INTERNALLY IN C++
INTRODUCTION
WHAT ARE VECTORS?
Vectors in C++ function the same way as Arrays in a dynamic manner i.e. vectors can resize itself automatically whenever an item is added/deleted from it. The data elements in Vectors are placed in contiguous memory locations and Iterator can be easily used to access those elements.Moreover, insertion of items takes place at the end of Vector. Unlike arrays, which are used to store sequential data and are static in nature, Vectors provide more flexibility to the program
How are vectors stored in C++?
To create a vector, you need to follow the below given syntax.
Syntax:
vector< object_type > variable_name;
Example:
#include <vector>
Using namespace std;
int main()
{
vector<int> my_vector;
}
- Object type defines a data type stored in a vector (e.g., <int>, <double> or <string>)
- variable is a name that you choose for the data
- elements specified the number of elements for the data
It is mandatory to determine the type and variable name. However, the number of elements is optional.
Basically, all the data elements are stored in contiguous storage. Whenever we want to access or move through the data, you can use iterators.
The data elements in C++ vectors are inserted at the end. We Use modifiers to insert new elements or delete existing ones.
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.
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, we have to 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(size_ == reserved_size_)
resize(reserved_size_ + _DEFAULT_VECTOR_SIZE);
array_[size_] = t;
size_++;
}
Ø The resize function is used to set the size of the reserved memory
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.
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()
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;
};
{ return array_ + size_; }
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 is a basic introduction of commonly used features of vectors and the implementation of C++ STL vector container.
