当前位置:   article > 正文

C++面试:STL篇_c++面试stl相关

c++面试stl相关

STL个人小结:

stl是c++的标准模板库,stl6大组件
容器:存储数据,本质是类模板
vector:底层是动态数组,连续内存支持随机存取,尾部增删效率高,内部增删O(n)
list:底层是双链表,内存不连续,只能顺序访问,任意位置增删都是O(1)
deque:整体连续,支持随机存取,首尾增删效率高,但是迭代器太复杂,所以一般只有当既要随机存取又要首尾增删采用deque。
unordered_set:无序集合,去重,用于查找元素是否存在
unordered_map:用于查找元素是否存在及其出现次数。
map:底层红黑树,有序,也是用于查找元素,它的特点就是稳定。
multimap,multiset允许键重复

算法:处理数据,本质是函数模板,如find,sort
迭代器:是个模板类,提供了一种通用的遍历容器的接口,使我们不需要关心容器具体的实现细节。迭代器内部封装了指针,它像是一个智能指针,所以它的通用性、安全性比一般指针更好。
迭代器失效的情况:vector:尾部增删,尾迭代器end失效,中间增删:增删位置之后的迭代器全部失效,且若插入元素使得size==capacity,则全部失效。deque和vector一样。而list/map/set删除节点仅当前节点的迭代器失效。所以对于序列式容器:it = v.erase(it); 关联式容器:c.erase(it++);

仿函数:也叫函数对象:重载了函数调用运算符operator()的类,把函数操作封装在类里,复用性高。

class A{
public:
    bool flag;
    A(bool a): flag(a) {}
    bool operator()(int a, int b) {return flag ? a < b : a > b;}
};
int main() {
    vector<int>nums{1,3,2};
    sort(nums.begin(), nums.end(), A(0));//只需要改变一个数字就可实现升降序
    cout << nums[0];
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

适配器:用于把一个现有类的接口转换成我们需要的接口,像栈,队列,优先级队列就是容器适配器,底层由deque实现,上层提供不同的接口功能。
空间配置器allocator:c++里的new/delete都是2个操作,stl allocator把他们分开:对象构造有construct()负责,对象释放由destroy()负责(内部调用构造和析构函数),内存配置由allocate()负责,内存释放由deallocate()负责。Stl采用两级空间配置器,主要是更好的处理小内存(brk的内存池管理差一点)。当需要的内存<=128字节,调用二级配置器,>128字节,调用一级配置器。一级配置器中allocate(),deallocate()内部就是malloc,free(我们知道大于128k时malloc调用的是mmap)。二级配置器使用内存池机制,他用一个数组维护16条链表,每个链表挂着不同大小的内存块,0号链表挂的全是8字节的内存块,最大128字节,他会按你的需要去查找对应大小链表是否空闲,若不够就找更大的链表,若不空闲就要向内存池申请,若所有链表都无法满足,就调用一级配置器。
vector:底层是动态数组,可以动态扩容,扩容过程:当size>capcity,先重新申请一块1.5(vs)/2(gcc)倍大小的连续内存,拷贝原数据,释放原内存。为什么是成倍扩容:若是固定大小扩容,当数据增多可能导致频繁扩容,效率太低了,而成倍扩容可以较好的应对元素数量变化,减少扩容次数,所以选择成倍扩容,考虑内存的使用,倍数不能太大。
vector释放空间:vector空间是只增不减的,即clear(清空容器size变0),resize只会动size,不会动capcity,reserve改变最大容量,只有大于当前的才会生效。只有析构才会回收空间。

priority_queue:优先级队列,一般vector为底层容器,堆为数据处理规则,它有着队列的操作,且对数据进行优先级排列,常见的大小顶堆排列规则。
push_back:一定有拷贝操作,而emplace_back()支持直接传入多个构造参数,在尾部就地构造,不会拷贝。

class A{
public:
    int a, b;
    A(int a, int b):a(a), b(b) {cout << "默认构造";}
    A(const A& a) {cout << "拷贝构造";}
};
int main() {
    vector<A> v;
    //v.emplace_back(1,2); 默认构造
    v.push_back(A(1,2));//默认+拷贝
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

deque:双端队列,以多段连续空间组成。
结构:采用一块map数组作中控台,存的每个元素都是指针,分别指向一段连续内存,叫缓冲区,这里就是存储数据的地方。deque的迭代器有4个,cue指向缓冲区当前元素,first指向缓冲区头,last指向尾,使得首尾增删效率高,node指向map主控。当当前缓冲区遍历完就要通过node访问中控台,得到下一个指针来到下一块缓冲区。维护了整体连续的假象,支持随机存取。且扩容也方便:只需要在map数组里添加指针元素指向新内存即可,不需要像vector那样麻烦。

哈希表:数组+链表的结构,unordered_map/unordered_set底层都是哈希表,无序,首先定义一个哈希函数如取余法,把key映射到哈希表的数组的索引上,即把元素放入哈希表,但是不同元素通过哈希函数计算结果可能相同,即哈希冲突,一般用拉链法挂着一个链表下、线性探测(向后找,找到表尾再回表头,直到找到空桶)、扩容(设置合适的负载因子(元素数量/哈希表尺寸),unordered_map默认是1,可减小减少哈希冲突)、设计一个合适的哈希函数。后续查找先通过哈希函数定位到他在数组哪个位置O(1),再遍历链表,只要哈希冲突不严重,链表不是很长,也是O(1),所以查找是O(1),增删在链表上操作,也是o(1),即增删改查都是O(1)。

map和set:底层红黑树,set的节点是value, map的节点是键值对,有序,set的迭代器是const,不允许修改元素值,map可以修改value,支持下标操作,但不能改key。
**红黑树:**得先说2叉查找树,它容易出现单链表情况,所以有了AVL树(任何节点的左右子树高度差<=1)通过旋转保持高度平衡保证查找效率,但每次增删节点都要旋转整棵树,所以增删效率很低。而红黑树则是二叉查找数和AVL树的折中,他是大致平衡的二叉查找树。红黑树:它的节点是黑或红,根节点是黑,叶节点都是黑色的空结点,红节点的子节点都是黑的,且任一节点到每个叶节点的所有路径包含相同数目的黑节点。这5条性质保证它的大致平衡即查找时间基本是logn,增删节点通过变色和旋转,且只旋转该节点到叶节点保证它的增删时间是logn。所以增删改查都是logn。故若查找操作多,增删操作少,用AVL树,若2者操作数差不多,用红黑树。红黑树与哈希表相比就是有序,稳定,增删改查都是Ologn,哈希表理论上是O(1),但若发生严重的冲突就是O(n)。

map[]和find:map[]访问若存在返回引用,不存在会创建一个新的键值对,不会报错。find用于查询键若存在返回迭代器,不存在返回map.end()的迭代器

stack,queue:容器适配器,底层默认deque实现

array: 底层是静态数组,相当于把静态数组变成了容器,使得它可以使用一些容器的操作。

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号