C++ STL Complete Guide

Standard Library

C++ STL: Complete Guide to Standard Template Library

Master C++ Standard Template Library (STL): containers, algorithms, iterators, functors. Learn with practical examples and best practices for efficient programming.

Containers

Data Structures

Algorithms

Sort, Search, Transform

Iterators

Container Access

Functors

Function Objects

C++ Tutorial · Standard Template Library

The STL provides battle-tested containers and algorithms. Learn vectors, maps, iterators, and common algorithms—productivity multipliers for interviews and production code.

What you will learn

Use vector, list, deque, and map appropriately
Iterate with iterators and range-based for
Apply sort, find, count from <algorithm>
Choose container by complexity needs
Combine containers with modern C++ idioms

Why this topic matters

STL questions appear in most C++ interviews—complexity, iterator invalidation, and when to pick vector vs map.

Key terms & indexing

C++ STL std::vector C++ map C++ algorithms

Introduction to STL

The Standard Template Library (STL) is a powerful set of C++ template classes that provide common data structures and algorithms. STL is a core part of C++ Standard Library and revolutionized C++ programming with generic programming concepts.

Why Use STL?

Code reusability and standardization
Type safety with templates
Efficient, well-tested implementations
Reduces development time
Portable across compilers and platforms
Follows consistent design patterns

STL Components

Containers: Store and organize data
Algorithms: Perform operations on data
Iterators: Access container elements
Functors: Function objects
Allocators: Memory management
Adaptors: Modify container interfaces

STL Architecture

Containers
vector, list, map, set

Iterators
begin(), end(), ++, --

Algorithms
sort(), find(), transform()

Functors
function objects

Algorithms use iterators to operate on containers

C++ STL Containers Comparison

The following table compares different STL containers with their characteristics, time complexities, and use cases:

Container	Header	Characteristics	Time Complexity	Use Cases
vector	#include <vector>	Dynamic array, random access	Access: O(1) Insert/Delete: O(n)	Default choice, when need array-like
deque	#include <deque>	Double-ended queue, fast ends	Push/Pop ends: O(1) Middle ops: O(n)	Queue/stack, sliding window
list	#include <list>	Doubly linked list	Insert/Delete: O(1) Access: O(n)	Frequent insertions/deletions
forward_list	#include <forward_list>	Singly linked list	Insert/Delete: O(1) Access: O(n)	Memory efficient list
array	#include <array>	Fixed-size array (C++11)	All ops: O(1)	Fixed size, stack allocation
set	#include <set>	Unique keys, sorted	Most ops: O(log n)	Unique collection, sorted
multiset	#include <set>	Duplicate keys, sorted	Most ops: O(log n)	Sorted bag, with duplicates
map	#include <map>	Key-value pairs, sorted keys	Most ops: O(log n)	Dictionary, associative array
multimap	#include <map>	Multiple values per key, sorted	Most ops: O(log n)	One-to-many mapping
unordered_set	#include <unordered_set>	Unique keys, hashed	Avg: O(1) Worst: O(n)	Fast lookup, no ordering
unordered_map	#include <unordered_map>	Key-value pairs, hashed	Avg: O(1) Worst: O(n)	Fast dictionary, no ordering
stack	#include <stack>	LIFO (uses deque by default)	All ops: O(1)	Function calls, undo/redo
queue	#include <queue>	FIFO (uses deque by default)	All ops: O(1)	BFS, task scheduling
priority_queue	#include <queue>	Max-heap (uses vector by default)	Push/Pop: O(log n) Top: O(1)	Dijkstra, scheduling

1. Sequence Containers

Sequence containers store elements in a linear sequence. They maintain the order of insertion and allow access by position.

Common Sequence Containers

vector

vector<int> v = {1, 2, 3};
v.push_back(4);
v.pop_back();

list

list<int> l = {1, 2, 3};
l.push_front(0);
l.pop_front();

deque

deque<int> d = {1, 2, 3};
d.push_front(0);
d.push_back(4);

Examples

1. vector push

vector v = {1,2,3};
v.push_back(4);

2. list splice

list a={1,2}, b={3};
a.splice(a.end(), b);

3. deque ends

deque d;
d.push_front(1);
d.push_back(2);

4. array fixed

array a = {1,2,3};
cout << a[1];

5. range-for vector

for (int x : v) cout << x;

6. vector reserve

v.reserve(1000);  // fewer reallocations

Choosing Sequence Containers:

vector: Default choice, good for most cases
list: When frequent insertions/deletions in middle
deque: When need fast operations at both ends
array: When fixed size known at compile time
forward_list: When memory is critical constraint

Common Mistakes:

Using [] operator without bounds checking
Invalidating iterators (vector reallocation)
Forgetting to check empty() before front()/back()
Using list when vector would be better
Not reserving capacity for large vectors

2. Associative Containers

Associative containers store elements in sorted order (or hashed) for fast lookup based on keys. They implement tree or hash table data structures.

Common Associative Containers

set

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

map

map<string, int> m;
m["Alice"] = 25;
m.find("Alice");

unordered_set

unordered_set<int> us;
us.insert(10);
us.find(10);

unordered_map

unordered_map<string, int> um;
um["Bob"] = 30;
um.find("Bob");

Examples

1. map insert

map m;
m["apple"] = 3;

2. unordered_map

unordered_map um;
um["kiwi"] = 5;

3. set unique

set s = {3,1,3,2};
// stores 1,2,3

4. multimap equal keys

multimap mm;
mm.insert({'a',1});
mm.insert({'a',2});

5. find in map

