Introduction to Sequence Containers

Sequence containers are a type of container that maintains the order of elements in the container. Unlike associative containers, where elements are stored and accessed by a key, sequence containers maintain the order of insertion. C++ provides several types of sequence containers, each with its unique characteristics.

std::vector

std::vector is a dynamic array that can grow or shrink in size. It provides constant time access to elements and linear time for insertion and deletions at the end. It is define inside the <vector> header file. Vector store elements of similar types (Homogenous data).

• Vector elements are placed in contiguous storage so that they can be accessed and traversed using iterators.
• In vector, data is inserted at the end. Inserting the end takes differential time, as sometimes the array may need to be extended.
• Removing the last element takes only constant time because no resizing happens.
• Inserting or deleting at the beginning or in the middle is linear in time.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // Accessing elements
    std::cout << "First element: " << vec[0] << std::endl;

    // Inserting elements
    vec.push_back(6);

    // Iterating through elements
    for (int num : vec) {
        std::cout << num << " ";
    }

    return 0;
}

First element: 1
1 2 3 4 5 6  

Default Constructor:

std::vector<int> myVector;

Creates an empty vector of integers.

Size Constructor:

std::vector<int> myVector(5);

Creates a vector of size 5 with default-initialized integers.

Vector Initialization:

Method 1 – 

// Initializer list
vector<int> myVector1 = {1, 2, 3, 4, 5};

// Uniform initialization
vector<int> myVector2 {1, 2, 3, 4, 5};

Method 2 – 

vector<int> myVector3(5, 12);

Here, 5 is the size of the vector and 12 is the value.

This code creates an int vector with size 5 and initializes the vector with the value of 12. So, the vector is equivalent to:

vector<int> myVector3 = {12, 12, 12, 12, 12};

Complete example – 

#include <iostream>
#include <vector>
using namespace std;

int main() {

  // initializer list
  vector<int> vector1 = {1, 2, 3, 4, 5};

  // uniform initialization
  vector<int> vector2{6, 7, 8, 9, 10};

  // method 3
  vector<int> vector3(5, 12);

  cout << "vector1 = ";

  // ranged loop
  for (const int& i : vector1) {
    cout << i << "  ";
  }

  cout << "\nvector2 = ";

  // ranged loop
  for (const int& i : vector2) {
    cout << i << "  ";
  }

  cout << "\nvector3 = ";

  // ranged loop
  for (int i : vector3) {
    cout << i << "  ";
  }

  return 0;
}

// Output
vector1 = 1  2  3  4  5  
vector2 = 6  7  8  9  10  
vector3 = 12  12  12  12  12 

Value Constructor:

std::vector<int> myVector(3, 42);

Creates a vector of size 3 with all elements initialized to 42.

Range Constructor:

std::vector<int> myVector = {1, 2, 3, 4, 5};

Creates a vector and initialized it with the elements {1, 2, 3, 4, 5}.

operator[]:

int element = myVector[2];

Accesses the element at index 2 in the vector.

at:

int element = myVector.at(2);

Accesses the element at index 2 with bounds checking.

front: This function returns a reference to the first element of the vector. This is useful when you need to access the starting element without modifying the vector.

int firstElement = myVector.front();

Accesses the first element of the vector.

back: This function returns a reference to the last element in the vector. It is typically used when the last inserted element needs to be accessed or modified.

int lastElement = myVector.back();

Accesses the last element of the vector.

size: The size function returns the number of elements in the vector. This is helpful in loops or conditions where the vector's length is a determining factor.

size_t size = myVector.size();

Returns the number of elements in the vector.

empty:

bool isEmpty = myVector.empty();

Returns true if the vector is empty; otherwise, returns false.

capacity:

size_t capacity = myVector.capacity();

Returns the current capacity of the vector.

reserve:

myVector.reserve(100);

Increases the capacity of the vector to at least 100 elements.

shrink_to_fit:

myVector.shrink_to_fit();

Reduces the capacity to fit the size of the vector.

clear: This function removes all elements from the vector, making it empty. It reduces the vector's size to zero but does not free the memory allocated by the vector.

#include <bits/stdc++.h>
        using namespace std;
        
        int main() {
            vector<int> v = {10, 20, 30};
            v.clear();
            cout << "Size after clear: " << v.size();
            return 0;
        }

Removes all elements from the vector.

insert: This function inserts elements at a specified position in the vector. It shifts all elements at and after the insertion point to the right, increasing the vector's size.

myVector.insert(myVector.begin() + 2, 99);

Inserts the value 99 at the position myVector.begin() + 2.

erase: This function removes an element from the vector by a position causing all subsequent elements to be shifted one positions to the left. This helps reduce the size of the vector by one.

myVector.erase(myVector.begin() + 1);

Erases the element at the position myVector.begin() + 1.

push_back: This function adds a new element at the end of the vector. This is often used to append element in a loop or based on certain conditions.

myVector.push_back(77);

Adds the value 77 to the end of the vector.

#include <bits/stdc++.h>
        using namespace std;
        
        int main() {
            vector<int> v = {1, 2, 3};
            v.push_back(4);
            v.push_back(5);
            for (int i : v) {
                cout << i << " ";
            }
            return 0;
        }

pop_back:

myVector.pop_back();

Removes the last element from the vector.

resize:

myVector.resize(8, 5);

Changes the size of the vector to 8, initializing new elements with the value 5.

swap: The swap function swaps the contents of two vectors. This is efficient way to swap large vectors since it only waps the internal poinnters rather than copying elements.

std::vector<int> anotherVector = {10, 20, 30};
myVector.swap(anotherVector);

Swaps the content of myVector and anotherVector.

Iterators

Vectors support iterators, which allow traversal through the elements in the vector. Iterators behave like pointers and can be used for accessing elements or performing operations on the vector.

#include <bits/stdc++.h>
        using namespace std;
        
        int main() {
            vector<int> v = {10, 20, 30};
            for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
                cout << *it << " ";
            }
            return 0;
        }

10 20 30

For each

The for_each loop in C++11 allows for a simpler way to iterate over vectors. It simplifies the syntax and enhances code readability.

#include <bits/stdc++.h>
        using namespace std;
        
        int main() {
            vector<int> v = {10, 20, 30};
            for (int i : v) {
                cout << i << " ";
            }
            return 0;
        }

10 20 30

Time Complexity for doing various operations on vector is -

• Random access – constant O(1)
• Insertion or removal of elements at the end – constant O(1)
• Insertion or removal of elements – linear in the distance to the end of the vector O(N)
• Knowing the size – constant O(1)
• Resizing the vector – Linear O(N)