C++标准库容器设计解析

### C++ 标准库容器设计解析 在 C++ 编程中，标准库的合理使用和容器的设计是至关重要的。下面将详细介绍标准库的组织、容器设计的不同方式及其优缺点。 #### 1. 标准库组织与使用规范 标准库中有多个与数值相关的头文件，它们各自提供了不同的功能： | 头文件 | 功能 | | ---- | ---- | | `<complex>` | 提供复数及相关操作 | | `<valarray>` | 提供数值向量及相关操作 | | `<numeric>` | 提供通用数值操作 | | `<cmath>` | 提供标准数学函数 | | `<cstdlib>` | 提供 C 风格随机数 | 需要注意的是，由于历史原因，`abs()`、`fabs()` 和 `div()` 函数在 `<cstdlib>` 中，而非 `<cmath>`。在使用标准库时，有以下重要规范： - **禁止修改标准头文件**：用户或库实现者不允许添加或删除标准头文件中的声明，也不能通过定义宏或在上下文声明来改变头文件内容和声明含义。违反这些规则的程序不符合标准且不具有可移植性。 - **必须包含头文件**：使用标准库功能时，必须包含相应头文件，自行编写相关声明不是符合标准的做法。因为有些实现会基于标准头文件的包含进行编译优化，有些则通过头文件触发标准库功能的优化实现。 - **可特化实用模板**：程序员可以为非标准库的用户自定义类型特化实用模板，如 `swap()`。 #### 2. 语言支持部分 标准库中有一小部分是语言支持功能，这些功能是程序运行所必需的，因为语言特性依赖于它们： - **`new` 和 `delete` 操作符支持函数**：相关函数在 `<new>` 中介绍。 - **运行时类型识别**：依赖 `type_info` 类，在 `<typeinfo>` 中介绍。 - **标准异常类**：在 `<new>`、`<typeinfo>`、`<ios>`、`<exception>` 和 `<stdexcept>` 中介绍。 - **程序启动和终止**：相关内容在相关文档中有讨论。 #### 3. 容器设计概述 容器是用于存放其他对象的对象，如列表、向量和关联数组等。C++ 标准库容器的设计要满足两个标准：为单个容器设计提供最大自由度，同时让容器向用户呈现通用接口。这样既能实现容器实现的最优效率，又能让用户编写不依赖特定容器的代码。 #### 4. 传统容器设计方式及其优缺点 ##### 4.1 专用容器和迭代器 - **容器定义**： ```cpp template<class T> class Vector { public: explicit Vector(size_t n); T& operator[](size_t); // ... }; template<class T> class List { public: class Link { /* ... */ }; List(); void put(T*); T* get(); // ... }; ``` 每个类提供接近理想使用的操作，且可选择合适的表示方式，不考虑其他类型的容器。常见操作如 `List` 的 `put()` 和 `Vector` 的 `operator[]()` 小且易于内联。 - **迭代器设计**：为了实现对容器元素的遍历，定义了一个通用的迭代器接口 `Iterator`： ```cpp template<class T> class Iterator { public: virtual T* first() = 0; virtual T* next() = 0; }; ``` 并为 `Vector` 和 `List` 分别实现了具体的迭代器： ```cpp template<class T> class Vector_iterator : public Iterator<T> { Vector<T>& v; size_t index; public: Vector_iterator(Vector<T>& vv) :v(vv), index(0) { } T* first() { return (v.size()) ? &v[index=0] : 0; } T* next() { return (++index<v.size()) ? &v[index] : 0; } }; template<class T> class List_iterator : public Iterator<T> { List<T>& lst; List<T>::Link p; public: List_iterator(List<T>&); T* first(); T* next(); }; ``` 可以用以下图形表示它们之间的关系： ```mermaid graph LR A[Vector] --> C[Iterator] B[List] --> C C --> D[Vector_iterator] C --> E[List_iterator] ``` - **迭代器使用示例**： ```cpp int count(Iterator<char>& ii, char term) { int c = 0; for (char* p = ii.first(); p; p=ii.next()) if (*p==term) c++; return c; } ``` - **优缺点总结**： | 优点 | 缺点 | | ---- | ---- | | 单个容器简单高效 | 迭代器访问有虚拟函数调用开销 | | 容器间共性要求少，可通过迭代器和包装类纳入通用框架 | 迭代器类层次结构易复杂 | | 通过迭代器提供使用共性 | 容器和对象缺乏共性，通用服务提供复杂 | | 同一容器可定义不同迭代器满足不同需求 | | | 容器默认类型安全且同质 | | | 容器非侵入式，内置类型和外部布局结构体可直接使用 | | #### 5. 基于基类的容