强曰为道
与天地相似，故不违。知周乎万物，而道济天下，故不过。旁行而不流，乐天知命，故不忧.
文档目录

C/C++ Linux 开发教程（GCC + CMake） / 标准模板库（STL）

标准模板库（STL）

1. 序列容器

容器底层结构随机访问头部插入尾部插入迭代器失效
std::vector动态数组O(1)O(n)摊销 O(1)重分配时全部失效
std::deque分段数组O(1)O(1)O(1)插入/删除可能失效
std::list双向链表O(n)O(1)O(1)仅被删元素失效
std::forward_list单向链表O(n)O(1)O(1)仅被删元素失效
std::array固定数组O(1)❌❌从不失效
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <forward_list>
#include <array>

int main() {
    // vector — 动态数组，最常用
    std::vector<int> vec = {1, 2, 3};
    vec.push_back(4);
    vec.emplace_back(5);  // 原地构造，避免拷贝
    std::cout << "vector: ";
    for (auto v : vec) std::cout << v << " ";  // 1 2 3 4 5
    std::cout << "\n  size=" << vec.size()
              << ", capacity=" << vec.capacity() << "\n";

    // deque — 双端队列
    std::deque<int> dq = {2, 3, 4};
    dq.push_front(1);
    dq.push_back(5);
    std::cout << "deque: ";
    for (auto v : dq) std::cout << v << " ";  // 1 2 3 4 5
    std::cout << "\n";

    // list — 双向链表
    std::list<int> lst = {10, 20, 30};
    lst.push_front(5);
    lst.push_back(40);
    lst.sort();  // 链表自带排序
    std::cout << "list (sorted): ";
    for (auto v : lst) std::cout << v << " ";  // 5 10 20 30 40
    std::cout << "\n";

    // forward_list — 单向链表
    std::forward_list<int> fl = {3, 2, 1};
    fl.sort();
    std::cout << "forward_list: ";
    for (auto v : fl) std::cout << v << " ";  // 1 2 3
    std::cout << "\n";

    // array — 固定大小数组
    std::array<int, 5> arr = {5, 4, 3, 2, 1};
    std::sort(arr.begin(), arr.end());
    std::cout << "array: ";
    for (auto v : arr) std::cout << v << " ";  // 1 2 3 4 5
    std::cout << "\n";

    return 0;
}

vector 的内存管理

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;

    // 观察容量增长
    for (int i = 0; i < 20; ++i) {
        v.push_back(i);
        std::cout << "size=" << v.size()
                  << " capacity=" << v.capacity() << "\n";
    }

    // reserve — 预分配内存
    std::vector<int> v2;
    v2.reserve(100);  // 预分配 100 个元素的空间
    std::cout << "reserve 后: size=" << v2.size()
              << " capacity=" << v2.capacity() << "\n";

    // shrink_to_fit — 释放多余内存
    v2.resize(10);
    v2.shrink_to_fit();
    std::cout << "shrink 后: size=" << v2.size()
              << " capacity=" << v2.capacity() << "\n";

    return 0;
}

💡 提示：如果事先知道元素数量，使用 reserve() 预分配可以避免多次重分配和拷贝。

2. 关联容器

容器底层结构键唯一有序查找复杂度
std::set红黑树✅✅O(log n)
std::map红黑树✅✅O(log n)
std::multiset红黑树❌✅O(log n)
std::multimap红黑树❌✅O(log n)
#include <iostream>
#include <set>
#include <map>

int main() {
    // set — 唯一值集合
    std::set<int> s = {5, 3, 1, 4, 2, 3};  // 重复的 3 被忽略
    std::cout << "set: ";
    for (auto v : s) std::cout << v << " ";  // 1 2 3 4 5（自动排序）
    std::cout << "\n";

    s.insert(6);
    s.erase(3);
    std::cout << "set.find(4) 存在: " << std::boolalpha
              << (s.find(4) != s.end()) << "\n";

    // map — 键值对
    std::map<std::string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores["Charlie"] = 92;

    // 遍历
    for (const auto& [name, score] : scores) {  // 结构化绑定 (C++17)
        std::cout << name << ": " << score << "\n";
    }

    // 查找
    if (auto it = scores.find("Bob"); it != scores.end()) {
        std::cout << "Bob 的分数: " << it->second << "\n";
    }

    // multiset — 允许重复
    std::multiset<int> ms = {1, 2, 2, 3, 3, 3};
    std::cout << "count(2): " << ms.count(2) << "\n";  // 2
    std::cout << "count(3): " << ms.count(3) << "\n";  // 3

    // multimap — 允许重复键
    std::multimap<std::string, std::string> courses;
    courses.emplace("Alice", "Math");
    courses.emplace("Alice", "Physics");
    courses.emplace("Bob", "Math");

    auto [begin, end] = courses.equal_range("Alice");
    std::cout << "Alice 的课程:\n";
    for (auto it = begin; it != end; ++it) {
        std::cout << "  " << it->second << "\n";
    }

    return 0;
}

