库组织与容器设计全解析

# 库组织与容器设计全解析 ## 1. 标准库基础概述 在标准库中，有多个与数值相关的部分，它们各自承担着不同的功能： | 部分 | 功能 | | ---- | ---- | | `<complex>` | 处理复数及其相关操作 | | `<valarray>` | 用于数值向量及其操作 | | `<numeric>` | 提供广义的数值操作 | | `<cmath>` | 包含标准的数学函数 | | `<cstdlib>` | 提供 C 风格的随机数功能 | 需要注意的是，由于历史原因，`abs()`、`fabs()` 和 `div()` 被放在 `<cstdlib>` 中，而非与其他数学函数一起放在 `<cmath>` 里。同时，用户或库实现者不能随意对标准头文件进行增删声明操作，也不能通过定义宏或在上下文中声明来改变头文件内容和声明含义，否则程序将不符合标准且不具备可移植性。不过，程序员可以针对非标准库的用户自定义类型对实用模板（如 `swap()`）进行特化。 标准库中有一部分是语言支持功能，这些功能是程序运行所必需的，因为语言特性依赖于它们： - 支持 `new` 和 `delete` 运算符的库函数在 `<new>` 中。 - 运行时类型识别依赖于 `<typeinfo>` 中的 `type_info` 类。 - 标准异常类在 `<new>`、`<typeinfo>`、`<ios>`、`<exception>` 和 `<stdexcept>` 中。 - 程序的启动和终止相关内容也有相应的规定。 ## 2. 容器设计理念 容器是用于容纳其他对象的对象，常见的有列表、向量和关联数组等。C++ 标准库容器的设计旨在满足两个关键标准：一是在单个容器设计上提供最大的自由度，二是让容器为用户呈现一个通用的接口。这样既能保证容器实现的最佳效率，又能让用户编写的代码独立于所使用的特定容器。 ## 3. 传统容器设计风格分析 ### 3.1 专用容器与迭代器 这种方式通过为向量和列表分别定义最适合其用途的类来实现： ```cpp template<class T> class Vector { // optimal public: explicit Vector(size_t n); // initialize to hold n objects with value T() T& operator[](size_t); // ... }; template<class T> class List { // optimal public: class Link { /* ... */ }; List(); // initially empty void put(T*); // put before current element T* get(); // get current element // ... }; ``` 每个类都提供了接近理想的操作，并且可以独立选择合适的表示方式，使得操作的实现接近最优。例如，`List` 的 `put()` 和 `Vector` 的 `operator[]()` 操作简单且易于内联。 为了实现对容器元素的遍历，定义了一个迭代器类 `Iterator`： ```cpp template<class T> class Iterator { // common interface (abstract class §2.5.4, §12.3) public: // return 0 to indicate no-more-elements virtual T* first() = 0; // pointer to first element virtual T* next() = 0; // pointer to next element }; ``` 并为 `Vector` 和 `List` 分别提供了具体的迭代器实现： ```cpp template<class T> class Vector_iterator : public Iterator<T> { // Vector implementation Vector<T>& v; size_t index; // index of current element 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] ```