STL in C++ Complete Reference Guide

Master the Standard Template Library - Containers, Iterators, Algorithms, and Functors

Table of Contents

• Introduction to STL
• STL Components
• Containers
• Iterators
• Algorithms
• Functors
• Common Operations
• Best Practices

Introduction to STL

The Standard Template Library (STL) is a powerful set of C++ template classes that provide common data structures and algorithms. It's part of the C++ standard library and is widely used in competitive programming and software development.

Why Use STL?

• Reusability: Pre-written, tested, and optimized code
• Efficiency: Highly optimized implementations
• Type Safety: Template-based, compile-time type checking
• Time Saving: No need to implement common data structures
• Standardization: Consistent interface across containers

Key Concept: STL is based on generic programming using templates, making it type-safe and efficient. All STL components are in the std namespace.

STL Components

STL consists of four main components:

1. Containers

Data structures that store objects. Examples: vector, list, map, set

2. Iterators

Objects that point to elements in containers. Examples: begin(), end(), iterator types

3. Algorithms

Functions that operate on containers. Examples: sort(), find(), count()

4. Functors

Function objects that can be used with algorithms. Examples: less, greater, custom comparators

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

int main() {
    // Container: vector
    vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // Algorithm: sort
    sort(vec.begin(), vec.end());
    
    // Iterator: to access elements
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        cout << *it << " ";
    }
    
    return 0;
}

Containers

Containers are divided into three categories: Sequence, Associative, and Unordered Associative containers.

Sequence Containers

Store elements in a linear sequence.

1. vector

Dynamic array with random access. Best for: Frequent access, adding/removing at end.

#include <vector>
using namespace std;

vector<int> v;
v.push_back(10);      // Add element
v.push_back(20);
v.push_back(30);

cout << v[0] << endl;        // Access: 10
cout << v.size() << endl;    // Size: 3
v.pop_back();                // Remove last element

// Iteration
for (int x : v) {
    cout << x << " ";
}

Time Complexity: O(1) for access, O(1) amortized for push_back, O(n) for insertion in middle

2. list

Doubly linked list. Best for: Frequent insertion/deletion at any position.

#include <list>
using namespace std;

list<int> l;
l.push_back(10);
l.push_front(5);
l.insert(l.begin(), 1);  // Insert at beginning

l.remove(10);  // Remove all occurrences of 10
l.sort();      // Sort the list

Time Complexity: O(1) for insertion/deletion, O(n) for access

3. deque

Double-ended queue. Best for: Adding/removing at both ends.

#include <deque>
using namespace std;

deque<int> dq;
dq.push_back(10);
dq.push_front(5);
dq.pop_back();
dq.pop_front();

Associative Containers

Store elements in sorted order. Implemented as balanced binary search trees.

4. set

Collection of unique elements, sorted. Best for: Maintaining unique sorted elements.

#include <set>
using namespace std;

set<int> s;
s.insert(30);
s.insert(10);
s.insert(20);
s.insert(10);  // Duplicate ignored

// Elements are automatically sorted: 10, 20, 30
for (int x : s) {
    cout << x << " ";
}

s.find(20);    // Returns iterator
s.erase(10);   // Remove element

Time Complexity: O(log n) for insert, find, erase

5. map

Key-value pairs, sorted by key. Best for: Dictionary-like structures.

#include <map>
using namespace std;

map<string, int> m;
m["apple"] = 5;
m["banana"] = 3;
m["cherry"] = 8;

cout << m["apple"] << endl;  // Access: 5

// Iteration
for (auto& pair : m) {
    cout << pair.first << ": " << pair.second << endl;
}

m.find("banana");  // Returns iterator
m.erase("apple");  // Remove by key

Time Complexity: O(log n) for insert, find, erase

6. multiset and multimap

Similar to set and map but allow duplicate keys.

Unordered Associative Containers (C++11)

Hash table-based containers. Faster access but unordered.

7. unordered_set

#include <unordered_set>
using namespace std;

unordered_set<int> us;
us.insert(10);
us.insert(20);
us.insert(30);

us.find(20);  // O(1) average case

Time Complexity: O(1) average, O(n) worst case

8. unordered_map

#include <unordered_map>
using namespace std;

unordered_map<string, int> um;
um["one"] = 1;
um["two"] = 2;

cout << um["one"] << endl;  // O(1) access

Container Adapters

Special containers that provide restricted interfaces.

9. stack

#include <stack>
using namespace std;

stack<int> st;
st.push(10);
st.push(20);
st.push(30);

cout << st.top() << endl;  // 30
st.pop();  // Remove top

10. queue

#include <queue>
using namespace std;

queue<int> q;
q.push(10);
q.push(20);
q.push(30);

cout << q.front() << endl;  // 10
q.pop();  // Remove front

11. priority_queue

#include <queue>
using namespace std;

priority_queue<int> pq;  // Max heap by default
pq.push(30);
pq.push(10);
pq.push(20);

cout << pq.top() << endl;  // 30 (largest)
pq.pop();

Container Comparison

Container	Access	Insert	Delete	Ordered
vector	O(1)	O(n)	O(n)	Yes
list	O(n)	O(1)	O(1)	Yes
set	O(log n)	O(log n)	O(log n)	Yes
map	O(log n)	O(log n)	O(log n)	Yes
unordered_set	O(1)	O(1)	O(1)	No
unordered_map	O(1)	O(1)	O(1)	No

Iterators

Iterators are objects that point to elements in containers. They provide a way to access container elements.

Types of Iterators