3. 无序容器

容器底层结构查找平均查找最差
std::unordered_set哈希表O(1)O(n)
std::unordered_map哈希表O(1)O(n)
std::unordered_multiset哈希表O(1)O(n)
std::unordered_multimap哈希表O(1)O(n)
#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> word_count;

    // 统计单词频率
    std::string words[] = {"hello", "world", "hello", "cpp", "world", "hello"};
    for (const auto& w : words) {
        word_count[w]++;
    }

    for (const auto& [word, count] : word_count) {
        std::cout << word << ": " << count << "\n";
    }

    // 自定义哈希函数
    struct Point {
        int x, y;
        bool operator==(const Point& o) const { return x == o.x && y == o.y; }
    };

    struct PointHash {
        size_t operator()(const Point& p) const {
            auto h1 = std::hash<int>{}(p.x);
            auto h2 = std::hash<int>{}(p.y);
            return h1 ^ (h2 << 1);
        }
    };

    std::unordered_map<Point, std::string, PointHash> pointNames;
    pointNames[{1, 2}] = "A";
    pointNames[{3, 4}] = "B";

    std::cout << "(1,2) → " << pointNames[{1, 2}] << "\n";

    // bucket 统计
    std::cout << "bucket_count: " << word_count.bucket_count() << "\n";
    std::cout << "load_factor: " << word_count.load_factor() << "\n";

    return 0;
}

⚠️ 注意：自定义类型用作无序容器的键时，必须提供自定义哈希函数和相等比较运算符。

4. 容器适配器

适配器底层容器接口
std::stackdeque(默认)push, pop, top
std::queuedeque(默认)push, pop, front, back
std::priority_queuevector(默认)push, pop, top
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <functional>

int main() {
    // stack — LIFO
    std::stack<int> stk;
    stk.push(10);
    stk.push(20);
    stk.push(30);
    std::cout << "stack: ";
    while (!stk.empty()) {
        std::cout << stk.top() << " ";  // 30 20 10
        stk.pop();
    }
    std::cout << "\n";

    // queue — FIFO
    std::queue<std::string> q;
    q.push("first");
    q.push("second");
    q.push("third");
    std::cout << "queue: ";
    while (!q.empty()) {
        std::cout << q.front() << " ";  // first second third
        q.pop();
    }
    std::cout << "\n";

    // priority_queue — 默认最大堆
    std::priority_queue<int> maxHeap;
    maxHeap.push(3);
    maxHeap.push(1);
    maxHeap.push(4);
    maxHeap.push(1);
    maxHeap.push(5);
    std::cout << "max-heap: ";
    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " ";  // 5 4 3 1 1
        maxHeap.pop();
    }
    std::cout << "\n";

    // 最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(4);
    std::cout << "min-heap: ";
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";  // 1 3 4
        minHeap.pop();
    }
    std::cout << "\n";

    return 0;
}

5. 迭代器类别与失效

迭代器类别支持操作典型容器
输入迭代器++, *, ==, !=istream_iterator
输出迭代器++, *ostream_iterator
前向迭代器输入 + 输出forward_list, unordered_*
双向迭代器前向 + --list, set, map
随机访问迭代器双向 + [], +n, -nvector, deque, array
连续迭代器 (C++20)随机访问 + 内存连续vector, array, string

迭代器失效场景

#include <iostream>
#include <vector>
#include <list>

