STL深入剖析¶

🎯 学习目标¶

完成本章学习后，你将能够： - 全面理解STL六大组件的架构设计与协作关系 - 深入掌握各类容器的底层实现原理与性能特征 - 熟练运用STL算法解决实际工程问题 - 理解迭代器萃取（traits）技术的设计哲学 - 掌握仿函数、std::function与lambda的关系 - 了解内存分配器的实现原理与自定义方法 - 规避STL常见性能陷阱，写出高效的C++代码

上图展示了容器、算法、迭代器、仿函数、适配器、分配器之间的协作关系。

一、STL总体架构¶

STL（Standard Template Library）是C++标准库中最核心的泛型组件库，由Alexander Stepanov设计，其核心思想是将数据结构与算法分离，通过迭代器作为中间桥梁实现解耦。

1.1 六大组件概览¶

组件	说明	典型代表
容器（Containers）	存储数据的数据结构	`vector`, `map`, `unordered_map`
算法（Algorithms）	操作数据的函数模板	`sort`, `find`, `transform`
迭代器（Iterators）	容器与算法之间的桥梁	`begin()`, `end()`, 各种iterator
仿函数（Functors）	行为类似函数的对象	`less<>`, `greater<>`, 自定义仿函数
适配器（Adapters）	对组件进行接口转换	`stack`, `queue`, `back_inserter`
分配器（Allocators）	管理内存分配与释放	`allocator<T>`, 自定义分配器

1.2 组件协作关系¶

C++

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

int main() {
    // 容器：存储数据
    std::vector<int> vec = {5, 3, 1, 4, 2};  // std::vector 动态数组，自动管理内存

    // 算法 + 迭代器 + 仿函数 协作
    std::sort(vec.begin(),   // 迭代器：指定范围起点
              vec.end(),     // 迭代器：指定范围终点
              std::greater<int>());  // 仿函数：指定比较策略

    // 算法 + 迭代器
    std::for_each(vec.begin(), vec.end(), [](int x) {  // Lambda表达式，[]为捕获列表
        std::cout << x << " ";  // 输出: 5 4 3 2 1
    });
    std::cout << std::endl;

    return 0;
}

设计哲学：STL通过泛型编程（Generic Programming）实现了算法与数据结构的正交分解。M个容器 × N个算法，只需要M+N个实现，而不是M×N个。

二、序列容器深入¶

2.1 vector —— 动态数组¶

内存增长策略¶

vector底层是一块连续内存，当元素个数超过当前容量时，会触发重新分配（reallocation）：

分配一块更大的内存（通常为当前容量的 1.5倍（MSVC）或 2倍（GCC/Clang））
将旧元素移动/拷贝到新内存
释放旧内存

C++

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    std::cout << "size\tcapacity\tdata_ptr" << std::endl;

    for (int i = 0; i < 20; ++i) {
        v.push_back(i);
        std::cout << v.size() << "\t"
                  << v.capacity() << "\t\t"
                  << v.data() << std::endl;
    }
    // 观察：每次capacity不够时，地址会变化（发生了重新分配）
    return 0;
}

迭代器失效场景¶

C++

#include <iostream>
#include <vector>

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

    // ❌ 错误：插入可能导致所有迭代器失效
    // auto it = v.begin();
    // v.push_back(6);  // 若触发reallocation，it失效！
    // *it;             // 未定义行为

    // ✅ 正确：删除时使用erase返回的新迭代器
    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0) {
            it = v.erase(it);  // erase返回下一个有效迭代器
        } else {
            ++it;
        }
    }

    for (int x : v) std::cout << x << " ";  // 输出: 1 3 5
    std::cout << std::endl;

    return 0;
}

📋 面试要点：vector迭代器失效规则——插入时若触发扩容则全部失效，删除时被删元素及之后的迭代器失效。

2.2 deque —— 双端队列¶

deque的底层是分段连续内存，由一个中控器（map，即指针数组）管理多个固定大小的缓冲区（buffer）。

Text Only

中控器 map:   [buf_ptr0] [buf_ptr1] [buf_ptr2] [buf_ptr3]
                  |          |          |          |
缓冲区:       [__|__|__] [__|__|__] [__|__|__] [__|__|__]

