【STL】综述

STL，一文即可知

---

---

😊点此到文末惊喜↩︎

---

一、STL基本知识

概述

1. STL六大组件（前三个是主要的）
   • 容器（Containers）：使用类模板(class template)实现的各种数据结构
   • 算法（Algorithms）：使用函数模板(function template)实现的各种常用算法
   • 迭代器（Iterators）：使用类模板(class template)通过重载指针操作函数实现遍历对象集合元素的泛型指针
   • 仿函数（Functors）：使用重载operator()的class或class template实现函数对象（将对象像函数一样调用）
   • 适配器（Adaptors）：使用类模板(class template)通过修饰容器、仿函数接口或迭代器实现功能的转换
   • 分配器（Allocators）：使用类模板(class template)实现内存资源的管理
     
2. 特点
   • STL模板主要由算法、容器、迭代器三者组成，将数据和算法分离。算法通过迭代器操作容器存储的数据，其中迭代器和容器一一对应。
   • STL主要依赖于模板思想，提供了足够的通用性，减少了对OOP的依赖。
     

---

容器

1. 分类
   • 序列式容器：按位置索引，逻辑结构为线性表
     • 数组容器array<T, N>
     • 向量容器vector<T>
     • 双端队列容器deque<T>
     • 链式容器list<T>
     • 正向链容器forward_list<T>
   • 关联式容器：按键值索引，逻辑结构为树
     • set / multiset / unordered_set / unordered_multimap
     • map / multimap / unordered_map / unordered_multimap
   • 容器适配器：以序列式容器为底层构造的适配器，不是容器
     • 栈stack<T>
     • 队列queue<T>
     • 优先队列priority_queue <T>

集合	底层实现	是否有序	数值重复	更改数值	查询效率	增删效率
set	红黑树	有序	否	否	O(log n)	O(log n)
multiset	红黑树	无序	是	否	O(log n)	O(log n)
unordered_set	哈希表	无序	否	否	O(1)	O(1)
unordered_multiset	哈希表	无序	是	否	O(1)	O(1)
map	红黑树	有序	不可重复	不可修改	O(log n)	O(log n)
multimap	红黑树	有序	可重复	不可更改	O(log n)	O(log n)
unordered_map	哈希表	无序	不可重复	不可更改	O(1)	O(1)
unordered_multimap	哈希表	无序	可重复	不可更改	O(1)	O(1)

---

二、序列式容器详述

数组容器array

1. 原理：在普通数组的基础上，增加了一些功能函数
2. 特点
   • 大小固定，无法进行动态的增删
   • 可以进行随机访问或更改
3. 功能函数的作用示例
   • at(n)：返回容器中n处位置元素的引用，该函数自动检查n是否在有效的范围内，如果不是则抛出out_of_range异常

---

向量容器vector

1. 原理
   • 底层为数组，使用三个迭代器（指针）表示，start表示容器首部位置，finish表示已使用末尾位置，end_of_storage表示整个容器的末尾位置（最大容量）
     
2. vector扩容
   • 扩容原理
     • 寻找新内存：内存中寻找一个与前一段空间相比两倍大小的空间作为扩充空间
     • 拷贝旧数据：调用拷贝构造函数将原数据拷贝到新内存空间的前半段
     • 释放旧内存：调用析构函数释放原内存空间
   • 注意：一旦发生内存扩容，指向原空间的迭代器可能失效，即迭代器指针指向不变，但是内容变了，eg：erase()和insert()移动部分元素和扩容操作
   • 相关函数
     • push_back()：未达最大容量，则直接在备用空间上建构元素，并调整迭代器finish，使vector变大。已达最大容量，则进行扩容。
     • insert()：未达到最大容量，则把当前要插入元素的位置后面的元素向后移动，然后把待插入元素插入到相应的位置。已达到最大容量进行扩容。
       
3. 元素的访问
   • operator[]：直接跳转位置访问元素，速度是很快的，时间复杂度为O(1)
   • at()：本质调用operator[]，此外增加了越界检查
