C++ STL Cheat Sheet

#include <vector>#include <map>#include <unordered_map>#include <set>std::vector<int> v = {1, 2, 3};v.push_back(4);                    // O(1) amortizedv.pop_back();                      // O(1)std::map<std::string, int> m;      // sorted, red-black tree, O(log n) opsm["apple"] = 3;m.insert({"banana", 5});std::unordered_map<std::string, int> um;  // hash table, O(1) avg opsum["cherry"] = 7;std::set<int> s = {3, 1, 2};       // sorted, unique elementss.insert(4);

#include <algorithm>#include <numeric>std::vector<int> v = {5, 3, 1, 4, 2};std::sort(v.begin(), v.end());                       // ascending sortstd::sort(v.begin(), v.end(), std::greater<int>());  // descending sortauto it = std::find(v.begin(), v.end(), 3);            // linear searchbool has4 = std::binary_search(v.begin(), v.end(), 4);  // requires sorted rangeint sum = std::accumulate(v.begin(), v.end(), 0);auto max_it = std::max_element(v.begin(), v.end());v.erase(std::remove(v.begin(), v.end(), 3), v.end()); // erase-remove idiom

std::vector<int> v = {1, 2, 3, 4, 5};std::for_each(v.begin(), v.end(), [](int n) { std::cout << n << " "; });int threshold = 3;auto count = std::count_if(v.begin(), v.end(),        [threshold](int n) { return n > threshold; });   // capture by valuestd::transform(v.begin(), v.end(), v.begin(),        [](int n) { return n * n; });                    // square each elementstd::sort(v.begin(), v.end(),        [](int a, int b) { return a > b; });              // custom comparator

std::vector<int> v = {1, 2, 3, 4, 5};// vector: push_back may reallocate -> ALL iterators/pointers/refs invalidatedauto it = v.begin();v.push_back(6);        // it may now be dangling if capacity was exceeded// erase invalidates the erased iterator and everything after itfor (auto it2 = v.begin(); it2 != v.end(); ) {    if (*it2 % 2 == 0) it2 = v.erase(it2);   // erase returns the next valid iterator    else ++it2;}// std::map/std::set: insert/erase invalidate only iterators to erased elements// (unlike vector, other iterators remain valid - node-based container)std::map<int, int> m = {{1, 1}, {2, 2}};auto mit = m.find(1);m.erase(2);             // mit is still valid, m.find(2) result would not be// deque: insert/erase at ends preserve iterators to other elements but// invalidate all iterators on insert/erase in the middle

struct Point { int x, y; };// Ordered container: provide operator< or a comparatorstruct PointCmp {    bool operator()(const Point& a, const Point& b) const {        return std::tie(a.x, a.y) < std::tie(b.x, b.y);   // lexicographic    }};std::set<Point, PointCmp> orderedPoints;// Unordered container: needs both hash and equalitystruct PointHash {    std::size_t operator()(const Point& p) const {        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);    }};struct PointEq {    bool operator()(const Point& a, const Point& b) const {        return a.x == b.x && a.y == b.y;    }};std::unordered_set<Point, PointHash, PointEq> pointSet;// Lambda comparator for a priority_queue (min-heap instead of default max-heap)auto cmp = [](int a, int b) { return a > b; };std::priority_queue<int, std::vector<int>, decltype(cmp)> minHeap(cmp);

struct Widget {    std::string name;    Widget(std::string n) : name(std::move(n)) {}};std::vector<Widget> widgets;// push_back(Widget(...)) constructs a temporary then moves/copies it inwidgets.push_back(Widget("gear"));// emplace_back constructs the element in place - no temporary, no movewidgets.emplace_back("bolt");        // forwards args directly to Widget's ctorstd::map<std::string, Widget> catalog;catalog.emplace("g1", "gear");        // in-place construction of both key and value// Moving an entire container transfers ownership of its internal buffer, O(1)std::vector<Widget> moved = std::move(widgets);// widgets is now valid but unspecified (typically empty) - do not rely on its contents

#include <span>#include <string_view>// string_view: non-owning view over character data, no allocationvoid printName(std::string_view name) {   // accepts std::string, const char*, literals    std::cout << name.substr(0, 3) << "\n";  // substr on a view is O(1), no copy}// span (C++20): non-owning view over any contiguous sequencevoid sumAll(std::span<const int> data) {    int total = std::accumulate(data.begin(), data.end(), 0);}int arr[] = {1, 2, 3};std::vector<int> vec = {4, 5, 6};sumAll(arr);   // works for C arrayssumAll(vec);   // and vectors, without copying either// Caution: both are non-owning - never return a view of a local temporary