Vector, List & Deque

Why Not Just Use Arrays?

Back in Lesson 6 you learned raw C++ arrays: int arr[10];. They work, but they have a big limitation — their size is fixed at compile time. You can't add an 11th element to a 10-element array. If you don't know how many items you'll need ahead of time, a raw array is the wrong tool.

In Lesson 9 you saw the manual fix: allocate with new, track the size yourself, and remember to delete[] it when you're done — or leak memory. The C++ Standard Template Library (STL) gives you container classes that do all of that bookkeeping automatically and safely. The first and most important one is std::vector.

std::vector — Your Default Container

A vector<T> stores elements of type T in one contiguous block of memory, just like an array — which means indexing with [] is just as fast as a raw array (O(1)). Unlike an array, it can grow.

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

int main() {
    vector<int> scores; // empty vector, grows automatically

    scores.push_back(90);
    scores.push_back(85);
    scores.push_back(77);

    cout << "Number of scores: " << scores.size() << endl;

    for (auto s : scores) { // range-based for loop
        cout << s << " ";
    }
    cout << endl;

    scores.pop_back(); // removes the last element (77)
    cout << "After pop_back, size = " << scores.size() << endl;

    return 0;
}

Notice scores started completely empty — no size given up front. .push_back() adds an element to the end (amortized O(1) — occasionally the vector has to grow and copy everything, but averaged over many pushes, each one is effectively constant time). .pop_back() removes the last element in O(1). .size() always tells you exactly how many elements are currently stored.

Indexing: [] vs .at()

Just like an array, you can read or write any element with []. Vector also gives you .at(), which does the same thing but checks the index is valid first and throws an exception if it isn't.

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

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

    cout << "nums[2] = " << nums[2] << endl;       // fast, no bounds check
    cout << "nums.at(2) = " << nums.at(2) << endl;  // safe, checked

    nums[0] = 100; // elements are mutable through []

    try {
        cout << nums.at(10) << endl; // index out of range!
    } catch (const std::out_of_range& e) {
        cout << "Caught error: " << e.what() << endl;
    }

    return 0;
}

std::list — The Doubly-Linked List

std::list<T> stores elements as separate nodes, each holding a value plus pointers to the next and previous node — a doubly-linked list. Elements are scattered across memory, not contiguous.

That trade-off flips vector's strengths and weaknesses: list can't be indexed with [] at all (there's no operator for it — reaching element 5 means walking 5 nodes from the start, O(n)). But once you already have an iterator pointing at a position, inserting or removing there is O(1) — no shifting, just re-linking a couple of pointers.

#include <iostream>
#include <list>
#include <string>
using namespace std;

int main() {
    list<string> names = {"Alice", "Bob", "Charlie"};

    auto it = names.begin();
    ++it; // now points at "Bob"
    names.insert(it, "Zoe"); // O(1) — no shifting needed

    for (const string& n : names) {
        cout << n << " ";
    }
    cout << endl; // Alice Zoe Bob Charlie

    return 0;
}

std::deque — Double-Ended Queue

std::deque<T> (pronounced "deck") behaves like a vector — indexable with [] — but adds one superpower: it can grow or shrink efficiently from both ends, not just the back.

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

int main() {
    deque<int> dq;

    dq.push_back(2);
    dq.push_back(3);
    dq.push_front(1);
    dq.push_front(0);

    for (int n : dq) cout << n << " ";
    cout << endl; // 0 1 2 3

    dq.pop_front();
    dq.pop_back();

    cout << "front = " << dq.front() << ", back = " << dq.back() << endl;

    return 0;
}

A vector's push_front() doesn't even exist — inserting at position 0 would mean shifting every other element down, an O(n) operation, so the STL deliberately doesn't offer a misleadingly-named fast method for it. A deque is built specifically to make front and back operations both O(1), which makes it the natural choice for things like a sliding-window buffer or a task queue processed from either end.

Choosing the Right Container

Lesson Summary