目录

STL——标准模板库（Standard Template Library）

vector原理

vector实现机制

 vector迭代器失效场景？    

vector之间如何赋值，具体有几种方式？

list原理

map原理

set原理

底层结构

红黑树性质

红黑树比AVL树的优点

map为什么选择红黑树做底层数据结构

除了红黑树，map还可以用什么实现？？？

数据库的东西↓

红黑树性质和相对其他的优缺点

b+树相比b树

redis跳表和红黑树

红黑树目的， 插入节点的流程

红黑树 & B+ 树对比

STL——标准模板库（Standard Template Library）

C++中STL用法超详细总结_一只大笨猫的博客-CSDN博客_c++ stl

        STL的一个重要特点是数据结构和算法的分离。

        STL另一个重要特性是它不是面向对象的。主要依赖模板。

 六大组件：容器、迭代器、算法、仿函数、适配器、分配器

 序列式容器：vector 、 deque 、list

        关联式容器：set、multiset 、 map 、 multimap

迭代器 Iterator : 用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。

---

vector原理

        vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。

        vector 和数组类似，拥有一段连续的内存空间，并且起始地址不变。因此能高效的进行随机存取，时间复杂度为 o(1);但因为内存空间是连续的，所以在进行插入删除操作时，会造成内存块的拷贝，时间复杂度为 o(n)。

        另外，当数组中内存空间不够时，会重新申请一块内存空间并进行内存拷贝。连续存储结构：vector 是可以实现动态增长的对象数组，支持对数组高效率的访问和在数组尾端的删除和插入操作，在中间和头部删除和插入相对不易，需要挪动大量的数据。

        它与数组最大的区别就是 vector 不需程序员自己去考虑容量问题，库里面本身已经实现了容量的动态增长，而数组需要程序员手动写入扩容函数进形扩容。

        内存自增长 、内存占用空间只增不减

优点：

        1. 可以使用下标访问个别的元素

        2. 迭代器可以按照不同的方式遍历容器

        3. 可以在容器的末尾增加或删除元素

---

vector实现机制

维护一块连续的线性空间，空间不足时，重新配置空间，移动数据，释放原空间，会造成迭代器失效

 vector迭代器失效场景？

        1.当插入（push_back）一个元素后，end操作返回的迭代器肯定失效。

        2.当插入一个元素后，capacity返回值与没有插入元素之前相比有改变，则需要重新加载整个容器，此时first和end操 作返回的迭代器都会失效。

        3.当进行删除操作（erase，pop_back）后，指向删除点的迭代器全部失效；指向删除点后面的元素的迭代器也将全部失效。

---

vector之间如何赋值，具体有几种方式？

方法一：

//定义具有10个整型元素的向量（尖括号为元素类型名，它可以是任何合法的数据类型），不具有初值，其值不确定
vectora(10);

方法二：

//定义具有10个整型元素的向量，且给出的每个元素初值为1
vectora(10,1);

方法三：

//用向量b给向量a赋值，a的值完全等价于b的值
vectora(b);

方法四：

//将向量b中从0-2（共三个）的元素赋值给a，a的类型为int型
vectora(b.begin(),b.begin+3);

方法五：

 //从数组中获得初值
int b[7]={1,2,3,4,5,6,7};
vector a(b,b+7）;

---

list原理

        list 是由双向链表实现的，因此内存空间是不连续的。只能通过指针访问数据，所以 list 的随机存取非常没有效率，时间复杂度为 o(n);但由于链表的特点，能高效地进行插入和删除。

        非连续存储结构：list 是一个双链表结构，支持对链表的双向遍历。

        每个节点包括三个信息：元素本身，指向前一个元素的节点（prev）和指向下一个元素的节点（next）。

        因此 list 可以高效率的对数据元素任意位置进行访问和插入删除等操作。由于涉及对额外指针的维护，所以开销比较大。

区别：

        vector 的随机访问效率高，但在插入和删除时（不包括尾部）需要挪动数据，不易操作。

        list 的访问要遍历整个链表，它的随机访问效率低。但对数据的插入和删除操作等都比较方便，改变指针的指向即可。

        list 是单向的，vector 是双向的。vector 中的迭代器在使用后就失效了，而 list 的迭代器在使用之后还可以继续使用。

---

map原理

        map提供的是一种键值对容器，里面的数据都是成对出现的。每一对中的第一个值称之为关键字(key)，不可重复 （multimap 可以）；第二个称之为该关键字的对应值。

        map支持 [ ]  ， multimap 不支持。

map内部自建一颗红黑树(一 种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。

---

set原理

        关联容器，含有 Key 类型对象的已排序集。常用红黑树实现。自动排序。

底层结构

vector	数组	支持快速随机访问
list	双向链表	支持快速增删
deque	一个中央控制器和多个缓冲区
stack	一般用 list 或 deque 实现，封闭头部即可，不用 vector 的原因应该是容量大小有限制，扩容耗时
queue	一般用 list 或 deque 实现，封闭头部即可，不用 vector 的原因应该是容量大小有限制，扩容耗时（stack 和 queue 其实是适配器,而不叫容器，因为是对容器的再封装）
priority_queue	一般为 vector 为底层容器，堆 heap 为处理规则来管理底层容器实现
set	红黑树	有序，不重复
multiset	红黑树	有序，可重复
map	红黑树	有序，不重复
multimap	红黑树	有序，可重复
hash_set	hash 表	无序，不重复
hash_multiset	hash 表	无序，可重复
hash_map	hash 表	无序，不重复
hash_multimap	hash 表	无序，可重复

红黑树性质

红黑树是一颗二叉搜索树，也是多种平衡搜索树的一种，可以保证最坏情况下时间复杂度为O(lgn)。

 

 

红黑树比AVL树的优点

AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。
 

map为什么选择红黑树做底层数据结构

红黑树在查找，插入删除的性能都是O(logn)，且性能稳定，所以STL里面很多结构包括map底层实现都是使用的红黑树。

除了红黑树，map还可以用什么实现？？？

数据库的东西↓

红黑树性质和相对其他的优缺点

红黑树与AVL树，各自的优缺点总结_破碎则重建的博客-CSDN博客_红黑树的缺点

b+树相比b树

一文彻底搞懂MySQL基础：B树和B+树的区别_码农富哥-CSDN博客_b树和b+树有什么区别

redis跳表和红黑树

红黑树目的， 插入节点的流程

红黑树 & B+ 树对比

红黑树多用在内部排序，即全放在内存中的

B+树多用于外存上时，B+也被成为一个磁盘友好的数据结构； 这也是为什么 mysql索引使用b+树而不使用红黑树