头尾插入/删除 O(1)
随机访问 O(1)（通过计算在哪个缓冲区的哪个位置）
中间插入/删除 O(n)

C++

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq;

    // 头部和尾部都能高效插入
    dq.push_back(1);
    dq.push_back(2);
    dq.push_front(0);
    dq.push_front(-1);

    for (int x : dq) std::cout << x << " ";  // -1 0 1 2
    std::cout << std::endl;

    // 随机访问
    std::cout << "dq[2] = " << dq[2] << std::endl;  // 1

    return 0;
}

2.3 list —— 双向链表¶

list底层是双向循环链表，每个节点包含前驱指针、后继指针和数据域。

C++

#include <iostream>
#include <list>
#include <algorithm>

int main() {
    std::list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6};

    // list有自己的sort（因为std::sort要求RandomAccessIterator）
    lst.sort();

    // 去重（需先排序）
    lst.unique();

    // splice：O(1)拼接
    std::list<int> lst2 = {100, 200};
    lst.splice(lst.end(), lst2);  // lst2的元素移动到lst末尾

    for (int x : lst) std::cout << x << " ";
    std::cout << std::endl;
    // lst2此时为空
    std::cout << "lst2 size: " << lst2.size() << std::endl;  // 0

    return 0;
}

2.4 forward_list —— 单向链表（C++11）¶

C++

#include <iostream>
#include <forward_list>

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

    // 只能向前遍历，没有size()成员函数
    fl.push_front(0);

    // 在某个位置后插入
    auto it = fl.begin();
    std::advance(it, 2);
    fl.insert_after(it, 99);

    for (int x : fl) std::cout << x << " ";
    std::cout << std::endl;  // 0 1 2 99 3 4 5

    return 0;
}

2.5 array —— 固定大小数组（C++11）¶

C++

#include <iostream>
#include <array>
#include <algorithm>

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

    std::sort(arr.begin(), arr.end());

    // 与原生数组不同，支持赋值、比较
    std::array<int, 5> arr2 = arr;  // 合法

    std::cout << "size: " << arr.size() << std::endl;     // 5
    std::cout << "front: " << arr.front() << std::endl;   // 1
    std::cout << "at(2): " << arr.at(2) << std::endl;     // 3（带越界检查）

    return 0;
}

序列容器性能对比¶

操作	vector	deque	list	forward_list	array
随机访问	O(1)	O(1)	O(n)	O(n)	O(1)
头部插入	O(n)	O(1)	O(1)	O(1)	—
尾部插入	均摊O(1)	O(1)	O(1)	O(n)	—
中间插入	O(n)	O(n)	O(1)*	O(1)*	—
内存布局	连续	分段连续	不连续	不连续	连续

*list/forward_list中间插入为O(1)前提是已经持有目标位置的迭代器。

三、关联容器¶

3.1 有序关联容器 —— 红黑树¶

set、multiset、map、multimap 底层都是红黑树（Red-Black Tree）——一种自平衡二叉搜索树。

红黑树性质： 1. 每个节点非红即黑 2. 根节点为黑 3. 叶子（NIL）节点为黑 4. 红节点的子节点必须为黑 5. 从任一节点到其所有叶子的路径上，黑节点数相同

所有操作（查找、插入、删除）都是 O(log n)。

C++

#include <iostream>
#include <map>
#include <set>

int main() {
    // === map 示例 ===
    std::map<std::string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores["Charlie"] = 92;
    scores.insert({"David", 88});

    // 遍历是有序的（按key升序）
    for (const auto& [name, score] : scores) {
        std::cout << name << ": " << score << std::endl;
    }

    // lower_bound / upper_bound
    auto it = scores.lower_bound("Bob");
    std::cout << "lower_bound(Bob): " << it->first << std::endl;

    // === multimap 示例（允许重复key）===
    std::multimap<int, std::string> grade_students;
    grade_students.insert({90, "Alice"});
    grade_students.insert({90, "Charlie"});
    grade_students.insert({85, "Bob"});

    auto range = grade_students.equal_range(90);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << " got " << it->first << std::endl;
    }

    // === set 示例 ===
    std::set<int> s = {3, 1, 4, 1, 5, 9};  // 自动去重排序
    std::cout << "set size: " << s.size() << std::endl;  // 5
    std::cout << "count(1): " << s.count(1) << std::endl; // 1

    return 0;
}

