C++ STL Containers & Functions

The mental model ↑ top

Do not memorize random functions. First identify what kind of container you are dealing with.

Master function table ↑ top

Note: contains() is C++20. Before C++20, use find(x) != container.end().

vector<data_type> arr — full practical reference ↑ top

#include <vector>
using namespace std;

vector<int> arr;
vector<int> a = {10, 20, 30};
vector<int> b(5);        // 5 integers, initialized to 0
vector<int> c(5, 7);     // {7, 7, 7, 7, 7}

Examples

vector<int> arr = {10, 20, 30};

arr.push_back(40);                // {10,20,30,40}
arr.insert(arr.begin() + 1, 15);  // {10,15,20,30,40}

arr[2] = 99;                      // {10,15,99,30,40}

arr.erase(arr.begin() + 3);       // {10,15,99,40}
arr.pop_back();                   // {10,15,99}

cout << arr.front();             // 10
cout << arr.back();              // 99
cout << arr.size();              // 3

deque ↑ top

Think: “vector-like indexing, but efficient insertion/removal at both ends.”

deque<int> dq = {20, 30};

dq.push_front(10);     // {10,20,30}
dq.push_back(40);      // {10,20,30,40}

dq.pop_front();        // {20,30,40}
dq.pop_back();         // {20,30}

dq[0] = 99;
dq.insert(dq.begin()+1, 50);
dq.erase(dq.begin());

Useful functions: push_front, push_back, emplace_front, emplace_back, insert, emplace, pop_front, pop_back, erase, [], at, front, back.

list ↑ top

std::list is a doubly linked list. It supports fast insertion/removal when you already have an iterator, but no random indexing.

list<int> li = {10, 20, 30};

li.push_front(5);
li.push_back(40);

li.pop_front();
li.pop_back();

auto it = li.begin();
++it;
li.insert(it, 15);
li.erase(it);

li.remove(20);      // remove every element equal to 20
li.reverse();
li.sort();

set and multiset ↑ top

A set stores unique sorted keys. A multiset is sorted but allows duplicates.

set<int> s;

s.insert(10);
s.insert(30);
s.insert(20);
s.insert(10);        // duplicate: not added

// s = {10, 20, 30}

Checking if something exists

if (s.find(20) != s.end()) {
    cout << "Found";
}

// C++20:
if (s.contains(20)) {
    cout << "Found";
}

Why no push_back()?

A set decides the storage position automatically according to ordering. There is no meaningful “back insertion” operation.

multiset deletion trap

multiset<int> ms = {2, 2, 2, 5};

ms.erase(2);             // removes ALL 2s

auto it = ms.find(2);
if (it != ms.end())
    ms.erase(it);        // removes only ONE 2

unordered_set ↑ top

Same basic set operations, but hash-based and not sorted.

unordered_set<string> seen;

seen.insert("evt1");
seen.emplace("evt2");

if (seen.find("evt1") != seen.end()) {
    cout << "Already seen";
}

seen.erase("evt1");

Average complexity: insertion/search/deletion ≈ O(1). Worst case can be O(n).

map / unordered_map ↑ top

A map stores key → value pairs.

unordered_map<string, int> freq;

freq["apple"] = 3;     // insert or replace
freq["apple"]++;       // increment
freq["banana"] = 1;

Iterating

for (auto &entry : freq) {
    cout << entry.first << " " << entry.second << '\n';
}

// Cleaner with structured bindings:
for (auto &[key, value] : freq) {
    cout << key << " " << value << '\n';
}

stack, queue, priority_queue ↑ top

stack<int> st;

st.push(10);
st.push(20);

cout << st.top();  // 20
st.pop();           // removes 20

st.empty();
st.size();

queue<int> q;

q.push(10);
q.push(20);

cout << q.front(); // 10
cout << q.back();  // 20

q.pop();             // removes 10
q.empty();
q.size();

priority_queue<int> pq;

pq.push(10);
pq.push(50);
pq.push(20);

cout << pq.top();   // 50
pq.pop();

priority_queue<int,
    vector<int>,
    greater<int>> minHeap;

array and string ↑ top

std::array

array<int, 4> a = {10,20,30,40};

a[1] = 99;
cout << a.at(2);
cout << a.front();
cout << a.back();
cout << a.size();

a.fill(7);

std::array has fixed size, so no push_back, insert, erase, or resize.

std::string

string s = "hello";

s.push_back('!');          // "hello!"
s.pop_back();              // "hello"
s += " world";             // append
s.append("!");             // append
s.insert(5, " nice");      // insert
s.erase(5, 5);             // erase range by index/count
s.replace(0, 5, "Hi");     // replace substring

char c = s[0];
size_t pos = s.find("world");

insert vs emplace vs push_back ↑ top

Simple types: do not overthink emplace

vector<int> v;
v.push_back(10);       // perfectly fine
v.emplace_back(10);    // also fine, but no meaningful advantage here

Objects: emplace_back becomes more natural

struct Student {
    string name;
    int age;

    Student(string n, int a) : name(n), age(a) {}
};

vector<Student> students;

students.push_back(Student("Mohammed", 21));
students.emplace_back("Mohammed", 21);

Deletion / erase patterns ↑ top

Vector: erase by index

v.erase(v.begin() + i);

Vector: erase a range

v.erase(v.begin() + l, v.begin() + r); // [l, r)

Set/map: erase by value/key

s.erase(x);
m.erase(key);

Erase while iterating

for (auto it = v.begin(); it != v.end(); ) {
    if (*it < 0)
        it = v.erase(it);
    else
        ++it;
}

Remove all occurrences from vector

v.erase(remove(v.begin(), v.end(), x), v.end());

In C++20 you can also use:

erase(v, x);
erase_if(v, [](int x) { return x < 0; });

How to replace / update elements ↑ top

// set replacement
set<int> s = {10,20,30};

s.erase(20);
s.insert(25);

Finding elements ↑ top

Sequence containers

Use the generic algorithm std::find.

auto it = find(v.begin(), v.end(), 30);

if (it != v.end()) {
    cout << "Found";
}

Associative containers

Use the container's own find().

if (s.find(30) != s.end()) { ... }
if (m.find("alice") != m.end()) { ... }

Iterators: why begin() keeps appearing ↑ top

An iterator acts roughly like a pointer to an element.

vector<int> v = {10,20,30};

auto it = v.begin();   // points to 10

cout << *it;          // 10
++it;
cout << *it;          // 20

v.end();               // points ONE POSITION AFTER the last element

For vector random access:

v.begin() + 2   // iterator to index 2

But this is not valid for every container:

list<int> li = {10,20,30};

// li.begin() + 2;    // INVALID
auto it = li.begin();
advance(it, 2);       // works

Common mistakes to avoid ↑ top

Which function should I use? — 20-second decision guide ↑ top

Final memory trick

vector/deque/list → push_back
deque/list        → push_front too
set/map           → insert
stack/queue/heap  → push

Need in-place construction?
push_back  → emplace_back
push       → emplace
insert     → emplace