免费一级a做爰网站,企业管理培训课程机构有哪些,网站 不备案,网站推广的短视频推广STL#xff0c;一文即可知 文章目录一、STL基本知识概述容器二、序列式容器详述数组容器array向量容器vector双端队列容器deque链式容器list正向链容器forward_list二、关联式容器详述红黑树RB-Tree哈希表参考博客#x1f60a;点此到文末惊喜↩︎ 一、STL基本知识
概述
STL…
STL一文即可知 文章目录一、STL基本知识概述容器二、序列式容器详述数组容器array向量容器vector双端队列容器deque链式容器list正向链容器forward_list二、关联式容器详述红黑树RB-Tree哈希表参考博客点此到文末惊喜↩︎ 一、STL基本知识
概述
STL六大组件前三个是主要的 容器Containers使用类模板(class template)实现的各种数据结构算法Algorithms使用函数模板(function template)实现的各种常用算法迭代器Iterators使用类模板(class template)通过重载指针操作函数实现遍历对象集合元素的泛型指针仿函数Functors使用重载operator()的class或class template实现函数对象将对象像函数一样调用适配器Adaptors使用类模板(class template)通过修饰容器、仿函数接口或迭代器实现功能的转换分配器Allocators使用类模板(class template)实现内存资源的管理 特点 STL模板主要由算法、容器、迭代器三者组成将数据和算法分离。算法通过迭代器操作容器存储的数据其中迭代器和容器一一对应。STL主要依赖于模板思想提供了足够的通用性减少了对OOP的依赖。 容器
分类 序列式容器按位置索引逻辑结构为线性表 数组容器arrayT, N向量容器vectorT双端队列容器dequeT链式容器listT正向链容器forward_listT 关联式容器按键值索引逻辑结构为树 set / multiset / unordered_set / unordered_multimapmap / multimap / unordered_map / unordered_multimap 容器适配器以序列式容器为底层构造的适配器不是容器 栈stackT队列queueT优先队列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
原理在普通数组的基础上增加了一些功能函数特点 大小固定无法进行动态的增删可以进行随机访问或更改 功能函数的作用示例 at(n)返回容器中n处位置元素的引用该函数自动检查n是否在有效的范围内如果不是则抛出out_of_range异常 向量容器vector
原理 底层为数组使用三个迭代器指针表示start表示容器首部位置finish表示已使用末尾位置end_of_storage表示整个容器的末尾位置最大容量 vector扩容 扩容原理 寻找新内存内存中寻找一个与前一段空间相比两倍大小的空间作为扩充空间拷贝旧数据调用拷贝构造函数将原数据拷贝到新内存空间的前半段释放旧内存调用析构函数释放原内存空间 注意一旦发生内存扩容指向原空间的迭代器可能失效即迭代器指针指向不变但是内容变了egerase()和insert()移动部分元素和扩容操作相关函数 push_back()未达最大容量则直接在备用空间上建构元素并调整迭代器finish使vector变大。已达最大容量则进行扩容。insert()未达到最大容量则把当前要插入元素的位置后面的元素向后移动然后把待插入元素插入到相应的位置。已达到最大容量进行扩容。 元素的访问 operator[]直接跳转位置访问元素速度是很快的时间复杂度为O(1)at()本质调用operator[]此外增加了越界检查 初始化//定义具有10个整型元素的向量尖括号为元素类型名它可以是任何合法的数据类型不具有初值其值不确定
vectorinta(10);
//定义具有10个整型元素的向量且给出的每个元素初值为1
vectorinta(10,1);
//用向量b给向量a赋值a的值完全等价于b的值
vectorinta(b);
//将向量b中从0-2共三个的元素赋值给aa的类型为int型
vectorinta(b.begin(),b.begin()3);
//从数组中获得初值
int b[7]{1,2,3,4,5,6,7};
vectorint a(b,b7;常用内置函数#includevector
vectorint 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个元素不包括b6
a.insert(a.begin()1,b3,b6);
//返回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为向量向量的比较操作还有 !
ab;双端队列容器deque
原理由一个中控器和多个缓冲区组成中控器中的每个节点指向一片连续的缓冲区在逻辑上形成连续的双端队列// deque的迭代器数据结构
_Elt_pointer _M_cur; //用于保存迭代器当前位置
_Elt_pointer _M_first; //保存迭代器当前所属buffer的开始位置
_Elt_pointer _M_last;//保存迭代器当前所属buffer的结束位置
_Map_pointer _M_node; //用于保存迭代器当前所属的节点位置特点 双端进行插入和删除时间复杂度为O(1)特别是头部插入比vector快。支持随机访问O(1)但顺序访问比vector慢这是由deque数据结构决定的中控器节点数量 max(元素数量/512 2, 8)512是默认的每个buffer大小。 头端插入push_front()尾部插入与该原理类似 头部buffer空间足够时直接从后往前插入头部buffer不足时 当中控器节点足够时则申请一个头部buffer当中控器节点不足时重新申请一整块中控器节点内存并将buffer地址进行浅拷贝 中间插入insert() 检测插入位置 若在前半部分则从后向前移动1位若在后半部分则从前向后移动1位 移动前现在头部或尾部进行一次尝试插入如果buffer不足则进行扩容足够则插入。 链式容器list
原理底层数据结构为一个双向循环链表(SGI STL版本有些只是用双向链表实现)相比双向链表只需要一个指针即可表示首尾元素另一个通过指针的自增或自减获得templatetypename T,...
// 头节点
class list
{//...//指向链表的头节点并不存放数据__list_nodeT* node;//...以下还有list 容器的构造函数以及很多操作函数
}
//链表节点数据结构
struct __List_node{//...__list_nodeT* prev;// prev 指针用于指向前一个节点__list_nodeT* next;// next 指针用于指向后一个节点T myval;// myval 用于存储当前元素的值//...
}特点 链表中的迭代器只能进行前移和后移操作通过重载运算符实现的插入删除比较方便而且不会造成迭代器失效STL中list和vector是两个最长被用的容器 基本操作
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 原理底层数据结构为单链表只能使用正向迭代器进行顺序遍历。 特点 因为只能通过自增前面元素的迭代器来到达序列的终点所以back()、push_back()、pop_back()、emplace_back()也无法使用forward_list 的操作比 list 容器还要快而且占用的内存更少 二、关联式容器详述
红黑树RB-Tree
定义 红黑树是一种自平衡的二叉查找树左右子树高度差可能大于1与平衡二叉树的差别每个节点具有红黑的颜色性质 每个结点的颜色必定是红色或黑色根节点是黑色的所有叶子节点都是黑色的NULL结点除叶子节点每个节点都是具有两个孩子每个红色结点的两个子结点都是黑色。从每个叶子到根的所有路径上不能有两个连续的红色结点从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点 结论 原理颜色性质约束了红黑树的大致平衡即从根到叶子的最长的可能路径不多于最短的可能路径的两倍长在最坏的情况下也能保证O(log2N)O(log_2N)O(log2N)的时间复杂度证明最短的可能路径都是黑色结点最长的可能路径有交替的红色和黑色结点。因为根据所有最长的路径都有相同数目的黑色结点这就表明了没有路径能多于任何其他路径的两倍长。 特点 操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例这个在高度上的理论上限允许红黑树在最坏情况下都是高效的而不同于普通的二叉查找树红黑树不会像二分搜索树一样退化为链表。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外由于它的设计任何不平衡都会在三次旋转之内解决 红黑树的旋转 原因插入和删除操作可能导致无法维持红黑树的性质基本旋转 左旋左右左也就是左旋是把该节点作为其右孩子的左孩子右旋右左右也就是右旋就是把该节点作为其左孩子的右孩子 一般默认插入的节点为红色只有出现连续的红色操作才会引发自平衡操作如果出现 将插入节点的父节点变为黑色持续向根节点进行变红的试探如果不满足再进行旋转操作 红黑树RBT和平衡二叉树ALV的比较 结构对比 RBT牺牲了高度平衡特性换取插入和删除的引起不平衡后旋转操作的减少。查找对比 AVL 查找时间复杂度最好最坏情况都是O(logN)RBT在最坏情况实际略差。插入删除对比 插入和删除结点很容易造成树结构的不平衡而RBT的平衡度要求较低。 当插入节点引起树的不平衡时当插入一个结点都引起了树的不平衡AVL和RBT都最多需要2次旋转操作。但在大量数据插入的情况下RBT需要通过旋转变色操作来重新达到平衡的频度要小于AVL。当删除节点引起树的不平衡时AVL最多需要logN 次旋转操作而RBT最多只需要3次。 应用 着名的Linux的的进程调度完全公平调度程序用红黑树管理进程控制块进程的虚拟内存区域都存储在一颗红黑树上每个虚拟地址区域都对应红黑树的一个节点左指针指向相邻的地址虚拟存储区域右指针指向相邻的高地址虚拟地址空间。IO多路复用的epoll的的的实现采用红黑树组织管理的的的sockfd以支持快速的增删改查。Nginx的的的中用红黑树管理定时器因为红黑树是有序的可以很快的得到距离当前最小的定时器。
哈希表
原理 在关键字和存储地址间建立对应关系使得元素的查找可以以O(1)的效率进 少年我观你骨骼清奇颖悟绝伦必成人中龙凤。 秘籍点击图中书籍·有缘·赠予你 点此跳转到首行↩︎
参考博客 详解 C STL 六大组件看完不懂打我… 容器适配器stack,queue和priority_queue array容器 [c] c std::vector 底层实现机制 基于源码剖析vector实现原理及注意事项 C STL笔记四deque容器 C STL list容器底层实现详解版 STL之序列式容器(六)、forward_list容器 红黑树 BST(二叉搜索树),AVL(平衡二叉树)、RBT(红黑树)的区别 红黑树变色和旋转图文案例讲解