3.2 无序关联容器 —— 哈希表¶

unordered_set、unordered_multiset、unordered_map、unordered_multimap 底层是哈希表（Hash Table），采用拉链法（separate chaining）解决冲突。

核心概念： - 桶（bucket）：哈希表中的每个槽位 - 负载因子（load factor）：元素数 / 桶数，默认最大1.0 - rehash：当负载因子超过阈值时，重新分配更多桶并重新哈希所有元素

C++

#include <iostream>
#include <unordered_map>
#include <unordered_set>

int main() {
    std::unordered_map<std::string, int> umap;
    umap["apple"] = 3;
    umap["banana"] = 5;
    umap["cherry"] = 2;

    // 查看哈希表内部状态
    std::cout << "bucket_count: " << umap.bucket_count() << std::endl;
    std::cout << "load_factor: " << umap.load_factor() << std::endl;
    std::cout << "max_load_factor: " << umap.max_load_factor() << std::endl;

    // 手动rehash
    umap.reserve(100);  // 预分配足够桶，减少rehash次数

    // 查看每个桶的元素数
    for (size_t i = 0; i < umap.bucket_count(); ++i) {
        if (umap.bucket_size(i) > 0) {
            std::cout << "Bucket " << i << " has "
                      << umap.bucket_size(i) << " elements" << std::endl;
        }
    }

    // 自定义类型作为key需要提供hash函数和==运算符
    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 {
            // 常见做法：组合多个字段的hash
            size_t h1 = std::hash<int>{}(p.x);
            size_t h2 = std::hash<int>{}(p.y);
            return h1 ^ (h2 << 1);
        }
    };

    std::unordered_set<Point, PointHash> point_set;
    point_set.insert({1, 2});
    point_set.insert({3, 4});
    std::cout << "point_set size: " << point_set.size() << std::endl;

    return 0;
}

📋 面试要点：map vs unordered_map选型——需要有序遍历用map(O(log n))；只需要查找/插入用unordered_map(均摊O(1))；数据量小且key类型简单优先unordered_map。

四、容器适配器¶

容器适配器不是独立的容器，而是对已有容器的接口封装，限制其操作方式。

4.1 stack —— 栈¶

C++

#include <iostream>
#include <stack>
#include <deque>
#include <vector>

int main() {
    // 默认底层容器是deque
    std::stack<int> s1;

    // 可以指定底层容器为vector
    std::stack<int, std::vector<int>> s2;

    s1.push(1);
    s1.push(2);
    s1.push(3);

    while (!s1.empty()) {
        std::cout << s1.top() << " ";  // 3 2 1
        s1.pop();
    }
    std::cout << std::endl;

    return 0;
}

4.2 queue —— 队列¶

C++

#include <iostream>
#include <queue>

int main() {
    // 默认底层容器是deque
    std::queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);

    while (!q.empty()) {
        std::cout << q.front() << " ";  // 1 2 3
        q.pop();
    }
    std::cout << std::endl;

    return 0;
}

4.3 priority_queue —— 优先队列¶

C++

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

