文章目录

• • 一、STL基本知识
  • • 概述
    • 容器
  • 二、序列式容器详述
  • • 数组容器array
    • 向量容器vector
    • 双端队列容器deque
    • 链式容器list
    • 正向链容器forward_list
  • 参考博客

😊点此到文末惊喜↩︎

一、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
     • 向量容器vector
     • 双端队列容器deque
     • 链式容器list
     • 正向链容器forward_list
   • 关联式容器：按键值索引，逻辑结构为树
     • set / multiset / unordered_set / unordered_multimap
     • map / multimap / unordered_map / unordered_multimap
   • 容器适配器：以序列式容器为底层构造的适配器，不是容器
     • 栈stack
     • 队列queue
     • 优先队列priority_queue

二、序列式容器详述

数组容器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个整型元素的向量（尖括号为元素类型名，它可以是任何合法的数据类型），不具有初值，其值不确定
   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）;
   

5. 常用内置函数

   #include
   vector 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. 原理：底层数据结构为一个双向循环链表

   template
   struct __List_node{//...__list_node* prev;// prev 指针用于指向前一个节点__list_node* next;// next 指针用于指向后一个节点T myval;// myval 用于存储当前元素的值//...
   }
   

正向链容器forward_list

🚩点此跳转到首行↩︎

参考博客

1. 详解 C++ STL 六大组件，看完不懂打我…
2. 容器适配器stack,queue和priority_queue
3. array容器
4. [c++] c++ std::vector 底层实现机制
5. 基于源码剖析vector实现原理及注意事项
6. C++ STL笔记四：deque容器；deque内部工作原理；deque构造函数；deque赋值；deque大小；deque存取；deque排序；deque插入删除
7. 待定引用
8. 待定引用