STL 源码剖析 | 第1章：概论

STL 是一套程序库

1、STL 概论

1、从子程序、程序、函数、类别，到函数库、类别库、各种组件，从结构化设计、模块化设计、面向对象设计，到模式的归纳整理

为的就是 复用性 的提升

复用性 必须建立在某种标准之上 —— 不论是 语言层次的标准，或 数据交换的标准，或 通讯协议的标准

2、STL 的价值在于 两方面。就低层次而言，STL 带给我们一套 极具实用价值的零部件，以及 一个整合的组织；STL 还带给我们一个高层次的、以泛型思维 为基础的、系统化的、条理分明的 “软件组件分类学”

以抽象概念 为主体而非以实际类 为主体的结构，形成了一个严谨的接口标准。在此接口之下，任何组件都有最大的独立性，并以 迭代器（iterator）胶合起来，或以 配接器（adapter）互相配接，或以 仿函数（functor）动态选择某种策略

2、STL 六大组件 功能与运用

1. 容器（containers）： 各种数据结构，如 vector, list, deque, set, map, … 用来存放数据。从实现的角度来看，STL 容器是一种 类模板 template <typename T> class MyClass
2. 算法： 各种常用算法如 sort, search, copy, erase…
3. 迭代器（iterators）： 扮演 容器与算法之间的胶合剂，是所谓的 “泛型指针（能够 指向任何类型数据的指针，通常是没有具体类型限制的指针 void*，void* 指针常用于函数参数，允许该函数接收不同类型的数据。要解引用一个 void* 指针，必须先将它强制转换为具体类型的指针：*(static_cast<int*>(p))）”，共有五种类型，以及 其它衍生变化
   从实现的角度来看，迭代器是一种将 operator*, operator->, operator++, operator-- 等指针相关操作予以重载的 类模板。所有 STL 容器都附带有自己专属的迭代器——只有容器设计者 才知道如何遍历自己的元素。原生指针（后来为了 增强指针操作的安全性和简化内存管理 使用智能指针） 也是一种迭代器
4. 仿函数（functors）： 行为类似函数，可作为算法的某种策略。从实现的角度来看, 仿函数是一种重载了 operator() 的 类 或 模板类。一般函数指针 可视为狭义的仿函数
5. 配接器（adapters）： 一种用来修饰 容器 或 仿函数 或 迭代器接口 的东西。例如，STL 提供的 queue 和 stack，虽然看似容器，其实只能算是一种容器配接器，因为它们的底部完全借助 deque。所有操作都由底层的 deque 供应。改变 functor 接口者，称为 function adapter; 改变 container 接口者，称为 container adapter; 改变 iterator 接口者，称为 iterator adapter
6. 配置器（allocators）： 负责空间配置与管理。从实现的角度来看，配置器是一个实现了 动态空间配置、空间管理、空间释放的 模板类

目前所有的 C++ 编译器 一定支持有一份 STL。在相应的各个 C++ 头文件（headers）中。STL 并非以二进制代码 面貌出现，而是 以源代码面貌供应。按 C++ Standard 的规定，所有标准头文件都不再有扩展名

3、语法

3.1 临时对象的产生和应用

刻意制造 临时对象的方法是，在型别名称之后 直接加一对小括号，并可指定初值，例如 Shape(3,5) 或 int(8)，其意义相当于 调用相应的 constructor 且 不指定对象名称。STL 最常将此技巧应用于 仿函数 与 配置器

3.2 静态常量整数成员 在 class 内部直接初始化

template <typename T>
class testClass {
public: // expedientstatic const int _datai = 5;static const long _datal = 3L;static const char _datac = 'c';
};

3.3 increment / decrement / dereference 操作符

increment / decrement / dereference 操作符在迭代器的实现上 占有非常重要的地位，因为任何一个迭代器 都必须体现出前进（increment, operator++) 和 取值（dereference, operator*）功能，前者还分为 前置式（prefix）和后置式（postfix）两种

