标准模板库

标准模板库（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等

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

#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;
}

迭代器[编辑 | 编辑源代码]

迭代器是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等

例如：

#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;
}

设计理念[编辑 | 编辑源代码]

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标准引入了范围库等重大改进

实际应用示例[编辑 | 编辑源代码]

统计单词频率[编辑 | 编辑源代码]

#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";
    }
}

使用STL实现快速排序[编辑 | 编辑源代码]

#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);
}

性能考虑[编辑 | 编辑源代码]

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替代组件

学习资源[编辑 | 编辑源代码]

在线资源[编辑 | 编辑源代码]

参见[编辑 | 编辑源代码]

C++
泛型编程
[[模板 (