STL Skill

Production-Grade Learning Skill | Standard Template Library

Master C++ containers, algorithms, and iterators for efficient programming.

Container Selection Guide

Decision Flowchart

Need to store data?
│
├── Need key-value pairs?
│   ├── Need ordering? → std::map
│   └── Need fast lookup? → std::unordered_map
│
├── Need unique elements only?
│   ├── Need ordering? → std::set
│   └── Need fast lookup? → std::unordered_set
│
└── Need sequence?
    ├── Need random access?
    │   ├── Size changes often? → std::vector (default)
    │   └── Fixed size? → std::array
    ├── Need fast insert at both ends? → std::deque
    └── Need fast insert in middle? → std::list

Complexity Reference

*amortized **at ends

Containers

std::vector (Default Choice)

cpp
1#include <vector>
2
3std::vector<int> v;
4
5// Initialization
6std::vector<int> v1 = {1, 2, 3, 4, 5};
7std::vector<int> v2(10, 0);  // 10 zeros
8std::vector<int> v3(v1.begin(), v1.end());  // Copy
9
10// Modification
11v.push_back(6);           // Add to end
12v.emplace_back(7);        // Construct in place (prefer)
13v.pop_back();             // Remove last
14v.insert(v.begin(), 0);   // Insert at position
15v.erase(v.begin() + 2);   // Remove at position
16
17// Best practices
18v.reserve(100);           // Pre-allocate (avoid reallocations)
19v.shrink_to_fit();        // Release unused memory

std::map / std::unordered_map

cpp
1#include <map>
2#include <unordered_map>
3
4// Ordered map (red-black tree)
5std::map<std::string, int> scores;
6scores["Alice"] = 95;
7scores["Bob"] = 87;
8
9// Unordered map (hash table) - faster lookup
10std::unordered_map<std::string, int> cache;
11cache["key1"] = 100;
12
13// Safe access
14if (auto it = scores.find("Alice"); it != scores.end()) {
15    std::cout << it->second << "\n";
16}
17
18// C++17 structured bindings
19for (const auto& [name, score] : scores) {
20    std::cout << name << ": " << score << "\n";
21}
22
23// Insert or update (C++17)
24scores.insert_or_assign("Charlie", 90);
25
26// Insert if not exists
27scores.try_emplace("Dave", 85);

Algorithms

Non-Modifying

cpp
1#include <algorithm>
2#include <numeric>
3
4std::vector<int> v = {1, 2, 3, 4, 5};
5
6// Find
7auto it = std::find(v.begin(), v.end(), 3);
8auto it2 = std::find_if(v.begin(), v.end(), [](int n) { return n > 3; });
9
10// Count
11size_t count = std::count_if(v.begin(), v.end(), [](int n) { return n % 2 == 0; });
12
13// All/Any/None
14bool allPos = std::all_of(v.begin(), v.end(), [](int n) { return n > 0; });
15bool anyNeg = std::any_of(v.begin(), v.end(), [](int n) { return n < 0; });
16
17// Accumulate
18int sum = std::accumulate(v.begin(), v.end(), 0);
19int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<>());

Modifying

cpp
1// Transform
2std::transform(v.begin(), v.end(), v.begin(), [](int n) { return n * 2; });
3
4// Sort
5std::sort(v.begin(), v.end());  // Ascending
6std::sort(v.begin(), v.end(), std::greater<>());  // Descending
7
8// Stable sort (preserves relative order of equal elements)
9std::stable_sort(v.begin(), v.end());
10
11// Remove (erase-remove idiom)
12v.erase(std::remove_if(v.begin(), v.end(), [](int n) { return n < 0; }), v.end());
13
14// C++20: std::erase_if (much cleaner)
15std::erase_if(v, [](int n) { return n < 0; });
16
17// Unique (remove consecutive duplicates)
18v.erase(std::unique(v.begin(), v.end()), v.end());

Binary Search (Sorted Containers)

cpp
1std::vector<int> sorted = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
2
3// Check if exists
4bool found = std::binary_search(sorted.begin(), sorted.end(), 5);
5
6// Find position
7auto lower = std::lower_bound(sorted.begin(), sorted.end(), 5);  // First >= 5
8auto upper = std::upper_bound(sorted.begin(), sorted.end(), 5);  // First > 5
9auto range = std::equal_range(sorted.begin(), sorted.end(), 5);  // Both

C++20 Ranges

cpp
1#include <ranges>
2namespace rv = std::views;
3
4std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
5
6// Lazy pipeline (no intermediate allocations)
7auto result = data
8    | rv::filter([](int n) { return n % 2 == 0; })  // Keep evens
9    | rv::transform([](int n) { return n * n; })   // Square
10    | rv::take(3);                                  // First 3
11
12// Materialize when needed
13std::vector<int> squares(result.begin(), result.end());
14// squares = {4, 16, 36}
15
16// Range algorithms
17std::ranges::sort(data);
18auto it = std::ranges::find(data, 5);

Troubleshooting

Iterator Invalidation

Safe Patterns

cpp
1// ❌ BAD: Iterator invalidation
2for (auto it = v.begin(); it != v.end(); ++it) {
3    if (*it < 0) v.erase(it);  // Invalidates it!
4}
5
6// ✅ GOOD: Return new iterator
7for (auto it = v.begin(); it != v.end(); ) {
8    if (*it < 0) {
9        it = v.erase(it);  // erase returns next valid iterator
10    } else {
11        ++it;
12    }
13}
14
15// ✅ BETTER: Use algorithm
16std::erase_if(v, [](int n) { return n < 0; });

Unit Test Template

cpp
1#include <gtest/gtest.h>
2
3TEST(STLTest, VectorOperations) {
4    std::vector<int> v = {1, 2, 3};
5
6    v.push_back(4);
7    EXPECT_EQ(v.size(), 4);
8    EXPECT_EQ(v.back(), 4);
9
10    v.pop_back();
11    EXPECT_EQ(v.size(), 3);
12}
13
14TEST(STLTest, MapOperations) {
15    std::map<std::string, int> m;
16    m["a"] = 1;
17    m["b"] = 2;
18
19    EXPECT_EQ(m["a"], 1);
20    EXPECT_TRUE(m.contains("b"));  // C++20
21}
22
23TEST(STLTest, Algorithms) {
24    std::vector<int> v = {3, 1, 4, 1, 5, 9};
25
26    std::sort(v.begin(), v.end());
27    EXPECT_TRUE(std::is_sorted(v.begin(), v.end()));
28
29    auto it = std::find(v.begin(), v.end(), 5);
30    EXPECT_NE(it, v.end());
31}

C++ Plugin v3.0.0 - Production-Grade Learning Skill