STL 标准模板库

STL 是 C++ 的标准库，提供通用的数据结构和算法。

容器（Containers）

顺序容器

#include <vector>
#include <list>
#include <deque>

std::vector<int> vec = {1, 2, 3};   // 动态数组
std::list<int> lst = {1, 2, 3};     // 双向链表
std::deque<int> deq;                 // 双端队列

关联容器

#include <set>
#include <map>

std::set<int> s;                    // 有序集合
std::map<std::string, int> m;       // 有序映射
m["apple"] = 5;

// C++11 新增
std::unordered_map<std::string, int> um;  // 哈希表实现

迭代器（Iterators）

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

// 遍历
for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

// 范围 for（C++11）
for (auto &x : vec) {
    std::cout << x << " ";
}

算法（Algorithms）

#include <algorithm>

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

// 排序
std::sort(v.begin(), v.end());

// 查找
auto it = std::find(v.begin(), v.end(), 4);

// 反转
std::reverse(v.begin(), v.end());

面试题

vector 的扩容机制

• 容量不足时，通常扩容为原来的 1.5~2 倍
• 重新分配内存，拷贝元素

map 和 unordered_map 的区别

特性	map	unordered_map
底层实现	红黑树	哈希表
查找效率	O(log n)	O(1) 平均
元素有序	是	否