int main() {
    // 默认是最大堆，底层vector + heap算法
    std::priority_queue<int> max_heap;
    max_heap.push(3);
    max_heap.push(1);
    max_heap.push(4);
    max_heap.push(1);
    max_heap.push(5);

    std::cout << "Max heap: ";
    while (!max_heap.empty()) {
        std::cout << max_heap.top() << " ";  // 5 4 3 1 1
        max_heap.pop();
    }
    std::cout << std::endl;

    // 最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    min_heap.push(3);
    min_heap.push(1);
    min_heap.push(4);

    std::cout << "Min heap: ";
    while (!min_heap.empty()) {
        std::cout << min_heap.top() << " ";  // 1 3 4
        min_heap.pop();
    }
    std::cout << std::endl;

    // 自定义比较器
    auto cmp = [](const std::pair<int,std::string>& a,
                   const std::pair<int,std::string>& b) {
        return a.first > b.first;  // 按first升序（最小堆）
    };
    // decltype(cmp)推导lambda类型作为模板参数; pq(cmp)将lambda实例传入构造函数（两者缺一不可）
    std::priority_queue<std::pair<int,std::string>,
                        std::vector<std::pair<int,std::string>>,
                        decltype(cmp)> pq(cmp);
    pq.push({3, "C"});
    pq.push({1, "A"});
    pq.push({2, "B"});

    while (!pq.empty()) {
        auto [val, name] = pq.top();
        std::cout << val << ":" << name << " ";  // 1:A 2:B 3:C
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

适配器	默认底层容器	可选底层容器	核心操作
`stack`	`deque`	`vector`, `list`	`push`, `pop`, `top`
`queue`	`deque`	`list`	`push`, `pop`, `front`, `back`
`priority_queue`	`vector`	`deque`	`push`, `pop`, `top`

五、迭代器深入¶

5.1 五种迭代器分类¶

STL定义了五种迭代器类别，形成继承层次：

Text Only

InputIterator      OutputIterator
      \               /
    ForwardIterator
          |
  BidirectionalIterator
          |
  RandomAccessIterator

迭代器类别	能力	代表容器
InputIterator	单遍前向只读 `++`, `*`, `==`	`istream_iterator`
OutputIterator	单遍前向只写 `++`, `*`	`ostream_iterator`, `back_inserter`
ForwardIterator	多遍前向读写	`forward_list`, `unordered_xxx`
BidirectionalIterator	双向 `++`, `--`	`list`, `set`, `map`
RandomAccessIterator	任意跳跃 `+n`, `-n`, `[]`	`vector`, `deque`, `array`

5.2 迭代器萃取（Iterator Traits）¶

std::iterator_traits是一个traits类，用于在编译期提取迭代器的属性：

C++

#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <type_traits>

// 利用tag dispatch实现针对不同迭代器类型的优化
template <typename Iterator>
void advance_impl(Iterator& it, int n, std::random_access_iterator_tag) {
    // RandomAccessIterator: 直接跳跃 O(1)
    it += n;
    std::cout << "[RandomAccess] O(1) advance" << std::endl;
}

template <typename Iterator>
void advance_impl(Iterator& it, int n, std::bidirectional_iterator_tag) {
    // BidirectionalIterator: 逐步移动 O(n)
    if (n > 0) while (n--) ++it;
    else while (n++) --it;
    std::cout << "[Bidirectional] O(n) advance" << std::endl;
}

template <typename Iterator>
void advance_impl(Iterator& it, int n, std::input_iterator_tag) {
    // InputIterator: 只能前进
    while (n--) ++it;
    std::cout << "[Input/Forward] O(n) advance" << std::endl;
}

template <typename Iterator>
void my_advance(Iterator& it, int n) {
    // 通过iterator_traits萃取迭代器类别，进行tag dispatch
    using category = typename std::iterator_traits<Iterator>::iterator_category;
    advance_impl(it, n, category{});
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto vit = vec.begin();
    my_advance(vit, 3);           // [RandomAccess] O(1) advance
    std::cout << *vit << std::endl;  // 4

    std::list<int> lst = {1, 2, 3, 4, 5};
    auto lit = lst.begin();
    my_advance(lit, 3);           // [Bidirectional] O(n) advance
    std::cout << *lit << std::endl;  // 4

    return 0;
}

📋 面试要点：traits技术是STL的灵魂之一。iterator_traits允许算法在编译期根据迭代器类别选择最优实现，是策略模式在模板编程中的体现。

六、STL算法精讲¶

STL算法定义在 <algorithm> 和 <numeric> 头文件中，通过迭代器操作容器而不依赖具体容器类型。

6.1 排序相关算法¶

C++

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

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

    // sort: 底层使用IntroSort（快排+堆排+插入排序的混合）
    // 平均O(n log n)，最坏O(n log n)
    std::sort(v.begin(), v.end());
    // v: 1 2 3 4 5 6 7 8 9

    // partial_sort: 只排前k个，O(n log k)
    std::vector<int> v2 = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    std::partial_sort(v2.begin(), v2.begin() + 3, v2.end());
    // v2前3个: 1 2 3 (后面无序)

    // nth_element: 找第n小并分区，O(n)平均
    std::vector<int> v3 = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    std::nth_element(v3.begin(), v3.begin() + 4, v3.end());
    std::cout << "5th smallest: " << v3[4] << std::endl;  // 5
    // v3[4]左边都 <= v3[4]，右边都 >= v3[4]

    // stable_sort: 保持相等元素相对顺序，底层归并排序，O(n log n)
    struct Student {
        std::string name;
        int score;
    };
    std::vector<Student> students = {
        {"Alice", 90}, {"Bob", 90}, {"Charlie", 85}, {"David", 90}
    };
    std::stable_sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            return a.score > b.score;
        });
    // 分数相同的Alice, Bob, David保持原始相对顺序
    for (const auto& s : students) {
        std::cout << s.name << ":" << s.score << " ";
    }
    std::cout << std::endl;

    return 0;
}

