在C++的STL中，顺序容器是按顺序存储数据的容器类，用于存储和操作数据集合。顺序容器主要包括 vector、deque、list 和 forward_list，它们各自有不同的实现方式和应用场景。下面详细介绍每种顺序容器的特点、常用操作及其应用场景。
是一种动态数组，可以动态调整大小，同时支持快速的随机访问。
- 连续存储： 内部数据存储在连续的内存中，因此支持快速的随机访问（O(1)）。
- 动态扩展：当添加新元素超过当前容量时， 会自动分配更大的内存块，将数据复制过去。通常，新容量是原来的 1.5 倍或 2 倍，具体取决于实现。
- 自动管理内存：当超出容量时， 会自动分配更多空间；当 销毁时，内存会自动释放。
- 迭代器失效：当 扩容或元素被删除时，原有的迭代器可能失效，因为底层内存块可能会更改。
：在末尾添加一个元素。
：删除末尾的一个元素。
：调整 vector 的大小。
：访问指定位置的元素（带边界检查）。
：访问指定位置的元素（不带边界检查）。
以下是 常用函数的原型说明，包括构造函数、元素访问、容量管理、修改操作等。
- 构造函数
提供了多种构造方式，可以根据不同的需求创建 对象。
- 元素访问
- 迭代器
- 容量管理
- 修改操作
- 赋值操作
是一种双端队列，支持在两端进行高效的插入和删除操作。
- 双端队列： 支持在头部和尾部进行高效的插入和删除操作，适合实现双向队列、双向缓存等结构。
- 分块存储： 将数据分块存储在不同的内存块中，方便在头尾插入数据而不移动整个容器。
- 快速访问：虽然不像 那样提供严格连续的内存，但 仍支持常数时间（O(1)）的随机访问，效率接近 。
- 迭代器的稳定性： 的迭代器在头部和尾部插入和删除操作时不会失效（除非扩容），但在中间插入和删除时会导致迭代器失效。
：在头部插入一个元素。
：删除头部的元素。
：在尾部插入一个元素。
：删除尾部的元素。
和 ：访问指定位置的元素。
- 构造函数
- 元素访问
- 迭代器
- 容量管理
- 修改操作
- 赋值操作
list 是一种双向链表，元素不连续存储，支持高效的插入和删除操作。
- 双向链表： 是一个双向链表，每个节点包含指向前后节点的指针。
- 高效插入和删除：在任意位置进行插入或删除的时间复杂度为常数时间 O(1)，适合需要频繁插入、删除的场景。
- 迭代器稳定性：由于不使用连续内存， 中的插入或删除操作不会使其他迭代器失效，只有删除操作会使相关迭代器失效。
- 不支持随机访问： 不支持使用 [] 或 at 访问特定位置的元素，访问指定位置的元素需要顺序遍历，时间复杂度为 O(n)。
和 ：在头部或尾部插入元素。
和 ：删除头部或尾部的元素。
：在指定位置插入元素。
：删除指定位置的元素。
- 构造函数
- 元素访问
- 迭代器
- 容量管理
- 修改操作
- 赋值操作
- 专有操作
std::list 提供了一些特有的操作，主要用于链表的合并、拆分和排序：
是一种单向链表，与 类似，但只支持单向遍历，只包含指向下一个节点的指针。其设计目标是提供比 更小的内存开销和更高的性能，适用于需要简单链表结构且只需从头到尾单向遍历的场景。
- 单向链表：每个节点只包含一个指向下一个节点的指针，不包含指向前一个节点的指针。
- 轻量级：因为只有一个方向的指针，相比 ，内存开销更小。
- 高效的头部插入和删除：在链表头部插入或删除操作的时间复杂度为 O(1)，适合实现简单的队列或栈。
- 不支持双向遍历和随机访问：只能从头到尾单向遍历链表，不支持 [] 或 at 进行随机访问。
：在头部插入元素。
：删除头部的元素。
：在指定位置后插入元素。
：删除指定位置后的元素。
- 构造函数
- 元素访问
std::forward_list 不提供随机访问，因此只有一个头部访问函数。
- 迭代器
- 容量管理
- 修改操作
的修改操作比 简单，因为它是单向链表，没有提供像 emplace_back 或 push_back 的操作。
- 赋值操作
- 专有操作
由于 std::forward_list 的单向链表特性，它也支持一些常用的链表操作：
看到这边可能有些朋友会有疑惑，怎么list和forward_list有专有操作，vector和deque没有呢？
和 的设计目标是提供快速的随机访问和高效的序列操作，因此它们的接口更关注基础的顺序操作（如插入、删除、访问等），而没有添加复杂的专有操作。相比之下，std::list 和 std::forward_list 基于链表结构，这使得它们天然支持一些高级操作，如合并、排序、去重等。这些操作在链表结构上可以在不移动大量数据的情况下高效实现，因此它们被设计为专有操作。
以下是 std::list 和 std::forward_list 具有这些专有操作的原因，以及 std::vector 和 std::deque 不需要这些操作的原因：
- std::list 和 std::forward_list 的专有操作
merge：将两个已排序的链表合并成一个，且链表的合并操作只需调整指针，而无需移动大量数据，因此链表合并非常高效。这在链表结构上可以实现 O(1) 的操作复杂度。
splice：将一个链表中的元素移动到另一个链表中，只需改变指针指向，而不必复制或移动数据，这对于链表来说是一项很自然的操作，能以 O(1) 的复杂度完成。
remove 和 remove_if：删除符合条件的节点只需调整链表指针，因此链表结构的删除操作可以高效完成，不会涉及到大量元素的移动。
unique：去除连续重复的元素，在链表结构中通过遍历实现，不需要进行大量的元素重排。
sort：链表可以通过交换指针高效排序，而无需像数组那样移动大量数据。
这些操作利用了链表节点的指针特性，使得复杂操作可以高效地实现。
- std::vector 和 std::deque 的设计侧重点
快速随机访问：std::vector 和 std::deque 设计上重视连续内存的快速访问特性。由于其内存是连续的，直接支持 O(1) 的随机访问，这是链表无法做到的。
简单顺序操作：std::vector 和 std::deque 的主要操作集中在顺序插入和删除，特别是 std::vector 优化了尾部操作，而 std::deque 额外支持高效的头尾操作。
高级操作不适用：由于内存是连续存储的，执行类似 merge、splice 的操作需要移动大量数据，这样的操作会非常低效；而 sort、remove 等操作，std::vector 和 std::deque 可以通过算法库中的通用函数（如 std::sort、std::remove）来完成。这样的算法函数在这些连续容器上效率很高，因为它们能利用直接访问的优势。
总结
链表容器（list、forward_list）：使用指针操作节点，高效支持高级操作，因此提供了专有的成员函数。
连续内存容器（vector、deque）：基于连续内存，更适合直接访问和基础顺序操作，专有操作反而会影响效率。因此这些容器专注于基础的增删查操作，不提供链表专有的高级操作。
可以通过标准算法来对 vector 和 deque 执行类似的操作。例如：
排序：
去重：
合并：
和 的功能更偏向于高效的内存管理和随机访问，使用标准算法库可以很好地完成类似 list 的操作，但不需要专门的成员函数来实现。
list和forward_list为什么不推荐使用标准算法?
标准算法库中的大部分算法（如 std::sort、std::merge 等）假设数据结构支持 随机访问迭代器。这在连续存储的容器（如 std::vector 和 std::deque）上可以实现高效的操作，但 std::list 和 std::forward_list 只提供双向迭代器或单向迭代器，无法满足这些算法的随机访问要求。因此，尝试在链表上使用标准算法可能会导致编译错误，或效率极低。
选择顺序容器时，可以根据需求来选择：
：适合需要随机访问和尾部操作较多的场景，如动态数组。
：适合双端操作和适度随机访问的场景，如双端队列。
：适合在任意位置频繁插入、删除的场景，典型的双向链表。
：适合单向遍历、头部插入删除频繁、资源受限的场景。
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/cjjbc/58346.html