目录
C++中有两种类型的容器：顺序容器和关联容器 。
顺序容器主要有vector、list、deque等 。其中vector表示一段连续的内存，基于数组实现，list表示非连续的内存，基于链表实现，deque与vector类似，但是对首元素提供插入和删除的双向支持。关联容器主要有map和set。map是key-value形式，set是单值。map和set只能存放唯一的key，multimap和multiset可以存放多个相同的key。
1.vector
是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。
（1）vector是将元素置于一个连续的动态数组（数组长度任意改变）中加以管理的容器；
（2）vector可以随机存取元素（支持索引值直接存取，用[ ]或at()方法），c++提供排序、搜索等操作，对数据的处理速度快；
（3）vector尾部添加或移除元素很快。但是在中间或头部插入、移除就很费时。
vector特点：可高效随机访问和动态调整大小.
vector使用场景：
1、存储和操作可变长的数据集：可以方便地存储和操作可变长的数据集，列入存储用户输入、文件读取内容等；
2、动态增加和删除元素：由于vector的大小可以根据需要动态调整。因此它非常适合在运行时根据需求增加和删除元素；
3、作为临时缓冲区：如果需要在算法中存储临时结果或进行排序、搜索等操作，可以使用vector作为临时缓冲区提高性能；
总之需要动态数组对元素进行频繁插入删除和访问操作时用vector
vector和动态数组的区别
1、对大小的调整：vector容器的大小是动态调整的，当需要插入和删除元素时，它会自动进行内存管理并调整容器的大小，而动态数组需要手动实现内存管理和大小调整。
2、内存分配：vector容器使用堆内存进行元素的存储，并通过重新分配内存空间来保证足够的容量，而动态数组通常使用指针表示数组，并在需要时手动重新分配内存空间。
3、容量增长策略：vector在需要增加容量时，通常会将当前容量翻倍，这样可以减少频繁的内存重分配操作提高效率 而动态数组的扩展是根据具体情况实现。
4、功能和方法：vector容器提供了丰富的成员函数和操作符重载，方便对元素进行插入、删除、访问等操作并提供迭代器遍历元素，而动态数组相对较简单只能通过索引直接访问元素。
2.deque
Vector 容器是单向开口的连续内存空间， deque 则是一种双向开口的连续线性空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作。当然， vector 容器也可以在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。
deque特点：
1.Deque 容器是连续的空间。
2.Deque 是由一段一段的定量的连续空间构成。
3.Deque 最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间，复制，释放的轮回，代价就是复杂的迭代器架构。
Deque 容器和 vector 容器最大的差异：
一在于 deque 允许使用常数项时间对头端 进行元素的插入和删除操作。对deque的排序操作，可将deque先复制到vector，排序后在复制回deque。
二在于 deque 没有容量的概念，因为它是动态的以分段连续空间组合而成（小片的连续，小片间用链表相连，实际上内部有一个map的指针，因为知道类型，所以还是可以使用[]，只是速度没有vector快），随时可以增加一段新的空间并链接起来。
使用场景：
1.数据缓存：在很多系统中，需要对频繁访问的数据进行缓存，以提高数据访问效率。例如，在数据库系统中，对于经常查询的记录，可以将其存储在deque中作为缓存。当有新的数据需要缓存时，如果deque已满，可以从deque的一端（比如末尾）删除元素，同时从另一端（比如开头）插入新元素，这样可以保持缓存的动态更新，并且由于deque在两端操作的高效性，能够快速地进行数据的替换和更新。
2.页面缓存：在操作系统中，对于内存中的页面缓存也可以采用deque进行管理。当内存紧张需要释放一些页面时，可以从deque的一端删除页面信息，而当新的页面被调入内存时，可以在deque的另一端插入相关信息，从而实现页面缓存的动态调整。
3.信号处理：在信号处理领域，如音频、视频信号的处理中，对于连续的信号流，也可以采用类似的滑动窗口方法进行分析。将信号值依次放入deque中，通过在两端进行数据的删除和插入操作来维持窗口大小不变，进而对窗口内的数据进行各种分析处理，如计算信号的均值、方差等统计指标。
3.双向任务队列：在某些任务调度场景中，不仅需要按照先进先出（FIFO）的原则处理任务，还可能需要从队列的两端进行操作。例如，在一个多任务处理系统中，可能有一批紧急任务需要优先处理，这些紧急任务可以从队列的前端插入，而常规任务依然按照 FIFO 原则从后端插入。当处理任务时，也可以从队列的两端进行选取，比如先处理前端的紧急任务，再处理后端的常规任务。deque正好满足这种双向操作的需求，能够高效地在两端插入和删除任务。
4.动态数组替代：在一些情况下，当需要频繁地在数组的两端进行元素插入和删除操作时，使用deque比普通的数组（如 C++ 中的std::vector）更有优势。例如，在一个实时数据采集系统中，不断有新的数据点加入，同时也可能需要删除最早采集到的数据点，deque可以在两端高效地进行这些操作，而普通数组在两端进行插入删除操作时效率相对较低，所以deque可以作为一种高效的动态数组替代品，用于这种需要频繁在两端操作的场景。
5.可变长数据结构需求：当需要一个可变长的数据结构，并且主要的操作集中在两端时，deque是一个很好的选择。比如在一个图形处理程序中，可能需要不断地在一个数据结构中添加或删除图形元素，并且这些操作主要发生在两端，deque能够满足这种可变长且两端操作高效的需求。
Deque 适用于需要在两端高效进行插入、删除元素操作的场景，如缓存管理、滑动窗口算法、双向任务或消息队列、兼具栈和队列功能模拟以及作为动态数组替代品等多种情况。
3.list
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通 过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点） 组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
相较于 vector 的连续线性空间， list 就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list 对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list 永远是常数时间。（每个元素间用链表相连）访问随机元素不如vector快（list链表需要通过指针逐一遍历到访问节点），随机的插入元素比vector快，对每个元素分配空间，所以不存在空间不够，重新分配的情况。
List 和 vector 是两个最常被使用的容器。
List 容器是一个双向链表：
1.采用动态存储分配，不会造成内存浪费和溢出
2.链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
3.链表灵活，但是空间和时间额外耗费较大
list 容器的迭代器：
1. List 容器不能像 vector 一样以普通指针作为迭代器，因为其节点不能保证在同一 块连续的内存空间上。List 迭代器必须有能力指向 list 的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list 正确的递增，递减、取值、成员 取用” 是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点 的数据值，成员取用时取的是节点的成员。
2.由于 list 是一个双向链表，迭代器必须能够具备前移、后移的能力，所以 list 容器 提供的是 Bidirectional Iterators.
3.List 有一个重要的性质，插入操作和删除操作都不会造成原有 list 迭代器的失效。这在 vector 是不成立的，因为 vector 的插入操作可能造成记忆体重新配置，导致 原有的迭代器全部失效，甚至 List 元素的删除，也只有被删除的那个元素的迭代 器失效，其他迭代器不受任何影响。
list 容器的数据结构：list 容器不仅是一个双向链表，而且还是一个循环的双向链表。
list容器的使用场景：
1、需要频繁在任意位置进行插入和删除操作
2、需要维护有序数据时：list容器支持排序算法可以方便地对元素进行排序操作
4.map
Map 的特性是，所有元素都会根据元素的键值自动排序。 Map 所有的元素都是 pair，同时拥有实值和键值， pair 的第一元素被视为键值，第二元素被视为实值， map 不允许两个元素有相同的键值。
我们可以通过 map 的迭代器改变 map 的键值吗？答案是不行，因为 map 的键值关系到 map 元素的排列规则，任意改变 map 键值将会严重破坏 map 组织。如果想要修改元素的实值，那么是可以的。
Map 和 list 拥有相同的某些性质，当对它的容器元素进行新增操作或者删除操作时，操作之前的所有迭代器，在操作完成之后依然有效，当然被删除的那个元素的迭代器必然是个例外。
Multimap 和 map 的操作类似，唯一区别 multimap 键值可重复。
Map 和 multimap 都是以红黑树为底层实现机制。
（红黑树为底层实现机制：红黑树的每个节点都被标记为红色或者黑色，这是它区别于普通二叉查找树的一个重要特征。）平衡二叉树仍然是一颗有序二叉树，只不过它在保持有序的同时，保持了平衡。所谓平衡，即每颗子树的左右子树高度差不超过1，通俗地理解，即左右子树差不多的样子。
需要旋转的四种情况：
map容器是一种关联容器，它基于红黑树实现，红黑树是一种自平衡二叉搜索树，具有以下特点：
1、每个节点要么红要么黑
2、根节点和叶子节点是黑的
3、如果一个节点是红色，则其子节点必须是黑色
4、从任意节点到每个叶子节点的简单路径上包含相同数量的黑色节点
这些特性确保了红黑树的平衡性并保证了插入、删除和查找操作的时间复杂度都为O(logn)
map底层使用红黑树来存储键值对，每个节点包含一个键和对应的值，并按照键的大小进行排序。通过比较键值，可以高效的进行插入删除和查找操作
map使用场景：
1、字典实现；
2、数据索引；
3、统计字母出现频率的统计；
4、任务调度表的实现：每个任务具有不同的优先级map可以按照键的顺序对任务进行排序和调度。
unordered_map容器的底层实现通常是通过哈希表来实现的，具体来说他使用了一个数组为哈希桶，每个桶中存储着一个链表或红黑树：
元素插入时：unordered_map会根据键的哈希值选择一个桶，并将元素插入到该桶中，如果多个元素的哈希值相同，则会以链表或红黑树的形式连接在同一个桶上，这样可以确保快速查找和删除元素；
查找元素时：首先计算键的哈希值，并确定所在的桶，然后它会遍历对应桶中的链表或红黑树，进行比较操作，直到找到目标元素或遍历完所有可能的位置；
删除元素时：也需要按照相同的方式定位到目标元素所在的桶和位置，并进行删除操作。
unordered_map通过哈希表实现了基于键-值对存储和检索数据的功能，并提供了平均O(1)时间复杂度的插入查找和删除操作。
5.set
Set 的特性：以二叉排序树的形式存储元素，set中的元素在插入、删除时就会自动排序。 Set 的元素不像 map 那样可以同时拥有实值和键值，set 的元素即是键值又是实值。 Set 不允许两个元素有相同的键值。set 和 multiset 的区别是：set 插入的元素不能相同，但是 multiset 可以相同。
我们可以通过 set 的迭代器改变 set 元素的值吗？不行，因为 set 元素值就是其键值，关系到 set 元素的排序规则。如果任意改变 set 元素值，会严重破坏 set 组织。 换句话说，set 的 iterator 是一种 const_iterator.
set 拥有和 list 某些相同的性质，当对容器中的元素进行插入操作或者删除操作的 时候，操作之前所有的迭代器，在操作完成之后依然有效，被删除的那个元素的迭代器必然是一个例外。
set特点：
1.每个元素的键值都唯一，不允许两个元素有相同的键值；
2.所有元素都会根据元素的键值自动排序（默认从小到大）；
3.set 中的元素不像 map 那样可以同时拥有实值(value)和键值(key)，只能存储键，是单纯的键的集合；
4.set 中元素的值不能直接被改变；
5.set 支持大部分的map的操作，但是 set 不支持下标的操作，而且没有定义mapped_type类型。
应用场景：
1.去除重复数据：在处理大量数据时，如从数据库查询结果、日志文件记录、传感器采集的数据等中，经常会遇到数据存在重复的情况。set 容器可以轻松地将这些数据进行去重处理，只保留唯一的元素，以便后续更准确地进行数据分析、统计等操作。
2.数据排序与分组：当需要对一组无序的数据按照特定规则（通常是默认的小于比较规则，但也可自定义）进行排序，并且后续可能基于排序结果进行分组或进一步分析时，set 容器能够在插入数据的同时自动完成排序，使得数据处于有序状态，方便后续操作。
3.搜索算法辅助：在一些搜索算法中，比如深度优先搜索（DFS）、广度优先搜索（BFS）等，可能需要记录已经访问过的节点状态，以避免重复访问。set 容器可以用来存储这些已经访问过的节点，利用其元素唯一性确保不会出现重复记录，从而提高搜索算法的效率。
4.配置项存储：在软件应用程序中，对于各种配置项（如系统设置、用户偏好设置等），可以使用 set 容器来存储。因为配置项通常要求唯一性（例如不同的配置参数名不能重复），并且可能需要按照一定顺序进行处理或显示，set 容器正好满足这些需求，能够确保配置项的有序存储和唯一性。
5.节点标记与状态管理：在图形（如无向图、有向图）和网络（如计算机网络、社交网络）相关的应用中，对于图中的节点可能需要标记其状态（如是否已访问、是否为关键节点等），或者存储其相关属性（如节点的权重、颜色等）。set 容器可以用来存储这些节点的标记或属性，利用其唯一性确保每个节点只有一个对应的标记或属性记录，并且在需要对节点进行排序（如按照节点权重排序）时也能满足要求。
6.queue
Queue 是一种先进先出 (First In First Out,FIFO) 的数据结构，它有两个出口， queue 容器允许从一端新增元素，从另一端移除元素。
Queue 所有元素的进出都必须符合 ” 先进先出 ” 的条件，只有 queue 的顶端元素，才有机会被外界取用。Queue 不提供遍历功能，也不提供迭代器。
使用场景：
1.操作系统任务调度：在操作系统中，多个进程或线程可能需要按照一定的顺序执行。例如，当有多个用户程序同时请求 CPU 资源时，操作系统可以将这些任务放入一个队列中，按照先来先服务的原则（FIFO），依次将队列中的任务分配给 CPU 进行处理。这样可以保证每个任务都能在合适的时间得到处理，并且体现了公平性原则。
2.网络数据传输：在网络通信中，数据的发送和接收速度可能不一致。例如，当服务器接收来自多个客户端的大量数据时，服务器可能无法立即处理所有接收到的数据。此时，可以将接收到的数据先放入一个队列中作为缓冲，然后按照一定的节奏（如按照接收的先后顺序）从队列中取出数据进行处理，这样可以避免数据丢失，同时也能保证数据处理的有序性。
3.硬件设备数据交互：在一些硬件设备（如打印机、扫描仪等）与计算机的交互中，设备的处理速度可能跟不上计算机发送数据的速度。例如，打印机打印速度有限，当计算机连续发送多个打印任务时，这些任务可以先被放入一个队列中，打印机按照 FIFO 原则从队列中取出任务进行打印，这样可以保证打印任务的有序进行，避免出现混乱。
4.最短路径问题：在求解图中的最短路径问题（如求两点之间的最短路径）时，广度优先搜索算法常常被使用，而队列在其中起到了关键作用。通过将节点放入队列并按照 FIFO 原则进行操作，可以逐步探索从起始节点到目标节点的所有可能路径，并找到其中最短的一条，因为在这个过程中，先进入队列的节点会先被探索到，所以能够保证找到的路径是最短的。
5.异步通信：在现代软件开发中，很多应用程序采用异步通信的方式来提高系统的性能和灵活性。例如，在一个 Web 应用程序中，前端用户界面与后端服务器之间可能存在大量的消息交互。这些消息可以先被放入一个消息队列中，然后在后台按照 FIFO 原则进行处理，这样可以使前端用户界面在发送消息后可以继续进行其他操作，而不必等待后端服务器的即时回应，同时也能保证消息处理的有序性。
7.stack
stack 是一种先进后出 (First In Last Out,FILO) 的数据结构，它只有一个出口，形式如图所示。stack 容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端外，没有任何其他方法可以存取 stack 的其他元素。换言之， stack 不允许有遍历 行为。
有元素推入栈的操作称为 :push, 将元素推出 stack 的操作称为 pop
stack 没有迭代器： Stack 所有元素的进出都必须符合 ” 先进后出 ” 的条件，只有 stack 顶端的元素，才有机会被外界取用。Stack 不提供遍历功能，也不提供迭代器。
使用场景：
1.函数调用栈：在程序执行过程中，当一个函数调用另一个函数时，系统会将当前函数的执行状态（如局部变量、返回地址等）压入一个栈中，这个栈被称为函数调用栈。当被调用函数执行完毕后，再从栈中弹出之前压入的执行状态，使得程序能够继续在调用函数处执行下去。例如，在一个多层嵌套的函数调用中，如main函数调用functionA，functionA又调用functionB，每次调用时相关执行状态都会被压入栈中，调用结束后再依次弹出，以保证程序的正确执行流程。
2.中缀表达式转后缀表达式及求值：在处理数学表达式求值问题时，常常需要先将中缀表达式（如3 + 4 * 2）转换为后缀表达式（如3 4 2 * +），然后再对后缀表达式进行求值。栈在这个过程中起到了关键作用。在将中缀表达式转换为后缀表达式时，操作符会根据其优先级被压入或弹出栈，从而得到正确的后缀表达式。在对后缀表达式求值时，数字会被依次读入，遇到操作符时，就从栈中弹出相应数量的数字进行运算，运算结果再压入栈中，最终栈顶元素就是表达式的结果。
3.页面浏览历史记录：浏览器会将用户浏览过的页面网址按照访问的先后顺序压入一个栈中。当用户点击后退按钮时，浏览器会从栈中弹出最近访问过的页面网址，并加载该页面，实现后退功能。而当用户点击前进按钮时，如果之前有通过后退操作弹出过页面网址，那么这些网址会再次被压入栈中（但此时栈顶元素是当前页面网址），这样就可以实现前进功能，使得用户能够方便地在浏览历史中穿梭。
4.二叉树的遍历与转换：在对二叉树进行一些遍历（如先序遍历、中序遍历、后序遍历）时，栈可以用来辅助实现。例如，在先序遍历中，先访问根节点，然后将右子树和左子树依次压入栈中，以便后续依次访问；在中序遍历中，先将左子树全部压入栈中，然后依次弹出并访问，访问完根节点后再将右子树压入栈中；在后序遍历中，先将根节点、右子树和左子树依次压入栈中，然后通过一些特定的弹出和访问规则来实现后序遍历。此外，在将二叉树转换为其他数据结构（如链表、数组等）时，栈也可以起到辅助作用，帮助实现数据的有序转移和处理。
8.STL 容器使用时机
1.deque 的使用场景：比如排队购票系统，对排队者的存储可以采用 deque ，支持 头端的快速移除，尾端的快速添加。如果采用 vector ，则头端移除时，会移动大量 的数据，速度慢。
2.vector 与 deque 的比较：
一：vector.at() 比 deque.at() 效率高，比如 vector.at(0) 是固定的， deque 的开始位 置 却是不固定的。
二：如果有大量释放操作的话，vector 花的时间更少，这跟二者的内部实现有关。
三：deque 支持头部的快速插入与快速移除，这是 deque 的优点。
3.list 的使用场景：比如公交车乘客的存储，随时可能有乘客下车，支持频繁的不确实位置元素的移除插入。
4.set 的使用场景：比如对手机游戏的个人得分记录的存储，存储要求从高分到低分 的顺序排列。
5.map 的使用场景：比如按 ID 号存储十万个用户，想要快速要通过 ID 查找对应的 用户。二叉树的查找效率，这时就体现出来了。如果是 vector 容器，最坏的情况 下可能要遍历完整个容器才能找到该用户。
下面是选择顺序容器类型的一些准则
1.如果我们需要随机访问一个容器则vector要比list好得多 。
2.如果我们已知要存储元素的个数则vector 又是一个比list好的选择。
3.如果我们需要的不只是在容器两端插入和删除元素则list显然要比vector好
4.除非我们需要在容器首部插入和删除元素否则vector要比deque好。
5.如果只在容易的首部和尾部插入数据元素，则选择deque.
6.如果只需要在读取输入时在容器的中间位置插入元素，然后需要随机访问元素，则可考虑输入时将元素读入到一个List容器，接着对此容器重新拍学，使其适合顺序访问，然后将排序后的list容器复制到一个vector容器
以上是对现有资料的总结：https://blog.csdn.net/weixin_50963877/article/details/134897457