STL Containers in C++

Table of Contents

• •STL Containers in C++
  • •Table of Contents
  • •Sequence Containers
    • •vector
    • •array
    • •deque
    • •list
    • •forward_list
  • •Associative Containers
    • •set
    • •multiset
    • •map
    • •multimap
  • •Unordered Containers
  • •Container Adapters
    • •stack
    • •queue
    • •priority_queue
  • •Choosing Containers
  • •Best Practices
    • •✅ Do
    • •❌ Don't
  • •Quick Reference
  • •Compile & Run

---

Sequence Containers

vector

Dynamic array with fast random access:

#include <vector>

vector<int> v = {1, 2, 3};
v.push_back(4);
v.pop_back();
v[0] = 10;
v.at(1);          // Bounds-checked access
v.front();        // First element
v.back();         // Last element
v.size();
v.empty();
v.clear();
v.insert(v.begin(), 0);
v.erase(v.begin());

array

Fixed-size array:

#include <array>

array<int, 5> arr = {1, 2, 3, 4, 5};
arr[0] = 10;
arr.at(1);
arr.size();       // Always 5
arr.fill(0);      // Set all to 0

deque

Double-ended queue:

#include <deque>

deque<int> dq = {2, 3, 4};
dq.push_front(1);  // Fast!
dq.push_back(5);
dq.pop_front();
dq.pop_back();

list

Doubly-linked list:

#include <list>

list<int> lst = {1, 2, 3};
lst.push_front(0);
lst.push_back(4);
lst.insert(next(lst.begin()), 5);
lst.remove(2);        // Remove all 2s
lst.sort();
lst.unique();
lst.reverse();

forward_list

Singly-linked list:

#include <forward_list>

forward_list<int> fl = {1, 2, 3};
fl.push_front(0);
fl.insert_after(fl.begin(), 5);

---

Associative Containers

set

Sorted unique elements:

#include <set>

set<int> s = {3, 1, 4, 1, 5};  // {1, 3, 4, 5}
s.insert(2);
s.erase(3);
s.find(4);        // Iterator or end()
s.count(5);       // 0 or 1
s.contains(2);    // C++20: true/false

multiset

Sorted, allows duplicates:

#include <set>

multiset<int> ms = {1, 1, 2, 2, 2};
ms.count(2);      // 3
ms.erase(ms.find(2));  // Remove one 2

map

Sorted key-value pairs:

#include <map>

map<string, int> m;
m["one"] = 1;
m["two"] = 2;
m.insert({"three", 3});
m.at("one");      // Throws if not found
m["one"];         // Creates if not found
m.find("two");
m.erase("one");

for (auto& [key, value] : m) {
    cout << key << ": " << value << endl;
}

multimap

Sorted, allows duplicate keys:

#include <map>

multimap<string, int> mm;
mm.insert({"a", 1});
mm.insert({"a", 2});
auto range = mm.equal_range("a");

---

Unordered Containers

Hash-based, O(1) average lookup:

#include <unordered_set>
#include <unordered_map>

unordered_set<int> us = {3, 1, 4};
us.insert(2);
us.find(3);

unordered_map<string, int> um;
um["key"] = 42;
um.bucket_count();
um.load_factor();

---

Container Adapters

stack

LIFO:

#include <stack>

stack<int> stk;
stk.push(1);
stk.push(2);
stk.top();   // 2
stk.pop();
stk.empty();

queue

FIFO:

#include <queue>

queue<int> q;
q.push(1);
q.push(2);
q.front();  // 1
q.back();   // 2
q.pop();

priority_queue

Max heap by default:

#include <queue>

priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
pq.top();   // 4 (largest)
pq.pop();

// Min heap:
priority_queue<int, vector<int>, greater<int>> minPQ;

---

Choosing Containers

---

Best Practices

✅ Do

// 1. Reserve capacity when size is known
vector<int> v;
v.reserve(1000);

// 2. Use emplace for in-place construction
vector<pair<int, string>> vp;
vp.emplace_back(1, "hello");

// 3. Use range-based for
for (const auto& elem : container) { }

// 4. Use structured bindings for maps
for (const auto& [key, value] : myMap) { }

❌ Don't

// 1. Don't use [] on map for checking existence
// Creates entry if not found!
if (myMap["key"]) { }  // BAD

// Use find or count instead
if (myMap.find("key") != myMap.end()) { }
if (myMap.count("key")) { }

// 2. Don't invalidate iterators
for (auto it = v.begin(); it != v.end(); ) {
    if (*it == 0) it = v.erase(it);  // Correct
    else ++it;
}

---

Quick Reference

// Common operations
container.size()
container.empty()
container.clear()
container.begin() / container.end()

// Sequence
vector: push_back, pop_back, [], at
deque:  push_front/back, pop_front/back
list:   push_front/back, insert, remove

// Associative
set/map: insert, erase, find, count
unordered_*: same, plus bucket_count

// Adapters
stack:  push, pop, top
queue:  push, pop, front, back
priority_queue: push, pop, top

Compile & Run

g++ -std=c++17 -Wall examples.cpp -o examples && ./examples