C++容器知识点总结

### C++容器知识点总结 #### 一、Vector **理论** `Vector` 是 C++ 标准库中的一个动态数组容器。它支持随机访问，并且能够自动管理内存。`Vector` 的内部实现是一个连续的内存区域，这使得它可以提供快速的随机访问性能。 **扩容策略** 在早期版本的编译器如 VC6.0 中，`Vector` 的扩容策略通常是按固定比例（例如 2 倍）进行扩容。而在较新的版本如 VC2005 及以后的版本中，扩容策略变得更加智能，可能会根据实际情况调整。但通常情况下，当 `Vector` 需要扩容时，其执行步骤如下： 1. **配置新空间**：分配一块新的内存区域，其大小通常大于当前的内存大小。 2. **复制旧元素**：将原有内存中的所有元素复制到新内存区域。 3. **释放旧空间**：释放原内存区域，归还给系统。 **数据成员及操作** `Vector` 提供了一系列用于管理和操作元素的方法： - **数据成员**： - `Iterator start;`：指向已使用内存区域的起始位置。 - `Iterator finish;`：指向已使用内存区域的末尾（即下一个可用位置）。 - `Iterator end_of_storage;`：指向已分配内存的末尾。 - **常用成员函数**： - `Iterator begin();`：返回指向容器第一个元素的迭代器。 - `Iterator end();`：返回指向容器最后一个元素之后的迭代器。 - `Reference front();`：返回对容器第一个元素的引用。 - `Reference back();`：返回对容器最后一个元素的引用。 - `Size_type size();`：返回容器当前的大小。 - `Size_type capacity();`：返回容器的容量，即可以容纳的最大元素数量。 - `Void push_back(const T& x);`：在容器末尾添加一个元素。 - `Void pop_back();`：移除容器末尾的元素。 - `Iterator erase(Iterator position);`：移除指定位置的元素，并返回下一个元素的迭代器。 - `Void insert(Iterator position, Size_type n, const T& value);`：在指定位置前插入 `n` 个值为 `value` 的元素。 - `Void clear();`：移除容器中的所有元素，但不改变容器的容量。 #### 二、List **理论** `List` 实现了一个双向循环链表。每个节点包含指向其前后节点的指针，使得插入和删除操作非常高效。与 `Vector` 不同的是，`List` 不支持随机访问。 **特性** - 插入和删除操作不会使任何现有的迭代器失效。 - 支持双向遍历。 **常用操作** - `Void push_front(const T& x);`：在列表头部插入一个元素。 - `Void push_back(const T& x);`：在列表尾部插入一个元素。 - `Void pop_front();`：移除列表头部的元素。 - `Void pop_back();`：移除列表尾部的元素。 - `Void remove(const T& value);`：移除所有值为 `value` 的元素。 - `Void unique();`：移除所有连续重复的元素，只保留一个。 - `Void splice(Iterator position, List& x);`：将另一个 `List` 的所有元素移到当前 `List` 的指定位置之前。 - `Void splice(Iterator position, List& x, Iterator i);`：将 `x` 中由 `i` 指向的元素移到当前 `List` 的指定位置之前。 - `Void merge(List& x);`：将 `x` 中的所有元素合并到当前 `List` 中，要求两个 `List` 已经被排序。 - `Void reverse();`：反转 `List` 中元素的顺序。 - `Void sort();`：对 `List` 进行排序。 #### 三、Deque (双端队列) **理论** `Deque` 是一种支持两端插入和删除操作的容器。它类似于 `Vector`，但在两端都有较高的性能。`Deque` 内部使用分段的连续内存块来存储数据。 **特点** - 支持快速的前端和后端插入/删除操作。 - 支持随机访问。 **常用操作** - `Void push_front(const T& x);`：在容器前端插入一个元素。 - `Void push_back(const T& x);`：在容器后端插入一个元素。 - `Void pop_front();`：移除容器前端的元素。 - `Void pop_back();`：移除容器后端的元素。 - 其他操作与 `Vector` 类似。 以上介绍了 C++ 标准库中三种常见的容器：`Vector`、`List` 和 `Deque`。每种容器都有其特定的应用场景，选择合适的容器类型可以使程序更加高效。