C++ Standard Library Skill

Container Selection Guide

Need sequential access + fast random access?
  → vector (default choice for sequences)

Need fast insert/delete at both ends?
  → deque

Need fast insert/delete anywhere + stable iterators?
  → list (doubly linked) or forward_list (singly linked)

Need sorted unique keys with O(log n) lookup?
  → set / map

Need sorted non-unique keys?
  → multiset / multimap

Need O(1) average lookup, no ordering?
  → unordered_set / unordered_map

Need LIFO?
  → stack (adapter over deque/vector)

Need FIFO?
  → queue (adapter over deque)

Need priority queue (always extract min/max)?
  → priority_queue (adapter over vector with heap)

Container Complexity Summary

Container	Access	Insert Front	Insert Back	Insert Middle	Find
vector	O(1)	O(n)	O(1) amort	O(n)	O(n)
deque	O(1)	O(1) amort	O(1) amort	O(n)	O(n)
list	O(n)	O(1)	O(1)	O(1)	O(n)
set/map	O(log n)	—	—	O(log n)	O(log n)
unordered	O(1) avg	—	—	O(1) avg	O(1) avg

---

Iterators

Iterator Categories

Input Iterator → forward only, read once
Output Iterator → forward only, write once
Forward Iterator → forward, multiple passes
Bidirectional Iterator → forward + backward (list, set, map)
Random Access Iterator → + arithmetic (vector, deque, array)

Key invariant: never use an iterator after the container is modified (invalidation rules vary by container).

Common Patterns

// Range-based for (C++11)
for (auto& elem : container) { ... }

// Algorithm with iterator range
std::sort(v.begin(), v.end());
std::find(v.begin(), v.end(), value);
std::copy(src.begin(), src.end(), std::back_inserter(dst));

// Reverse iteration
for (auto it = c.rbegin(); it != c.rend(); ++it) { ... }

---

STL Algorithms

Non-Modifying

std::find(first, last, value)            // linear search
std::find_if(first, last, pred)          // search with predicate
std::count(first, last, value)           // count occurrences
std::all_of/any_of/none_of(first, last, pred)
std::for_each(first, last, func)
std::equal(first1, last1, first2)
std::mismatch(first1, last1, first2)     // first differing pair

Modifying

std::copy(first, last, dest)
std::move(first, last, dest)
std::transform(first, last, dest, func)
std::replace(first, last, old, new)
std::fill(first, last, value)
std::generate(first, last, gen)
std::remove(first, last, value)          // doesn't resize! Returns new end.
// Always pair with erase: v.erase(std::remove(v.begin(), v.end(), val), v.end());

Sorting

std::sort(first, last)                   // unstable, O(n log n)
std::stable_sort(first, last)            // stable, O(n log² n)
std::partial_sort(first, middle, last)   // sort first k elements
std::nth_element(first, nth, last)       // k-th element + partition
std::is_sorted(first, last)

Searching (Sorted Ranges)

std::binary_search(first, last, value)  // bool
std::lower_bound(first, last, value)    // first >= value
std::upper_bound(first, last, value)    // first > value
std::equal_range(first, last, value)    // [lower, upper) pair

Set Operations (on sorted ranges)

std::set_union, set_intersection, set_difference
std::merge(first1, last1, first2, last2, dest)

Numeric

std::accumulate(first, last, init)          // sum
std::accumulate(first, last, init, op)      // with custom op (product, etc.)
std::inner_product(first1, last1, first2, init)
std::partial_sum(first, last, dest)
std::adjacent_difference(first, last, dest)

---

Move Semantics (C++11)

Core Concept

Move semantics allow transfer of resources instead of copying — O(1) for string/vector moves.

std::string s1 = "hello";
std::string s2 = std::move(s1); // s1 now empty, s2 owns the resource

Rules

• std::move() casts to rvalue reference; doesn’t actually move
• After move, source is in valid-but-unspecified state
• Prefer move over copy when you no longer need the source
• Containers automatically use move when elements are move-constructible

Perfect Forwarding

template<typename T>
void wrapper(T&& arg) {
    target(std::forward<T>(arg)); // preserves value category
}

---

Lambda Expressions (C++11)

// Capture modes
[=]         // capture all by value
[&]         // capture all by reference
[x, &y]     // x by value, y by reference
[this]      // capture this pointer

// Lambda as comparator
auto cmp = [](const auto& a, const auto& b) { return a.key < b.key; };
std::sort(v.begin(), v.end(), cmp);

// Lambda with mutable (modify captured-by-value)
int count = 0;
auto inc = [count]() mutable { return ++count; };

---

Smart Pointers

// Exclusive ownership
std::unique_ptr<T> p = std::make_unique<T>(args...);
// auto p = std::make_unique<T>(); // prefer make_unique

// Shared ownership
std::shared_ptr<T> p = std::make_shared<T>(args...);
std::shared_ptr<T> p2 = p; // reference count incremented

// Non-owning observer
std::weak_ptr<T> wp = sp;
if (auto locked = wp.lock()) { /* use locked */ }

Rule: use unique_ptr by default; use shared_ptr only when multiple owners needed; never use raw new/delete.

---

String Operations

std::string s = "hello world";
s.find("world")             // position or string::npos
s.substr(pos, len)          // substring
s.replace(pos, len, "new")  // replace portion
s.compare(other)            // 0 if equal
std::to_string(42)          // number to string
std::stoi("42")             // string to int
std::stod("3.14")           // string to double

// C++17 string_view (non-owning)
std::string_view sv = "hello"; // no copy

---

Exception Handling

// Standard exception hierarchy
std::exception
  std::logic_error → std::invalid_argument, std::out_of_range, std::domain_error
  std::runtime_error → std::overflow_error, std::underflow_error

// Throw by value, catch by reference
try { throw std::runtime_error("message"); }
catch (const std::exception& e) { std::cerr << e.what(); }

// noexcept specification
void f() noexcept;    // guarantees no exceptions

---

Functional Objects and Adaptors

// Standard function objects
std::less<T>, std::greater<T>, std::equal_to<T>
std::plus<T>, std::minus<T>, std::multiplies<T>
std::logical_and<T>, std::logical_not<T>

// Function wrappers
std::function<int(int, int)> f = [](int a, int b) { return a + b; };
auto bound = std::bind(func, _1, 42); // partially apply