Reading time: 20 minutes | Coding time: 2 minutes

Vectors in C++ are one of the most used containers after arrays mainly because of the fact that the basis of operation of both the vectors and array are same to some extent.

In this article we will take a look into one of the most conventional ways of taking input in the vector as vector::push_back() and will try to find the complexity and other aspects in which it differs from the usual array implementation in taking the input.

One Major difference between array and vectors is their declaration type.
std::Array is declared as array<class type, size_t Size> while Vector declaration is done using Allocator Policy, vector<class type, class Allocator=std::allocator<type> > This puts up the fact that the array size must be declared at the compile time while vector can be or not be allocated any predefined memory as it can resize the limits to ensure multiple objects at different contiguous memory locations.

Vectors in C++ are Containers. Containers are abstract Data type in C++ which acts as a way to store multiple objects and follow specific rules to access the elements.

There are multiple methods which can be applied to containers, which includes:

• creating objects
• accessing the elements
• deleting the objects

Vector::push_back() method is used to insert elements at the back of the vector.

template<typename T>
void std::vector<T>::push_back(const T& obj)
{
    this->insert(this->end(),obj);
}

In C++11 and later standards the goto implementation of vector::push_back() has been reduced to providing/allocating data types at the compile time which is inserted at the back of the vector.

The general method for push_back() is:

void push_back(const value_type& val);

while for c++11 and later standards it's :

void push_back(value_type&& val);

Vector::push_back() for different data types:

• int

vector<int>Myvector;

Myvector.push_back(1);
Myvector.push_back(3);
Myvector.push_back(9);
Myvector.push_back(10);

Myvector={}  // initial vector elements(Myvector.empty())
Myvector={1,3,9,10} // final value in the vectors

• string

vector<string>Myvector;

string s1,s2,s3;
Myvector.push_back(s1);
Myvector.push_back(s2);
Myvector.push_back(s3);

Myvector={} //empty initially
Myvector={s1,s2,s3} // final value in the vectors (consists of string)

• Float

vector<float>Myvector;

Myvector.push_back(8.90);
Myvector.push_back(9.87);
Myvector.push_back(10.54);

Myvector={} //empty initially
Myvector={8.90,9.87,10.54} // final value in the vectors (consist of float data elements)

Vector::push_back() for 2D vectors

• First way describes how to make a 2D vector and insert row and column wise elements:

vector <vector<int>> Myvector;      //Declaring a vector of vectors.
for(int rowNumber=0; rowNumber <= 10; rowNumber++)
{  
    int Value = 1;
    vector<int>Column;   // column vector of the previously declared one.
    Myvector.push_back(Column);  // pushing behind the value for the columns.
    Myvector.at(rowNumber).push_back(Value);  // Pushing the rows at the appropriate column number vector.
} 

• Second way is more generic in nature. When we make the two vectors (the inner and the outer vector) by assigning values to one of them first and then declaring one vector as the part of the other:

vector<vector<int>>Myvector;        //Creating a vector of vector.                                                                   
int col= 6;                    //defining second vectors size.
Myvector.push_back(vector<int>{col}) ;         //pushing column vector into the row.

• Third Method can be described as the most naive way to take 2D vector input which is by simply taking input at the i-th column for each particular row:

Element access in 2D Vector

The most generic way is to iterate through each row and column to scrape the values present in the vector:

//in both the method one common way to access the elements is to iterate through the rows and columns one by one as:
 
for(int i=0;i<Myvector.size();i++)  //iterating through row
{
    for(int j=0;j<Myvector[i].size();j++) //iterating through column
            {
                std::cout<<Myvector[i][j]<<std::endl; //accessing each element 
            }
}

Time Complexity of a vector::push_back() operation

The complexity of the vector::push_back() operation is Amortized O(1).

What is amortized you may ask?

Simply said, Amortized complexity is basically the average of all the push_back() calls you would make in a vector in a particular range unit of time.

Any random push_back call will strictly be O(1) because we're essentially adding element at the end of the vector which is and can be done in constant time. But the moment the vector is empty or too small, (the vector.empty() check method can be used to proofcheck) the whole vector is reallocated and the time expense is usually O(vector.size()).

Therefore at an average the time complexity increases and become Amortized O(1).

We can essentially limit the complexity to strictly O(1) by reserving the vector some space by std::reserve().

Application of push_back.

The vector::push_back() call is an extremely inexpensive task and is widely used whenever vector container is used in general.