CodeWithAbdessamad

Stl Containers

STL Containers

In C++, the Standard Template Library (STL) provides a powerful collection of reusable data structures that form the backbone of efficient and flexible programming. Unlike raw arrays, STL containers offer dynamic sizing, automatic memory management, and optimized performance for common operations. Understanding these containers is essential for writing scalable, maintainable code. In this section, we’ll dive deep into four foundational STL containers: vector, list, map, and set. Each container solves specific problems with unique trade-offs—let’s explore them one by one.

Vector

The std::vector is a dynamic array that provides contiguous memory allocation with constant-time access and amortized constant-time insertion/deletion at the end. It’s ideal for scenarios requiring fast random access and efficient memory usage.

<code class="language-cpp">#include <vector>
<p>#include <iostream></p>

<p>int main() {</p>
<p>    std::vector<int> numbers = {1, 3, 5, 7};</p>
<p>    </p>
<p>    // Access elements by index</p>
<p>    std::cout << "First element: " << numbers[0] << '\n';</p>
<p>    </p>
<p>    // Add elements at the end (amortized O(1))</p>
<p>    numbers.push_back(9);</p>
<p>    std::cout << "After push: " << numbers.size() << " elements\n";</p>
<p>    </p>
<p>    // Remove last element (amortized O(1))</p>
<p>    numbers.pop_back();</p>
<p>    std::cout << "After pop: " << numbers.size() << " elements\n";</p>
<p>    </p>
<p>    // Iterate with range-based for loop</p>
<p>    for (int num : numbers) {</p>
<p>        std::cout << num << " ";</p>
<p>    }</p>
<p>    std::cout << '\n';</p>
<p>    </p>
<p>    return 0;</p>
<p>}</code>

Key features of vector:

  • Random access: O(1) time for operator[]
  • Resizing: Automatically allocates new memory when capacity is exceeded (amortized O(1))
  • Memory efficiency: Contiguous memory reduces cache misses
  • No pointer arithmetic: Simplifies code compared to raw arrays

When to use vector:

  • Storing sequences where you need fast indexing
  • Dynamic collections that grow/shrink predictably
  • Situations where memory locality matters (e.g., performance-critical code)

Example use case: Storing a list of user IDs in a web application where rapid random access is required.

List

std::list is a doubly linked list that provides efficient insertion and deletion at any position (O(1) for middle operations) but lacks random access. It’s perfect for scenarios where frequent modifications are needed without worrying about memory overhead.

<code class="language-cpp">#include <list>
<p>#include <iostream></p>

<p>int main() {</p>
<p>    std::list<int> numbers = {1, 3, 5, 7};</p>
<p>    </p>
<p>    // Insert at beginning (O(1))</p>
<p>    numbers.push_front(0);</p>
<p>    </p>
<p>    // Insert at end (O(1))</p>
<p>    numbers.push_back(9);</p>
<p>    </p>
<p>    // Iterate with iterator</p>
<p>    for (auto it = numbers.begin(); it != numbers.end(); ++it) {</p>
<p>        std::cout << *it << " ";</p>
<p>    }</p>
<p>    std::cout << '\n';</p>
<p>    </p>
<p>    // Remove middle element (O(1))</p>
<p>    auto it = numbers.begin();</p>
<p>    std::advance(it, 2); // Move to third element</p>
<p>    numbers.erase(it);</p>
<p>    </p>
<p>    return 0;</p>
<p>}</code>

Key features of list:

  • Bidirectional traversal: O(n) for random access
  • Efficient modifications: O(1) for insertions/deletions at any position
  • Memory usage: Higher overhead per element (pointers for links)
  • No contiguous memory: Avoids cache thrashing during frequent changes

When to use list:

  • Collections requiring frequent insertions/deletions in the middle
  • Scenarios where memory efficiency isn’t critical but speed of modification matters
  • Implementing algorithms like in-order traversal or stacks with dynamic size

Example use case: Maintaining a priority queue where elements are frequently reordered (e.g., task scheduling in a real-time system).

Map

std::map is a balanced binary search tree (red-black tree) that stores key-value pairs with O(log n) access, insertion, and deletion times. It guarantees sorted order by key and is ideal for associative lookups.

<code class="language-cpp">#include <map>
<p>#include <iostream></p>

