Data Structures and Algorithms | C++ STLs

In this article, we will be looking at a brief introduction to Data Structures and Algorithms | C++ STLs and some very important STLs like Pairs, Vectors, and Lists.

Vectors

Vector is another type of container in the C++ STL. This is similar to arrays but dynamic in nature i.e., it expands and contracts dynamically. It is abstract datatype as it hides all the internal work.

A vector helps in storing a collection of homogenous data under one variable name. We must specify the type of data we want to store during the declaration of a vector.

Syntax: vector<data_type> vector_name;

A vector can be declared in the following ways:

vector<data_type> vector_name;

Example:

vector<data_type> vector_name(size);

vector<int> vec(10); // A vector of size 10 will be created

vector<data_type> vector_name(size, value); // A vector of a given size, filled with given values is created

vector<int> vec(5,10); // A vector of size 5 with all elements as 10 will be created {10,10,10,10,10}

vector<data_type> vector_name{element1,element2,element3}; // A vector with the given elements will be created.

vector<int> vec{10,20,30,40}; //A vector with the given elements is created.

A Vector has size and capacity, the size of a vector is the number of elements in it and the capacity of a vector is the maximum number of elements the vector can hold.

Now that we know what a vector is there are several methods provided that are used to operate on a vector.

• size() – Returns the number of elements in the vector.
• max_size() – Returns the maximum number of elements that the vector can hold.
• capacity() – Returns the size of the storage space currently allocated to the vector expressed as the number of elements.
• resize(n) – Resizes the container so that it contains ‘n’ elements.
• empty() – Returns whether the container is empty.
• shrink_to_fit – Reduces the capacity of the container to fit its size and destroys all elements beyond the capacity.
• reserve() – Requests that the vector capacity is at least enough to contain n elements.

Now that we know how to operate on a vector let’s look at methods for traversing a vector i.e., the iterators.

• begin() – Returns an iterator pointing to the first element of the vector.
• end() – Returns an iterator pointing to the theoretical element that follows the last element in the vector.
• rbegin() – Returns a reverse iterator pointing to the last element in the vector (reverse beginning). It moves from the last element to the first one.
• rend() – Returns a reverse iterator pointing to the theoretical element preceding the first element in the vector (considered as reverse end)
• cbegin() – Returns a constant iterator pointing to the first element in the vector.
• cend() – Returns a constant iterator pointing to the theoretical element that follows the last element of the vector.
• crbegin() – Returns a constant reverse iterator pointing to the last element in the vector (reverse beginning). It moves from the last to the first element.
• crend() – Returns a constant reverse iterator pointing to the theoretical element preceding the first element in the vector (consider as reverse end).

Let us use all the methods in an example to understand them better:

// C++ program to illustrate the
// iterators in vector
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    vector<int> g1;
 
    for (int i = 1; i <= 5; i++)
        g1.push_back(i);
 
    cout << "Output of begin and end: ";
    for (auto i = g1.begin(); i != g1.end(); ++i)
        cout << *i << " ";
 
    cout << "\nOutput of cbegin and cend: ";
    for (auto i = g1.cbegin(); i != g1.cend(); ++i)
        cout << *i << " ";
 
    cout << "\nOutput of rbegin and rend: ";
    for (auto ir = g1.rbegin(); ir != g1.rend(); ++ir)
        cout << *ir << " ";
 
    cout << "\nOutput of crbegin and crend : ";
    for (auto ir = g1.crbegin(); ir != g1.crend(); ++ir)
        cout << *ir << " ";
 
    return 0;
}

Output:
Output of begin and end: 1 2 3 4 5 
Output of cbegin and cend: 1 2 3 4 5 
Output of rbegin and rend: 5 4 3 2 1 
Output of crbegin and crend : 5 4 3 2 1

Example:

// C++ program to illustrate the
// capacity function in vector
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    vector<int> g1;
 
    for (int i = 1; i <= 5; i++)
        g1.push_back(i);
 
    cout << "Size : " << g1.size();
    cout << "\nCapacity : " << g1.capacity();
    cout << "\nMax_Size : " << g1.max_size();
 
    // resizes the vector size to 4
    g1.resize(4);
 
    // prints the vector size after resize()
    cout << "\nSize : " << g1.size();
 
    // checks if the vector is empty or not
    if (g1.empty() == false)
        cout << "\nVector is not empty";
    else
        cout << "\nVector is empty";
 
    // Shrinks the vector
    g1.shrink_to_fit();
    cout << "\nVector elements are: ";
    for (auto it = g1.begin(); it != g1.end(); it++)
        cout << *it << " ";
 
    return 0;
}

Output:
Size : 5
Capacity : 8
Max_Size : 4611686018427387903
Size : 4

In the next article, we are going to have a look at Vectors and Lists.