int main() {
    // vector 迭代器失效
    std::vector<int> v = {1, 2, 3, 4, 5};

    // ❌ 错误：erase 后迭代器失效
    // for (auto it = v.begin(); it != v.end(); ++it) {
    //     if (*it == 3) v.erase(it);  // it 已失效
    // }

    // ✅ 正确：使用 erase 返回值
    for (auto it = v.begin(); it != v.end(); ) {
        if (*it == 3) {
            it = v.erase(it);  // 返回下一个有效迭代器
        } else {
            ++it;
        }
    }

    // ✅ C++20: std::erase_if
    // std::erase_if(v, [](int x) { return x == 3; });

    // list 迭代器：仅被删元素失效
    std::list<int> lst = {1, 2, 3, 4, 5};
    for (auto it = lst.begin(); it != lst.end(); ) {
        if (*it % 2 == 0) {
            it = lst.erase(it);  // 其他迭代器不受影响
        } else {
            ++it;
        }
    }

    std::cout << "vector: ";
    for (auto x : v) std::cout << x << " ";
    std::cout << "\n";

    std::cout << "list: ";
    for (auto x : lst) std::cout << x << " ";
    std::cout << "\n";

    return 0;
}

⚠️ 注意：vector 在 push_back 触发重分配时，所有迭代器、指针和引用都会失效。

6. 常用算法

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
#include <functional>

int main() {
    std::vector<int> v = {5, 3, 1, 4, 2, 3, 5};

    // sort — 排序
    std::sort(v.begin(), v.end());
    std::cout << "排序: ";
    for (auto x : v) std::cout << x << " ";  // 1 2 3 3 4 5 5
    std::cout << "\n";

    // unique — 去重（需先排序）
    auto last = std::unique(v.begin(), v.end());
    v.erase(last, v.end());
    std::cout << "去重: ";
    for (auto x : v) std::cout << x << " ";  // 1 2 3 4 5
    std::cout << "\n";

    // find — 查找
    auto it = std::find(v.begin(), v.end(), 3);
    if (it != v.end()) {
        std::cout << "找到 3，索引: " << std::distance(v.begin(), it) << "\n";
    }

    // count / count_if
    std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    auto even_count = std::count_if(data.begin(), data.end(),
                                     [](int x) { return x % 2 == 0; });
    std::cout << "偶数个数: " << even_count << "\n";  // 5

    // transform — 映射变换
    std::vector<int> doubled(data.size());
    std::transform(data.begin(), data.end(), doubled.begin(),
                   [](int x) { return x * 2; });
    std::cout << "翻倍: ";
    for (auto x : doubled) std::cout << x << " ";
    std::cout << "\n";

    // accumulate — 累加（在 <numeric> 中）
    int sum = std::accumulate(data.begin(), data.end(), 0);
    std::cout << "总和: " << sum << "\n";  // 55

    // reduce — C++17 并行友好版本
    int product = std::reduce(data.begin(), data.end(), 1, std::multiplies<int>());
    std::cout << "乘积: " << product << "\n";

    // any_of / all_of / none_of
    bool has_negative = std::any_of(data.begin(), data.end(),
                                     [](int x) { return x < 0; });
    bool all_positive = std::all_of(data.begin(), data.end(),
                                     [](int x) { return x > 0; });
    std::cout << "含负数: " << std::boolalpha << has_negative << "\n";
    std::cout << "全部正数: " << all_positive << "\n";

    // min_element / max_element
    auto [min_it, max_it] = std::minmax_element(data.begin(), data.end());
    std::cout << "最小: " << *min_it << ", 最大: " << *max_it << "\n";

    // partition — 分区
    std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8};
    auto pivot = std::partition(nums.begin(), nums.end(),
                                 [](int x) { return x % 2 == 0; });
    std::cout << "分区后: ";
    for (auto x : nums) std::cout << x << " ";
    std::cout << "\n";

    return 0;
}

7. 函数对象与 Lambda

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