6.2 查找与分区算法¶

C++

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

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

    // lower_bound: 第一个 >= value 的位置（要求有序）
    auto lb = std::lower_bound(v.begin(), v.end(), 5);
    std::cout << "lower_bound(5): index " << (lb - v.begin()) << std::endl;  // 4

    // upper_bound: 第一个 > value 的位置
    auto ub = std::upper_bound(v.begin(), v.end(), 5);
    std::cout << "upper_bound(5): index " << (ub - v.begin()) << std::endl;  // 5

    // partition: 将满足条件的元素移到前面
    std::vector<int> v2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    auto pivot = std::partition(v2.begin(), v2.end(),
                                [](int x) { return x % 2 == 0; });
    std::cout << "Even elements count: " << (pivot - v2.begin()) << std::endl;

    // stable_partition: 保持相对顺序
    std::vector<int> v3 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::stable_partition(v3.begin(), v3.end(),
                          [](int x) { return x % 2 == 0; });
    // v3: 2 4 6 8 10 1 3 5 7 9（偶数在前，奇数在后，各自保持原序）
    for (int x : v3) std::cout << x << " ";
    std::cout << std::endl;

    return 0;
}

6.3 变换与累积算法¶

C++

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

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

    // accumulate: 累积求和
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "sum: " << sum << std::endl;  // 15

    // accumulate: 自定义操作（求乘积）
    int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());
    std::cout << "product: " << product << std::endl;  // 120

    // transform: 将结果写入另一个容器
    std::vector<int> squared(v.size());
    std::transform(v.begin(), v.end(), squared.begin(),
                   [](int x) { return x * x; });
    for (int x : squared) std::cout << x << " ";  // 1 4 9 16 25
    std::cout << std::endl;

    // transform: 双序列操作
    std::vector<int> a = {1, 2, 3};
    std::vector<int> b = {10, 20, 30};
    std::vector<int> c(3);
    std::transform(a.begin(), a.end(), b.begin(), c.begin(), std::plus<int>());
    for (int x : c) std::cout << x << " ";  // 11 22 33
    std::cout << std::endl;

    // for_each: 对每个元素执行操作（可以有副作用）
    std::for_each(v.begin(), v.end(), [](int& x) { x *= 2; });
    for (int x : v) std::cout << x << " ";  // 2 4 6 8 10
    std::cout << std::endl;

    return 0;
}

6.4 remove-erase 惯用法¶

C++

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

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

    // std::remove并不真正删除元素！它只是将不满足条件的元素移到前面
    // 返回新的逻辑终点迭代器
    auto new_end = std::remove(v.begin(), v.end(), 2);
    // v可能是: [1, 3, 4, 5, ?, ?, ?]，new_end指向第一个?的位置

    // 必须配合erase才能真正删除
    v.erase(new_end, v.end());

    for (int x : v) std::cout << x << " ";  // 1 3 4 5
    std::cout << std::endl;

    // 一行写法（remove-erase idiom）
    std::vector<int> v2 = {1, 2, 3, 2, 4, 2, 5};
    v2.erase(std::remove(v2.begin(), v2.end(), 2), v2.end());

    // C++20: std::erase 更简洁
    // std::erase(v2, 2);

    // remove_if + erase: 删除满足条件的元素
    std::vector<int> v3 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    v3.erase(
        std::remove_if(v3.begin(), v3.end(), [](int x) { return x % 2 == 0; }),
        v3.end()
    );
    for (int x : v3) std::cout << x << " ";  // 1 3 5 7 9
    std::cout << std::endl;

    return 0;
}

