STL常用容器总结

1.Vector容器特性

vector 容器是一个长度动态改变的动态数组，既然也是数组，那么其内存是一段连续的内存，具有数组的随机存取的优点。

/+ 在这里插入图片描述

1.1.vector特性总结:

1.vector 是动态数组，连续内存空间，具有随机存取效率高的优点。
2.vector 是单口容器，在队尾插入和删除元素效率高，在指定位置插入会导致数据元素移动，效率低。

总结:

vector 是个动态数组，当空间不足的时候插入新元素，vector会重新申请一块更大的内存空间，将旧空间数据拷贝到新空间，然后释放旧空间。
vector是单口容器，所以在尾端插入和删除元素效率较高，在指定位置插入，势必会引起数据元素移动，效率较低。

2.Deque容器特性

deque和 vector 一样支持随机存取。 vector 是单向开口的连续性空间，而deque是一种双向开口的连续性空间，可以在头尾两端分别做元素的插入和删除操作。

2.1.deque和vector的最大差异？

一在于 deque 允许常数时间内对头端进行元素插入和删除操作。
二在于 deque没有容量的概念，因为它是动态的以分段的连续空间组合而成，随时可以增加一段新的空间并链接起来，换句话说，像 vector那样“因旧空间不足而重新分配一块更大的空间，然后再复制元素，释放空间”这样的操作不会发生在 deque 身上，也因此 deque没有必要提供所谓的空间保留功能。

在这里插入图片描述

deque操作示意图而deque容器原理如下：

在这里插入图片描述

deque原理示意图

2.2.deque特性总结:

1).双端插入和删除元素效率较高.
2).指定位置插入也会导致数据元素移动,降低效率.
3).可随机存取,效率高.

2.3.经验之谈 :

1.deque 是分段连续的内存空间，通过中控器维持一种连续内存空间的状态，其实现复杂性要大于vector等容器。
2.其迭代器的实现也更加复杂，在需要对deque 容器元素进行排序的时候，建议先将 deque 容器中数据数据元素拷贝到 vector容器中，对 vector 进行排序，然后再将排序完成的数据拷贝回 deque 容器。

3.Stack容器特性

1.stack 是一种先进后出(first in last out,FILO)的数据结构，它只有一个出口，stack 只允许在栈顶新增元素，移除元素，获得顶端元素，
2.除了顶端之外，其他地方不允许存取元素，只有栈顶元素可以被外界使用，也就是说 stack不具有遍历行为，没有迭代器。

在这里插入图片描述

3.1.Stack特性总结:

1.stack 是一种先进后出(first in last out,FILO)的数据结构，栈不能遍历,不支持随机存取，只能通过 top 从栈顶获取和删除元素。

4.Queue容器

1.queue 是一种先进先出(first in first out,FIFO)的数据类型,他有两个口，数据元素只能从一个口进，从另一个口出。
2.队列只允许从队尾加入元素，队头删除元素，必须符合先进先出的原则，queue和 stack 一样不具有遍历行为。

在这里插入图片描述

4.1.queue特性总结：

必须从一个口数据元素入队，另一个口数据元素出队。能随机存取，不支持遍历

5.List容器

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
在这里插入图片描述

list示意图而list原理示意图如下图：

在这里插入图片描述

list原理示意图

5.1.list特性总结

1.采用动态存储分配，不会造成内存浪费和溢出
2.链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
3.链表灵活，但是空间和时间额外耗费较大

5.2.链表和数组有什么区别？

1).数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
2).链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据元素。（数组中插入、删除数据项时，需要移动其它数据项）

6.set/multiset 容器

6.1 set/multiset特性

1.set/multiset 的特性是所有元素会根据元素的值自动进行排序。
2.set 是以RB-tree（红黑树，平衡二叉树的一种）为底层机制，其查找效率非常好。
3.set 容器中不允许重复元素，而multiset允许重复元素。

二叉树就是任何节点最多只允许有两个字节点。分别是左子结点和右子节点。
在这里插入图片描述

二叉树示意图

二叉搜索树，是指二叉树中的节点按照一定的规则进行排序，使得对二叉树中元素访问更加高效。
二叉搜索树的放置规则是：任何节点的元素值一定大于其左子树中的每一个节点的元素值，并且小于其右子树的值。
因此从根节点一直向左走，一直到无路可走，即得到最小值，一直向右走，直至无路可走，可得到最大值。
那么在二叉搜索树中找到最大元素和最小元素是非常简单的事情。
下图为二叉搜索树：
在这里插入图片描述
上面是二叉搜索树，那么当一个二叉搜索树的左子树和右子树不平衡的时候，那么搜索依据上图表示，搜索 9 所花费的时间要比搜索 17 所花费的时间要多，由于我们的输入或者经过我们插入或者删除操作，二叉树失去平衡，造成搜索效率降低。

7.map/multimap 容器

7.1map/multimap特性

map 具有键值和实值，所有元素根据键值自动排序。
pair 的第一元素被称为键值，第二元素被称为实值。
map也是以红黑树为底层实现机制。

map 和 multimap 区别在于，map 不允许相同 key 值存在，multimap 则允许相同 key 值存在。

8.STL容器共性机制

STL容器所提供的都是值(value)寓意，而非引用(reference)寓意，也就是说当我们给容器中插入元素的时候，容器内部实施了拷贝动作，将我们要插入的元素再另行拷贝一份放入到容器中，而不是将原数据元素直接放进容器中，也就是说我们提供的元素必须能够被拷贝。

1.除了 queue 和 stack 之外，每个容器都提供可返回迭代器的函数，运用返回的迭代器就可以访问元素。
2.通常 STL 不会抛出异常，需要使用者传入正确参数。
3.每个容器都提供了一个默认的构造函数和默认的拷贝构造函数。
4.大小相关的构造方法: 1 size()返回容器中元素的个数 2 empty()判断容器是否为空。