编辑“︁标准模板库”︁

{{NoteTA
|G1=IT
}}

'''标准模板库'''（Standard Template Library，简称'''STL'''）是[[C++]]编程语言的标准库中的一个重要组成部分，提供了一系列模板化的[[容器]]、[[算法]]、[[迭代器]]和[[函数对象]]。STL最初由Alexander Stepanov在[[惠普实验室]]开发，后于1994年被纳入C++标准库。

== 概述 ==

STL是[[泛型编程]]的典范，它通过[[模板 (编程)|模板]]机制实现了数据结构和算法的通用性。STL的核心思想是将数据结构和算法分离，通过迭代器作为两者之间的桥梁。这种设计使得算法可以独立于具体的数据结构工作，大大提高了代码的复用性。

STL的主要组成部分包括：
* '''容器'''：用于存储数据的模板类
* '''算法'''：作用于容器上的模板函数
* '''迭代器'''：访问容器元素的通用接口
* '''函数对象'''：行为类似函数的对象
* '''适配器'''：修改容器或函数对象接口的组件

== 核心组件 ==

=== 容器 ===

STL容器分为两大类：'''序列容器'''和'''关联容器'''。

==== 序列容器 ====
* '''[[std::vector]]'''：动态数组，支持快速随机访问
* '''[[std::list]]'''：双向链表，支持高效插入/删除
* '''[[std::deque]]'''：双端队列，支持首尾高效插入/删除
* '''[[std::array]]'''（C++11）：固定大小数组
* '''[[std::forward_list]]'''（C++11）：单向链表

==== 关联容器 ====
* '''[[std::set]]'''：唯一键的集合，按照键排序
* '''[[std::multiset]]'''：键可重复的集合，按照键排序
* '''[[std::map]]'''：键值对的集合，按照键排序
* '''[[std::multimap]]'''：键可重复的键值对集合，按照键排序
* '''[[std::unordered_set]]'''（C++11）：哈希集合
* '''[[std::unordered_map]]'''（C++11）：哈希映射

=== 算法 ===

STL提供了约100种算法，主要分为以下几类：

* '''非修改序列操作'''：如for_each、find、count等
* '''修改序列操作'''：如copy、transform、replace等
* '''排序及相关操作'''：如sort、stable_sort、binary_search等
* '''数值算法'''：如accumulate、inner_product等

这些算法通过迭代器与容器交互，不依赖于具体容器类型。例如：

<syntaxhighlight lang="cpp">
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {5, 3, 1, 4, 2};
    
    // 排序
    std::sort(v.begin(), v.end());
    
    // 查找
    auto it = std::find(v.begin(), v.end(), 3);
    
    // 反转
    std::reverse(v.begin(), v.end());
    
    return 0;
}
</syntaxhighlight>

=== 迭代器 ===

迭代器是STL的核心概念之一，它提供了访问容器元素的统一接口。STL定义了五种迭代器类别：

1. '''输入迭代器'''：只读，单向
2. '''输出迭代器'''：只写，单向
3. '''前向迭代器'''：读写，单向
4. '''双向迭代器'''：读写，双向移动
5. '''随机访问迭代器'''：读写，支持随机访问

迭代器使得算法可以独立于容器工作。例如，std::sort需要随机访问迭代器，因此可以用于vector但不能用于list（list提供了自己的sort成员函数）。

=== 函数对象 ===

函数对象（也称为仿函数）是重载了operator()的类对象，可以像函数一样被调用。STL提供了多种预定义的函数对象：

* '''算术运算'''：plus, minus, multiplies等
* '''比较运算'''：equal_to, not_equal_to, greater, less等
* '''逻辑运算'''：logical_and, logical_or, logical_not等

例如：

<syntaxhighlight lang="cpp">
#include <functional>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // 使用greater函数对象进行降序排序
    std::sort(v.begin(), v.end(), std::greater<int>());
    
    return 0;
}
</syntaxhighlight>

