STL 标准库全景

STL（Standard Template Library）是 C++ 标准库的核心，提供容器、算法、迭代器三大组件，是日常开发的基础设施。

STL 架构

STL 三大支柱
├── 容器（Containers）— 数据存储
│   ├── 序列容器：vector / deque / list / forward_list / array
│   ├── 关联容器：map / set / multimap / multiset
│   ├── 无序容器：unordered_map / unordered_set
│   └── 容器适配器：stack / queue / priority_queue
│
├── 算法（Algorithms）— 数据处理
│   ├── 非修改算法：find / count / search / equal
│   ├── 修改算法：copy / transform / fill / replace
│   ├── 排序算法：sort / stable_sort / partial_sort
│   ├── 数值算法：accumulate / inner_product / partial_sum
│   └── C++20 ranges 算法
│
└── 迭代器（Iterators）— 连接容器与算法
    ├── 输入/输出迭代器
    ├── 前向/双向/随机访问迭代器
    └── 反向/插入迭代器

容器选择指南

场景	推荐容器	原因
默认序列容器	vector	缓存友好，随机访问 O(1)
频繁头部插入	deque	两端 O(1) 插入
频繁中间插入	list	任意位置 O(1) 插入
编译期固定大小	array	栈分配，零开销
键值查找（有序）	map	O(log n)，有序遍历
键值查找（快速）	unordered_map	O(1) 平均，无序
去重集合	unordered_set	O(1) 查找
优先队列	priority_queue	O(log n) 插入/取最值

容器性能速查

vector:
  随机访问:  O(1)
  尾部插入:  O(1) 均摊
  中间插入:  O(n)
  查找:      O(n)

unordered_map:
  查找/插入: O(1) 均摊
  最坏情况:  O(n)（哈希冲突）
  内存:      较高（哈希表开销）

map:
  查找/插入: O(log n)
  有序遍历:  O(n)
  内存:      每节点独立分配（cache 不友好）

list:
  任意插入:  O(1)（已有迭代器）
  随机访问:  O(n)
  内存:      每节点独立分配

迭代器类别

#include <iterator>

// 迭代器层次（从弱到强）
// InputIterator → ForwardIterator → BidirectionalIterator → RandomAccessIterator

// 各容器的迭代器类别：
// vector, array, deque    → RandomAccessIterator（最强）
// list, map, set          → BidirectionalIterator
// forward_list            → ForwardIterator
// istream_iterator        → InputIterator

// 迭代器操作
std::vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin();

++it;           // 前进一步（所有迭代器）
it += 2;        // 前进多步（仅随机访问）
auto dist = std::distance(v.begin(), v.end());  // 5

// 反向迭代器
for (auto it = v.rbegin(); it != v.rend(); ++it) {
    std::cout << *it << " ";  // 5 4 3 2 1
}

// 插入迭代器
std::vector<int> dest;
std::copy(v.begin(), v.end(), std::back_inserter(dest));

常用算法速查

#include <algorithm>
#include <numeric>

std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

// 查找
auto it = std::find(v.begin(), v.end(), 5);
auto it2 = std::find_if(v.begin(), v.end(), [](int x){ return x > 4; });
bool has5 = std::binary_search(v.begin(), v.end(), 5);  // 需要有序

// 统计
int cnt = std::count(v.begin(), v.end(), 1);  // 2
int cnt2 = std::count_if(v.begin(), v.end(), [](int x){ return x > 4; });

// 排序
std::sort(v.begin(), v.end());
std::stable_sort(v.begin(), v.end());  // 保持相等元素的相对顺序
std::partial_sort(v.begin(), v.begin() + 3, v.end());  // 只排前3个

// 变换
std::transform(v.begin(), v.end(), v.begin(), [](int x){ return x * 2; });

// 数值
int sum = std::accumulate(v.begin(), v.end(), 0);
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>{});

// 集合操作（需要有序）
std::vector<int> a = {1,2,3,4}, b = {3,4,5,6}, result;
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                      std::back_inserter(result));  // {3, 4}

C++20 Ranges

#include <ranges>
#include <algorithm>

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

// 管道语法，惰性求值
auto result = v
    | std::views::filter([](int x) { return x % 2 == 0; })
    | std::views::transform([](int x) { return x * x; })
    | std::views::take(3);

for (int x : result) std::cout << x << " ";  // 4 16 36

// ranges 算法（不需要 begin/end）
std::ranges::sort(v);
auto it = std::ranges::find(v, 5);
std::ranges::reverse(v);

// 常用 views
std::views::iota(1, 10)          // 生成 1..9
std::views::repeat(42, 5)        // 重复 5 次 42（C++23）
std::views::zip(v1, v2)          // 打包两个范围（C++23）
std::views::enumerate(v)         // 带索引（C++23）
std::views::chunk(v, 3)          // 分块（C++23）

关键认知

STL 的设计哲学是算法与容器解耦，通过迭代器连接。vector 是 99% 场景的默认选择；C++20 Ranges 让算法组合变得优雅。选容器时先考虑访问模式，再考虑插入/删除模式。