STL — Vectors, Arrays and Deques

The C++ Standard Template Library (STL) gives you battle-tested, high-performance containers so you never need to reimplement linked lists, dynamic arrays, or queues from scratch. In competitive programming on platforms like Codeforces and CodeChef — where Indian contestants from IIT, NIT, and BITS campuses regularly rank globally — std::vector is by far the most-used container. Understanding it deeply, along with std::array and std::deque, is a prerequisite for any serious C++ role.

---

std::vector — The Workhorse Container

A vector is a dynamically resizable array. It stores elements contiguously in memory (like a raw array) and automatically reallocates when it runs out of space.

Declaring and Initialising

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

int main() {
    vector<int> v1;                        // Empty vector
    vector<int> v2(5);                     // 5 elements, initialised to 0
    vector<int> v3(5, 42);                 // 5 elements, all 42
    vector<int> v4 = {10, 20, 30, 40, 50}; // Initialiser list (C++11)
    vector<int> v5(v4);                    // Copy of v4

    cout << "v3: ";
    for (int x : v3) cout << x << " ";    // 42 42 42 42 42
    cout << endl;

    return 0;
}

Inserting and Removing Elements

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

int main() {
    vector<int> v;

    v.push_back(10);     // Add to end: [10]
    v.push_back(20);     // [10, 20]
    v.push_back(30);     // [10, 20, 30]

    v.pop_back();        // Remove last: [10, 20]

    v.insert(v.begin() + 1, 15);  // Insert 15 at index 1: [10, 15, 20]

    v.erase(v.begin());            // Remove first: [15, 20]

    cout << "Size: " << v.size() << endl;   // 2
    cout << "v[0]: " << v[0]     << endl;   // 15
    cout << "v.at(1): " << v.at(1) << endl; // 20 (bounds-checked)

    v.clear();   // Remove all elements, size becomes 0
    cout << "After clear, size: " << v.size() << endl; // 0

    return 0;
}

v[i] is unchecked (undefined behaviour on out-of-bounds). v.at(i) throws std::out_of_range — prefer it in non-performance-critical code.

Size and Capacity

size is the number of elements currently in the vector. capacity is how many elements it can hold before it must reallocate.

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

int main() {
    vector<int> v;
    cout << "size=" << v.size() << " cap=" << v.capacity() << endl;

    for (int i = 0; i < 10; i++) {
        v.push_back(i);
        cout << "size=" << v.size() << " cap=" << v.capacity() << endl;
    }
    return 0;
}

Typical output (capacity doubles on reallocation):

size=0 cap=0
size=1 cap=1
size=2 cap=2
size=3 cap=4
size=4 cap=4
size=5 cap=8
...
size=10 cap=16

reserve and shrink_to_fit

If you know in advance how many elements you will insert, call reserve to pre-allocate memory and avoid repeated reallocations:

vector<int> v;
v.reserve(1000);   // Allocate space for 1000 elements upfront
// Now push_back 1000 times with zero reallocations

shrink_to_fit() is a non-binding hint to the implementation to release excess capacity:

v.shrink_to_fit();   // capacity becomes size (implementation may ignore)

emplace_back vs push_back

emplace_back constructs the element in-place, avoiding a copy or move:

struct Point { double x, y; };

vector<Point> pts;
pts.push_back({1.0, 2.0});       // Creates temporary, then moves into vector
pts.emplace_back(3.0, 4.0);      // Constructs directly in vector — preferred

For simple types like int, there is no measurable difference. For large objects or those with expensive copy constructors, emplace_back is faster.

---

Iterators

Iterators are generalised pointers that traverse containers. Every STL container provides begin() and end() iterators.

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

