标准容器：序列与适配器详解

# 标准容器：序列与适配器详解 ## 1. 序列概述 序列遵循向量（vector）所描述的模式。标准库提供的基本序列有： - 向量（vector） - 列表（list） - 双端队列（deque） 基于这些基本序列，通过提供合适的接口创建了以下几种序列： - 栈（stack） - 队列（queue） - 优先队列（priority queue） 这些序列被称为容器适配器、序列适配器，或简称为适配器。 下面是这些序列的简单对比表格： | 序列类型 | 特点 | 适用场景 | | ---- | ---- | ---- | | 向量（vector） | 支持随机访问，预留空间功能独特，默认下标操作不进行范围检查 | 需要随机访问元素，元素增长较为连续的场景 | | 列表（list） | 插入和删除元素高效，不支持下标操作，提供双向迭代器 | 频繁进行插入和删除操作的场景 | | 双端队列（deque） | 两端操作效率高，下标操作接近向量的效率 | 两端需要频繁插入和删除元素的场景 | ### 1.1 向量（vector） 标准向量在相关文档中有详细描述。向量的预留空间功能是其独有的。默认情况下，使用 `[]` 进行下标操作时不进行范围检查。如果需要检查，可以使用 `at()` 方法、带检查的向量或带检查的迭代器。向量提供随机访问迭代器。 ### 1.2 列表（list） 列表是一种针对元素插入和删除操作进行了优化的序列。与向量和双端队列相比，列表的下标操作会非常慢，因此列表不提供下标操作。相应地，列表提供双向迭代器，而不是随机访问迭代器。这意味着列表通常会使用某种形式的双向链表来实现。 列表提供了除下标操作、`capacity()` 和 `reserve()` 之外的所有向量所提供的成员类型和操作。其模板定义如下： ```cpp template <class T, class A = allocator<T> > class std::list { public: // types and operations like vector’s, except [], at(), capacity(), and reserve() // ... }; ``` #### 1.2.1 拼接、排序和合并操作 除了一般的序列操作外，列表还提供了几个特别适合列表操作的方法： ```cpp template <class T, class A = allocator<T> > class list { public: // ... // list-specific operations: void splice(iterator pos, list& x); // move all elements from x to before pos in this list without copying. void splice(iterator pos, list& x, iterator p); // move *p from x to before pos in this list without copying. void splice(iterator pos, list& x, iterator first, iterator last); void merge(list&); // merge sorted lists template <class Cmp> void merge(list&, Cmp); void sort(); template <class Cmp> void sort(Cmp); // ... }; ``` 这些列表操作都是稳定的，即它们会保留具有相等值的元素的相对顺序。 下面是一个拼接操作的示例： 假设有两个列表： ```plaintext fruit: apple pear citrus: orange grapefruit lemon ``` 我们可以将 `citrus` 中的 `orange` 拼接到 `fruit` 中： ```cpp list<string>::iterator p = find_if(fruit.begin(), fruit.end(), initial('p')); fruit.splice(p, citrus, citrus.begin()); ``` 操作后结果为： ```plaintext fruit: apple orange pear citrus: grapefruit lemon ``` 需要注意的是，`splice()` 方法不会像 `insert()` 方法那样复制元素，它只是修改了列表的数据结构。 除了拼接单个元素和范围，我们还可以拼接整个列表： ```cpp fruit.splice(fruit.begin(), citrus); ``` 结果为： ```plaintext fruit: grapefruit lemon apple orange pear citrus: <empty> ``` 合并操作 `merge()` 用于合并两个已排序的列表，它会在保留顺序的同时将一个列表的元素移动到另一个列表中。例如： ```plaintext f1: apple quince pear f2: lemon grapefruit orange lime ``` 可以通过以下操作进行排序和合并： ```cpp f1.sort(); f2.sort(); f1.merge(f2); ``` 结果为： ```plaintext f1: apple grapefruit lemon lime orange pear quince f2: <empty> ``` 如果被合并的列表中有一个未排序，`merge()` 仍然会生成一个包含两个列表元素并集的列表，但不保证结果的顺序。 #### 1.2.2 前端操作 列表提供了针对第一个元素的操作，以补充每个序列都提供的针对最后一个元素的操作： ```cpp template <class T, class A = allocator<T> > class list { public: // ... // element access: reference front(); // reference to first element const reference front() const; void push_front(const T&); // add new first element void pop_front(); // remove first element // ... }; ``` 容器的第一个元素被称为前端（front）。对于列表，前端操作和后端操作一样高效和方便。在有选择的情况下，建议优先使用后端操作，因为使用后端操作编写的代码可以同时用于向量和列表。如果使用列表编写的代码有可能发展成为适用于多种容器的通用算法，那么最好优先使用更广泛可用的后端操作。 #### 1.2.3 其他操作 列表在元素插入和删除方面特别高效，因此在这些操作频繁的情况下，人们通常会优先选择列表。为了支持直接删除元素的常见方式，列表提供了以下操作： ```cpp template <class T, class A = allocator<T> > class list { public: // ... void remove(const T& val); template <class Pred> void remove_if(Pred p) ```