C++程序设计语言标准库：STL概述

一、前言

本专题是作者为了加强C++与数据结构的学习而作的记录，我所使用的STL版本为SGI STL，这里引用侯杰的《STL源码刨析》中的序言：

STL，虽然是一套程序库（library），却不只是一般印象中的程序库，而是一个有着划时代意义，背后拥有先进技术与深厚理论的产品。说它是产品也可以，说它是规格也可以，说是软件组件技术发展史上的一个大突破点，它也当之无愧。
1.1 STL 概论
长久以来，软件界一直希望建立一种可重复运用的东西，以及一种得以制造出“可重复运用的东西”的方法，让工程师/程序员的心血不致于随时间迁移、人事异动、私心欲念、人谋不减而烟消云散。从子程序（subroutines）、程序（procedures）、函数（functions）、类别（classes），到函数库（function libraries）、类别库（class libraries）、各种组件（components），从结构化设计、模块化设计、面向对象（object oriented）设计，到模式（patterns）的归纳整理，无一不是软件工程的漫漫奋斗史。为的就是复用性（reusability）的提升。
复用性必须建立在某种标准之上——不论是语言层次的标准，或数据交换的标准，或通讯协议的标准。但是，在许多工作环境下，就连软件开发最基本的数据结构（data structures）和算法（algorithms）都还迟迟未能有一套标准。大量程序员被迫从事大量重复的工作，竟是为了完成前人早已完成而自己手上并未拥有的程序代码。这不仅是人力资源的浪费，也是挫折与错误的来源。为了建立数据结构和算法的一套标准，并且降低其间的耦合(coupling)关系以提升各自的独立性、弹性、交互操作性(相互合作性，interoperability)，C++ 社群里诞生了 STL。
STL 的价值在于两方面。就低层次而言，STL 带给我们一套极具实用价值的零部件，以及一个整合的组织。这种价值就像 MFC 或 VCL 之于 Windows 软件开发过程所带来的价值一样，直接而明朗，令大多数人有最立即明显的感受。
除此之外，STL 还带给我们一个高层次的、以泛型思维(Generic Paradigm)为基础的、系统化的、条理分明的“软件组件分类学(components taxonomy)”。从这个角度来看，STL 是一个抽象概念库(library of abstract concepts)，这些“抽象概念”包括最基础的 Assignable(可被赋值)、Default Constructible(不需任何参数就可构造)、Equality Comparable(可判断是否等同)、LessThan Comparable(可比较小)、Regular(正规)…高阶一点的概念则包括 Input Iterator(具输入功能的迭代器)、Output Iterator(具输出功能的迭代器)、
Forward Iterator(单向迭代器)、Bidirectional Iterator(双向迭代器)、Random Access Iterator(随机存取迭代器)、Unary Function(一元函数)、Binary Function(二元函数)、Predicate(传回真假值的一元判断式)、Binary Predicate(传回真假值的二元判断式)…更高阶的概念包括 sequence container(序列式容器)、associative container(关联式容器)…

STL 的创新价值便在于具体叙述了上述这些抽象概念，并加以系统化。

换句话说，STL 所实现的，是依据泛型思维架设起来的一个概念结构。这个以抽象概念(abstract concepts)为主体
而非以实际类(classes)为主体的结构，形成了一个严谨的接口标准。在此接口之下，任何组件都有最大的独立性，
并以所谓迭代器(iterator)胶合起来，或以所谓配接器(adapter)互相配接，或以所谓仿函数(functor)动态选择某种
策略(policy 或 strategy)。

目前没有任何一种程序语言提供任何关键词(keyword)可以实质对应上述所谓的抽象概念。但是 C++ classes 允许
我们自行定义型别，C++ templates 允许我们将型别参数化，藉由两者结合并透过traits编程技法，形成了STL的绝佳温床.
关于STL的所谓软件组件分类学，以及所谓的抽象概念库，请参考[Austern98]——没有任何一本书籍在这方面说得比它更好、
更完善。