int main() {
    vector<int> v = {10, 20, 30, 40, 50};

    // Iterator-based loop
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // auto simplifies iterator declarations (C++11)
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // Range-based for (cleanest — C++11)
    for (auto x : v) {
        cout << x << " ";
    }
    cout << endl;

    // Reverse iteration
    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

Range-Based For with auto

The range-based for loop is almost always the right choice for simple traversal:

vector<string> cities = {"Delhi", "Mumbai", "Bengaluru", "Hyderabad"};

// Read-only — auto gives a copy
for (auto city : cities) {
    cout << city << endl;
}

// Read-only — auto& avoids copying (preferred for non-trivial types)
for (const auto& city : cities) {
    cout << city << endl;
}

// Mutation — use auto& without const
for (auto& city : cities) {
    city += " (India)";
}

---

Iterator Invalidation Rules

This is a critical interview topic and a source of nasty bugs. Certain vector operations invalidate existing iterators and pointers into the vector.

Operation	Invalidates
push_back / emplace_back (no reallocation)	None
push_back / emplace_back (triggers reallocation)	All iterators and pointers
insert before element i	Iterators at and after position i
erase at element i	Iterators at and after position i
clear	All iterators
reserve (causes reallocation)	All iterators and pointers

vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin() + 2;  // Points to element 3

v.push_back(6);   // May reallocate — 'it' is now dangling!
cout << *it;      // Undefined behaviour

Safe pattern: Capture indices, not iterators, when modifying a vector in a loop.

---

2D Vectors

A 2D vector is a vector of vectors — the C++ equivalent of a 2D array, but with dynamic sizing.

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

int main() {
    int rows = 3, cols = 4;

    // Declare and initialise a 3x4 grid with zeros
    vector<vector<int>> grid(rows, vector<int>(cols, 0));

    // Fill with values
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            grid[i][j] = i * cols + j + 1;

    // Print
    for (const auto& row : grid) {
        for (int val : row) {
            cout << val << "\t";
        }
        cout << endl;
    }

    // Jagged (ragged) 2D vector — rows of different lengths
    vector<vector<int>> triangle;
    for (int i = 1; i <= 4; i++) {
        triangle.push_back(vector<int>(i, i));
    }

    for (const auto& row : triangle) {
        for (int val : row) cout << val << " ";
        cout << endl;
    }

    return 0;
}

Output:

1    2    3    4
5    6    7    8
9    10   11   12

1
2 2
3 3 3
4 4 4 4

---

std::array — Stack-Allocated Fixed-Size Array

std::array wraps a raw C-style array in a class that provides STL-compatible iterators, size(), at(), and other methods. The size is fixed at compile time and the data lives on the stack — no heap allocation.

#include <iostream>
#include <array>
#include <algorithm>
using namespace std;

int main() {
    array<int, 5> arr = {50, 30, 10, 40, 20};

    cout << "Size: " << arr.size() << endl;
    cout << "Front: " << arr.front() << endl;
    cout << "Back: "  << arr.back()  << endl;

    sort(arr.begin(), arr.end());

    for (int x : arr) cout << x << " ";
    cout << endl;   // 10 20 30 40 50

    // arr.push_back(60);  // ERROR — fixed size, no push_back
    return 0;
}

std::array vs Raw Array vs std::vector

Feature	int arr[N]	std::array<int,N>	std::vector<int>
Size	Fixed (compile time)	Fixed (compile time)	Dynamic (runtime)
Memory	Stack	Stack	Heap
Bounds checking	None	at()	at()
STL iterators	Pointer arithmetic only	Full iterator support	Full iterator support
Pass to function	Decays to pointer, loses size	Passes with size intact	Passes with size
size() method	No (use sizeof)	Yes	Yes
Preferred when	Legacy code	Fixed, small, stack arrays	Variable-size collections

Prefer std::array over raw arrays in new code. Prefer std::vector when the size varies at runtime.

---

std::deque — Double-Ended Queue

A deque (pronounced "deck") supports fast insertion and deletion at both ends — O(1) amortised. Unlike vector, it does not store elements in a single contiguous block; instead it uses a sequence of fixed-size chunks.

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

int main() {
    deque<int> dq;

    dq.push_back(10);    // Add to back
    dq.push_back(20);
    dq.push_front(5);    // Add to front — O(1), unlike vector
    dq.push_front(1);

    // dq is now: 1, 5, 10, 20

    for (int x : dq) cout << x << " ";
    cout << endl;

    dq.pop_front();   // Remove from front
    dq.pop_back();    // Remove from back

    cout << "After pops: ";
    for (int x : dq) cout << x << " ";
    cout << endl;   // 5 10

    cout << "dq[1]: " << dq[1] << endl;   // Random access — O(1)
    return 0;
}

vector vs deque

Operation	vector	deque
push_back	O(1) amortised	O(1) amortised
push_front	O(n) — shifts all elements	O(1) amortised
Random access []	O(1)	O(1)
Memory layout	Contiguous	Chunked (not contiguous)
Cache performance	Excellent	Good (slightly lower than vector)

Use deque when you need efficient insertions at both ends (e.g., a sliding window, BFS queue). Use vector for everything else.

---

Worked Example: Student Marks — Store, Sort, and Report

This example mirrors real-world data pipeline code used in educational platforms like BYJU'S or Vedantu's backend analytics, and appears in entry-level C++ interviews at service companies.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
using namespace std;

struct Student {
    string name;
    int    rollNo;
    double marks;   // out of 100
};

// Comparator: sort by marks descending
bool byMarksDesc(const Student& a, const Student& b) {
    return a.marks > b.marks;
}

void printTable(const vector<Student>& students) {
    cout << "\n--- Student Report ---" << endl;
    cout << "Rank  Roll  Name                Marks  Grade" << endl;
    cout << string(55, '-') << endl;

    for (int i = 0; i < (int)students.size(); i++) {
        const Student& s = students[i];
        string grade;
        if      (s.marks >= 90) grade = "A+";
        else if (s.marks >= 75) grade = "A";
        else if (s.marks >= 60) grade = "B";
        else if (s.marks >= 45) grade = "C";
        else                    grade = "F";

        printf("%-6d%-6d%-20s%-7.1f%s\n",
               i + 1, s.rollNo, s.name.c_str(), s.marks, grade.c_str());
    }
}

int main() {
    vector<Student> students = {
        {"Riya Sharma",    101, 88.5},
        {"Arjun Mehta",    102, 72.0},
        {"Priya Nair",     103, 95.0},
        {"Vikram Singh",   104, 61.5},
        {"Sneha Iyer",     105, 40.0},
        {"Rohit Yadav",    106, 78.5},
        {"Ananya Das",     107, 55.0},
        {"Karthik Raj",    108, 91.0},
    };

    // Sort by marks descending
    sort(students.begin(), students.end(), byMarksDesc);
    printTable(students);

    // Statistics using vector and numeric algorithms
    vector<double> marks;
    marks.reserve(students.size());
    for (const auto& s : students) marks.push_back(s.marks);

    double total   = accumulate(marks.begin(), marks.end(), 0.0);
    double average = total / marks.size();
    double highest = *max_element(marks.begin(), marks.end());
    double lowest  = *min_element(marks.begin(), marks.end());

    cout << "\n--- Statistics ---" << endl;
    cout << "Total students: " << students.size() << endl;
    cout << "Average marks:  " << average  << endl;
    cout << "Highest marks:  " << highest  << endl;
    cout << "Lowest marks:   " << lowest   << endl;

    // Count students who passed (marks >= 45)
    int passed = 0;
    for (double m : marks) if (m >= 45) passed++;
    cout << "Passed:         " << passed << "/" << students.size() << endl;

    // 2D marks: store subject-wise marks for top 3 students
    // Columns: Maths, Science, English, Hindi
    vector<vector<double>> subjectMarks = {
        {95, 92, 96, 97},    // Priya (rank 1)
        {90, 94, 88, 92},    // Karthik (rank 2)
        {87, 89, 90, 88},    // Riya (rank 3)
    };

    cout << "\n--- Subject-wise (Top 3) ---" << endl;
    vector<string> subjects = {"Maths", "Science", "English", "Hindi"};
    for (int i = 0; i < 3; i++) {
        cout << students[i].name << ": ";
        for (int j = 0; j < 4; j++) {
            cout << subjects[j] << "=" << subjectMarks[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

Sample Output:

--- Student Report ---
Rank  Roll  Name                Marks  Grade
-------------------------------------------------------
1     103   Priya Nair          95.0   A+
2     108   Karthik Raj         91.0   A+
3     101   Riya Sharma         88.5   A
4     106   Rohit Yadav         78.5   A
5     102   Arjun Mehta         72.0   B
6     104   Vikram Singh        61.5   B
7     107   Ananya Das          55.0   C
8     105   Sneha Iyer          40.0   F

--- Statistics ---
Total students: 8
Average marks:  72.6875
Highest marks:  95
Lowest marks:   40

Passed:         7/8

--- Subject-wise (Top 3) ---
Priya Nair: Maths=95 Science=92 English=96 Hindi=97
Karthik Raj: Maths=90 Science=94 English=88 Hindi=92
Riya Sharma: Maths=87 Science=89 English=90 Hindi=88

---

Common Pitfalls

1. Iterator invalidation after modification. Storing an iterator into a vector, then calling push_back, may reallocate memory and leave the iterator dangling. Always recapture or use indices.

2. Using v[i] without bounds checking. Out-of-bounds access on [] is undefined behaviour — no exception, just silent corruption. Use v.at(i) during development.

3. Forgetting to reserve before bulk insertions. Inserting one million elements one by one without reserve triggers roughly 20 reallocations. Always reserve when the size is known.

4. Copying a vector when you meant to reference it. for (auto v : matrix) copies each inner vector. Use for (const auto& v : matrix) to avoid O(n^2) copying overhead.

5. Confusing size() return type. size() returns size_t, which is unsigned. Comparing v.size() - 1 when v is empty wraps around to a huge number. Use (int)v.size() or check !v.empty() first.

6. Deque vs vector misconception. deque does not guarantee contiguous storage. Passing dq.data() as a C-style array pointer is not valid the way v.data() is for vector.

---

Practice Exercises

1. Write a function that takes a vector<int> and returns a new vector containing only the even numbers, preserving order. Measure the difference in performance with and without reserve.

2. Implement a sliding window maximum using a deque<int> that stores indices. Given a vector of integers and window size k, print the maximum in every window of size k — a classic FAANG interview problem.

3. Use a 2D vector to implement matrix multiplication for two NxN matrices. Test with N=3 using sample matrices.

4. Given a vector<Student> (use the struct from the worked example), write a function that partitions students into passed and failed vectors using std::partition from <algorithm>.

5. Simulate a task queue for a customer service system (like Flipkart's order processing): use a deque<string> where new tasks are added to the back with push_back and urgent tasks are added to the front with push_front. Process tasks from the front.

---

Summary

• std::vector is the go-to sequence container: dynamic sizing, contiguous memory, excellent cache performance.
• push_back adds to the end in O(1) amortised; pop_back removes in O(1).
• emplace_back constructs elements in-place — prefer it over push_back for non-trivial types.
• Use reserve to pre-allocate memory when you know the approximate number of elements.
• at(i) performs bounds checking; operator[] does not.
• Iterator invalidation: any reallocation-triggering operation invalidates all iterators into the vector.
• std::array<T, N> is a fixed-size, stack-allocated array with full STL iterator support — prefer it over raw arrays.
• std::deque supports O(1) insertion and deletion at both ends but trades away contiguous storage.
• Range-based for with const auto& is the cleanest and most efficient way to iterate read-only.
• 2D vectors (vector<vector<T>>) provide dynamic 2D storage; jagged rows are naturally supported.