class INT
{friend ostream& operator<<(ostream& os, const INT& i);public:INT(int i) : m_i(i) { };// prefix : increment and then fetchINT& operator++(){++(this->m_i); // 随着 class 的不同，该行应该有不同的操作return *this;}// postfix : fetch and then incrementconst INT operator++(int){INT temp = *this;++(*this);return temp;}// prefix : decrement and then fetchINT& operator--(){--(this->m_i); // 随着 class 的不同，该行应该有不同的操作return *this;}// postfix : fetch and then decrementconst INT operator--(int){INT temp = *this;--(*this);return temp;}// dereferenceint& operator*() const{return (int)m_i;// 以上转换操作告诉编译器，你确实要将 const int 转为 non-const lvalue.// 如果没有这样明白地转型，有些编译器会给你警告，有些更严格的编译器会视为错误}private:int m_i;
};ostream& operator<<(ostream& os, const INT& i)
{os << '[' << i.m_i << ']';return os;
}

return (int)m_i;
// 以上转换操作告诉编译器，你确实要将 const int 转为 non-const lvalue.
// 如果没有这样明白地转型，有些编译器会给你警告，有些更严格的编译器会视为错误

const 成员函数：当 在成员函数的声明后面加上 const 关键字时，表示这个函数 不能修改类中的成员变量。因此，在 const 成员函数内部，类的成员变量会被视为 const，即使 它们在类的定义中不是 const 的。也就是说，m_i 在函数 int& operator*() const 内被视为 const int

返回左值引用：函数 int& operator*() const 的返回类型是 int&，表示返回的是一个左值引用。左值引用是 指向某个内存位置的引用，允许通过 该引用去修改该位置存储的值。但是由于该函数被标记为 const，如果直接返回 m_i，编译器会认为 试图返回一个 const 引用，并可能会报错或给出警告，因为 不能从 const 成员函数返回非 const 引用

3.4 前闭后开区间表示法 [ )

任何一个 STL 算法，都需要 获得由一对迭代器（泛型指针）所标示的区间，用以表示操作范围。这一对迭代器所标示的是个 前闭后开区间，以 [first, last) 表示

3.5 function call 操作符（operator()）

1、函数调用操作 也可以被重载

许多 STL 算法都提供了 两个版本，一个用于一般状况（例如 排序时 以递增方式排列), 一个用于特殊状况（例如排序时 由使用者指定以何种特殊关系 进行排列）。像这种情况，需要用户 指定某个条件或某个策略

过去 C 语言时代，欲将 函数当做参数传递，唯有通过函数指针 才能达成

int fcmp( const void* elem1, const void* elem2);qsort(ia, sizeof(ia)/sizeof(int), sizeof(int), fcmp);

但是函数指针 有缺点，最重要的是 它无法持有自己的状态（所谓 局部状态），也无法达到 组件技术中的可适配性 ——也就是无法 再将某些修饰条件加诸于其上 而改变其状态

#include <iostream>int applyDiscount(int price) {return price * 0.9;  // 10% 折扣
}int main() {int (*discountFunc)(int) = applyDiscount;  // 定义函数指针int price = 100;std::cout << "Price after discount: " << discountFunc(price) << std::endl; // 输出 90return 0;
}

函数指针 discountFunc 指向了 applyDiscount，并且我们通过调用 discountFunc(price) 来应用折扣。这种方法简单直接，但是存在以下局限性：

1. 无法持有自己的状态：函数指针 只能指向函数，但无法拥有 函数的内部状态。例如，如果 想动态改变折扣的比例（例如从10% 变化为 20%），那么你无法在函数指针中 实现这种状态持有。所有状态变化 只能通过外部逻辑控制
2. 无法扩展功能：假设 想在应用折扣之前，先执行 某些额外的操作（例如记录日志、统计调用次数等），使用函数指针 是无法做到的，因为函数指针 仅仅指向某个单一的函数，并且无法附加额外的逻辑

2、通过闭包或仿函数解决局限性
1】使用闭包（Lambda表达式）
通过闭包，可以创建 一个带有状态的函数，同时 还可以动态修改它的行为：

#include <iostream>
#include <functional>int main() {int discountRate = 10;  // 初始折扣率为10%// 使用闭包来创建带有状态的函数auto discountFunc = [discountRate](int price) mutable {return price * (1 - discountRate / 100.0);};int price = 100;std::cout << "Price after discount: " << discountFunc(price) << std::endl; // 输出 90// 修改闭包的状态（折扣率）discountRate = 20;discountFunc = [discountRate](int price) mutable {return price * (1 - discountRate / 100.0);};std::cout << "Price after discount: " << discountFunc(price) << std::endl; // 输出 80return 0;
}

