商城网站系统建设,怎样申请网站,深圳广告公司排名,wordpress 运行天数 小工具STL原理
STL ⼀共提供六⼤组件#xff0c;包括容器#xff0c;算法#xff0c;迭代器#xff0c;仿函数#xff0c;适配器和空间配置器#xff0c;彼此可以组合套⽤。容器通过配置器取得数据存储空间#xff0c;算法通过迭代器存取容器内容#xff0c;仿函数可以协助算…STL原理
STL ⼀共提供六⼤组件包括容器算法迭代器仿函数适配器和空间配置器彼此可以组合套⽤。容器通过配置器取得数据存储空间算法通过迭代器存取容器内容仿函数可以协助算法完成不同的策略变化适配器可以应⽤于容器、 仿函数和迭代器。
容器各种数据结构如 vectorlistdequesetmap⽤来存放数据 从实现的⻆度来讲是⼀种类模板。
算法是用来操作容器中的数据的模板函数如 sort插⼊快排堆排序search⼆分查找 从实现的⻆度来讲是⼀种⽅法模板。
迭代器提供了访问容器中对象的方法。从实现的⻆度来看迭代器是⼀种将 operator*operator-operatoroperator-- 等指针相关操作赋予重载的类模板所有的 STL 容器都有⾃⼰的迭代器。
仿函数从实现的⻆度看仿函数是⼀种重载了 operator() 的类或者类模板可以帮助算法实现不同的策略。
适配器⼀种⽤来修饰容器或者仿函数或迭代器接⼝的东⻄。简单的说就是一种接口类专门用来修改现有类的接口提供一种新的接口或调用现有的函数来实现所需要的功能。
空间配置器负责空间配置与管理从实现的⻆度讲配置器是⼀个实现了动态空间配置、空间管理空间释放的类模板。
常见容器及其原理
容器可以用于存放各种类型的数据基本类型的变量对象等的数据结构都是模板类分为顺序容器、关联式容器、容器适配器三种类型三种类型容器特性分别如下 顺序式容器 容器并非排序的元素的插入位置同元素的值无关。包含vector、deque、list具体实现原理如下 1vector 动态数组。元素在内存连续存放随机存取任何元素都能在常数时间完成在尾端增删元素具有较佳的性能。 2deque 双向队列。元素在内存连续存放****随机存取任何元素都能在常数时间完成仅次于vector在两端增删元素具有较佳的性能大部分情况下是常数时间。 3list 双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成不支持随机存取。无成员函数给定一个下标i访问第i个元素的内容只能从头部挨个遍历到第i个元素。 关联式容器 元素是排序的插入任何元素都按相应的排序规则来确定其位置在查找时具有非常好的性能通常以平衡二叉树的方式实现。包含set、multiset、map、multimap具体实现原理如下 1set/multiset set 即集合。set中不允许相同元素multiset中允许存在相同元素。 2map/multimap map与set的不同在于map中存放的元素有且仅有两个成员变量一个名为first另一个名为second。map根据first值对元素从小到大排序并可快速地根据first来检索元素。 注意map同multimap的不同在于是否允许存在first值相同的元素。 容器适配器 封装了一些基本的容器使之具备了新的函数功能比如把deque封装一下变为一个具有stack功能的数据结构。新得到的数据结构就叫适配器包含stack, queue, priority_queue具体实现原理如下 1stack 栈是项的有限序列并满足序列中被删除、检索和修改的项只能是最近插入序列的项栈顶的项后进先出。 2queue 队列。插入只可以在尾部进行删除、检索和修改只允许从头部进行先进先出。 3priority_queue 优先级队列。内部维持某种有序然后确保优先级最高的元素总是位于头部最高优先级元素总是第一个出列。
迭代器
什么是迭代器
Iterator迭代器模式又称游标Cursor模式用于提供一种方法顺序访问一个聚合对象中各个元素而又不需暴露该对象的内部表示。 或者这样说可能更容易理解Iterator模式是运用于聚合对象的一种模式通过运用该模式我们可以在不知道对象内部表示的情况下按照一定顺序由iterator提供的方法访问聚合对象中的各个元素。 由于Iterator模式的以上特性与聚合对象耦合在一定程度上限制了它的广泛运用一般仅用于底层聚合支持类如STL的list、vector、stack等容器类及ostream_iterator等扩展Iterator。
#include vector
#include iostream
using namespace std;int main() {vectorint v; //一个存放int元素的数组一开始里面没有元素v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vectorint::const_iterator i; //常量迭代器for (i v.begin(); i ! v.end(); i) //v.begin()表示v第一个元素迭代器指针i指向下一个元素cout *i ,; //*i表示迭代器指向的元素cout endl;vectorint::reverse_iterator r; //反向迭代器for (r v.rbegin(); r ! v.rend(); r)cout *r ,;cout endl;vectorint::iterator j; //非常量迭代器for (j v.begin();j ! v.end();j)*j 100;for (i v.begin();i ! v.end();i)cout *i ,;return 0;
}/* 运行结果1,2,3,4,4,3,2,1,100,100,100,100,
*/ 容器的end()方法返回一个迭代器需要注意这个迭代器不指向实际的元素而是表示末端元素的下一个元素这个迭代器起一个哨兵的作用表示已经处理完所有的元素。因此在查找的时候返回的迭代器不等于end()说明找到了目标等于end()说明检查了所有元素没有找到目标。
迭代器的作用
1用于指向顺序容器和关联容器中的元素
2通过迭代器可以读取它指向的元素
3通过非const迭代器还可以修改其指向的元素
迭代器和指针的区别
迭代器不是指针是类模板表现的像指针。他只是模拟了指针的一些功能重载了指针的一些操作符–、、–等。迭代器封装了指针是一个可遍历STL容器内全部或部分元素的对象本质是封装了原生指针是指针概念的一种提升提供了比指针更高级的行为相当于一种智能指针他可以根据不同类型的数据结构来实现不同的–等操作。
迭代器返回的是对象引用而不是对象的值所以cout只能输出迭代器使用取值后的值而不能直接输出其自身。
迭代器产生的原因
Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来使得不用暴露集合内部的结构而达到循环遍历集合的效果。
迭代器什么时候会失效迭代器如何删除元素
对于顺序式容器vectordeque来说使用erase后后边的每个元素的迭代器都会失效后边每个元素都往前移动一位erase返回下一个有效的迭代器。
对于关联式容器mapset来说使用了erase后当前元素的迭代器失效但是其结构是红黑树删除当前元素不会影响下一个元素的迭代器所以在调用erase之前记录下一个元素的迭代器即可。
对于list来说它使用了不连续分配的内存并且它的erase方法也会返回下一个有效的迭代器因此上面两种方法都可以使用。
容器容器上的迭代器类别vector随机访问deque随机访问list双向set/multiset双向map/multimap双向stack不支持迭代器queue不支持迭代器priority_queue不支持迭代器
vector原理
Vector在堆中分配了⼀段连续的内存空间来存放元素随着元素的加⼊它的内部机制会⾃⾏扩充空间以容纳新元素。vector 维护的是⼀个连续的线性空间⽽且普通指针就可以满⾜要求能作为 vector 的迭代器。
vector 的数据结构中其实就是三个迭代器构成的⼀个指向⽬前使⽤空间头的 iterator⼀个指向⽬前使⽤空间尾的iterator⼀个指向⽬前可⽤空间尾的 iterator。当有新的元素插⼊时如果⽬前容量够⽤则直接插⼊如果容量不够则容量扩充⾄两倍如果两倍容量不⾜ 就扩张⾄⾜够⼤的容量。 扩充的过程并不是直接在原有空间后⾯追加容量⽽是重新申请⼀块连续空间将原有的数据拷⻉到新空间中再释放原有空间完成⼀次扩充。需要注意的是每次扩充是重新开辟的空间所以扩充后原有的迭代器将会失效。
新增元素
Vector通过一个连续的数组存放元素如果集合已满在新增数据的时候就要分配一块更大的内存将原来的数据复制过来释放之前的内存再插入新增的元素。插入新数据可以通过最后插入push_back和通过迭代器在任何位置插入insert()。通过迭代器与第一个元素的距离知道要插入的位置即int index iter - begin()这个元素后面的所有元素都向后移动一个位置在空出来的位置上存入新增的元素。
//新增元素
void insert(const_iterator iter, const T t){int index iter - begin();if (index size_){if (size_ capacity_){int capa calculateCapacity();newCapacity(capa);}memmove(buf index 1, buf index, (size_ - index) * sizeof(T));buf[index] t;size_;}
}删除元素
删除也分两种删除最后一个元素pop_back和通过迭代器删除任意一个元素erase(iter)。通过迭代器删除要先找到要删除元素的位置即int index iter - begin()这个位置后面的每个元素都想前移动一个元素的位置。erase不释放内存只初始化成默认值。
删除全部元素clear只是循环调用了erase所以删除全部元素的时候不释放内存内存是在析构函数中释放的。
//删除元素
iterator erase(const_iterator iter){int index iter - begin();if (index size_ size_ 0){memmove(buf index, buf index 1, (size_ - index) * sizeof(T));buf[--size_] T();}return iterator(iter);
}push_back和emplace_back
如果要将一个临时变量push到容器的末尾push_back()需要先构造临时对象再将这个对象拷贝到容器的末尾最后销毁临时对象。而emplace_back() 会在容器中原地创建一个对象减少临时对象拷贝、销毁的步骤所以性能更高。
如果插入vector的类型的构造函数接受多个参数那么push_back只能接受该类型的对象而emplace_back还能接受该类型的构造函数的参数。如果只有一个构造参数push_back在c11就支持只把单个的构造参数传进去了写法更简洁效果、性能跟传对象是一模一样的会进行类型自动转换。
在性能上对于内置类型性能都一样而对于用户自定义的类emplace_pack仅在通过使用构造参数传入的时候更高效。
若通过构造参数向vector中插入对象emplace_back更高效
std::vectorA a;
a.emplace_back(1);
a.push_back(2);emplace_back仅调用有参构造函数 A (int x_arg)
push_back1调用有参构造函数 A (int x_arg) 创建临时对象2调用移动构造函数 A (A rhs) 到vector中3调用析构函数销毁临时对象
插入临时对象二者一样调用移动构造函数
std::vectorA a;
a.emplace_back(A(1));
a.push_back(A(2));插入对象都需要三步走建临时对象-移动-销毁临时对象
插入实例化的对象二者还是一样调用拷贝构造函数
std::vectorA a;
A obj(1);
a.emplace_back(obj);
a.push_back(obj);注意这里调用的是拷贝构造函数拷贝-销毁临时对象。
将N个元素使用push_back插入到vector中 求push_back操作的复杂度。参考1、2
考虑vector每次内存扩充两倍的情况。如果我们插入N个元素 则会引发lgN次的内存扩充而每次扩充引起的元素拷贝次数分别为2^0, 2^1, 2^2, …, 2^lgN把所有的拷贝次数相加得到 2^0 2^1 2^2 … 2^lgN 2 * 2^lgN - 1 约为 2N次共拷贝了N次最后一个元素所以总的操作大概为3N。所以每个push_back操作分摊3次 是O(1) 的复杂度。
为什么要成倍的扩容而不是一次增加一个固定大小的容量呢
采用成倍方式扩容可以保证常数的时间复杂度而增加指定大小的容量只能达到O(n)的时间复杂度因此使用成倍的方式扩容。
为什么是以两倍的方式扩容而不是三倍四倍或者其他方式呢
考虑可能产生的堆空间浪费成倍增长倍数不能太大使用较为广泛的扩容方式有两种以2倍的方式扩容或者以1.5倍的方式扩容。以2倍的方式扩容下一次申请的内存必然大于之前分配内存的总和导致之前分配的内存不能再被使用所以最好倍增长因子设置为(1,2)之间。倍数过大容易使申请的新空间比之前已经申请的旧空间还大导致空间的无法重复利用。
resize和reserve
首先必须弄清楚两个概念 capacity该值在容器初始化时赋值指的是容器能够容纳的最多的元素的个数还不能通过下标来访问因为此时容器中还没有创建任何对象。 size指的是此时容器中实际的元素个数可以通过下标访问0 ~ (size - 1)范围内的对象。
resize和reserve区别主要有以下几点 resize既分配了空间也创建了对象reserve表示容器预留空间但没有创建对象需要通过 insert() 或 push_back() 等创建对象。 resize既修改capacity大小也修改size大小reserve只修改capacity大小不修改size大小。 两者的形参个数不一样。 resize带两个参数一个表示容器大小一个表示初始值默认为0reserve只带一个参数表示容器预留空间的大小。
vector和数组的区别 内存中的位置 C中数组为内置的数据类型存放在栈中其内存的分配和释放完全由系统自动完成vector存放在堆中由STL库中程序负责内存的分配和释放使用方便。 大小能否变化 数组的大小在初始化后就固定不变而vector可以通过push_back或pop等操作进行变化。 初始化 数组不能将数组的内容拷贝给其他数组作为初始值也不能用数组为其他数组赋值而vector可以。 执行效率 数组效率 vector效率。主要原因是vector的扩容过程要消耗大量的时间。
deque原理
vector是单向开口尾部的连续线性空间deque则是一种双向开口的连续线性空间虽然vector也可以在头尾进行元素操作但是其头部操作的效率十分低下主要是涉及到整体的移动。deque和vector的最大差异一个是deque可以在常数时间内在头端进行元素操作二是deque没有容量的概念它是由分段连续空间组合而成的可以随时增加一段新的空间并链接起来。
deque虽然也提供随机访问的迭代器但是其迭代器并不是普通的指针其复杂程度比vector高很多因此除非必要否则一般使用vector而非deque。如果需要对deque排序可以先将deque中的元素复制到vector中利用sort对vector排序再将结果复制回deque。
deque由一段一段的定量连续空间组成一旦需要增加新的空间只要配置一段定量连续空间拼接在头部或尾部即可因此deque的最大任务是如何维护这个整体的连续性。
deque的数据结构如下
class deque{...
protected:typedef pointer* map_pointer;//指向map指针的指针map_pointer map; //指向mapsize_type map_size; //map的大小
public:...iterator begin();itertator end();...
}deque内部有一个指针指向mapmap是一小块连续空间其中的每个元素称为一个节点node每个node都是一个指针指向另一段较大的连续空间称为缓冲区这里就是deque中实际存放数据的区域默认大小为512bytes。
deque的迭代器数据结构如下
struct __deque_iterator{...T* cur; //迭代器所指缓冲区当前的元素T* first; //迭代器所指缓冲区第一个元素T* last; //迭代器所指缓冲区最后一个元素map_pointer node; //指向map中的node...
} 从deque的迭代器数据结构可以看出为了保持与容器联结迭代器主要包含上述4个元素。 deque迭代器的“”、“–”操作是远比vector迭代器繁琐其主要工作在于缓冲区边界如何从当前缓冲区跳到另一个缓冲区。当然deque内部在插入元素时如果map中node数量全部使用完且node指向的缓冲区也没有多余的空间这时会配置新的map2倍于当前2的数量来容纳更多的node也就是可以指向更多的缓冲区。在deque删除元素时也提供了元素的析构和空闲缓冲区空间的释放等机制。
list原理
相比于vector的连续线型空间list显得复杂许多它的好处在于插入或删除都只作用于一个元素空间因此list对空间的运用是十分精准的对任何位置元素的插入和删除都是常数时间。list不能保证节点在存储空间中连续存储也拥有迭代器迭代器的“”、“–”操作是指针操作list提供的迭代器类型是双向迭代器。
list节点的结构见如下源码
template class T
struct __list_node{typedef void* void_pointer;void_pointer prev;void_pointer next;T data;
}从源码可看出list显然是一个双向链表。list与vector的另一个区别是list在插入和接合操作之后都不会造成原迭代器失效而vector可能因为空间重新配置导致迭代器失效。
此外list也是一个环形链表因此只要一个指针便能完整遍历整个链表。list中node节点指针始终指向尾端的一个空白节点因此是一种“前闭后开”的区间结构。
list的空间管理默认采用alloc作为空间配置器为了方便以节点大小为配置单位还定义一个list_node_allocator函数一次性配置多个节点空间。
由于list的双向特性支持在头部和尾部两个方向进行push和pop操作当然还支持erasesplicesortmergereverse等操作。
vector 和 list 对比
vector一维数组
动态数组元素在内存中连续存放随机访问任何元素都在常数时间内完成在尾端增删元素性能较好。
特点元素在内存连续存放动态数组在堆中分配内存元素连续存放有保留内存如果减少大小后内存也不会释放。
优点和数组类似开辟一段连续的空间并且支持随机访问所以它的查找效率高其时间复杂度O(1)。
缺点由于开辟一段连续的空间所以插入删除会需要对数据进行移动比较麻烦时间复杂度O(n)另外当空间不足时还需要进行扩容。
list双向链表
双向链表元素在内存不连续存放在任何位置增删元素都能在常数时间完成不支持随机访问。
特点元素在堆中存放每个元素都是存放在一块内存中它的内存空间可以是不连续的通过指针来进行数据的访问。
优点底层实现是循环双链表当对大量数据进行插入删除时其时间复杂度O(1)。
缺点底层没有连续的空间只能通过指针来访问所以查找数据需要遍历其时间复杂度O(n)没有提供[]操作符的重载。
应用场景
vector拥有一段连续的内存空间因此支持随机访问如果需要高效的随机访问而不在乎插入和删除的效率使用vector。
list拥有一段不连续的内存空间如果需要高效的插入和删除而不关心随机访问则应使用list。
删除末尾的元素指针和迭代器如何变化删除中间的元素呢
对于vector而言删除某个元素以后该元素后边的每个元素的迭代器都会失效后边每个元素都往前移动一位erase返回下一个有效的迭代器。而对于list而言删除某个元素只有指向被删除元素的那个迭代器失效其它迭代器不受任何影响。
map和unordered_map
内部实现机理
map底层是红黑树内部的元素是有序的。map中的元素是按照二叉树搜索树存储的特点就是左子树上所有节点的键值都小于根节点的键值右子树所有节点的键值都大于根节点的键值使用中序遍历可将键值按照从小到大遍历出来。
unordered_map底层是哈希表内部的元素是无序的。哈希表采用了函数映射将存储位置与记录的关键字关联起来从而实现快速查找。
优缺点以及使用场景
map
优点map底层是红黑树内部的元素是有序的查找、增删操作都可以在O(lgn)的时间复杂度下完成因此效率非常的高。
缺点空间占用率高因为map内部实现了红黑树虽然提高了运行效率但是因为每一个节点都需要额外保存父节点孩子节点以及红黑性质使得每一个节点都占用大量的空间。
适用有顺序要求的问题用map会更高效一些。
unordered_map
优点底层是哈希表查找速度非常的快。
缺点哈希表的建立比较耗费时间。
适用对于查找问题unordered_map会更加高效一些因此遇到查找问题常会考虑用unordered_map。
对于unordered_map或者unordered_set容器其遍历顺序与创建该容器时输入元素的顺序是不一定一致的遍历是按照哈希表从前往后依次遍历的。
map下标操作 [ ] 和insert的区别
insert
insert 含义是在 map 中如果key存在则插入失败如果key不存在就创建这个keyvalue。实例: map.insert((key, value))。insert接受一个pair参数并且返回值也是一个pair。
返回值pair中
第一个元素是一个迭代器如果数据插入成功则指向插入关键字的位置用-解引用可以提取pair类型元素 若插入失败迭代器指向已经存在的该元素的位置。
第二个元素是一个bool类型变量如果关键字已在map中insert什么也不做second返回false插入失败如果关键字不存在元素被插入second返回true。
下标操作 [ ]
利用下标操作的含义是如果key存在就更新value如果key不存在就创建这个keyvalue对。实例map[key] value。
哈希冲突
对于不同的关键字可能得到同一个哈希地址这种现象称之为哈希冲突也叫哈希碰撞。
如何减少哈希冲突
一个好的哈希函数可以有效的减少哈希冲突的出现那什么样的哈希函数才是一个好的哈希函数呢通常来说一个好的哈希函数对于关键字集合中的任意一个关键字经过这个函数映射到地址集合中任何一个集合的概率是相等的。
常用的构造哈希函数的方法有以下几种 除留取余法关键字key除以某个不大于哈希表长m的数p所得余数为哈希地址。即f(key) key % p, p ≤ m 直接定址法取关键字或关键字的某个线性函数值为哈希地址。即 f(key) key 或者 f(key) a * key b 数字分析法假设关键字是以r为基的数如以10为基的十进制数并且哈希表中可能出现的关键字都是事先知道的则可以选取关键字的若干位数组成哈希表。
如何处理哈希冲突
虽然我们可以通过选取好的哈希函数来减少哈希冲突但是哈希冲突终究是避免不了的。那么碰到哈希冲突应该怎么处理呢 链地址法在碰到哈希冲突的时候将冲突的元素以链表的形式进行存储也就是哈希地址相同的元素都插入到同一个链表中元素插入的位置可以是表头头插法也可以是表尾尾插法。 开放定址法当发生地址冲突时按照某种方法继续探测哈希表中的其他存储单元直到找到空位置为止。 再哈希法选取若干个不同的哈希函数在产生哈希冲突的时候计算另一个哈希函数直到不再发生冲突为止。 建立公共溢出区专门维护一个溢出表当发生哈希冲突时将值填入溢出表中。
其中比较常用的是链地址法比如HashMap就是基于链地址法的哈希表结构所以unordered_map使用开链法解决哈希冲突。
但当链表过长时哈希表就会退化成一个链表查找某个元素的时间复杂度又变回了O(n)。因此当哈希表中的链表过长时就需要我们对其进行优化。二叉搜索树的查询效率是远远高于链表的。因此当哈希表中的链表过长时可以把这个链表变成一棵红黑树。红黑树是一个可以自平衡的二叉搜索树查询的时间复杂度为O(lgn)通过这样的优化可以提高哈希表的查询效率。
map和set
参考回答 set是一种关联式容器其特性如下 1以红黑树作为底层容器所有的元素都会被自动排序 2元素只有key没有valuevalue就是key 3不允许出现键值重复 4不能通过迭代器来改变set的值因为set的键值就是关键字set的迭代器是const的 map和set一样是关联式容器其特性如下 1map以红黑树作为底层容器所有元素是通过键进行自动排序的 2所有元素都是键值存在 3不允许键重复 4map的键是不能修改的但是其键对应的值是可以修改的 综上所述map和set底层实现都是红黑树map和set的区别在于map的值不作为键键和值是分开的。
AVL树、红黑树、B树
二叉搜索树
二叉搜索树的特点是一个节点的左子树的所有节点的值都小于这个节点右子树的所有节点的值都大于这个节点。但是当每次插入的元素都是二叉搜索树中最大的元素就会退化成了一条链表查找数据的时间复杂度变成了 O(n)。
AVL树
为了解决二叉搜索树在极端情况下退化成链表的问题**平衡二叉搜索树AVL 树**在二叉搜索树的基础上增加了一些条件约束每个节点的左子树和右子树的高度差不能超过 1一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡。也就是说节点的左子树和右子树仍然为平衡二叉树这样查询操作的时间复杂度就会一直维持在 O(logn) 。
不管我们是执行插入还是删除操作只要不满足上面的条件就要通过旋转来保持平衡而旋转是十分耗时的AVL树适合用于插入与删除次数比较少但查找多的情况。
红黑树
除了平衡二叉搜索树还有很多自平衡的二叉树比如红黑树它也是通过一些约束条件来达到自平衡。
红黑树也是一种二叉搜索树红黑树每一个结点都会额外记录结点的颜色红色或者黑色。通过对任何一条从根节点到叶子节点的路径上各个结点颜色的限制红黑树确保没有一条路径会比其他路径长两倍因此红黑树是一种弱平衡树。 对于要求严格的AVL树来说红黑树为了保持平衡旋转的次数较少所以对于搜索、插入、删除操作较多的情况下红黑树的综合能力较好。
红黑树是一种含有红黑结点并能自平衡的二叉搜索树它必须满足下面性质
性质1每个结点要么是红色要么是黑色性质2根节点是黑色性质3叶子结点都是黑色性质4每个红色结点的子结点一定都是黑色性质5任意一个结点到每个叶子结点的路径包含数量相同的黑色结点。
红黑树的应用
1、广泛用于C的STL中
2、著名的Linux的的进程调度完全公平调度程序用红黑树管理进程控制块进程的虚拟内存区域都存储在一颗红黑树上每个虚拟地址区域都对应红黑树的一个节点左指针指向相邻的地址虚拟存储区域右指针指向相邻的高地址虚拟地址空间;
3、IO多路复用的epoll的实现采用红黑树组织管理的的的sockfd支持快速的增删改查;
红黑树与AVL树的区别
红黑树是一种弱平衡二叉搜索树红黑树确保没有一条路径比其它路径长出两倍在相同的节点情况下AVL树的高度低于红黑树相对于要求严格的AVL树来说红黑树的旋转次数少所以对于插入与删除较多的情况红黑树的综合能力较好。由于AVL树高度平衡因此AVL树的查询效率更高。
B树
自平衡二叉树虽然能保持查询操作的时间复杂度在O(logn)但是本质上是一个二叉树每个节点只能有 2 个子节点那么当节点个数多的时候树的高度也会相应变高这样就会增加磁盘的 I/O 次数从而影响数据查询的效率。
为了解决降低树的高度的问题后面就出来了 B 树它不再限制一个节点就只能有 2 个子节点而是允许 M 个子节点 (M2)从而降低树的高度。
B 树就是对 B 树做了一个升级MySQL 中索引的数据结构就是采用了 B 树。B 树与 B 树的差异主要有 叶子节点最底部的节点才会存放实际数据索引记录非叶子节点只会存放索引所有索引都会在叶子节点出现叶子节点之间构成一个有序链表非叶子节点的索引也会同时存在于子节点中并且是子节点中所有索引的最大或最小值非叶子节点中有多少个子节点就有多少个索引
MySQL 默认的存储引擎 InnoDB 采用 B 树作为索引的数据结构原因有
B 树的非叶子节点不存放实际的记录数据仅存放索引因此数据量相同的情况下相比于同时存储索引和数据的 B 树来说B树的非叶子节点可以存放更多的索引因此 B 树可以比 B 树更「矮胖」查询底层节点的磁盘 I/O 次数会更少。B 树有大量的冗余节点所有非叶子节点都是冗余索引这些冗余索引让 B 树插入、删除的效率都更高比如删除根节点的时候不会像 B 树那样会发生复杂的树的变化B 树叶子节点之间用链表连接了起来有利于范围查询而 B 树要实现范围查询只能通过树的遍历来完成这会涉及多个节点的磁盘 I/O 操作范围查询效率不如 B 树。
容器适配器
标准库提供了三种顺序容器适配器queue(FIFO队列)、priority_queue(优先级队列)、stack(栈)。
适配器对容器进行包装使其表现出另外一种行为。例如stackint, vectorint 实现了栈的功能但其内部使用顺序容器vectorint来存储数据 相当于是vectorint表现出了栈的行为。
堆建⽴在完全⼆叉树上分为⼤根堆、⼩根堆。其在STL中做priority_queue的助⼿即以任何顺序将元素推⼊容器中然后取出时⼀定是从优先权最⾼的元素开始取完全⼆叉树具有这样的性质适合做priority_queue的底层。
优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue默认情况下priority_queue是最大堆。
stack和queue原理
stack栈是一种先进后出的数据结构只有一个入口和出口那就是栈顶除了获取栈顶元素外没有其他方法可以获取到内部的其他元素。stack这种单向开口的数据结构很容易由双向开口的deque或者list形成只需要根据stack的性质修改某些接口即可实现stack的源码如下
template class T, class Sequence dequeT
class stack{...
protected:Sequence c;
public:bool empty(){return c.empty();}size_type size() const{return c.size();}reference top() const {return c.back();}const_reference top() const{return c.back();}void push(const value_type x){c.push_back(x);}void pop(){c.pop_back();}
};从stack的数据结构可以看出其所有操作都是围绕Sequence完成而Sequence默认是deque数据结构。stack修改某种接口来实现栈的操作成为容器适配器。
stack除了默认使用deque作为其底层容器之外也可以使用双向开口的list只需要在初始化stack时将list作为第二个参数即可。由于stack只能操作顶端的元素因此其内部元素无法被访问也不提供迭代器。
queue队列是一种先进先出的数据结构只有一个入口和一个出口分别位于最底端和最顶端。除了出口元素外没有其他方法可以获取到内部的其他元素。
类似的queue这种先进先出的数据结构很容易由双向开口的deque或者list形成只需要根据queue的性质修改某些接口即可实现queue的源码如下
template class T, class Sequence dequeT
class queue{...
protected:Sequence c;
public:bool empty(){return c.empty();}size_type size() const{return c.size();}reference front() const {return c.front();}const_reference front() const{return c.front();}void push(const value_type x){c.push_back(x);}void pop(){c.pop_front();}
};从queue的数据结构可以看出其所有操作都也都是是围绕Sequence完成Sequence默认也是deque数据结构。同样queue也可以使用list作为底层容器不具有遍历功能没有迭代器。
heap原理
heap堆并不是STL的容器组件是priority_queue的底层实现机制因为大根堆总是最大值位于堆的根部优先级最高。
二叉堆本质是一种完全二叉树二叉树除了最底层的叶子节点之外都是填满的但是叶节点从左到右不会出现空隙。
完全二叉树内没有任何节点漏洞是非常紧凑的这样的一个好处是可以使用数组来存储所有的节点因为当其中某个节点位于i处其左节点必定位于2i处右节点位于2i 1处父节点位于i / 2向下取整处。这种以数组表示二叉树的方式称为隐式表述法。
因此我们可以使用一个数组和一组堆算法来实现最大堆每个节点的值大于等于其子节点的值和最小堆每个节点的值小于等于其子节点的值。由于数组不能动态的改变空间大小用vector代替数组是一个不错的选择。
那heap算法有哪些常见有的插入、弹出、排序和构造算法
push_heap插入算法
由于完全二叉树的性质新插入的元素一定是位于树的最底层作为叶子节点并填补由左至右的第一个空格。事实上在刚执行插入操作时新元素位于底层vector的end()处之后是上溯的过程。 新元素50在插入堆中后先放在vector的end()存着之后执行上溯过程调整其根结点的位置以便满足大根堆的性质。
pop_heap算法
堆的pop操作实际弹出的是根节点将其和vector最后一个元素进行替换然后再为这个被替换的元素找到一个合适的安放位置使整颗二叉树满足完全二叉树的条件。这个被挤掉的元素首先会与根结点的两个子节点比较并与较大的子节点更换位置如此一直往下直到这个被挤掉的元素大于左右两个子节点或者下放到叶子节点为止这个过程称为下溯。 根节点68被pop之后移到了vector的最底部将24挤出24被迫从根节点开始与其子节点进行比较直到找到合适的位置安身需要注意的是pop之后元素并没有被移走如果要将其移走可以使用pop_back()。
sort算法
因为pop_heap可以将当前heap中的最大值置于底层容器vector的末尾heap范围减1那么不断的执行pop_heap直到树为空即可得到一个递增序列。
make_heap算法
将一段数据转化为heap一个一个数据插入调用上面说的两种percolate算法即可。
priority_queue原理
priority_queue优先级队列是一个拥有权值观念的queue它跟queue一样是顶部入口底部出口在插入元素时元素并非按照插入次序排列它会自动根据权值通常是元素的实值排列权值最高排在最前面。
默认情况下priority_queue使用一个大根堆完成底层容器使用的是一般为vector堆heap为处理规则来管理底层容器实现。
priority_queue的这种实现机制导致其不被归为容器而是一种容器配接器。关键的源码如下
template class T, class Squence vectorT,
class Compare lesstypename Sequence::value_tyoe
class priority_queue{...
protected:Sequence c; // 底层容器Compare comp; // 元素大小比较标准
public:bool empty() const {return c.empty();}size_type size() const {return c.size();}const_reference top() const {return c.front()}void push(const value_type x){c.push_heap(x);push_heap(c.begin(), c.end(), comp);}void pop(){pop_heap(c.begin(), c.end(), comp);c.pop_back();}
};priority_queue的所有元素进出都有一定的规则只有queue顶端的元素权值最高者才有机会被外界取用它没有遍历功能也不提供迭代器。
STL的两级空间配置器
首先明白为什么需要二级空间配置器
动态开辟内存时要在堆上申请但若需要频繁地开辟、释放堆内存则就会在堆上造成很多外部碎片浪费了内存空间。随着外部碎片增多内存分配器在找不到合适内存情况下需要合并空闲块浪费了时间大大降低了效率。于是就设置了二级空间配置器当开辟内存128bytes时即视为开辟小块内存则调用二级空间配置器。一般默认选择二级空间配置器 如果分配的内存大于128字节才选择一级空间配置器。
一级空间配置器
一级空间配置器中重要的函数就是allocate、deallocate、reallocate。一级空间配置器是以malloc()free()realloc()等C函数执行实际的内存配置 。大致过程是
使用allocate来分配内存内部会调用malloc来分配内存成功则直接返回失败就调用处理函数如果用户自定义了内存分配失败的处理函数就调用没有的话就返回异常如果自定义了处理函数就进行处理处理完再继续尝试分配内存。 二级空间配置器 会维护16条链表分别是0-15号链表最小为8字节以8字节逐渐递增最大为128字节。传入一个字节参数表示需要多大的内存会自动校对到第几号链表如需要13bytes空间我们会给它分配16bytes大小在找到第n个链表后查看链表是否为空如果不为空直接从对应的free_list中取出将已经取出的指针向后移动一位。
如果对应的free_list为空先看其内存池是不是空如果内存池不为空
先检验它剩余空间是否够20个节点大小即所需内存大小(提升后) * 20若足够则直接从内存池中拿出20个节点大小的空间将其中一个分配给用户使用另外19个当作自由链表中的区块挂在相应的free_list下这样下次再有相同大小的内存需求时可直接取出使用。
如果不够20个节点大小则看它是否能满足1个节点大小如果够的话则直接拿出一个分配给用户然后从剩余的空间中分配尽可能多的节点挂在相应的free_list中。
如果连一个节点的内存都不能满足的话则将内存池中剩余的空间挂在相应的free_list中找到相应的free_list然后再给内存池申请内存。 二级空间配置器会使用malloc()从堆当中申请内存一次所申请的内存大小为 2 * 所需节点内存大小提升后* 20 一段额外空间申请40块一半拿来用一半放内存池中。
如果malloc()失败了说明堆上没有足够空间来分配这时二级空间配置器会从比所需节点空间大的free_list中一一搜索从比所需节点空间大的free_list中取出一个节点来使用。如果这也没找到说明比其大的free_list中都没有自由区块了那就要调用一级适配器了。
释放时调用deallocate()函数若释放的 n 128则调用一级空间配置器否则就直接将内存块挂在自由链表的合适位置。
STL二级空间配置器虽然解决了外部碎片的问题提高了效率但它同时增加了一些缺点
因为自由链表的管理问题它会把我们需求的内存块自动提升为8的倍数。若需要1个字节它会给你8个字节浪费了7个字节所以它又引入了内部碎片的问题若相似情况出现很多次就会造成很多内部碎片。
二级空间配置器是在堆上申请大块的内存池然后用自由链表管理。在程序执行过程中它将申请的内存一块一块都挂在自由链表上不会还给操作系统并且它的实现中所有成员全是静态的所以它申请的所有内存只有在进程结束才会释放内存还给操作系统由此带来的问题有
1若不断的开辟小块内存最后整个堆上的空间都被挂在自由链表上若想开辟大块内存就会失败
2若自由链表上挂很多内存块没有被使用当前进程又占着内存不释放这时别的进程在堆上申请不到空间也不可以使用当前进程的空闲内存由此就会引发多种问题。
