C++ Vectors: Understanding Its Importance & Its Use In Competitive Programming.

The main focus of this blog is to understand the key concepts of vector and how to implement them with ease in Competitive programming. This has been written on the basis of my experience and I have tried to include all the necessary information related to it. And I hope after going through this blog you will be able to appreciate this fact.

What is a Vector?

An obvious question for a beginner. So in simple words, a vector is simply an array but it is a little different from an array. It might sound fishy but the catch is: its main use is to overcome the disadvantages of an array.

Disadvantages of Array:

• Elements can not be deleted.
• The dynamic creation of arrays is not possible.
• Multiple data types can not be stored.

So in a nutshell, a vector is a dynamic array that has the ability to resize itself when an element is inserted or deleted.

Some important points related to vectors:

• Vector elements are placed in contiguous storage so that they can be accessed and traversed using iterators.
• In vectors, data is inserted at the end. Inserting at the end takes differential time, as sometimes there may be a need of extending the array.
• Removing the last element takes only constant time because no resizing happens. Inserting and erasing at the beginning or in the middle is linear in time.
• The header file required for vectors is #include<vector>.But if we use the header file #include<bits/stdc++.h>,then we don’t need to mention #include<vector>.

The syntax for declaring a vector:

vector<data_type>name_of_vector;

For example, a vector of int data-type can be declared as

vector<int>v;

Here v is the name of the vector and we can declare any name provided it is not a reserved keyword. In a similar fashion, we can have vectors of data types: long and long long int.

Insertion and Deletion of data in a vector:

To insert values into our vector we use the function push_back() i.e; to push values inside the vector and to calculate the size of the vector being formed we will use the function size(). The time complexity of push_back() is O(1).

NOTE:

For push_back():
Parameter: The value to be inserted in the vector is 
passed as a parameter.

For example, refer to the following CPP:

The output of the above code:

1 3 8 23 99
5

In this way, values are getting stored in the vector.

While solving problems we might come across a scenario, where we need to take a large number of integers and if suppose we are storing it in a vector, we can’t go on writing push_back function. Instead we use a loop(for/while) and we declare a variable say x, and then we take input into x and then we push this x into our vector.

For a better understanding refer to the C++ code given below:

Inputs:

n: 10
1 2 4 6 7 7 8 0 4 6

Output:

The values inside v are : 1 2 4 6 7 7 8 0 4 6
size of v : 10

Like we mention the size of an array before taking inputs, the same can be done for vectors as well. For example:

vector<int>v(5);  // vector of size 5

The above declaration creates a vector of size 5, very similar to an array of size {5}. And then we can take inputs into it as an array and if we want to increase its size we can do it via push_back().

Input:

1 4 6 9 8

Output:

Initial Size : 5
1 4 6 9 8 
New Size : 6
1 4 6 9 8 12

One thing to note in the above code is that we added only one element via push_back function; we could have added any number of elements into the vector according to our requirement.

Deletion of data from a vector:

This can be done by using the function pop_back() and its time complexity is O(1). But there is a catch, we can’t delete any element from a vector. By using pop_back() we can only remove an element(one element at a time) from the end of a vector and upon using this function, the size of the vector automatically reduces by one and it seems like that the element is permanently deleted. “But it is NOT the case the element which was supposed to be deleted still persists and it's just not being traversed as the length of the vector size decreases by 1 unit.”

NOTE:

For pop_back():
parameter:No parameters are passed.

For a better understanding of the above statements refer to the given C++ code:

Output:

5
Elements of the vector initially : 1 3 8 23 99
updated size : 4
Elements of the vector now : 1 3 8 23
The last element : 99

This is how push_back( ) works!

Now you might be thinking how to delete an element in the 0th index or any index in a vector. So for this, we use erase() function.

NOTE:

Syntax:

vector_name.erase(index);  //For erasing a particular element.
/*For removing a range of elements from any position. */
vector_name.erase(starting index,ending index);
Parameter:
Position of the element to be removed in the form of iterator.
or the range specified using start and end iterator.

As mentioned in the above parameter we need an iterator to get the position of the element which we want to erase. So for that, we must know about begin().

Before moving to the C++ code for understanding the application of erase() ;lets discuss about begin() function. This function returns the beginning position of the vector. In other words, it returns an iterator which points to the 0th index upon using begin() function.

Syntax for begin():

vector_name.begin();
Parameters: No parameters are passed

Now if suppose the name of the vector is m; so m.begin() gives the 0th position or index but if we want the 3rd index. So clearly,( m.begin()+3) will give the 3rd position.

Refer to the following C++ code to have a clear understanding.

Input:

1 4 6 9 8 2 3

Output:

Initially elements in the vector : 1 4 6 9 8 2 3 
Third element: 9
Elements in the vector after 1st operation : 1 4 6 8 2 3

For a better understanding of how to erase a range of values from a vector refer to the C++ code given below:

Input:

1 4 6 9 8 2 3

Output:

Initially elements in the vector : 1 4 6 9 8 2 3 
Elements in the vector after 1st operation : 1 4 3

Some important functions of STL for vectors:

• begin(): As discussed earlier it returns an iterator which points to the beginning of the vector or the 0th index. Its time complexity is O(1)
• end(): It returns an iterator that points to the end of the vector or just after the last element of the vector. Its time complexity is O(1).

Syntax for end():

vector_name.end()
Parameters: No parameters are passed.

• sort(): As the name suggests this function is used to sort the vector elements in ascending order. This function is also used for arrays and is very useful and it uses quicksort algorithm.

Syntax for sort():

For arrays: Consider an array a[n] of size n:
sort(a,a+n);
For vectors:Consider a vector v :
sort(v.begin(),v.end());

Now you must be thinking about how to arrange the vector elements in descending order in an efficient way by using sort(). So here is the solution:

For sorting an array in descending order of size n:
sort(a,a+n,greater<int>());
For sorting a vector in descending order:
sort(v.begin(),v.end(),greater<int>());

• reverse(): This function is used to reverse the elements in the vector.

Syntax for reverse():

reverse(v.begin(),v.end());

Refer to the C++ code given below for understanding the above concepts:

Output:

5
The elements in the vector before sorting : 2 4 3 6 9 
The elements in the vector after applying sort() : 2 3 4 6 9 
The elements in the vector after applying sort() (descending) : 
9 6 4 3 2 
The elements in the vector after applying reverse() : 2 3 4 6 9

• swap(): This function is used to swap the contents of one vector with the contents of another vector.

Syntax for swap():

vector_name1.swap(vector_name2);
Parameters:
The name of the vector with which
the contents have to be swapped.

Refer to the C++ code given below for understanding the above concepts:

Output:

The elements in the 1st vector :2 4 3 6 9 
The elements in the 2nd vector :5 7 3 1 6
The elements in the 1st vector :5 7 3 1 6 
The elements in the 2nd vector :2 4 3 6 9

• clear(): This function deletes all the elements from the vector and assigns an empty vector. Its time complexity is O(N) where N is the size of the vector.

Syntax:

vector_name.clear();

Illustration:

Output:

The elements in the vector initially : 2 4 3 6 9 
The elements in the vector now :

I hope you liked this content.