1. Input Iterator: Read-only, forward only
2. Output Iterator: Write-only, forward only
3. Forward Iterator: Read/write, forward only
4. Bidirectional Iterator: Can move backward (list, set, map)
5. Random Access Iterator: Can jump to any position (vector, deque)

Iterator Operations

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

vector<int> vec = {1, 2, 3, 4, 5};

// Iterator declaration
vector<int>::iterator it;

// Begin and end
it = vec.begin();  // Points to first element
it = vec.end();   // Points past last element

// Dereferencing
cout << *it << endl;  // Access element

// Increment
++it;  // Move to next element
it++;  // Also valid

// Comparison
if (it != vec.end()) {
    // Safe to dereference
}

// Range-based for loop (C++11)
for (auto& element : vec) {
    cout << element << " ";
}

// Traditional iteration
for (auto it = vec.begin(); it != vec.end(); ++it) {
    cout << *it << " ";
}

Reverse Iterators

vector<int> vec = {1, 2, 3, 4, 5};

// Reverse iteration
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
    cout << *it << " ";  // Output: 5 4 3 2 1
}

Algorithms

STL provides many algorithms in the <algorithm> header that work with containers.

Sorting Algorithms

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

vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};

// Sort in ascending order
sort(vec.begin(), vec.end());

// Sort in descending order
sort(vec.begin(), vec.end(), greater<int>());

// Partial sort (first 3 elements)
partial_sort(vec.begin(), vec.begin() + 3, vec.end());

// Check if sorted
bool isSorted = is_sorted(vec.begin(), vec.end());

Searching Algorithms

vector<int> vec = {1, 2, 3, 4, 5};

// Binary search (requires sorted container)
bool found = binary_search(vec.begin(), vec.end(), 3);

// Find element
auto it = find(vec.begin(), vec.end(), 3);
if (it != vec.end()) {
    cout << "Found at position: " << distance(vec.begin(), it) << endl;
}

// Count occurrences
int count = count(vec.begin(), vec.end(), 3);

// Lower bound (first element >= value)
auto lb = lower_bound(vec.begin(), vec.end(), 3);

// Upper bound (first element > value)
auto ub = upper_bound(vec.begin(), vec.end(), 3);

Modifying Algorithms

vector<int> vec = {1, 2, 3, 4, 5};

// Reverse
reverse(vec.begin(), vec.end());

// Rotate
rotate(vec.begin(), vec.begin() + 2, vec.end());

// Fill
fill(vec.begin(), vec.end(), 0);

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

// Remove duplicates (requires sorted)
unique(vec.begin(), vec.end());

Other Useful Algorithms

vector<int> vec = {1, 2, 3, 4, 5};

// Min/Max
int minVal = *min_element(vec.begin(), vec.end());
int maxVal = *max_element(vec.begin(), vec.end());

// Accumulate (sum)
#include <numeric>
int sum = accumulate(vec.begin(), vec.end(), 0);

// All of, Any of, None of (C++11)
bool allPositive = all_of(vec.begin(), vec.end(), 
                          [](int x) { return x > 0; });

// Swap
swap(vec[0], vec[1]);

// Next permutation
next_permutation(vec.begin(), vec.end());

Functors

Functors (function objects) are objects that can be called like functions. They're often used with algorithms.

Built-in Functors

#include <functional>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> vec = {3, 1, 4, 1, 5};

// Sort in descending order
sort(vec.begin(), vec.end(), greater<int>());

// Other functors
plus<int> add;
int result = add(5, 3);  // 8

multiplies<int> multiply;
result = multiply(4, 5);  // 20

Custom Functors

// Custom comparator
struct Compare {
    bool operator()(int a, int b) {
        return a > b;  // Sort descending
    }
};

vector<int> vec = {3, 1, 4, 1, 5};
sort(vec.begin(), vec.end(), Compare());

// Lambda expressions (C++11) - more convenient
sort(vec.begin(), vec.end(), [](int a, int b) {
    return a > b;
});

Common Operations

Complete Example: Using Multiple STL Components

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
using namespace std;

int main() {
    // Vector operations
    vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
    sort(vec.begin(), vec.end());
    
    // Remove duplicates
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    
    // Map for frequency counting
    map<int, int> freq;
    for (int x : vec) {
        freq[x]++;
    }
    
    // Set for unique elements
    set<int> uniqueSet(vec.begin(), vec.end());
    
    // Display results
    cout << "Sorted unique elements: ";
    for (int x : vec) {
        cout << x << " ";
    }
    
    return 0;
}

Best Practices

STL Best Practices

• Choose the right container: Use vector for random access, list for frequent insertions, map for key-value pairs
• Use auto keyword: Let compiler deduce iterator types (C++11)
• Prefer algorithms over loops: Use STL algorithms for better readability and performance
• Reserve space: Use reserve() for vectors when size is known
• Use const iterators: When you don't need to modify elements
• Avoid iterator invalidation: Don't modify containers while iterating
• Use emplace_back: Instead of push_back for better performance (C++11)
• Understand complexity: Know time complexity of operations

Common Mistakes

• Using wrong container for the task
• Iterator invalidation after container modification
• Not checking iterator validity before dereferencing
• Using algorithms on unsorted containers when sorted required
• Forgetting to include necessary headers

Performance Tips

// Good: Reserve space
vector<int> vec;
vec.reserve(1000);  // Avoids reallocations

// Good: Use emplace_back
vec.emplace_back(10);  // More efficient than push_back

// Good: Use const reference in range-based loops
for (const auto& element : vec) {
    // Read-only access
}

// Good: Use algorithms
sort(vec.begin(), vec.end());  // Optimized implementation

• Whatsapp
• Tweet
• Share
• Share
• Share

Sign up here with your email