<p>int main() {</p>
<p>    std::map<int, std::string> phoneBook = {</p>
<p>        {1, "Alice"},</p>
<p>        {3, "Bob"},</p>
<p>        {5, "Charlie"}</p>
<p>    };</p>
<p>    </p>
<p>    // Insert new pair (O(log n))</p>
<p>    phoneBook[7] = "Diana";</p>
<p>    </p>
<p>    // Find by key (O(log n))</p>
<p>    auto it = phoneBook.find(3);</p>
<p>    if (it != phoneBook.end()) {</p>
<p>        std::cout << "Found: " << it->second << '\n';</p>
<p>    }</p>
<p>    </p>
<p>    // Iterate in sorted order</p>
<p>    for (const auto& pair : phoneBook) {</p>
<p>        std::cout << pair.first << " -> " << pair.second << '\n';</p>
<p>    }</p>
<p>    </p>
<p>    return 0;</p>
<p>}</code>

Key features of map:

  • Sorted order: Keys are always ordered (ascending)
  • Unique keys: No duplicate keys allowed
  • Efficient lookups: O(log n) for all operations
  • Key comparisons: Uses std::less by default (can be customized)

When to use map:

  • Storing key-value pairs that need to be sorted (e.g., dictionaries)
  • Implementing fast lookups where keys are meaningful (e.g., user IDs, product codes)
  • Situations requiring unique keys with guaranteed order

Example use case: Building a spell-checker where words are stored in sorted order for fast dictionary lookups.

Set

std::set is a balanced binary search tree (like map) but stores only keys (no values). It provides O(log n) operations and guarantees uniqueness and sorted order. It’s simpler than map when you only need keys.

<code class="language-cpp">#include <set>
<p>#include <iostream></p>

<p>int main() {</p>
<p>    std::set<int> numbers = {1, 3, 5, 7};</p>
<p>    </p>
<p>    // Insert (O(log n))</p>
<p>    numbers.insert(9);</p>
<p>    </p>
<p>    // Check existence (O(log n))</p>
<p>    if (numbers.find(3) != numbers.end()) {</p>
<p>        std::cout << "3 exists\n";</p>
<p>    }</p>
<p>    </p>
<p>    // Iterate in sorted order</p>
<p>    for (int num : numbers) {</p>
<p>        std::cout << num << " ";</p>
<p>    }</p>
<p>    std::cout << '\n';</p>
<p>    </p>
<p>    // Remove element (O(log n))</p>
<p>    numbers.erase(5);</p>
<p>    </p>
<p>    return 0;</p>
<p>}</code>

Key features of set:

  • Unique elements: No duplicates allowed
  • Sorted order: Keys are always in ascending order
  • No values: Only keys are stored (useful for sets of identifiers)
  • Efficient membership testing: O(log n) time

When to use set:

  • Storing unique identifiers (e.g., user IDs, resource handles)
  • Implementing sets where order matters but values aren’t needed
  • Scenarios requiring fast membership checks without extra storage

Example use case: Tracking active user sessions where session IDs must be unique and ordered.

Comparative Overview

Feature vector list map set
Underlying Structure Dynamic array Doubly linked list Red-black tree Red-black tree
Access Time O(1) (random) O(n) (traversal) O(log n) O(log n)
Insertion Time O(n) (end) / O(n) (middle) O(1) (any position) O(log n) O(log n)
Deletion Time O(n) (end) / O(n) (middle) O(1) (any position) O(log n) O(log n)
Memory Overhead Low (contiguous) High (pointers per element) Medium (node pointers + data) Medium (node pointers only)
Key Requirement None (values) None (values) Unique keys Unique keys
Sorted Order No No Yes (by key) Yes (by key)
Best Use Case Fast random access sequences Frequent middle modifications Sorted key-value lookups Unique key sets

💡 Pro Tip: Choose vector for fast indexing, list for frequent middle changes, map for sorted key-value pairs, and set for unique keys. Always prioritize your specific use case over theoretical performance.

Summary

In this section, we explored four essential STL containers:

  • vector excels at fast random access and contiguous memory usage.
  • list shines with efficient insertions/deletions anywhere in the sequence.
  • map provides sorted key-value pairs with O(log n) operations.
  • set is the ideal choice for unique, sorted keys without associated values.

Understanding these containers lets you write code that’s both efficient and maintainable—whether you’re building a web app, processing large datasets, or implementing complex algorithms. Remember: the right container solves the right problem. 🚀