4. 初始化

   //定义具有10个整型元素的向量（尖括号为元素类型名，它可以是任何合法的数据类型），不具有初值，其值不确定
   vector<int>a(10);
   //定义具有10个整型元素的向量，且给出的每个元素初值为1
   vector<int>a(10,1);
   //用向量b给向量a赋值，a的值完全等价于b的值
   vector<int>a(b);
   //将向量b中从0-2（共三个）的元素赋值给a，a的类型为int型
   vector<int>a(b.begin(),b.begin()+3);
   //从数组中获得初值
   int b[7]={1,2,3,4,5,6,7};
   vector<int> a(b,b+7）;
   

5. 常用内置函数

   #include<vector>
   vector<int> a,b;
   //b为向量，将b的0-2个元素赋值给向量a
   a.assign(b.begin(),b.begin()+3);
   //a含有4个值为2的元素
   a.assign(4,2);
   //返回a的最后一个元素
   a.back();
   //返回a的第一个元素
   a.front();
   //返回a的第i元素,当且仅当a存在
   a[i];
   //清空a中的元素
   a.clear();
   //判断a是否为空，空则返回true，非空则返回false
   a.empty();
   //删除a向量的最后一个元素
   a.pop_back();
   //删除a中第一个（从第0个算起）到第二个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+3（不包括它）结束
   a.erase(a.begin()+1,a.begin()+3);
   //在a的最后一个向量后插入一个元素，其值为5
   a.push_back(5);
   //在a的第一个元素（从第0个算起）位置插入数值5,
   a.insert(a.begin()+1,5);
   //在a的第一个元素（从第0个算起）位置插入3个数，其值都为5
   a.insert(a.begin()+1,3,5);
   //b为数组，在a的第一个元素（从第0个元素算起）的位置插入b的第三个元素到第5个元素（不包括b+6）
   a.insert(a.begin()+1,b+3,b+6);
   //返回a中元素的个数
   a.size();
   //返回a在内存中总共可以容纳的元素个数
   a.capacity();
   //将a的现有元素个数调整至10个，多则删，少则补，其值随机
   a.resize(10);
   //将a的现有元素个数调整至10个，多则删，少则补，其值为2
   a.resize(10,2);
   //将a的容量扩充至100，
   a.reserve(100);
   //b为向量，将a中的元素和b中的元素整体交换
   a.swap(b);
   //b为向量，向量的比较操作还有 != >= > <= <
   a==b;
   

---

双端队列容器deque

1. 原理：由一个中控器和多个缓冲区组成，中控器中的每个节点指向一片连续的缓冲区，在逻辑上形成连续的双端队列

   // deque的迭代器数据结构
   _Elt_pointer _M_cur;  //用于保存迭代器当前位置
   _Elt_pointer _M_first; //保存迭代器当前所属buffer的开始位置
   _Elt_pointer _M_last;//保存迭代器当前所属buffer的结束位置
   _Map_pointer _M_node;  //用于保存迭代器当前所属的节点位置
   

   
2. 特点
   • 双端进行插入和删除，时间复杂度为O(1)，特别是头部插入比vector快。
   • 支持随机访问O(1)，但顺序访问比vector慢，这是由deque数据结构决定的
   • 中控器节点数量 = max(元素数量/512 + 2, 8)，512是默认的每个buffer大小。
3. 头端插入push_front()（尾部插入与该原理类似）
   • 头部buffer空间足够时，直接从后往前插入
   • 头部buffer不足时
     • 当中控器节点足够时，则申请一个头部buffer
     • 当中控器节点不足时，重新申请一整块中控器节点内存，并将buffer地址进行浅拷贝
4. 中间插入insert()
   • 检测插入位置
     • 若在前半部分则从后向前移动1位
     • 若在后半部分则从前向后移动1位
   • 移动前，现在头部或尾部进行一次尝试插入，如果buffer不足则进行扩容，足够则插入。

---

链式容器list

1. 原理：底层数据结构为一个双向循环链表(SGI STL版本，有些只是用双向链表实现)，相比双向链表只需要一个指针即可表示首尾元素（另一个通过指针的自增或自减获得）

   template<typename T,...>
   // 头节点
   class list
   {//...//指向链表的头节点，并不存放数据__list_node<T>* node;//...以下还有list 容器的构造函数以及很多操作函数
   }
   //链表节点数据结构
   struct __List_node{//...__list_node<T>* prev;// prev 指针用于指向前一个节点__list_node<T>* next;// next 指针用于指向后一个节点T myval;// myval 用于存储当前元素的值//...
   }
   

   
2. 特点
   • 链表中的迭代器只能进行前移和后移操作，通过重载运算符实现的
   • 插入删除比较方便，而且不会造成迭代器失效
   • STL中list和vector是两个最长被用的容器
3. 基本操作

size();//返回容器中元素的个数。
empty();//判断容器是否为空。
//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。
//如果容器变短，则末尾超出容器长度的元素被删除
resize(num);  
//重新指定容器的长度为num，若容器变成，则以elem值填充新位置。
//如果容器变短，则末尾超出容器长度的元素被删除。
resize(num,elem);push_back(elem);   //在容器尾部加入一个元素
pop_back();   //删除容器中最后一个元素
push_front(elem);  //在容器开头插入一个元素
pop_front();  //从哪个容器开头移除第一个元素
insert(pos,elem);  //在pos位置插elem元素的拷贝，返回新数据的位置
insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);  //在pos位置插入[beg,end)区间的数据，无返回值
clear(); //移除容器的所有数据
erase(beg,end);  //删除[beg,end)区间的数据，返回下一个数据的位置
erase(pos); //删除pos位置的数据，返回下一个数据的位置
remove(elem);  //删除容器中所有与elem值匹配的元素。