== 设计理念 ==

STL的设计基于以下几个关键理念：

1. '''泛型编程'''：通过模板实现算法和数据结构的通用性
2. '''效率优先'''：STL的实现通常非常高效，接近手工编写的代码
3. '''正交性'''：组件可以自由组合，互不干扰
4. '''可扩展性'''：用户可以定义自己的容器、算法和迭代器，与STL无缝集成

== 历史发展 ==

* '''1994年'''：STL首次被纳入C++标准草案
* '''1998年'''：成为C++98标准的一部分
* '''2003年'''：C++03标准对STL进行了小规模修订
* '''2011年'''：C++11标准增加了多个新容器和算法
* '''2017年'''：C++17标准进一步扩展了STL功能
* '''2020年'''：C++20标准引入了范围库等重大改进

== 实际应用示例 ==

=== 统计单词频率 ===

<syntaxhighlight lang="cpp">
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
#include <cctype>

void count_words() {
    std::map<std::string, int> word_count;
    std::string word;
    
    while (std::cin >> word) {
        // 转换为小写
        std::transform(word.begin(), word.end(), word.begin(),
                      [](unsigned char c) { return std::tolower(c); });
        // 统计词频
        ++word_count[word];
    }
    
    // 输出结果
    for (const auto& pair : word_count) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }
}
</syntaxhighlight>

=== 使用STL实现快速排序 ===

<syntaxhighlight lang="cpp">
#include <vector>
#include <algorithm>
#include <iterator>

template<typename RandomIt>
void quick_sort(RandomIt first, RandomIt last) {
    if (first == last) return;
    
    auto pivot = *std::next(first, std::distance(first, last) / 2);
    auto middle1 = std::partition(first, last, 
                                 [pivot](const auto& em) { return em < pivot; });
    auto middle2 = std::partition(middle1, last, 
                                 [pivot](const auto& em) { return !(pivot < em); });
    
    quick_sort(first, middle1);
    quick_sort(middle2, last);
}
</syntaxhighlight>

== 性能考虑 ==

STL组件的性能通常很高，但使用时仍需注意：

1. 容器选择影响性能：
   * vector适合随机访问和尾部操作
   * list适合频繁的中间插入/删除
   * deque适合首尾操作
   * 关联容器适合查找操作

2. 算法复杂度：
   * 如std::sort是O(N log N)
   * std::find是O(N)
   * std::binary_search是O(log N)但要求已排序

3. 内存分配：
   * 某些操作可能导致容器重新分配内存
   * 可预先reserve()以减少重新分配

== C++11/14/17/20中的改进 ==

* '''C++11'''：
  - 新增容器：array, forward_list, unordered_set/map等
  - 移动语义支持
  - 基于范围的for循环
  - lambda表达式

* '''C++14'''：
  - 泛型lambda
  - 改进的constexpr

* '''C++17'''：
  - std::optional, std::variant, std::any
  - 并行算法
  - 文件系统库

* '''C++20'''：
  - 范围库(Ranges)
  - 概念(Concepts)
  - std::span

== 扩展与替代方案 ==

1. '''Boost库'''：提供了许多STL的扩展组件
2. '''EASTL'''：Electronic Arts开发的STL替代实现
3. '''Folly'''：Facebook开发的C++库，包含STL扩展
4. '''Abseil'''：Google开发的C++库，包含STL替代组件

== 学习资源 ==

=== 推荐书籍 ===
* 《STL源码剖析》 - 侯捷
* 《Effective STL》 - Scott Meyers
* 《C++标准库》 - Nicolai M. Josuttis

=== 在线资源 ===
* [https://en.cppreference.com/w/ cppreference.com]
* [https://www.cplusplus.com/reference/ cplusplus.com]
* C++标准文档

== 参见 ==
* [[C++]]
* [[泛型编程]]
* [[模板 (