Containers
Containers are template classes used to store and organize data in a standard way.
They answer the question:
**How is data laid out in memory, and how does it grow or shrink?**
Containers are split into three categories:
- Sequential Containers
- Array, Vector, List, Forward List, Pair
- Associative Containers
- Set, MultiSet, unordered_set, unordered_multiset
- Adapter Containers
- Stack, Queue, Deque, priority Queue
Sequential Containers
Ordered collections where position matters
[ 0 ][ 1 ][ 2 ][ 3 ] <-- index-based access
Array
Arrays store multiple values of the same data type in contiguous memory with fixed size.
#include <array>
// std::array<data_type, no_of_elements> nameOfArray;
std::array<int, 3> a = {1,2,3};
Why use std::array instead of C arrays?
- Knows its size
- Works with STL algorithms
- Safer (no decay to pointer)
When to use
- Size known at compile time
- Stack allocation required
- Performance-critical code
Array has a fixed size and cannot be changed.
Always initialize it to avoid garbage values.
Vector
Vectors are dynamic arrays stored in contiguous memory.
#include <vector>
std::vector<int> v = {1,2,3};
std::vector<int> iv(3, 100); // {100,100,100}
std::cout << v.size(); // number of elements
std::cout << v.capacity(); // allocated storage
Common Operations
v.insert(v.begin() + 1, 5); // 1,5,2,3
v.push_back(4); // 1,5,2,3,4
v.insert(v.end(), 5); // 1,5,2,3,4,5
v.emplace(v.end(), 6); // 1,5,2,3,4,5,6
v.emplace_back(7); // 1,5,2,3,4,5,6,7
Range-based loop (C++11)
for (int& vec : v) {
std::cout << vec << " ";
}
Initialization from C-array
const static int size = 10;
int ia[size] = { 1, 2, 3, ,4, 5, 6, 7, 8, 9, 10};
vector<int> iv2(ia, ia+size);
Memory Growth Model
Capacity doubles on reallocation
[1][2][3] capacity=3
|
v
[1][2][3][_][_][_][_][_] capacity=8
When to use vector
- Fast random access
- Append-heavy workloads
- Cache-friendly iteration
Costs
- Reallocation is expensive
- Insert/remove in middle is O(n)
Properties
Push back → O(1) amortized
Insert middle → O(n)
Random access → O(1)
List
std::list is a doubly linked list.
#include <list>
std::list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3); // {1, 2, 3}
l.push_front(4); // {4, 1, 2, 3}
// Insert in middle
std::list<int>::iterator it = l.begin();
std::advance(it, 2);
l.insert(it, 5); // {4, 1, 5, 2, 3}
// You can not use [] or at() to access list element
for (const auto& elem : l) {
std::cout << elem << " ";
}
Memory Layout
[4] <-> [1] <-> [2] <-> [3]
Each node stores:
- value
- pointer to next
- pointer to previous
Why use list
- Frequent insertions/removals anywhere
- Stable iterators
Why NOT use list
- No random access
- Poor cache locality
- Higher memory overhead
Insert/delete anywhere → O(1)
Access by index → not allowed
Pair
std::pair groups two values, possibly of different types.
#include <utility>
pair<string, int>p = make_pair("Amr", 20);
pair<string, int>p2 = {"Tarek", 10};
pair<string, int>p3{"Hassan", 1};
// For accessing
cout<< p.first() << ":"<< p.second() << endl;
Memory model:
[first][second]
Used heavily inside map, unordered_map, return values, etc.
Associative Containers
Sorted or hashed collections optimized for lookup
Set
std::set stores unique, sorted keys.
#include <set>
std::set<int>s;
s.insert(4); // insert at the end
s.emplace(5); insert but faster
std::set<int, greater<int>s{12,3,4,5,6,23,121}; // sort descending
Tree-based structure
10
/ \
5 15
Properties
Insert → O(log n)
Find → O(log n)
Sorted → always
Unique → enforced
MultiSet
Allows duplicate values, still sorted.
std::multiset<int> ms;
ms.emplace(1);
ms.count(1);
Use when:
- You need sorting
- Duplicates are allowed
Map
std::map stores key-value pairs with unique, sorted keys.
#include <map>
std::map<int, std::string> myMap;
myMap[1] = "One";
myMap[2] = "Two";
// Search for key 1 auto
it = myMap.find(1);
if (it != myMap.end()) {
std::cout << "Key 1 found with value: " << it->second << std::endl;
} else {
std::cout << "Key 1 not found" << std::endl;
}
Internal model:
[ key ] -> [ value ]
Properties
Keys are uniqe and sorted
Insert / Search → O(log n)
delete → O(1)
Used when:
- Order matters
- Deterministic iteration
- Logarithmic performance is acceptable
Adapter Containers
Restricted interfaces built on top of other containers
Queue (FIFO)
#include <queue>
std::queue<int> q;
q.push(1); // will push to front (FI)
q.push(2);
q.push(3); // {3,2,1}
q.pop() // remove the front element (1) (FO)
q.back(); // 3
q.front(); // 1
Front --> [1][2][3] --> Back
Use when:
- Processing order matters
- FIFO semantics required
Deque
Double-ended queue.
#include <deque>
std::deque<int> dq;
dq.push_back(1);
dq.push_back(2);
dq.push_front(3); {3, 1, 2}
dq.pop_front(); // Remove the front element (3)
dq.pop_back(); // Remove the back element (2)
Memory layout (chunked):
[ ][ ][ ] [ ][ ][ ]
Why deque exists
- Fast front and back operations
- No full reallocation like vector
Queue and Deque are not contiguous they are saving the data in memory chunks, so it can grow and shrink more efficiently than `vector`
Stack (FILO)
#include <stack>
std::stack<int> stack;
// Add (push) elements to the stack
stack.push(10);
stack.push(20);
stack.push(30);
// Get (pop) elements from the stack
std::cout << "Popping elements from stack: \n";
while (!stack.empty()) {
// Get the top element
std::cout << stack.top() << std::endl;
// Remove the top element
stack.pop();
}
Top
[30]
[20]
[10]
Properties
Add / delete from back or front → O(1)
Add / delete from middle → O(n) (because of the shift needed)
Access [], or at() → O(1)
find → O(n) (slow search)
Used for:
- Recursion simulation
- Parsing
- Undo/redo logic