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 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 i-th position

Inserting values at i-th 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 i-th position, vector mark will have, mark = { 24, 9, 11, 7, 12, 8 }

Insertion of x, t times at i-th position

If we want, we can also insert a value t times at i-th 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 i-th position, vector mark will have, mark = { 24, 9, 11, 15, 15, 15, 15, 15, 7, 12, 8 }

Insertion of range of values at i-th 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 i-th 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 💻 🎵