---

正向链容器forward_list

1. 原理：底层数据结构为单链表，只能使用正向迭代器进行顺序遍历。

2. 特点

   • 因为只能通过自增前面元素的迭代器来到达序列的终点，所以back()、push_back()、pop_back()、emplace_back()也无法使用
   • forward_list 的操作比 list 容器还要快，而且占用的内存更少
     

---

二、关联式容器详述

红黑树RB-Tree

1. 定义
   • 红黑树是一种自平衡的二叉查找树
   • 左右子树高度差可能大于1（与平衡二叉树的差别）
   • 每个节点具有红黑的颜色性质
     • 每个结点的颜色必定是红色或黑色
     • 根节点是黑色的
     • 所有叶子节点都是黑色的NULL结点（除叶子节点每个节点都是具有两个孩子）
     • 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
     • 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点
2. 结论
   • 原理：颜色性质约束了红黑树的大致平衡，即从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，在最坏的情况下也能保证$O(lo{g}_{2}N)$的时间复杂度
   • 证明：最短的可能路径都是黑色结点，最长的可能路径有交替的红色和黑色结点。因为根据所有最长的路径都有相同数目的黑色结点，这就表明了没有路径能多于任何其他路径的两倍长。
3. 特点
   • 操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树
   • 红黑树不会像二分搜索树一样退化为链表。
   • 红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决
4. 红黑树的旋转
   • 原因：插入和删除操作可能导致无法维持红黑树的性质
   • 基本旋转
     • 左旋：左右左，也就是左旋是把该节点作为其右孩子的左孩子
     • 右旋：右左右，也就是右旋就是把该节点作为其左孩子的右孩子
   • 一般默认插入的节点为红色，只有出现连续的红色操作才会引发自平衡操作，如果出现
     • 将插入节点的父节点变为黑色，持续向根节点进行变红的试探，如果不满足，再进行旋转操作

5. 红黑树RBT和平衡二叉树ALV的比较
   • 结构对比： RBT牺牲了高度平衡特性，换取插入和删除的引起不平衡后旋转操作的减少。
   • 查找对比： AVL 查找时间复杂度最好，最坏情况都是O(logN)，RBT在最坏情况实际略差。
   • 插入删除对比： 插入和删除结点很容易造成树结构的不平衡，而RBT的平衡度要求较低。
     • 当插入节点引起树的不平衡时，当插入一个结点都引起了树的不平衡，AVL和RBT都最多需要2次旋转操作。但在大量数据插入的情况下，RBT需要通过旋转变色操作来重新达到平衡的频度要小于AVL。
     • 当删除节点引起树的不平衡时，AVL最多需要logN 次旋转操作，而RBT最多只需要3次。
6. 应用
   • 着名的Linux的的进程调度完全公平调度程序，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间。
   • IO多路复用的epoll的的的实现采用红黑树组织管理的的的sockfd，以支持快速的增删改查。
   • Nginx的的的中用红黑树管理定时器，因为红黑树是有序的，可以很快的得到距离当前最小的定时器。

哈希表

1. 原理
   • 在关键字和存储地址间建立对应关系，使得元素的查找可以以O(1)的效率进

---

少年，我观你骨骼清奇，颖悟绝伦，必成人中龙凤。 秘籍（点击图中书籍）·有缘·赠予你

---

🚩点此跳转到首行↩︎

参考博客

1. 详解 C++ STL 六大组件，看完不懂打我…
2. 容器适配器stack,queue和priority_queue
3. array容器
4. [c++] c++ std::vector 底层实现机制
5. 基于源码剖析vector实现原理及注意事项
6. C++ STL笔记四：deque容器
7. C++ STL list容器底层实现（详解版）
8. STL之序列式容器(六)、forward_list容器
9. 红黑树
10. BST(二叉搜索树),AVL(平衡二叉树)、RBT(红黑树)的区别
11. 红黑树变色和旋转，图文案例讲解