1 什么是STL

STL（Standard Template Library）是 C++ 标准库的重要组成部分，提供了高效、通用、可复用的数据结构和算法。STL 的核心设计思想是泛型编程（Generic Programming），即通过模板机制实现算法与容器的解耦，提高代码的复用性和可维护性。

STL 主要包括以下六大组件：

1. 容器（Containers）

2. 算法（Algorithms）

3. 迭代器（Iterators）

4. 适配器（Adapters）

5. 分配器（Allocators）

6. 仿函数（Functors）

2 STL 全解析

2.1 STL 容器

STL 容器分为三大类：顺序容器、关联容器、无序关联容器。（容器适配器 作为补充，常用于特定场景）

2.1.1 顺序容器（Sequence Containers）

2.1.2 关联容器（Associative Containers）

2.1.3 无序关联容器（Unordered Associative Containers，C++11）

2.1.4 容器适配器（Container Adapters）

2.1.5 容器用法举例

vector 示例：

#include <vector>
#include <iostream>

// Google风格代码，详细注释
int main() {
  // 创建一个整型vector并初始化
  std::vector<int> nums = {1, 3, 5, 7};

  // 插入新元素
  nums.push_back(9);

  // 随机访问
  std::cout << "第一个元素: " << nums[0] << std::endl;

  // 遍历
  for (const int& num : nums) {
    std::cout << num << " ";
  }
  std::cout << std::endl;
  return 0;
}

map 示例：

#include <map>
#include <string>
#include <iostream>

int main() {
  std::map<std::string, int> score;
  score["Alice"] = 90;
  score["Bob"] = 85;

  // 查找
  if (score.find("Alice") != score.end()) {
    std::cout << "Alice得分: " << score["Alice"] << std::endl;
  }
  return 0;
}

2.2 STL 算法

STL 提供了 60+ 种通用算法，主要包括：

• 非变易算法（如 find、count、for_each）

• 变易算法（如 sort、reverse、replace）

• 排序与查找算法（如 sort、binary_search、lower_bound）

• 数值算法（如 accumulate、adjacent_difference）

算法与容器解耦，依赖迭代器操作容器。

sort 示例：

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

int main() {
  std::vector<int> v = {4, 2, 8, 6};
  // 升序排序
  std::sort(v.begin(), v.end());
  for (const int& n : v) std::cout << n << " ";
  std::cout << std::endl;
  return 0;
}

自定义排序：

std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });  // 降序

2.3 STL 迭代器

STL 迭代器是连接容器与算法的桥梁，类似指针，支持不同类型容器的遍历和操作。

迭代器分类：

1. 输入迭代器（InputIterator）

2. 输出迭代器（OutputIterator）

3. 前向迭代器（ForwardIterator）

4. 双向迭代器（BidirectionalIterator）

5. 随机访问迭代器（RandomAccessIterator）

示例：

#include <list>
#include <iostream>

int main() {
  std::list<int> l = {1, 2, 3};
  for (std::list<int>::iterator it = l.begin(); it != l.end(); ++it) {
    std::cout << *it << " ";
  }
  std::cout << std::endl;
  return 0;
}

2.4 STL 适配器

stack 示例：

#include <stack>
#include <iostream>

int main() {
  std::stack<int> stk;
  stk.push(1);
  stk.push(2);
  std::cout << "栈顶元素: " << stk.top() << std::endl;
  stk.pop();
  return 0;
}

queue 示例：

#include <queue>
#include <iostream>

int main() {
  std::queue<int> q;
  q.push(1);
  q.push(2);
  std::cout << "队首元素: " << q.front() << std::endl;
  q.pop();
  return 0;
}

priority_queue 示例：

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

int main() {
  std::priority_queue<int> pq;
  pq.push(3);
  pq.push(1);
  pq.push(5);
  std::cout << "最大元素: " << pq.top() << std::endl;
  pq.pop();
  return 0;
}

2.5 STL 分配器（Allocators）

分配器是 STL 的内存管理机制，默认为 std::allocator<T>，可自定义以适应特殊内存需求。大多数场景无需关心，了解其存在即可。

2.6 STL 仿函数与 Lambda 表达式

仿函数是重载了 operator() 的类或结构体，可作为自定义比较器或算法参数。

示例：

struct Greater {
  bool operator()(int a, int b) const { return a > b; }
};

std::set<int, Greater> s;  // 降序排列

Lambda 与算法结合：

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

int main() {
  std::vector<int> v = {1, 2, 3, 4};
  int cnt = std::count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
  std::cout << "偶数个数: " << cnt << std::endl;
  return 0;
}

3 STL 与传统方法对比

手写链表 vs. STL::list：

• 手写链表需手动管理节点和内存，易出错，代码冗长。

• STL::list 自动管理节点和内存，接口统一，异常安全，极大提升开发效率。

手写排序 vs. std::sort：

• 手写排序算法易出错，效率难以保证。

• STL::sort 底层实现高效，支持自定义比较器，性能极佳。

手写哈希表 vs. unordered_map：

• 手写哈希表需处理哈希冲突、扩容等复杂细节。

• STL::unordered_map 内部已做优化，接口友好，效率高。

4 STL 进阶技巧

1. 自定义类型作为 key 的注意事项

   • map/set 需提供 < 运算符重载或自定义比较器。

   • unordered_map 需自定义哈希函数和相等比较器。

2. STL 容器非线程安全

   • 多线程访问需自行加锁。

3. 性能优化

   • vector 预分配空间：reserve()

   • map/set 插入效率为 O(log⁡n)，unordered_map 为均摊 O(1)

4. 内存管理

   • STL 容器会自动析构元素，但存储指针时需自行释放内存。

5. 容器嵌套

   • 支持如 vector<map<string, int>> 等复杂嵌套结构。

5 STL 适用场景

• 绝大多数 C++ 开发场景都应优先使用 STL 容器和算法。

• 性能极端要求或特殊需求可考虑自定义实现。

• 代码可读性、可维护性、健壮性显著提升。