在正式开始之前，相信很多读者对C++的各种特性感到云里雾里的，为什么会有迭代器之类的这样那样的特性呢。其实例如像C++中的迭代器机制设计的一个重要目标就是为了让自定义的容器类能够像内置类型一样方便地进行元素访问和遍历。这种设计使得开发者可以编写出通用的算法，这些算法不依赖于具体的容器实现细节，而是通过迭代器来抽象化对容器元素的操作。一句话概括就是C++中的迭代器之类的特性就是为了使得自定义类也能像内置类型一样使用。
在C++中，许多语言特性都是基于内置的数据类型和运算符构建的，并且这些特性往往可以通过重载运算符或使用特定的关键字来扩展到用户自定义类型。下面是一些重要的C++特性和它们所对应的内置元素：### 1. 迭代器与运算符
如你提到的，迭代器通过重载`++`（前缀和后缀）、`*`（解引用）、`->`（成员访问）等运算符来模拟指针的行为，从而提供了一种统一的方式来遍历容器中的元素。### 2. 类型转换与构造函数/析构函数
- **隐式类型转换**：通过单参数构造函数或转换操作符实现。
- **显式类型转换**：使用`explicit`关键字修饰构造函数以避免隐式类型转换。
- **用户定义的转换**：通过定义转换构造函数和类型转换操作符来允许对象之间的转换。### 3. 内存管理与运算符
- `new` 和 `delete`：用于动态分配和释放内存。
- `new[]` 和 `delete[]`：用于数组形式的动态内存分配和释放。### 4. 输入输出流与运算符
- `<<` 和 `>>`：通常用于重载输入输出流操作符，以便能够方便地将数据写入输出流（如`cout`）或从输入流（如`cin`）读取数据。### 5. 关系运算符
- `==`, `!=`, `<`, `>`, `<=`, `>=`：用于比较两个值或对象的大小关系，可以被重载以适应用户定义类型的比较逻辑。### 6. 算术运算符
- `+`, `-`, `*`, `/`, `%`：基本算术运算，同样可以被重载以支持用户定义类型的操作。### 7. 赋值运算符
- `=`：默认情况下会执行浅拷贝，但如果需要深拷贝或其他行为，则需要重载赋值运算符。### 8. 智能指针与RAII
- `std::unique_ptr`, `std::shared_ptr`, `std::weak_ptr`：智能指针提供了自动内存管理功能，遵循资源获取即初始化（RAII）原则，帮助避免内存泄漏问题。### 9. 异常处理与关键字
- `try`, `catch`, `throw`：用于异常处理机制，使得程序能够在发生错误时进行适当的恢复或清理工作。### 10. 模板与泛型编程
- 模板是C++的一种特性，它允许编写与类型无关的代码，适用于任何类型的数据。模板不仅限于函数模板，还包括类模板。### 11. Lambda表达式
- Lambda表达式是一种匿名函数，可以直接在代码中定义并使用，极大地简化了算法中的小函数定义过程。### 12. 命名空间
- `namespace`：用于组织代码结构，防止命名冲突。### 13. 友元函数和友元类
- `friend`关键字：用来指定某个函数或类可以访问另一个类的私有成员。总而言之，C++中的这些特性都是为了解决C语言存在的一些问题，通过上述这些特性，C++提供了丰富的工具集来构建复杂而高效的程序。下面是对 **STL（Standard Template Library，标准模板库）** 的组成部分及其实现方式的详细描述：---### 1. **容器（Containers）**
- **定义**：- 容器是用来存储和管理数据的数据结构。- 常见的容器包括 `vector`、`list`、`deque`、`set`、`map` 等。
- **实现**：- 从实现角度看，容器是 **类模板（class template）**。- 容器类模板可以根据不同的数据类型实例化，例如 `vector<int>` 或 `vector<string>`。
- **特点**：- 容器是 STL 中体积最大的部分，类似于冰山在海面下的部分（即大部分实现细节对用户不可见）。- 每种容器都有其特定的数据组织方式和性能特性。---### 2. **算法（Algorithms）**
- **定义**：- 算法是对数据进行操作的函数，例如排序、查找、复制、删除等。- 常见的算法包括 `sort`、`search`、`copy`、`erase` 等。
- **实现**：- 从实现角度看，算法是 **函数模板（function template）**。- 算法通过迭代器与容器交互，因此可以适用于多种容器。
- **特点**：- 算法与容器分离，通过迭代器连接，实现了高度的通用性。---### 3. **迭代器（Iterators）**
- **定义**：- 迭代器是容器与算法之间的桥梁，提供了一种统一的方式来访问容器中的元素。- 迭代器类似于“泛型指针”，支持指针相关的操作（如 `*`、`->`、`++`、`--` 等）。
- **实现**：- 从实现角度看，迭代器是 **类模板（class template）**。- 迭代器重载了指针相关的操作符（如 `operator*`、`operator->`、`operator++` 等）。
- **分类**：- 迭代器分为五种类型：输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机存取迭代器。- 每种容器都提供了自己专属的迭代器，因为只有容器设计者才知道如何遍历自己的元素。
- **特点**：- 原生指针（native pointer）也是一种迭代器。---### 4. **仿函数（Functors）**
- **定义**：- 仿函数是行为类似函数的对象，可以作为算法的策略（policy）。- 例如，`std::less` 是一个仿函数，用于比较两个元素的大小。
- **实现**：- 从实现角度看，仿函数是重载了 `operator()` 的类或类模板。- 仿函数可以是普通类，也可以是模板类。
- **特点**：- 普通函数指针可以视为狭义的仿函数。- 仿函数可以保存状态，因此比普通函数更灵活。---### 5. **配接器（Adapters）**
- **定义**：- 配接器是用来修饰容器、仿函数或迭代器接口的工具。- 例如，`stack` 和 `queue` 是容器配接器，它们的底层实现基于 `deque`。
- **分类**：- **容器配接器**：如 `stack`、`queue`，它们基于底层容器（如 `deque`）提供新的接口。- **仿函数配接器**：如 `std::bind`，用于改变仿函数的接口。- **迭代器配接器**：如 `std::reverse_iterator`，用于改变迭代器的行为。
- **实现**：- 配接器的实现技术复杂，需要根据具体需求逐一分析。---### 6. **配置器（Allocators）**
- **定义**：- 配置器负责内存空间的分配和管理。- 它为容器提供动态内存分配、管理和释放的功能。
- **实现**：- 从实现角度看，配置器是 **类模板（class template）**。- 配置器实现了动态内存分配的相关操作（如 `allocate`、`deallocate` 等）。
- **特点**：- 配置器是 STL 中较为底层的部分，通常对用户透明。- 用户可以通过自定义配置器来优化内存管理。---STL六大组件的交互关系：Container（容器） 通过 Allocator（内存分配器） 取得数据储存空间，Algorithm（算法） 通过 Iterator（迭代器） 存取 Container 内容，Functor（函数对象） 可以协助 Algorithm（算法） 完成不同的策略变化，Adapter（适配器） 可以修饰或套接 Functor。
在SGI STL中，头文件概略可分为五组：
- C++ 标准规范下的C头文件(无扩展名)，例如 cstdio, cstdlib, cstring...
- C++ 标准程序库中不属于STL范畴者，例如 stream, string...相关文件。
- STL 标准头文件（无扩展名），例如 vector, deque, list, map, algorithm, functional ...
- C++ Standard定案前，HP所规范的STL头文件，例如 vector.h, deque.h, list.h, map.h, algo.h, function.h ...
- SGI STL内部文件(STL真正实现于此)，例如 stl_vector.h, stl_deque.h, stl_list.h, stl_map.h, stl_algo.h, stl_function.h ...不同的编译器对 C++语言的支持程度不尽相同。作为一个希望具备广泛移植能力的程序库，SGI STL 准备了一个环境组态文件 `<stl_config.h>`，其中定义了许多常量，标示某些组态的成立与否。所有 STL 头文件都会直接或间接包含这个组态文件，并以条件式写法，让预处理器（pre-processor）根据各个常量决定取舍哪一段程序代码。`<stl_config.h>`文件起始处有一份常量定义说明，然后即针对各家不同的编译器以及可能的不同版本，给予常量设定。从这里我们可以一窥各家编译器对标准C++的支持程度。当然随着版本的演进，这些组态都有可能改变。下面是完整的代码代码：```javascript
/*** 版权所有 (c) 1994* Hewlett-Packard 公司** 允许使用、复制、修改、分发和销售此软件及其文档，任何目的均可，无需费用，* 前提是上述版权声明出现在所有副本中，并且该版权声明和此许可声明出现在* 支持文档中。Hewlett-Packard 公司不对该软件的适用性作任何陈述。* 它是“按原样”提供的，没有明示或暗示的保证。** 版权所有 (c) 1997* Silicon Graphics 公司** 允许使用、复制、修改、分发和销售此软件及其文档，任何目的均可，无需费用，* 前提是上述版权声明出现在所有副本中，并且该版权声明和此许可声明出现在* 支持文档中。Silicon Graphics 公司不对该软件的适用性作任何陈述。* 它是“按原样”提供的，没有明示或暗示的保证。**/#ifndef __STL_CONFIG_H
# define __STL_CONFIG_H// 这个文件的功能：
//  (1) 如果编译器尚未定义 bool、true 和 false，则定义它们。
//  (2) 如果编译器的标准库不支持 drand48() 函数，则定义 __STL_NO_DRAND48。
//  (3) 如果编译器无法处理模板类的静态成员，则定义 __STL_STATIC_TEMPLATE_MEMBER_BUG。
//  (4) 如果编译器不支持 typename 关键字，则将 'typename' 定义为空宏。
//  (5) 如果编译器支持类模板的部分特化，则定义 __STL_CLASS_PARTIAL_SPECIALIZATION。
//  (6) 如果编译器支持函数模板的部分排序（即函数模板的部分特化），则定义 __STL_FUNCTION_TMPL_PARTIAL_ORDER。
//  (7) 如果编译器支持通过显式提供模板参数来调用函数模板，则定义 __STL_EXPLICIT_FUNCTION_TMPL_ARGS。
//  (8) 如果编译器支持类的模板成员，则定义 __STL_MEMBER_TEMPLATES。
//  (9) 如果编译器不支持 explicit 关键字，则将 'explicit' 定义为空宏。
//  (10) 如果编译器无法处理依赖于先前模板参数的默认模板参数，则定义 __STL_LIMITED_DEFAULT_TEMPLATES。
//  (11) 如果编译器在进行非类型模板参数的函数模板参数推导时有问题，则定义 __STL_NON_TYPE_TMPL_PARAM_BUG。
//  (12) 如果编译器无法支持迭代器的 -> 操作符，则定义 __SGI_STL_NO_ARROW_OPERATOR。
//  (13) 如果编译器（在当前编译模式下）支持异常，则定义 __STL_USE_EXCEPTIONS。
//  (14) 如果我们将 STL 放入命名空间，则定义 __STL_USE_NAMESPACES。
//  (15) 如果这是在 SGI 编译器上编译，并且用户没有选择 pthreads 或无线程，则定义 __STL_SGI_THREADS。
//  (16) 如果这是在 WIN32 编译器上以多线程模式编译，则定义 __STL_WIN32THREADS。
//  (17) 适当地定义与命名空间相关的宏（__STD、__STL_BEGIN_NAMESPACE 等）。
//  (18) 适当地定义与异常相关的宏（__STL_TRY、__STL_UNWIND 等）。
//  (19) 根据是否定义了 __STL_ASSERTIONS，将 __stl_assert 定义为测试或空宏。#ifdef _PTHREADS
#   define __STL_PTHREADS
#endif# if defined(__sgi) && !defined(__GNUC__)
#   if !defined(_BOOL)
#     define __STL_NEED_BOOL
#   endif
#   if !defined(_TYPENAME_IS_KEYWORD)
#     define __STL_NEED_TYPENAME
#   endif
#   ifdef _PARTIAL_SPECIALIZATION_OF_CLASS_TEMPLATES
#     define __STL_CLASS_PARTIAL_SPECIALIZATION
#   endif
#   ifdef _MEMBER_TEMPLATES
#     define __STL_MEMBER_TEMPLATES
#   endif
#   if !defined(_EXPLICIT_IS_KEYWORD)
#     define __STL_NEED_EXPLICIT
#   endif
#   ifdef __EXCEPTIONS
#     define __STL_USE_EXCEPTIONS
#   endif
#   if (_COMPILER_VERSION >= 721) && defined(_NAMESPACES)
#     define __STL_USE_NAMESPACES
#   endif 
#   if !defined(_NOTHREADS) && !defined(__STL_PTHREADS)
#     define __STL_SGI_THREADS
#   endif
# endif# ifdef __GNUC__
#   include <_G_config.h>
#   if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8)
#     define __STL_STATIC_TEMPLATE_MEMBER_BUG
#     define __STL_NEED_TYPENAME
#     define __STL_NEED_EXPLICIT
#   else
#     define __STL_CLASS_PARTIAL_SPECIALIZATION
#     define __STL_FUNCTION_TMPL_PARTIAL_ORDER
#     define __STL_EXPLICIT_FUNCTION_TMPL_ARGS
#     define __STL_MEMBER_TEMPLATES
#   endif/* glibc 2.0 之前的版本非常有问题。我们必须为其禁用线程。它应该升级到 glibc 2.0 或更高版本。 */
#   if !defined(_NOTHREADS) && __GLIBC__ >= 2 && defined(_G_USING_THUNKS)
#     define __STL_PTHREADS
#   endif
#   ifdef __EXCEPTIONS
#     define __STL_USE_EXCEPTIONS
#   endif
# endif# if defined(__SUNPRO_CC) 
#   define __STL_NEED_BOOL
#   define __STL_NEED_TYPENAME
#   define __STL_NEED_EXPLICIT
#   define __STL_USE_EXCEPTIONS
# endif# if defined(__COMO__)
#   define __STL_MEMBER_TEMPLATES
#   define __STL_CLASS_PARTIAL_SPECIALIZATION
#   define __STL_USE_EXCEPTIONS
#   define __STL_USE_NAMESPACES
# endif# if defined(_MSC_VER)
#   if _MSC_VER > 1000
#     include <yvals.h>
#   else
#     define __STL_NEED_BOOL
#   endif
#   define __STL_NO_DRAND48
#   define __STL_NEED_TYPENAME
#   if _MSC_VER < 1100
#     define __STL_NEED_EXPLICIT
#   endif
#   define __STL_NON_TYPE_TMPL_PARAM_BUG
#   define __SGI_STL_NO_ARROW_OPERATOR
#   ifdef _CPPUNWIND
#     define __STL_USE_EXCEPTIONS
#   endif
#   ifdef _MT
#     define __STL_WIN32THREADS
#   endif
# endif# if defined(__BORLANDC__)
#   define __STL_NO_DRAND48
#   define __STL_NEED_TYPENAME
#   define __STL_LIMITED_DEFAULT_TEMPLATES
#   define __SGI_STL_NO_ARROW_OPERATOR
#   define __STL_NON_TYPE_TMPL_PARAM_BUG
#   ifdef _CPPUNWIND
#     define __STL_USE_EXCEPTIONS
#   endif
#   ifdef __MT__
#     define __STL_WIN32THREADS
#   endif
# endif# if defined(__STL_NEED_BOOL)typedef int bool;
#   define true 1
#   define false 0
# endif# ifdef __STL_NEED_TYPENAME
#   define typename
# endif# ifdef __STL_NEED_EXPLICIT
#   define explicit
# endif# ifdef __STL_EXPLICIT_FUNCTION_TMPL_ARGS
#   define __STL_NULL_TMPL_ARGS <>
# else
#   define __STL_NULL_TMPL_ARGS
# endif# ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
#   define __STL_TEMPLATE_NULL template<>
# else
#   define __STL_TEMPLATE_NULL
# endif// __STL_NO_NAMESPACES 是一个钩子，用户可以通过它禁用命名空间
// 而无需编辑库头文件。
# if defined(__STL_USE_NAMESPACES) && !defined(__STL_NO_NAMESPACES)
#   define __STD std
#   define __STL_BEGIN_NAMESPACE namespace std {
#   define __STL_END_NAMESPACE }
#   define  __STL_USE_NAMESPACE_FOR_RELOPS
#   define __STL_BEGIN_RELOPS_NAMESPACE namespace std {
#   define __STL_END_RELOPS_NAMESPACE }
#   define __STD_RELOPS std
# else
#   define __STD 
#   define __STL_BEGIN_NAMESPACE 
#   define __STL_END_NAMESPACE 
#   undef  __STL_USE_NAMESPACE_FOR_RELOPS
#   define __STL_BEGIN_RELOPS_NAMESPACE 
#   define __STL_END_RELOPS_NAMESPACE 
#   define __STD_RELOPS 
# endif# ifdef __STL_USE_EXCEPTIONS
#   define __STL_TRY try
#   define __STL_CATCH_ALL catch(...)
#   define __STL_RETHROW throw
#   define __STL_NOTHROW throw()
#   define __STL_UNWIND(action) catch(...) { action; throw; }
# else
#   define __STL_TRY 
#   define __STL_CATCH_ALL if (false)
#   define __STL_RETHROW 
#   define __STL_NOTHROW 
#   define __STL_UNWIND(action) 
# endif#ifdef __STL_ASSERTIONS
# include <stdio.h>
# define __stl_assert(expr) \if (!(expr)) { fprintf(stderr, "%s:%d STL assertion failure: %s\n", \__FILE__, __LINE__, # expr); abort(); }
#else
# define __stl_assert(expr)
#endif#endif /* __STL_CONFIG_H */// 本地变量:
// 模式:C++
// 结束:

下面是对上面代码的解释：

/*** 版权所有 (c) 1994* Hewlett-Packard 公司** 允许使用、复制、修改、分发和销售此软件及其文档，任何目的均可，无需费用，* 前提是上述版权声明出现在所有副本中，并且该版权声明和此许可声明出现在* 支持文档中。Hewlett-Packard 公司不对该软件的适用性作任何陈述。* 它是“按原样”提供的，没有明示或暗示的保证。** 版权所有 (c) 1997* Silicon Graphics 公司** 允许使用、复制、修改、分发和销售此软件及其文档，任何目的均可，无需费用，* 前提是上述版权声明出现在所有副本中，并且该版权声明和此许可声明出现在* 支持文档中。Silicon Graphics 公司不对该软件的适用性作任何陈述。* 它是“按原样”提供的，没有明示或暗示的保证。**/

#ifndef __STL_CONFIG_H
# define __STL_CONFIG_H

如果__STL_CONFIG_H尚未定义，则定义它，以避免多次包含这个头文件。

// 这个文件的功能：
//  (1) 如果编译器尚未定义 bool、true 和 false，则定义它们。
//  (2) 如果编译器的标准库不支持 drand48() 函数，则定义 __STL_NO_DRAND48。
//  (3) 如果编译器无法处理模板类的静态成员，则定义 __STL_STATIC_TEMPLATE_MEMBER_BUG。
//  (4) 如果编译器不支持 typename 关键字，则将 'typename' 定义为空宏。
//  (5) 如果编译器支持类模板的部分特化，则定义 __STL_CLASS_PARTIAL_SPECIALIZATION。
//  (6) 如果编译器支持函数模板的部分排序（即函数模板的部分特化），则定义 __STL_FUNCTION_TMPL_PARTIAL_ORDER。
//  (7) 如果编译器支持通过显式提供模板参数来调用函数模板，则定义 __STL_EXPLICIT_FUNCTION_TMPL_ARGS。
//  (8) 如果编译器支持类的模板成员，则定义 __STL_MEMBER_TEMPLATES。
//  (9) 如果编译器不支持 explicit 关键字，则将 'explicit' 定义为空宏。
//  (10) 如果编译器无法处理依赖于先前模板参数的默认模板参数，则定义 __STL_LIMITED_DEFAULT_TEMPLATES。
//  (11) 如果编译器在进行非类型模板参数的函数模板参数推导时有问题，则定义 __STL_NON_TYPE_TMPL_PARAM_BUG。
//  (12) 如果编译器无法支持迭代器的 -> 操作符，则定义 __SGI_STL_NO_ARROW_OPERATOR。
//  (13) 如果编译器（在当前编译模式下）支持异常，则定义 __STL_USE_EXCEPTIONS。
//  (14) 如果我们将 STL 放入命名空间，则定义 __STL_USE_NAMESPACES。
//  (15) 如果这是在 SGI 编译器上编译，并且用户没有选择 pthreads 或无线程，则定义 __STL_SGI_THREADS。
//  (16) 如果这是在 WIN32 编译器上以多线程模式编译，则定义 __STL_WIN32THREADS。
//  (17) 适当地定义与命名空间相关的宏（__STD、__STL_BEGIN_NAMESPACE 等）。
//  (18) 适当地定义与异常相关的宏（__STL_TRY、__STL_UNWIND 等）。
//  (19) 根据是否定义了 __STL_ASSERTIONS，将 __stl_assert 定义为测试或空宏。

这些注释详细描述了文件的功能，列出了它将为不同编译器和环境设置的一些宏定义。

#ifdef _PTHREADS
#   define __STL_PTHREADS
#endif

如果检测到使用了Pthreads库（即多线程支持库），则定义__STL_PTHREADS宏。

# if defined(__sgi) && !defined(__GNUC__)
#   if !defined(_BOOL)
#     define __STL_NEED_BOOL
#   endif
...
# endif

这段代码根据不同编译器的特征定义一些宏。例如，如果使用的是SGI编译器且未定义_BOOL，则定义__STL_NEED_BOOL，表示需要为bool类型提供支持。

# ifdef __GNUC__
#   include <_G_config.h>
...
# endif

如果使用GCC编译器，则包含_G_config.h配置文件，并根据GCC的版本来设置一些特定的宏。

# if defined(__STL_NEED_BOOL)typedef int bool;
#   define true 1
#   define false 0
# endif

如果编译器没有定义bool类型，则通过定义bool为int类型，并指定true为1、false为0来手动定义它。

# ifdef __STL_NEED_TYPENAME
#   define typename
# endif

如果编译器不支持typename关键字，则将其定义为空宏，以避免编译错误。

# ifdef __STL_USE_NAMESPACES
#   define __STD std
#   define __STL_BEGIN_NAMESPACE namespace std {
#   define __STL_END_NAMESPACE }
# else
#   define __STD 
#   define __STL_BEGIN_NAMESPACE 
#   define __STL_END_NAMESPACE 
# endif

这部分代码根据是否启用了命名空间（__STL_USE_NAMESPACES）来定义与命名空间相关的宏。如果启用，则使用std命名空间；否则，定义为空。

# ifdef __STL_USE_EXCEPTIONS
#   define __STL_TRY try
#   define __STL_CATCH_ALL catch(...)
#   define __STL_RETHROW throw
#   define __STL_NOTHROW throw()
#   define __STL_UNWIND(action) catch(...) { action; throw; }
# else
#   define __STL_TRY 
#   define __STL_CATCH_ALL if (false)
#   define __STL_RETHROW 
#   define __STL_NOTHROW 
#   define __STL_UNWIND(action) 
# endif

如果启用了异常处理（__STL_USE_EXCEPTIONS），则定义与异常处理相关的宏（例如try、catch等）。如果没有启用异常处理，则这些宏被定义为空或无效。

#ifdef __STL_ASSERTIONS
# include <stdio.h>
# define __stl_assert(expr) \if (!(expr)) { fprintf(stderr, "%s:%d STL assertion failure: %s\n", \__FILE__, __LINE__, # expr); abort(); }
#else
# define __stl_assert(expr)
#endif

如果启用了断言（__STL_ASSERTIONS），则定义一个断言宏，它会在条件不成立时输出错误信息并中止程序；否则，定义为空宏。

#endif /* __STL_CONFIG_H */

结束条件编译，防止头文件被重复包含。

学习STL还要知道两个概念，第一个就是组态。STL中的“组态”是指通过模板、分配器、函数对象、迭代器适配器等机制，定制和扩展STL的行为。理解组态的概念有助于更好地使用STL，并在需要时进行深度定制。
组态的核心思想是泛型编程，通过模板和配置实现代码的通用性和灵活性。STL的组态机制使得：

容器和算法可以独立于数据类型。
用户可以根据需求定制行为（如内存分配、比较逻辑）。
代码复用性高，易于扩展。

第二个是临时对象。所谓临时对象，就是一种无名对象（unnamed objects）。它的出现如果不在程序员的预期之下（例如任何 pass by value 操作都会引发 copy 操作，于是形成一个临时对象），往往造成效率上的负担。但有时候刻意制造一些临时对象，却又是使程序干净清爽的技巧。刻意制造临时对象的方法是，在型别名称之后直接加一对小括号，并可指定初值，例如 Shape(3,5) 或 int(8)，其意义相当于调用相应的 constructor 且不指定对象名称。STL 最常将此技巧应用于仿函数（functor）与算法的搭配上。

二、关于STL的一些介绍

increment/dereference 操作符在迭代器的实现上占有非常重要的地位，因为任何一个选代器都必须实现出前进（increment，operator++）和取值（dereference，operator*）功能，前者还分为前置式（prefix）和后置式（postfix）两种，有非常规律的写法。有些选代器具备双向移动功能，那么就必须再提供 decrement 操作符（也分前置式和后置式两种）。
在迭代器的实现中，increment（operator++）和dereference（operator*）操作符是核心功能，因为它们是迭代器能够遍历容器并访问元素的基础。此外，对于双向迭代器，还需要实现decrement（operator--）操作符。以下是这些操作符的实现规律及其重要性：

1. **Dereference 操作符 (`operator*`)**

功能：返回迭代器当前指向的元素的引用。

实现：

T& operator*() const {return *current; // current 是迭代器内部指向元素的指针
}

示例：

auto it = vec.begin();
int value = *it; // 获取第一个元素的值

2. Increment 操作符 (`operator++`)

功能：将迭代器移动到下一个元素。

分为两种形式：

前置式 (++it)：先移动迭代器，再返回移动后的迭代器。

Iterator& operator++() {++current; // 移动到下一个元素return *this;
}

后置式 (it++)：先返回当前迭代器，再移动迭代器。

Iterator operator++(int) {Iterator temp = *this; // 保存当前迭代器++current; // 移动到下一个元素return temp; // 返回移动前的迭代器
}

示例：

auto it = vec.begin();
++it; // 前置式
it++; // 后置式

3. Decrement 操作符 (`operator--`)

功能：将迭代器移动到上一个元素（仅适用于双向迭代器）。

分为两种形式：

前置式 (--it)：先移动迭代器，再返回移动后的迭代器。

Iterator& operator--() {--current; // 移动到上一个元素return *this;
}

后置式 (it--)：先返回当前迭代器，再移动迭代器。

Iterator operator--(int) {Iterator temp = *this; // 保存当前迭代器--current; // 移动到上一个元素return temp; // 返回移动前的迭代器
}

示例：

auto it = vec.end();
--it; // 前置式
it--; // 后置式

任何一个 STL 算法，都需要获得由一对迭代器(泛型指针) 所标示的区间，用以表示操作范围。这一对迭代器所标示的是个所谓的前闭后开区间，以[first,last)表示。也就是说，整个实际范围从 first 开始，直到 last-1。迭代器 last所指的是“最后一个元素的下一位置”。这种 off by one (偏移一格，或说 pass theend) 的标示法，带来了许多方便。
STL算法使用前闭后开区间（[first, last)）的设计，通过统一性和数学一致性带来了显著的优势。

1. 空区间的自然表示

优势：当first == last时，区间为空，无需额外判断。

示例：

std::vector<int> empty_vec;
auto begin = empty_vec.begin(); // 指向“起始”（无元素）
auto end = empty_vec.end();     // 与begin相等
// [begin, end) 表示空区间

2. 循环条件的统一性

优势：所有迭代器类型（包括单向迭代器）均支持!=比较，循环可写为for (auto it = first; it != last; ++it)。

示例：

std::list<int> lst{1, 2, 3};
for (auto it = lst.begin(); it != lst.end(); ++it) {// 处理每个元素
}

3. 区间长度直接计算

优势：对于随机访问迭代器，元素个数为last - first，无需额外调整。

示例：

std::vector<int> vec{10, 20, 30};
size_t count = vec.end() - vec.begin(); // 3

4. 子区间分割与合并的简洁性

优势：分割区间时，中间点mid可直接作为子区间端点，避免重叠。

示例：

auto mid = vec.begin() + 1;
auto left = [vec.begin(), mid);  // 包含vec[0]
auto right = [mid, vec.end());   // 包含vec[1], vec[2]

5. 算法终止条件的统一处理

优势：算法返回last表示未找到元素或操作完成，无需特殊值。

示例：

auto pos = std::find(vec.begin(), vec.end(), 42);
if (pos == vec.end()) {// 未找到
}

6. 与数学半开区间的一致性

优势：区间长度和数学定义一致（[a, b)的长度为b - a），减少计算错误。

示例：

int arr[] = {0, 1, 2, 3}; // 区间[arr, arr+4)包含4个元素
size_t len = arr + 4 - arr; // 4

很少有人注意到，函数调用操作（C++语法中的左右小括号）也可以被重载。
许多STL算法都提供了两个版本，一个用于一般状况（例如排序时以递增方式排列），一个用于特殊状况（例如排序时由使用者指定以何种特殊关系进行排列）。
像这种情况，需要用户指定某个条件或某个策略，而条件或策略的背后由一整组操作构成，便需要某种特殊的东西来代表这“一整组操作”。
代表“一整组操作”的，当然是函数。过去C语言时代，欲将函数当做参数传递，唯有通过函数指针（pointer to function，或称function pointer）才能达成。
但是函数指针有缺点，最重要的是它无法持有自己的状态（所谓局部状态，local states），也无法达到组件技术中的可适配性（adaptability）——也就是无法再将某些修饰条件加诸于其上而改变其状态。
为此，STL算法的特殊版本所接受的所谓“条件”或“策略”或“一整组操作”，都以仿函数形式呈现。所谓仿函数（functor）就是使用起来像函数一样的东西。如果你针对某个 class 进行 operator() 重载，它就成为一个仿函数。至于要成为一个可配接的仿函数，还需要做一些额外的努力。
C++ 中的仿函数（functor）是一个非常强大且灵活的特性，尤其是在 STL 算法中，仿函数的使用为程序提供了巨大的灵活性和可扩展性。让我们深入探讨一下这些概念。

函数指针的局限性

首先，C 语言中的函数指针虽然能够让我们将函数作为参数传递，但它有一些局限性：

无法持有状态：函数指针指向的是一个静态的函数，它无法携带任何额外的上下文或状态。这对于许多需要“状态”或“策略”的场景来说是一个很大的问题。例如，在排序时，我们可能希望根据不同的策略来调整排序的行为，而这些策略可能需要携带一些上下文信息。
缺乏适配性：函数指针本身是一个很简单的指向函数的指针，它不能随着时间的推移根据外部条件改变其行为。而仿函数可以通过对象的状态调整行为，满足更加复杂的需求。

仿函数（Functor）在 STL 中的作用

C++ 中的仿函数通过重载 operator()，使得类的对象能够像普通函数一样被调用。仿函数除了能够模拟函数指针的功能外，它们还可以持有状态，并根据这些状态来调整行为，这就是你提到的“适配性”。

在 STL 中，很多算法（如 std::sort）都接受函数对象作为参数，这允许用户定义自己的操作逻辑，而这些操作逻辑可以非常灵活地控制和调整。例如：

状态管理：仿函数可以持有内部的状态，例如，排序策略可能需要记录某些参数，或者改变比较逻辑。
可扩展性：因为仿函数是类实例，它们可以继承、扩展，并且实现多态性。这样可以在不同的场景中适配不同的行为。
可配置性：仿函数的实例化时，可以根据具体的需求初始化不同的参数，以实现不同的行为。

例子：STL 算法中的仿函数

你提到的排序算法（如 std::sort）就可以使用仿函数来实现自定义的排序逻辑。下面是一个经典的例子，展示如何使用仿函数来进行自定义排序：

#include <iostream>
#include <vector>
#include <algorithm>// 定义一个仿函数，用于自定义排序（降序）
class CompareDescending {
public:// operator() 重载，使得对象可以像函数一样被调用bool operator()(int a, int b) {return a > b;  // 降序排列}
};int main() {std::vector<int> v = {4, 2, 9, 1, 5, 6};// 使用自定义的比较函数对象进行排序std::sort(v.begin(), v.end(), CompareDescending());// 打印排序后的结果for (int num : v) {std::cout << num << " ";}return 0;
}

在上面的代码中，CompareDescending 是一个仿函数，它重载了 operator()，使得 std::sort 可以通过它来进行自定义的排序。仿函数让我们能够将排序规则封装成一个类，并且可以在排序过程中根据类的状态调整排序行为。

仿函数的适配性（Adaptability）

仿函数的适配性，指的是它们可以根据不同的需求灵活地改变行为。这通常通过以下几种方式实现：

通过构造函数传递参数：可以在仿函数的构造函数中传递参数，从而影响仿函数的行为。
通过成员函数修改状态：仿函数的内部状态可以通过成员函数进行修改，改变排序或其他操作的策略。
继承与多态：仿函数可以通过继承和多态来实现更复杂的行为，适应不同的场景需求。

例如，假设我们希望根据不同的规则来比较两个数，仿函数的设计可以支持这一需求：

class CompareByModulo {int divisor;
public:CompareByModulo(int d) : divisor(d) {}  // 传递一个参数来定义比较规则bool operator()(int a, int b) {return (a % divisor) < (b % divisor);  // 按照除以 divisor 余数的大小排序}
};int main() {std::vector<int> v = {4, 2, 9, 1, 5, 6};// 按照元素除以3的余数来排序std::sort(v.begin(), v.end(), CompareByModulo(3));for (int num : v) {std::cout << num << " ";}return 0;
}

这里，CompareByModulo 是一个仿函数，它根据构造时传入的 divisor 来决定如何排序。这种设计允许我们灵活地为不同的情况定义排序规则。
仿函数（functor）为 C++ 提供了一个强大的工具，使得我们能够以类的方式封装行为，而不仅仅是一个函数指针。通过重载 operator()，仿函数能够像函数一样调用，同时可以保持状态，并根据需要调整行为。它们不仅支持基本的函数功能，还提供了更多的适配性和灵活性，尤其在 STL 算法中，能够根据不同的策略灵活地适配不同的需求。这种设计充分体现了 C++ 的面向对象和泛型编程的优越性。

三、总结

下一篇作者将从STL中的算法开始介绍。