10 STL Containers & Iterators

Overview: Data Structure Abstractions

The C++ Standard Template Library (STL) provides container templates. Understanding how they manage memory and compile-time comparators is key to writing high-performance code.

---

1. Sequence Containers: std::vector Allocation Mechanics

std::vector represents a contiguous, dynamic array on the heap.

std::vector<int> vec;
vec.push_back(10);

Memory Reallocation Mechanics:

• Contiguous Memory: Elements are stored side-by-side in memory. This enables $O(1)$ random access (vec[i]) and cache-friendly iteration.
• Capacity vs. Size: Size is the number of active elements. Capacity is the total allocated buffer size.
• The Reallocation Step: When size exceeds capacity, the vector:
  1. Allocates a new, larger memory block (usually 1.5x or 2x the old capacity).
  2. Copies or moves existing elements from the old block to the new block.
  3. Destructs the old elements and deallocates the old memory block. This reallocation step is costly ($O(N)$), but amortized over time, adding elements remains $O(1)$. Use vec.reserve(size) to pre-allocate memory and avoid this overhead.

---

2. Ordered vs. Unordered Associative Containers

Feature	Ordered Containers (std::set / std::map)	Unordered Containers (std::unordered_set / std::unordered_map)
Underlying Structure	Self-balancing Red-Black Tree	Hash Table (bucket arrays)
Element Order	Maintained in sorted order of keys.	Arbitrary/Unsorted.
Time Complexity	$O(\log N)$ for search, insert, and delete.	$O(1)$ average; $O(N)$ worst-case.
Iterator Capabilities	Bi-directional traversal.	Forward-only traversal.
Key Requirement	Requires Comparison operator (<).	Requires Hash function & Equality operator (==).

---

3. Iterators and Sentinel Bounds

Iterators act as pointers to traverse STL containers.

• begin(): Points to the first element in the container.
• end(): Points to the sentinel element just past the last element (used to detect loop termination).

[ Element 1 ] -> [ Element 2 ] -> [ Element 3 ] -> [ Sentinel/Past-the-end ]
      ^                                                  ^
   begin()                                             end()

---

4. Custom Object Comparators

When using custom objects as keys in a std::map or std::set, the container must know how to sort them. You can implement this by:

1. Overloading operator< within the custom class.
2. Providing a comparator functor (a struct with an overloaded operator()).

---

💻 Conceptual Code Demonstration

#include <iostream>
#include <vector>
#include <map>
 
struct Student {
    int id;
    std::string name;
    
    Student(int i, const std::string& n) : id(i), name(n) {}
};
 
// Custom Comparator Functor
struct CompareStudentID {
    bool operator()(const Student& lhs, const Student& rhs) const {
        return lhs.id < rhs.id; // Sorted in ascending order of ID
    }
};
 
int main() {
    // 1. Vector capacity optimization
    std::vector<int> numbers;
    numbers.reserve(100); // Pre-allocates buffer for 100 elements to avoid reallocations
    
    // 2. Map with Custom Object keys and custom comparator
    std::map<Student, double, CompareStudentID> gradebook;
    
    gradebook.insert({Student(101, "Alice"), 94.5});
    gradebook.insert({Student(102, "Bob"), 88.0});
    
    // 3. Iterating using STL Iterators
    std::map<Student, double, CompareStudentID>::iterator it;
    for (it = gradebook.begin(); it != gradebook.end(); ++it) {
        std::cout << "ID: " << it->first.id 
                  << " | Name: " << it->first.name 
                  << " | Grade: " << it->second << '\n';
    }
    
    return 0;
}