📋 面试要点：为什么std::sort要求RandomAccessIterator？因为底层IntroSort需要随机跳跃访问元素；list只能用自己的成员函数sort（底层归并排序）。

七、仿函数与function对象¶

7.1 仿函数（Functor）¶

仿函数是重载了 operator() 的类对象，可以像函数一样调用。

C++

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

// 自定义仿函数
struct AbsCompare {
    bool operator()(int a, int b) const {
        return std::abs(a) < std::abs(b);
    }
};

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

    // 使用STL内置仿函数
    std::sort(v.begin(), v.end(), std::greater<int>());
    // v: 4 3 -1 -2 -5

    // 使用自定义仿函数
    std::sort(v.begin(), v.end(), AbsCompare());
    // v: -1 -2 3 4 -5  (按绝对值升序)

    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;

    return 0;
}

7.2 std::function —— 通用可调用对象包装¶

C++

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

// 普通函数
int add(int a, int b) { return a + b; }

// 仿函数
struct Multiply {
    int operator()(int a, int b) const { return a * b; }
};

int main() {
    // std::function可以包装任何可调用对象
    std::function<int(int, int)> func;

    // 包装普通函数
    func = add;
    std::cout << "add(3,4) = " << func(3, 4) << std::endl;  // 7

    // 包装仿函数
    func = Multiply();
    std::cout << "multiply(3,4) = " << func(3, 4) << std::endl;  // 12

    // 包装lambda
    func = [](int a, int b) { return a - b; };
    std::cout << "subtract(3,4) = " << func(3, 4) << std::endl;  // -1

    // 实用场景：回调函数容器
    std::vector<std::function<int(int, int)>> operations = {
        add,
        Multiply(),
        [](int a, int b) { return a - b; },
    };

    for (auto& op : operations) {
        std::cout << op(10, 3) << " ";  // 13 30 7
    }
    std::cout << std::endl;

    return 0;
}

7.3 std::bind 与 lambda¶

C++

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

int main() {
    using namespace std::placeholders;

    // bind: 绑定部分参数
    auto add5 = std::bind(std::plus<int>(), _1, 5);
    std::cout << "add5(10) = " << add5(10) << std::endl;  // 15

    // lambda实现同样功能（更推荐）
    auto add5_lambda = [](int x) { return x + 5; };
    std::cout << "add5_lambda(10) = " << add5_lambda(10) << std::endl;  // 15

    // 实际应用：参数绑定
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // 使用bind
    int count1 = std::count_if(v.begin(), v.end(),
                               std::bind(std::greater<int>(), _1, 5));

    // 使用lambda（更清晰）
    int count2 = std::count_if(v.begin(), v.end(),
                               [](int x) { return x > 5; });

    std::cout << "count > 5: " << count1 << " " << count2 << std::endl;  // 5 5

    return 0;
}

最佳实践：C++11之后，推荐使用lambda代替bind，因为lambda更直观、可读性更强，编译器也更容易优化。

八、内存分配器¶

8.1 std::allocator 标准接口¶

C++

#include <iostream>
#include <memory>
#include <vector>

int main() {
    std::allocator<int> alloc;

    // 分配内存（不构造对象）
    int* p = alloc.allocate(5);

    // 在已分配的内存上构造对象
    for (int i = 0; i < 5; ++i) {
        std::allocator_traits<std::allocator<int>>::construct(alloc, p + i, i * 10);
    }

    for (int i = 0; i < 5; ++i) {
        std::cout << p[i] << " ";  // 0 10 20 30 40
    }
    std::cout << std::endl;

    // 析构对象
    for (int i = 0; i < 5; ++i) {
        std::allocator_traits<std::allocator<int>>::destroy(alloc, p + i);
    }

    // 释放内存
    alloc.deallocate(p, 5);

    return 0;
}

8.2 SGI STL 二级分配器（内存池）¶

SGI STL的分配器采用二级分配器设计：

一级分配器：大于128字节直接调用 malloc/free，失败时调用OOM处理函数
二级分配器（内存池）：小于等于128字节，使用16个自由链表（free list）管理，分别对应8, 16, 24, ..., 128字节的内存块

Text Only

