Hi Everyone ✋
In this tutorial we will talk about Vector.
So, what is vector actually?
Vector is a dynamic array container of C++ STL. Vector is a sequential container of STL. Array data structure is great for random access. But it has a fixed size array limitation.
In a dynamic array, we don’t have to worry about the fixed sized limitation because in a dynamic array, array size dynamically increases as the element increases.
Vector’s underlying data structure is Array.
Now, a question can arise, how vector manage to solve array’s fixed sized problem while using array as underlying data structure?
The answer is, vector uses a dynamically allocated array. When the array gets full, vector creates a new array with double size of current array, copy the current array element to new array then delete the current array.
Below a demo implementation of vector
#include <iostream>
using namespace std;
template <typename T>
class VectorClass
{
// arr is the integer pointer
// which stores the address of our vector
T *arr;
// capacity is the total storage
// capacity of the vector
int capacity;
// current is the number of elemets present in the vector
int current;
// Default constructor to initialise
public:
VectorClass() {
// an initial capacity of 1 element and
// allocating storage using dynamic allocation
arr = new T[1];
capacity = 1;
current = 0;
}
// function to add element at last
void push(T data) {
// if the number of elements is equal to the
// capacity, that means we don't have space to
// accommodate more elements. We need to double the
// capacity
if (current == capacity) {
T *temp = new T[2 * capacity];
// copying all old elements
for (int i = 0; i < capacity; i++) {
temp[i] = arr[i];
}
// deleting previous array
delete[] arr;
arr = temp;
capacity = capacity * 2;
}
// Inserting data
arr[current++] = data;
}
// function to delete element from last
void pop() {
current;
}
// function to return vector size
int size() {
return current;
}
// function to return vector capacity
int getCapacity() {
return capacity;
}
// removes all element
void clear() {
current = 0;
}
// return the index element
T at(int index) {
if(index < current) {
return arr[index]
}
// this will produce out of bound error
return arr[1];
}
// this returns the first element
T front() {
if(current > 0) {
return arr[0];
}
// this will produce out of bound error
return arr[1];
}
// this returns the last element
T back() {
if (current > 0)
{
return arr[current  1];
}
// this will produce out of bound error
return arr[1];
}
// display all elements
void display() {
for (int i = 0; i < current; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
int main(int argc, char const *argv[])
{
VectorClass <int> myVector;
myVector.push(52);
myVector.push(22);
myVector.push(13);
myVector.push(27);
myVector.push(72);
cout << "Vector size is: " << myVector.size() << endl;
cout << "Vector capacity is: " << myVector.getCapacity() << endl;
cout << "Vector elements" << endl;
myVector.display();
myVector.pop();
myVector.pop();
cout << "Vector size is: " << myVector.size() << endl;
cout << "Vector capacity is: " << myVector.getCapacity() << endl;
cout << "Vector elements" << endl;
myVector.display();
return 0;
}
Now let’s learn about common operations of vector in the following
Header File Inclusion for vector
#include <vector>
Declaration & Initialization
1D Vector Declaration
Empty 1D vector declaration
The following code will declare a vector of int values
vector <int> intValues;
And for vector of double values use following code
vector <double> douValues;
By using following code will declare a vector of string values
vector <string> nameList;
Declaring uninitialized vector
The following code will declare a vector of int values of size of 24 and the vector is completely uninitialized
vector<int> mark(24);
Declaring sized vector with value
By using following code we can declare sized vector with same values. Here, we are declaring an int value type vector which has size of 24 and the whole vector is initialized with value 95
vector<int> mark(24, 95);
Another way to declare initialized sized vector is —
vector<int> mark { 10, 20, 45, 30, 60 };
Here, we are declaring an int value type vector which has size of 5. This vector will be initialized by the given values.
2D Vector Declaration
Empty 2D vector declaration
2D vector is kind of a nested vector (vector inside vector). If we see the following code carefully we will understand that we are declaring a vector of vectors. Following code declares an empty 2D vector.
vector< vector<int> > table;
Fixed row sized 2D vector declaration
By using following code we are declaring a 2D vector with fixed row size initialization
vector< vector<int> > table(row);
We can declare fixed row sized 2D vector different way by declaring an array of vector.
vector< int > table[row];
Fixed row and col sized 2D vector declaration
Vector with fixed row and column can be declared in one line using constructor —
vector< vector<int> > table(row, vector<int>(col));
Here,


 We are declaring a 1D vector of type
vector<int>
.  Outer 1D vector fixed size is row
 Outer 1D vector’s value is
vector<int>(col)
by which this vector’s every element in this row is initialized  Inner 1D vector is
vector<int>(col)
, which has fixed is col but have no value. That’s why inner vector is uninitialized in result whole matrix is uninitialized.  Outer 1D vector + Inner 1D vector = makes the 2D vector or matrix
 We are declaring a 1D vector of type

We can do the same thing in different way,
// Declaration can be done in two ways
// one
vector< vector<int> > table(row);
// two
vector <int> table[row];
// Setting the fixed columns for each can be done in two ways too
// resizing the each row element to column size
for (int i = 0; i < table.size(); i++) {
table[i].resize(col);
}
// Assigning the vector array elements with fixed sized 1D vector
for (int i = 0; i < table.size(); i++) {
table[i] = vector<int>(col);
}
Fixed row and col sized 2D vector declaration with values
So far, we declared fixed row and col sized 2D vector without values. We can easily declare fixed row and col sized 2D vector with values by inserting value parameter to inner vector’s constructor easily. Below code will declare fixed row and col sized 2D vector with values 22.
vector< vector<int> > table(row, vector<int>(col, 22));
Again, we can do same thing in different ways but I am leaving that for our reader’s to try.
Insertion
Insertion at the end
We can easily insert an element to a vector at the end position by using push_back() method.
vector <int> mark;
mark.push_back(7);
mark.push_back(12);
mark.push_back(8);
After insertion at the end, vector mark will have, mark = { 7, 12, 8 }
Insertion at the beginning
When we try to insert values at the beginning. We need following things —


 Insert() method of vector
 Iterator position, where we want to insert the values
 value we wanna insert

mark.insert(mark.begin(), 9);
mark.insert(mark.begin(), 24);
When we complete inserting at the beginning, vector mark will have, mark = { 24, 9, 7, 12, 8 }
Insertion at ith position
Inserting values at ith position is similar to inserting values at the beginning, Just we need an extra i for our desired position —
mark.insert(mark.begin() + i, 11);
// if i = 2, then
mark.insert(mark.begin() + 2, 11);
After insertion at the ith position, vector mark will have, mark = { 24, 9, 11, 7, 12, 8 }
Insertion of x, t times at ith position
If we want, we can also insert a value t times at ith position. For that we just need to add an extra parameter to insert() method in the middle position —
mark.insert(mark.begin() + i, t, x);
// if i = 3, t = 5, x = 15
mark.insert(mark.begin() + 3, 5, 15);
After insertion of x, t times at the ith position, vector mark will have, mark = { 24, 9, 11, 15, 15, 15, 15, 15, 7, 12, 8 }
Insertion of range of values at ith position
We can insert a range of values to a vector using insert() method. For inserting range of values to a vector we need —


 insert() method
 iterator position where we wanna insert
 range value’s begin() iterator
 range value’s end() iterator

vector <int> arr {2, 5, 7}
mark.insert(mark.begin() + i, arr.begin(), arr.end());
// if i = 0
mark.insert(mark.begin(), arr.begin(), arr.end());
After insertion of range of values at ith position, mark = { 2, 5, 7, 24, 9, 11, 15, 15, 15, 15, 15, 7, 12, 8 }
Accessing Element
[] subscript operator
Like array vector element indexing start from 0. Accessing vector element with subscript operator is like accessing array elements of an array using subscript operator —
// the following line will print 9 as output
cout << mark[4] << endl;
// the following line will print 2 as output
cout << mark[0] << endl;
at() method
For accessing element, at() method work same as [] subscript operator.
// the following line will print 9 as output
cout << mark.at(4) << endl;
// the following line will print 2 as output
cout << mark.at(0) << endl;
Now, one can wonder why why at() method needed when we have [] subscript operator. But at() method is useful for pointer object type because pointer object can not use [] subscript operator directly. If we use [] subscript operator directly for pointer objects this will show error.
// declaring a pointer object of vector
vector <int> *pVect = &mark;
// following line will give error
cout << pVect[4] << endl;
// the following line will print 9 as output
cout << pVect > at(4) << endl;
But, we can use [] subscript operator for pointer object by dereferencing pointer —
// first dereferencing the pointer object
// then use parenthesis around it
// then use the [] subscript operator
// the following line will print 9 as output
cout << (*pVect)[4] << endl;
Front and Back element
We can easily access front and back element of a vector by using front() and back() method —
// front() method for access front element
// the following line will print 2 as output
cout <<< mark.front() << endl;
// back() method for accessing last element
// the following line will print 8 as output
cout << mark.back() << endl;
Deletion
Removing the Last Element
There are two ways by which we can remove the last element of vector —


 pop_back() method
 resize() method

// pop_back() removes last element from vector
mark.pop_back();
// resize() method resizes vector size
// we can resizes vector size to (current vector size  1) to remove last element
mark.resize(mark.size()  1);
After removing last element twice, mark = { 2, 5, 7, 24, 9, 11, 15, 15, 15, 15, 15, 7 }
Removing the First Element
For removing the first element of vector we need following element —


 erase() method
 first iterator position of vector

// using erase() method
// removing first element of vector
mark.erase(mark.begin());
After removing first element, mark = { 5, 7, 24, 9, 11, 15, 15, 15, 15, 15, 7 }
Removing a specific Element
Removing a specific element is similar to removing first element from vector, we just need erase() method and desired position.
// using erase() method
// we need the iterator position
mark.erase(mark.begin() + i);
// if i = 2
mark.erase(mark.begin() + 2);
After removing a specific element, mark = { 5, 7, 9, 11, 15, 15, 15, 15, 15, 7 }
Removing a range of elements
For removing a range of elements we need the following —


 erase() method
 start iterator position of range elements
 end iterator position of range elements

// erase() method
// start iterator of range  mark.begin() + 3
// end iterator of range  mark.begin() + 5
// removing a specific range of elements
mark.erase(mark.begin() + 3, mark.begin() + 5);
After removing a range of elements, mark = { 5, 7, 9, 11, 15, 15, 15, 15, 15, 7 }
Removing elements by value
With the help of std::algorithm method remove(), we can remove vector elements which matches to given value and given range.
// remove() method is an std::algorithm method
// remove() method helps earse() method to remove value that equals given value
mark.erase(remove(mark.begin(), mark.end(), 7), mark.end());
After removing elements by a given value, mark = { 5, 9, 11, 15, 15, 15, 15, 15 }
Removing duplicate elements
For removing duplicate elements first we need to sort the vector elements. For sorting vector elements we can use std:algorithm sort() —
// sorting the vector in ascending order
sort(mark.begin(), mark.end());
We will learn about sort() in details in algorithm sections.
Now, we can use std::algorithm unique() to remove duplicate methods —
// sorting the vector in ascending order
mark.erase(unique(mark.begin(), mark.end()), mark.end());
After removing duplicate elements, mark = { 5, 9, 11, 15}
Removing all elements
If we want to remove all elements of vector, we can just use clear() method —
// clear() methods removes all elements of a vector
mark.clear();
Reversing
Reverse the full vector
We can reverse a whole vector using std::algorithm reverse() method —
// declaring a vector
vector<int> mark { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
// using reverse() to reverse the whole vector
reverse(mark.begin(), mark.end());
After reversing mark will be, mark = { 9, 8, 7, 6, 5, 4, 3, 2, 1 }
Reverse a specific range
When we want to reverse a specific range in a vector, we just need desired range in reverse() method —
// declaring a vector
vector<int> mark { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
// using reverse() to reverse specific range
// mark.begin() + 2, is the start position of the range
// mark.begin() + 5, is the end position of the range
reverse(mark.begin() + 2, mark.begin() + 5);
After reversing the specific range, mark = { 1, 2, 5, 4, 3, 6, 7, 8, 9}
Vector Object Operations
Copying a vector object to another
For copying a vector object to another, just follow along the following codes —
// declaring two vector objects
vector<int> oldVect { 1, 2, 3, 4, 5, 6, 7 };
vector <int> newVect;
// now copying all oldVect elements to newVect
// this is achieved by operator overloading for vector objects
newVect = oldVect;
// now newVect contains all elements of oldVect
// another way to do this is to use constructor
// this is achieved by copy constructor
vector <int> copyVect(oldVect);
// now copyVect contains all elements of oldVect
Comparing vector objects
For comparing vectors we can use relational operators —
// declaring three vector objects
vector <int> vectOne { 1, 2, 3 };
vector <int> vectTwo { 1, 2, 3 };
vector <int> vectThree { 1, 2 };
// now comparing two vector with == relation operator
if (vectOne == vectTwo) {
cout << "Two are equal" << endl;
} else {
cout << "Two are not equal" << endl;
}
// now comparing two vector with != relation operator
if (vectOne != vectThree) {
cout << "Two are not equal" << endl;
} else {
cout << "Two are equal" << endl;
}
Output of above code will be
Two are equal
Two are not equal
Time Complexity of Vector
Operation  Description  Time Complexity 

[ ] subscript operator or at()  Random Access  O(1) 
front()  Accessing front element  O(1) 
back()  Accessing back element  O(1) 
begin()  Returns the iterator pointing to the first element of vector  O(1) 
end()  Returns the iterator pointing next to the last element of vector  O(1) 
empty()  Returns a bool value False if vector is not empty True if vector is empty  O(1) 
size()  Returns the number of elements present in the vector  O(1) 
resize()  Resizes the vector to the new length which can be less than or greater than the current length  O(n) 
clear()  Removes all element of the vector  O(n) 
push_back()  Insert value at end  O(1) 
pop_back()  Removes value at end  O(1) 
insert()  Insert new element or elements at a particular position of a vector  O(n + m) n  elements inserted m  elements moved 
erase()  Removes single element or range of elements  O(n + m) n  elements inserted m  elements moved 
Applications
Adjacency List
Adjacency list is a form of graph representation where adjacency describes a particular node’s neighbors in a graph. We can create adjacency list easily by using array of vectors.
Let’s say, we have V vertices. Then adjacency list will be —
// If the nodes are denoted by integer and starts from 0
vector <int> adja[v];
// If the nodes are denoted by integer and starts from 0
vector <int> adja[v + 1];
// If the nodes are denoted by char
vector <char> adja[v];
// If the nodes are denoted by string
vector <string> adja[v];
For now, that’s all from vector
See you next time. 😍
Happy Coding 💻 🎵
What is meant by “m” in complexity of insert and erase?
“m” is the number of elements moved or shifted positions in a vector
Example,
For insert() – when we try to insert values at the beginning, whole vector elements will shifted towards right to make space. here, number of elements shifted is m. And number of values we will insert is n.
For erase() – when we erase certain elements from vector, it creates the the positions empty. If the deleted element isn’t in the last position then it breaks vector’s sequential property. To preserve the sequential property we need to move elements right to left to fill the empty positions. Here, m is number of elements shifted or moved from right to left to preserve the sequential property of vector.
Nice going. Keep it up dost!
Good job. Keep going
Thanks for your blog, nice to read. Do not stop.