MoonL

概述#

STL（Standard Template Library）是 C++ 标准库中基于模板的容器、迭代器、算法、仿函数、适配器、空间配置器的集合。

• 高复用：同一套组件适配多种类型。
• 高性能：如 vector 连续内存、sort 优化实现。
• 可移植：符合标准的编译器均提供。

六大组件#

迭代器#

广义指针：可解引用、可前进，使算法与容器解耦。

每个容器定义 iterator / const_iterator，以及 C++11 起的 cbegin() 等。

序列式容器#

1
std::vector<int> v = {1, 2, 3};
2
v.reserve(100);       // 只扩容量，不改变 size
3
v.push_back(4);
4
v.shrink_to_fit();    // 请求归还多余容量（非强制）

关联式容器#

底层多为红黑树（平衡二叉搜索树），有序，查找 O(log n)。

1
std::map<std::string, int> scores;
2
scores["alice"] = 90;
3

4
std::set<int> s = {3, 1, 2};  // 自动排序去重（set 内唯一）

自定义类型作键需提供严格弱序比较（或 C++20 透明比较 / 自定义哈希用于 unordered_*）。

无序关联容器（补充）#

unordered_map / unordered_set：哈希表，平均 O(1) 查找，无序。

容器适配器#

1
std::stack<int> st;
2
st.push(1);
3
st.top();

算法#

通过迭代器区间 [first, last) 操作，与容器分离。

• 质变：修改区间内容 — copy, fill, sort, remove, transform …
• 非质变：只读 — find, count, for_each（若仿函数写元素则例外）

1
std::vector<int> v = {3, 1, 4, 1, 5};
2
std::sort(v.begin(), v.end());
3
auto it = std::find(v.begin(), v.end(), 4);

仿函数（函数对象）#

重载 operator() 的类型，可带状态：

1
struct Greater {
2
    bool operator()(int a, int b) const { return a > b; }
3
};
4
std::sort(v.begin(), v.end(), Greater{});
5
// 或 std::sort(v.begin(), v.end(), std::greater<int>{});

谓词：返回 bool 的仿函数，如 std::less、std::equal_to。

内建仿函数：plus, minus, multiplies, less, logical_and 等。

适配器#

• stack / queue / priority_queue：容器适配器。
• reverse_iterator、insert_iterator：迭代器适配器。
• bind1st / bind2nd（C++11 前常用，现多被 lambda 与 std::bind 替代）。

容器选择策略#

C++11 相关（与 STL 配合）#

• auto、nullptr、范围 for：for (auto& x : v)
• Lambda：std::sort(v.begin(), v.end(), [](int a, int b){ return a > b; });
• 移动语义：push_back(std::move(x)) 减少拷贝