discountFunc 是一个闭包，封装了折扣率 discountRate 的状态。可以在后续代码中 通过修改折扣率 来动态改变折扣函数的行为，避免了 函数指针无法保存状态的缺陷

Lambda 表达式基本结构

[capture](parameters) mutable -> return_type { body }

1）[capture]（捕获列表）
捕获列表 用于 指定 lambda 表达式可以“捕获”哪些外部变量，也就是说，可以使用 lambda 表达式之外的变量。在这段代码中，捕获列表是 [discountRate]，表示 discountRate 这个外部变量将被捕获并可以在 lambda 表达式中使用

具体捕获方式包括：
1、按值捕获（[discountRate]）：捕获 discountRate 的当前值，并在 lambda 表达式内部 保留这个值的副本。即使 discountRate 在外部环境中改变，lambda 中的 discountRate 也不会变化，因为它是按值捕获的
2、按引用捕获（[&discountRate]）：捕获 discountRate 的引用。如果外部的 discountRate 值发生变化，lambda 表达式中的 discountRate 也会随之变化
3、[=] 或 [&]：捕获所有外部变量，分别按值或按引用捕获。[=] 按值捕获所有外部变量，[&] 按引用捕获所有外部变量
在代码中，[discountRate] 表示按值捕获变量 discountRate

2）mutable
默认情况下，lambda 表达式中的捕获变量 在函数体内是不可修改的，尤其是 按值捕获时，lambda 表达式会把捕获的变量视为 const。因此，如果想在 lambda 内部修改按值捕获的变量，需要加上 mutable 关键字
discountRate 是按值捕获的，但通过使用 mutable 关键字，你可以在 lambda 内部修改 discountRate 的值（即使是在按值捕获的情况下）。不过在这段代码中，mutable 虽然使捕获的变量可修改，但实际并没有修改 discountRate

3）auto
auto 关键字用于 自动推导类型。在这里，auto discountFunc 表示 discountFunc 的类型 将由编译器根据右边的 lambda 表达式自动推导。lambda 表达式 实际上 会生成一个匿名的闭包类型（通常称为 lambda closure），可以用 auto 来持有它

2】用仿函数（Functor）
另一种方式是 使用仿函数，即通过重载函数 调用运算符 operator() 来定义一个带有状态的对象：

#include <iostream>class Discount {
public:Discount(int rate) : discountRate(rate) {}// 重载函数调用运算符，变成仿函数int operator()(int price) const {return price * (1 - discountRate / 100.0);}private:int discountRate;  // 折扣率
};int main() {Discount discountFunc(10);  // 调用 Discount 的构造函数，创建一个带有10%折扣的仿函数int price = 100;std::cout << "Price after discount: " << discountFunc(price) << std::endl;  // 输出 90，使用重载的调用运算符Discount discountFunc20(20);  // 创建一个带有20%折扣的仿函数std::cout << "Price after discount: " << discountFunc20(price) << std::endl;  // 输出 80return 0;
}

Discount 类是一个仿函数，它内部存储了折扣率。通过创建不同的 Discount 对象，我们可以灵活地应用不同的折扣率，而且还可以在同一个对象中保持状态。这种方式相比函数指针更具扩展性和灵活性

2、STL 算法的特殊版本 所接受的所谓“条件”或 “策略”或 “一整组操作”，都以仿函数形式呈现。所谓仿函数（functor）就是 使用起来像函数一样的东西。如果 针对某个 class 进行 operator() 重载，它就成为一个仿函数

// file: lfunctor.cpp 
#include <iostream> 
using namespace std;// 由于将 operator() 重载了，因此 plus 成了一个仿函数 
template <class T> 
struct plus {     T operator()(const T& x, const T& y) const { return x + y; } 
};// 由于将 operator() 重载了，因此 minus 成了一个仿函数 
template <class T> 
struct minus {     T operator()(const T& x, const T& y) const { return x - y; } 
};int main() 
{     // 以下产生仿函数对象     plus<int> plusobj; minus<int> minusobj;// 以下使用仿函数，就像使用一般函数一样 cout << plusobj(3,5) << endl; // 8 cout << minusobj(3,5) << endl; // -2// 以下直接产生仿函数的临时对象（第一对小括号），并调用之（第二对小括号） cout << plus<int>()(43,50) << endl; // 93 cout << minus<int>()(43,50) << endl; // -7
}