Free List Array (16个):
[0]  -> 8bytes块  -> 8bytes块  -> ...
[1]  -> 16bytes块 -> 16bytes块 -> ...
[2]  -> 24bytes块 -> 24bytes块 -> ...
...
[15] -> 128bytes块 -> 128bytes块 -> ...

好处：减少内存碎片、减少malloc调用次数、提高小对象分配效率。

8.3 自定义分配器示例¶

C++

#include <iostream>
#include <vector>
#include <cstdlib>

// 简单的自定义分配器：追踪分配行为
template <typename T>
struct TrackingAllocator {
    using value_type = T;

    TrackingAllocator() = default;
    template <typename U>
    TrackingAllocator(const TrackingAllocator<U>&) {}

    T* allocate(std::size_t n) {
        std::cout << "[Alloc] " << n << " objects, "
                  << n * sizeof(T) << " bytes" << std::endl;
        return static_cast<T*>(std::malloc(n * sizeof(T)));
    }

    void deallocate(T* p, std::size_t n) {
        std::cout << "[Dealloc] " << n << " objects, "
                  << n * sizeof(T) << " bytes" << std::endl;
        std::free(p);
    }
};

template <typename T, typename U>
bool operator==(const TrackingAllocator<T>&, const TrackingAllocator<U>&) { return true; }

template <typename T, typename U>
bool operator!=(const TrackingAllocator<T>&, const TrackingAllocator<U>&) { return false; }

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

    for (int i = 0; i < 10; ++i) {
        v.push_back(i);
    }
    // 可以观察到vector扩容时的分配与释放模式

    return 0;
}

九、STL性能陷阱与最佳实践¶

9.1 vector vs list 选型¶

C++

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

int main() {
    const int N = 1000000;

    // === 尾部插入性能 ===
    auto t1 = std::chrono::high_resolution_clock::now();
    std::vector<int> vec;
    for (int i = 0; i < N; ++i) vec.push_back(i);
    auto t2 = std::chrono::high_resolution_clock::now();

    std::list<int> lst;
    for (int i = 0; i < N; ++i) lst.push_back(i);
    auto t3 = std::chrono::high_resolution_clock::now();

    auto vec_time = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
    auto lst_time = std::chrono::duration_cast<std::chrono::microseconds>(t3 - t2).count();

    std::cout << "vector push_back: " << vec_time << " us" << std::endl;
    std::cout << "list push_back:   " << lst_time << " us" << std::endl;
    // vector通常更快！因为缓存友好（连续内存）

    return 0;
}

原则：默认用vector。即使需要中间插入，除非元素数量极大且频繁在中间插入/删除，否则vector的缓存友好性通常使其比list更快。

9.2 reserve 预分配¶

C++

#include <iostream>
#include <vector>
#include <chrono>

int main() {
    const int N = 10000000;

    // 不预分配：多次reallocation
    auto t1 = std::chrono::high_resolution_clock::now();
    std::vector<int> v1;
    for (int i = 0; i < N; ++i) v1.push_back(i);
    auto t2 = std::chrono::high_resolution_clock::now();

    // 预分配：零次reallocation
    std::vector<int> v2;
    v2.reserve(N);
    for (int i = 0; i < N; ++i) v2.push_back(i);
    auto t3 = std::chrono::high_resolution_clock::now();

    auto time1 = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
    auto time2 = std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2).count();

    std::cout << "Without reserve: " << time1 << " ms" << std::endl;
    std::cout << "With reserve:    " << time2 << " ms" << std::endl;

    return 0;
}

9.3 emplace_back vs push_back¶

C++

#include <iostream>
#include <vector>
#include <string>

struct HeavyObject {
    std::string data;
    int id;

    HeavyObject(std::string d, int i) : data(std::move(d)), id(i) {
        std::cout << "Constructor: " << data << std::endl;
    }
    HeavyObject(const HeavyObject& other) : data(other.data), id(other.id) {
        std::cout << "Copy: " << data << std::endl;
    }
    HeavyObject(HeavyObject&& other) noexcept : data(std::move(other.data)), id(other.id) {
        std::cout << "Move: " << data << std::endl;
    }
};

