Sequence Containers std::vector in C++

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.

Suppose you have to store the roll numbers of 100 students in a class. Since roll numbers are integers, we can simply use an array:

int rollNumber[100];

// Initialize roll numbers 1 to 100
for (int i = 0; i < 100; i++) {
	rollNumber[i] = i + 1;
}

This works fine as long as the number of students is fixed.

But what if a few more students take admission later?

Let's say 10 new students join, making the total count 110. Now, our array of size 100 is insufficient. A feasible solution would be to create a new array of size 110 and copy all the roll numbers again – which is tedious and inefficient.

There is another way to handle this is to create dynamic array using pointers and the new operator:

int* rollNumber = new int[110]; // dynamically allocate array of size 110

for (int i = 0; i < 110; i++) {
	rollNumber[i] = i + 1;
}

// Remember to free memory later
delete[] rollNumber;

This approach overcomes the fixed-size problem of normal arary because we can decide the size at runtime.

However, it still has major drawbacks:

• If more students join again, we must create a new array with a larger size and manually copy old data.
• We must manage memory ourselves (new / delete), otherwise memory leaks occur.

To make resizing automatic, safe, and convenient, C++ provides the std::vector container, which handles dynamic memory management internally while still giving the efficiency of arrays.

Traditional Arrays vs std::vector

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 defined inside the <vector> header file. Vector store elements of similar types (Homogenous data).

• Contiguous Memory: 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.
• Dynamic Resizing: It automatically adjusts its size when new elements are added or removed. You don't have to worry about creating a bigger array manually.

Example:

#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  

Constructor:

The std::vector container provides several constructors to create vectors in different ways. Its main purpose is to initialize the object's data members.

1 Default Constructor:

Creates an empty vector.

std::vector<int> myVector; // empty vector of int.

Creates an empty vector of integers. Initially it has size = 0, Capacity = 0. Elements can be added later with push_back().

2 Size Constructor:

Creates a vector with n elments, elements are value-initialized (e.g., zeroes for int).

std::vector<int> myVector(5); // {0, 0, 0, 0, 0}

Creates a vector of size 5 with default-initialized 

3 Vector Initialization:

Method 1 – 

Allows constructing vectors with a list of values inside {}.

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

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

Method 2 – (Fill Constructor)

Creates a vector with n elements, each initialized to a given value.

vector<int> myVector3(5, 12); // {12, 12, 12, 12, 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};

4 Range Constructor

Constructs a vector by copying elements form another container's range.

int arr[] = {1, 2, 3, 4, 5};
std::vector<int> v4(arr, arr + 5); // {1, 2, 3, 4, 5}

It is useful when converting arrays (or other containers) into vectors.

5 Copy Constructor

Creates a new vector as a copy of another vector.

std::vector<int> v5 = v4; // copy of v4

It performs a deep copy of all elements.

6 Move Constructor (C++11 and later)

Constructs a vector by taking over the resources of another vector (no deep copy).

std::vector<int> v6 = std::move(v5);

• Afrer this, v5 is left in a valid but unspecified state (usually empty).
• Very efficient for temporary vectors.

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 

Accessing Elements

operator[]:

Like an traditional array, we can access the vector's elements using the index operator [].

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

int main() {
    vector<int> rollNumber = {101, 102, 103, 104, 105};

    cout << "First student: " << rollNumber[0] << endl;

    // Modify
    rollNumber[1] = 110;
    cout << "Updated second student: " << rollNumber[1] << endl;

    return 0;
}

• Indexing start from 0.
• Accessing out-of-bounds elements is unsafe and leads to undefined behavior.

at: (safer)

int element = myVector.at(2); 

Accesses the element at index 2 with bounds checking.

• It performs bounds checking, preventing undefined behavior.
• Throws an exception if the index is invalid.

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.

Capacity:

Vectors 

size():

It returns the number of elements currently stored in the vector.

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.

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

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    cout << "Size: " << v.size() << endl;  // Output: 5
}

Returns the number of elements in the vector.

empty:

Checks if the vector contains no elements. Returns true if empty.

bool isEmpty = myVector.empty();

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

capacity:

Returns the total memory allocated, i.e., how many elements the vector can hold before needing to reallocate.

size_t capacity = myVector.capacity();

Returns the current capacity of the vector.

Notes:

• Capacity ≥ size.
• When size exceeds capacity, vector automatically reallocates memory, usually doubling its previous capacity.

reserve(n):

Pre-allocates memory for at least n elements.

• Reduces the number of reallocations if you know the size in advance.

vector<int> v;
v.reserve(10);
cout << "Capacity after reserve: " << v.capacity() << endl;

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

shrink_to_fit():

Requests the vector to reduce capacity to fit the current size, freeing unused memory.

v.pop_back(); // Remove elements
v.shrink_to_fit();
cout << "Capacity after shrink_to_fit: " << v.capacity() << endl;

Note: This is non-binding request; the implementation may or may not reduce capacity.

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)