## [1]一.C++内置顺序容器 | 容器类型 | 位置 | 名称 | 访问 | 头部插入 | 尾部插入 | 中部插入 | 存储结构 | | -------------------- | ---------------- | -------------- | ------------ | -------- | -------- | -------- | ------------------------------ | | `vector` | `<vector>` | 向量 | 快速随机访问 | 慢 | 快 | 慢 | 动态数组 | | `deque` | `<deque>` | 双端队列 | 快速随机访问 | 快 | 快 | 慢 | 通过指针数组连接的多个动态数组 | | `list` | `<list>` | 双向链表 | 双向顺序访问 | 快 | 快 | 快 | 双向链表 | | [11+] `forward_list` | `<forward_list>` | 单向链表 | 单向顺序访问 | 快 | 快 | 快 | 双向链表 | | [11+] `array` | `<array>` | 固定大小的数组 | 快速随机访问 | 不支持 | 不支持 | 不支持 | 数组 | | `string` | `<string>` | 字符串 | 快速随机访问 | 慢 | 快 | 慢 | 动态数组 | ## [$]二.顺序容器选择原则 1. 一般使用 `vector`. 2. 如果你的程序有很多小的元素，且空间的额外开销很重要，则不要使用 `list` 或 `forward list` 。 3. 如果程序要求随机访问元素，应使用 `vector` 或 `deque` . 4. 如果程序要求在容器的中间插入或删除元素，应使用 `list` 或 `forward_list`. 5. 如果程序需要在头尾位置插入或删除元素，但不会在中间位置进行插入或删除操作，则使用 `deque`。 ## [$]三.顺序容器的特色操作 ### 1.插入操作 + 插入操作会使迭代器失效。 + 将元素插入到 `vector` 、`deque` 和 `string` 中的任何位置可能会耗费较多时间。 + C++11之前， `insert` 函数的返回值为 `void` 。 | 函数 | 不适用容器 | 含义 | | ------------------------------------------------ | -------------- | ------------------------------------------------------ | | `void c.push_back(const T &el);` | `forward_list`、`array` | 在末尾插入元素。 | | [11+]`void c.emplace_back(const T &el1,const T &el2,...);` | `forward_list`、`array` | 在末尾插入多个元素。 | | `void c.push_front(const T &el);` | `array`、`vector`、`string` | 在头部插入元素。 | | [11+]`void c.emplace_front(const T &el1,const T &el2,...);` | `array`、`vector`、`string` | 在头部插入多个元素。 | | `c.insert(p,const T &el);`| `array` | 在迭代器 `p` 指向的元素之前插入一个元素。返回指向新添加的元素的迭代器。 | | `c.insert(p,size_type n,const T &el);`| `array` | 在迭代器 `p` 指向的元素之前插入`n`个元素，每个元素的值为 `t`。返回指向新添加的元素的迭代器。 | | `c.insert(p,b,e);`| `array` | 在迭代器 `p` 指向的元素之前插入`b` 和 `e`之间的元素。`b`和`e`不能指向`c`中的元素。 | | [11+]`c.insert(p,{a,b,c,...});`| `array` | 在迭代器 `p` 指向的元素之前插入花括号中的元素。返回指向新添加的元素的迭代器。 | | [11+]`c.emplace(p,const T &el1,const T &el2,...);`| `array` | 在迭代器 `p` 指向的元素之前插入多个元素。返回指向新添加的元素的迭代器。 | ### 2.访问操作 + 只有 `at` 越界访问时，才会抛出 `out_ of_ range` 的异常。 | 函数或语句| 不适用容器 | 含义| | ------------------------------------------------ | -------------- | ------------------------------------------------------ | | `c.at(n);` | `forward_list`、`list` | 返回下标为 `n`的元素的引用。| | `c[n];` | `forward_list`、`list` | 返回下标为 `n`的元素的引用。| | `c.back();` | `forward_list` | 返回尾元素的引用。| | `c.front();` | 无 | 返回首元素的引用。| ### 3.删除操作 + 删除操作会使迭代器失效。 + 删除一个指向不存在的元素的迭代器是未定义的。 + 删除空容器中的元素是未定义的。 | 函数 | 不适用容器 | 含义 | | ------------------------------------------------ | -------------- | ------------------------------------------------------ | | `void c.pop_back(const T &el);` | `forward_list`、`array` | 删除末尾元素。 | | `void c.pop_front(const T &el);` | `array`、`vector`、`string` | 删除第一个元素。 | | `c.erase(p);`| `forward_list`、`array` | 删除迭代器 `p` 指向的元素。返回下一个元素的迭代器。 | | `c.erase(b,e);`| `forward_list`、`array` | 删除迭代器 [`b`,`e`] 之间的元素。返回下一个元素的迭代器。 |