// 函数对象（仿函数）
struct Multiply {
    int factor;
    explicit Multiply(int f) : factor(f) {}
    int operator()(int x) const { return x * factor; }
};

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};

    // 函数对象
    std::transform(v.begin(), v.end(), v.begin(), Multiply(3));
    std::cout << "×3: ";
    for (auto x : v) std::cout << x << " ";
    std::cout << "\n";

    // Lambda 表达式
    v = {1, 2, 3, 4, 5};

    // 基本 Lambda
    auto square = [](int x) { return x * x; };
    std::transform(v.begin(), v.end(), v.begin(), square);

    // 带捕获的 Lambda
    int threshold = 10;
    auto count = std::count_if(v.begin(), v.end(),
                                [threshold](int x) { return x > threshold; });
    std::cout << "大于 " << threshold << " 的个数: " << count << "\n";

    // 捕获方式
    int a = 1, b = 2;
    auto by_value = [a, b]() { return a + b; };     // 值捕获
    auto by_ref = [&a, &b]() { a++; b++; };         // 引用捕获
    auto all_value = [=]() { return a + b; };        // 所有变量值捕获
    auto all_ref = [&]() { a++; b++; };              // 所有变量引用捕获
    auto mixed = [a, &b]() { b += a; };              // 混合捕获

    // C++14 初始化捕获（移动捕获）
    auto ptr = std::make_unique<int>(42);
    auto lambda = [p = std::move(ptr)]() {
        std::cout << "移动捕获: " << *p << "\n";
    };
    lambda();

    // C++14 泛型 Lambda
    auto generic = [](auto x, auto y) { return x + y; };
    std::cout << generic(3, 4) << "\n";      // 7
    std::cout << generic(1.5, 2.5) << "\n";  // 4.0

    // std::function — 通用可调用对象包装器
    std::function<int(int)> fib = [&fib](int n) -> int {
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    };
    std::cout << "fib(10) = " << fib(10) << "\n";  // 55

    return 0;
}

8. STL 容器选择指南

需要随机访问？
├── 是 → 需要在中间频繁插入/删除？
│        ├── 是 → std::deque
│        └── 否 → std::vector（默认首选）
└── 否 → 需要键值对？
         ├── 是 → 需要有序？
         │        ├── 是 → std::map
         │        └── 否 → std::unordered_map（更快）
         └── 否 → 需要快速查找？
                  ├── 是 → std::set / std::unordered_set
                  └── 否 → 需要 FIFO/LIFO/优先级？
                           ├── FIFO → std::queue
                           ├── LIFO → std::stack
                           └── 优先级 → std::priority_queue
场景推荐容器理由
默认序列容器std::vector缓存友好，空间紧凑
频繁头部插入/删除std::dequeO(1) 头尾操作
频繁中间插入/删除std::listO(1) 插入/删除
键值查找（有序）std::mapO(log n) 有序遍历
键值查找（无序）std::unordered_map平均 O(1) 查找
集合运算std::set有序，支持交并差
固定大小数组std::array零开销，栈上分配
仅需 FIFOstd::queue简化接口
优先级排序std::priority_queue堆结构，O(log n) 插入

实现场景：LRU 缓存

#include <iostream>
#include <unordered_map>
#include <list>

template <typename K, typename V>
class LRUCache {
    size_t capacity_;
    std::list<std::pair<K, V>> items_;  // 最近使用在前
    std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> index_;

public:
    explicit LRUCache(size_t cap) : capacity_(cap) {}

    V get(const K& key) {
        auto it = index_.find(key);
        if (it == index_.end()) {
            throw std::runtime_error("Key not found");
        }
        // 移到列表头部
        items_.splice(items_.begin(), items_, it->second);
        return it->second->second;
    }

    void put(const K& key, const V& value) {
        auto it = index_.find(key);
        if (it != index_.end()) {
            // 已存在：更新并移到头部
            it->second->second = value;
            items_.splice(items_.begin(), items_, it->second);
            return;
        }

        // 满了：淘汰最久未使用
        if (items_.size() >= capacity_) {
            auto& old = items_.back();
            index_.erase(old.first);
            items_.pop_back();
        }

        items_.emplace_front(key, value);
        index_[key] = items_.begin();
    }

    void print() const {
        for (const auto& [k, v] : items_) {
            std::cout << k << ":" << v << " ";
        }
        std::cout << "\n";
    }
};

int main() {
    LRUCache<int, std::string> cache(3);

    cache.put(1, "A");
    cache.put(2, "B");
    cache.put(3, "C");
    cache.print();  // 3:C 2:B 1:A

    cache.get(1);    // 访问 1，移到头部
    cache.print();   // 1:A 3:C 2:B

    cache.put(4, "D");  // 淘汰 2
    cache.print();       // 4:D 1:A 3:C

    return 0;
}

扩展阅读