auto it = m.find("apple");
if (it != m.end()) cout << it->second;

6. lower_bound set

set st={1,3,5};
auto it = st.lower_bound(3);

Ordered vs Unordered Containers

Use ordered containers (set/map) when you need sorted elements or range queries. Use unordered containers when you need faster lookups and don't care about order.

3. Container Adaptors

Container adaptors provide specialized interfaces for stacks, queues, and priority queues. They use underlying containers but restrict access patterns.

Container Adaptor Syntax

stack

stack<int> s;
s.push(10);
s.top();
s.pop();

queue

queue<int> q;
q.push(10);
q.front();
q.pop();

priority_queue

priority_queue<int> pq;
pq.push(10);
pq.top();
pq.pop();

Examples

1. stack LIFO

stack st;
st.push(10);
cout << st.top(); st.pop();

2. queue FIFO

queue q;
q.push(1); q.push(2);
cout << q.front(); q.pop();

3. priority_queue

priority_queue pq;
pq.push(3); pq.push(10);
cout << pq.top();

4. stack from deque

stack> custom;

5. empty check

if (!q.empty()) q.pop();

6. size()

cout << st.size();

stack

LIFO (Last In First Out)
Operations: push(), pop(), top()
Default container: deque
Use for: function calls, undo/redo
Time complexity: O(1) for all operations

queue

FIFO (First In First Out)
Operations: push(), pop(), front(), back()
Default container: deque
Use for: BFS, task scheduling
Time complexity: O(1) for all operations

priority_queue

Max-heap by default
Operations: push(), pop(), top()
Default container: vector
Use for: Dijkstra, scheduling
Time complexity: O(log n) push/pop

4. STL Algorithms

STL provides over 100 algorithms that operate on ranges of elements. Algorithms are template functions that work with iterators.

Common Algorithm Categories

Non-modifying

find(), count()
for_each(), all_of()
search(), mismatch()

Modifying

copy(), transform()
replace(), fill()
generate(), remove()

Sorting

sort(), stable_sort()
partial_sort()
nth_element()

Numeric

accumulate()
inner_product()
partial_sum()
adjacent_difference()

Examples

1. sort vector

vector v={5,1,4};
sort(v.begin(), v.end());

2. find

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

3. count_if

int c = count_if(v.begin(), v.end(),
    [](int x){ return x%2==0; });

4. accumulate

int sum = accumulate(v.begin(), v.end(), 0);

5. transform

transform(v.begin(), v.end(), v.begin(),
    [](int x){ return x*2; });

6. max_element

auto it = max_element(v.begin(), v.end());

Algorithm Best Practices:

Prefer STL algorithms over hand-written loops (safer, clearer)
Use predicates (functions/lambdas) for custom comparisons
Remember iterator validity (some algorithms invalidate iterators)
Use back_inserter, front_inserter, inserter for output
Check algorithm preconditions (e.g., sorted ranges for binary search)
Use std::begin() and std::end() for C-style arrays

5. Iterators and Functors

Iterators provide a uniform way to access container elements. Functors (function objects) allow treating functions as objects.

Iterator Categories

Input: Read only, forward
Output: Write only, forward
Forward: Read/write, forward
Bidirectional: Forward/backward
Random Access: Direct access
Contiguous: C++17, contiguous memory

Functor Types

Function Objects: Classes with operator()
Function Pointers: Traditional C functions
Lambdas: C++11 anonymous functions
std::function: Type-erased callable
Binders: bind(), bind_front(), bind_back()

Examples

1. begin/end

for (auto it=v.begin(); it!=v.end(); ++it)
    cout << *it;

2. reverse_iterator

for (auto it=v.rbegin(); it!=v.rend(); ++it)
    cout << *it;

3. insert iterator

back_insert_iterator> bi(v);
*bi++ = 9;

4. less functor

sort(v.begin(), v.end(), less());

5. lambda predicate

remove_if(v.begin(), v.end(), [](int x){return x<0;});

6. distance

cout << distance(v.begin(), v.end());

When to Use Each Callable Type:

Function objects: When you need state or type erasure isn't needed
Function pointers: For C compatibility or simple functions
Lambdas: Most common case - concise and can capture context
std::function: When you need to store different callables with same signature
Bind expressions: When you need to fix some arguments of a function

6. STL Best Practices and Common Mistakes

STL Best Practices

Prefer algorithms over hand-written loops
Use auto for iterator types (C++11)
Choose the right container for your use case
Use emplace operations when possible (C++11)
Reserve capacity for vectors when size is known
Use range-based for loops for simple iteration
Prefer unordered_map over map when order not needed

Common Mistakes

Iterator invalidation after container modification
Using wrong iterator category for algorithm
Forgetting to check empty() before front()/back()
Memory leaks with pointers in containers
Inefficient container choice for operations
Not using move semantics (C++11)
Undefined behavior with mismatched allocators

Examples

1. Use auto range-for

for (const auto& x : v) cout << x;

2. Reserve capacity

v.reserve(n);

3. Prefer algorithms

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

4. Use emplace

v.emplace_back(42);

5. Bad: C-style loop index errors

for (int i=0; i<=v.size(); ++i) {}

6. Bad: invalidate iterators

v.push_back(1); // it may be invalid

Frequently asked questions

When should I use vector vs list?

vector default for sequential data—cache friendly; list for frequent middle inserts (rare in practice).

What is iterator invalidation?

Certain operations (resize, erase) invalidate iterators—do not use stale iterators afterward.

Is map always a tree?

std::map is ordered tree; std::unordered_map is hash table with average O(1) lookup.