Vector in C++

Vector is a template based container, some behavior like a Dynamic Array. It can expands its memory at run time and uses contiguous memory location to store elements just like Array. It stores any type of element in vector by specifying the type as template argument.

Lets see an example,

#include <vector>
int main()
{
   // This is a vector of int
    std::vector<int> vecOfInts;
 
    // While Adding it automatically adjusts it's size
    for(int i = 0; i < 10; i++)
        vecOfInts.push_back(i);
 
    std::vector<int>::iterator it = vecOfInts.begin();
    while(it != vecOfInts.end())
    {
        std::cout<<*it<<" , ";
        it++;
    }
    for(int i = 0; i < vecOfInts.size(); i++)
        std::cout<<vecOfInts[i]<<" , ";
    std::cout<<std::endl;
 
    return 0;
}

Important Points about std::vector : 

1. Ordered Collection: In std::vector elements order will remain same in which they are inserted.
2. Provides random access: Operator [] provides random access just like arrays. 
3. Performance: It Performs better if insertion and deletion is in end only. It gives worst performance if insertion/deletion is at middle or at starting of vector. 
4. Contains Copy: It always stores copy of the object not the same reference. So, if you are adding objects of user defined classes the you should define copy constructor and assignment operator in you class.

How does std::vector works internally ?

std::vector allocates a memory on heap & store all its elements in contiguous memory location. But what if memory it allocated initially is completely filled ?

First discuss about std::vector size and  std::vector capacity, Vector size means how many elements are present in vector and vector capacity means how much  continuous memory is allocated in heap for this vector, So vector capacity always greater than or equal to vector size. 

For example, let’s create a vector of integer  i.e. std::vector. Now suppose it’s initial capacity is to store 20 elements, but in our application we want to store 25 elements in it. Then what will happen when we will insert 21st element?

When std::vector’s internal memory (Capacity) completely finishes then it increases the size of its memory, by performs following steps,

1. It will allocate a bigger chunk of memory on heap i.e. almost double the size of previously vector capacity.
2. Then it copies all the elements from old memory location to new one. In case our elements are user defined objects then their copy constructor will be called. It makes this step quite heavy in terms of speed and performance.
3. Then after successful copying it deletes the old memory.

Let;s check std::vector capacity and size with example :

#include <iostream>
#include <vector>
using namespace std;

struct Sample
{
    Sample(){}
    Sample(const Sample & obj)
    {
        std::cout<<"Sample copy constructor"<<std::endl;
    }
};
int main()
{
    std::vector<Sample> vecOfInts;
 
    std::cout<<"Capacity :: "<<vecOfInts.capacity()<<std::endl;
    std::cout<<"Size :: "<<vecOfInts.size()<<std::endl;
    int capcity = vecOfInts.capacity();
    for(int i = 0; i < capcity + 1; i++)
        vecOfInts.push_back(Samplstd::vector e());
 
    std::cout<<"Capacity :: "<<vecOfInts.capacity()<<std::endl;
        std::cout<<"Size :: "<<vecOfInts.size()<<std::endl;
 
    for(int i = 0; i < capcity + 1; i++)
            vecOfInts.push_back(Sample());
 
    std::cout<<"Capacity :: "<<vecOfInts.capacity()<<std::endl;
    std::cout<<"Size :: "<<vecOfInts.size()<<std::endl;
 
    return 0;
}

How to use vector efficiently in C++?

1. Vector will be more efficient if elements are inserted or removed from the back-end only.
   
   As, vector internally stores all the elements in consecutive memory location. Therefore, if an element is added in middle, then vector right shifts all the right side elements of that location by 1. Also, if elements were user defined objects then copy constructors for all those elements are called.
   
   
   Similarly If element is erased from the middle, then vector left shifts all the right side elements of that location by 1. Also, if elements were user defined objects then copy constructors for all those elements are called.
   
   
   But if elements are inserted or deleted from the back-end only then this costly shifting will not happen.
   
   
2.  Set the storage of vector initially using reserve() member function.
   
   As vector is a kind of container in which user can store unlimited elements. Internally it allocates storage to store the elements but during insertion if new memory requirement surpasses the current capacity then it allocates a bigger chunk of storage and copies all the existing elements there. It’s a huge burden for application because if elements in vector are user defined objects then in every new movement to new storage location copy constructor of elements will be called.
   
   We can avoid this if in our application by reserving the vector capacity initially by calling reserve() function. This reserve() function requests the vector capacity to be at least enough to contain n elements. It only increases the vector’s capacity, size remains same.
   
   
3. Instead of adding single element in multiple calls, large set of elements is added in single call
   
   Adding single element can cause,
   
   1. Shifting of some elements in vector
   2. Allocation of new memory and movement of all elements on new location
   If we add a single element multiple times than all the above things can happen multiple times. Whereas, if we insert elements in together i.e. in a set than this shifting and copying can happen only once. vector can check if it has the capacity to store n elements or not or it needs to shift some elements by n location.