int main() {
    std::vector<HeavyObject> v;
    v.reserve(4);

    std::cout << "=== push_back ===" << std::endl;
    v.push_back(HeavyObject("hello", 1));
    // 先构造临时对象，再移动到容器中

    std::cout << "\n=== emplace_back ===" << std::endl;
    v.emplace_back("world", 2);
    // 直接在容器内存中原地构造，零拷贝零移动！

    return 0;
}

9.4 移动语义对STL的影响¶

C++

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

int main() {
    std::vector<std::string> src = {"hello", "world", "foo", "bar"};

    // 移动整个容器 O(1)
    std::vector<std::string> dst = std::move(src);
    // src现在为空（有效但未指定状态）

    std::cout << "dst size: " << dst.size() << std::endl;   // 4
    std::cout << "src size: " << src.size() << std::endl;    // 0

    // insert支持移动
    std::vector<std::string> v1 = {"a", "b"};
    std::vector<std::string> v2 = {"c", "d"};
    v1.insert(v1.end(),
              std::make_move_iterator(v2.begin()),
              std::make_move_iterator(v2.end()));

    std::cout << "v1: ";
    for (const auto& s : v1) std::cout << s << " ";  // a b c d
    std::cout << std::endl;

    return 0;
}

STL最佳实践速查表¶

场景	最佳实践
知道元素数量	`reserve()` 预分配
插入对象	优先 `emplace_back` 而非 `push_back`
删除元素	remove-erase 惯用法（C++20用 `std::erase`）
遍历时删除	使用 `erase` 返回值更新迭代器
查找	有序用 `lower_bound`，无序用 `unordered_map::find`
排序	只需前k个用 `partial_sort`，只需第k个用 `nth_element`
容器选择	默认 `vector`，键值对 `unordered_map`，有序 `map`
字符串拼接	大量拼接用 `reserve` + `append`，或用 `ostringstream`

✏️ 练习¶

练习1：LRU缓存¶

使用 std::list 和 std::unordered_map 实现一个LRU缓存，支持 get(key) 和 put(key, value) 操作，时间复杂度均为O(1)。

练习2：TopK问题¶

给定一个包含100万个整数的vector，使用STL算法在O(n)时间复杂度内找出最大的100个数。

练习3：自定义排序¶

有一个 vector<pair<string, int>>，先按int降序排序，int相同时按string字典序升序排序。分别用仿函数和lambda实现。

练习4：词频统计¶

读入一段英文文本（string），统计每个单词出现次数，再按出现次数降序输出。要求使用 unordered_map、vector、sort。

练习5：迭代器适配器¶

使用 std::back_inserter、std::ostream_iterator 配合 std::copy 和 std::transform，实现将一个vector中所有元素平方后输出到标准输出。

📋 面试要点¶

高频问题¶

vector扩容机制：1.5倍 vs 2倍增长策略，为什么不是固定大小？均摊O(1)分析。
map vs unordered_map：底层分别是红黑树和哈希表，时间复杂度、内存消耗、有序性差异。
迭代器失效：哪些操作会导致哪些容器的迭代器失效？vector insert/erase、map erase、unordered_map rehash。
sort的底层实现：IntroSort = 快排 + 堆排 + 插排的混合策略，为什么要混合？
remove-erase idiom：为什么std::remove不直接删除？它的返回值是什么？
emplace_back vs push_back：什么时候emplace_back真的能避免拷贝？什么时候没区别？
traits技术：iterator_traits是什么？有什么用？type_traits呢？
容器选型：给定场景（频繁查找/频繁插入/有序遍历等）如何选择容器？
priority_queue：底层是什么？如何实现最小堆？自定义比较器的写法？
内存分配器：SGI STL的内存池为什么要设计二级分配器？自由链表如何管理？

回答模板¶

Q: vector和list如何选型？ A: 默认选vector。vector连续内存，缓存命中率高，尾部操作均摊O(1)。list单元素操作O(1)但缓存不友好，只有在需要频繁在已知位置插入/删除且元素非常大时才考虑list。实际benchmark中，即使中间插入，元素为int级别的vector通常也比list快。

💡 本章小结¶

本章从六大组件入手，系统地剖析了STL的设计思想和实现细节。STL是C++最强大的武器之一，深入理解其原理不仅能写出更高效的代码，更是面试中的必考内容。下一章将学习C++17/20/23的现代新特性，这些新特性与STL紧密结合，能进一步提升代码质量和开发效率。