T:2019/11/28 W:四 17:0:11
容器和算法
1. map
和set
有什么区别,分别又是怎么实现的?
-
map
和set
都是STL
中的关联容器,其底层实现都是红黑树(RB-Tree
)。由于map
和set
所开放的各种操作接口,RB-tree
也都提供了,所以几乎所有的map
和set
的操作行为,都只是转调RB-tree
的操作行为。 -
map
和set
区别在于: 1)map
中的元素是key-value(关键字—值)对
:关键字起到索引的作用,值则表示与索引相关联的数据;set
只是关键字的简单集合,它的每个元素只包含一个关键字。 2)set
的迭代器是const
的,不允许修改元素的值;而map
虽然不允许修改关键字(Key)
,但是允许修改value
。 其原因是map
和set
都是根据关键字排序来保证其有序性的,如果允许修改key
的话,那么首先需要删除该键,然后调节平衡,再插入修改后的键值,调节平衡,如此一来,严重破坏了map
和set
的结构,导致iterator
失效。所以STL
中将set
的迭代器设置成const
,不允许修改迭代器的值;而map
的迭代器则不允许修改key
值,允许修改value
值。 3)map
支持下标操作,set
不支持下标操作。map
可以用key
做下标,map
的下标运算符[ ]
将关键码作为下标去执行查找,如果关键码不存在,则插入一个具有该关键码和mapped_type
类型默认值的元素至map
中,因此下标运算符[ ]
在map应用中需要慎用,const_map
不能用,只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用,mapped_type
类型没有默认值也不应该使用。如果find
能解决需要,尽可能用find
。
2. 请你来介绍一下STL
的allocator
STL
的分配器用于封装STL
容器在内存管理上的底层细节。- 在
C++
中,其内存配置和释放包括两个关键之:new
和delete
:new
运算分两个阶段:1) 调用::operator new
配置内存;2) 调用对象构造函数初始化对象delete
运算分两个阶段:1) 调用对象析构函数;2) 调用::operator delete
释放内存
- 在
STL allocator
将以上阶段分作四个函数分别负责:allocate函数
负责分配内存空间,deallocate函数
负责内存释放,construct
负责对象构造,destroy
负责对象析构. - 为了提升内存管理效率, 减少申请小内存造成的内存碎片化问题,
SGI STL
采用两级分配至, 当分配空间的大小超过128B
的时候,会使用第一级空间配置器, 当分配空间大小小于128B
时,采用第二级空间配置器.- 一级空间配置器直接使用
malloc
,realloc
,free
函数进行内存空间分配和释放. - 二级空间配置器使用内存池技术管理内存, 使用
16
个链表维护8-128byte
的16级别的小内存块.
- 一级空间配置器直接使用
- 参考: C++ STL 的内存优化
3. STL
迭代器删除元素
- 这个主要考察的是迭代器失效的问题。
1) 对于序列容器
vector
,deque
来说,使用erase(itertor)
后,后边的每个元素的迭代器都会失效,但是后边每个元素都会往前移动一个位置,但是erase
会返回下一个有效的迭代器 2) 对于关联容器map set来说,使用了erase(iterator)后,当前元素的迭代器失效,但是其结构是红黑树,删除当前元素的,不会影响到下一个元素的迭代器,所以在调用erase之前,记录下一个元素的迭代器即可。 3) 对于list来说,它使用了不连续分配的内存,并且它的erase方法也会返回下一个有效的iterator,因此上面两种正确的方法都可以使用。
4. STL
中MAP
数据存放形式
- 红黑树。
unordered map
底层结构是哈希表
5. STL
有什么基本组成
STL
主要由六大部分组成:容器
,迭代器
,仿函数
,算法
,适配器
,配置器
- 他们之间的关系:
- 配置器为容器提供空间, 它是对空间动态分配,管理和释放的实现
- 迭代器实现了容器和算法的衔接, 算法通过迭代器获取容器中的内容
- 仿函数可以协助算法完成各种操作,适配器用来套接适配仿函数
6. STL
中map
, unordered_map
, multimap
map
,unordermap
以及multimap
都是关联容器,实现从键值(Key
)到实值(Value
)的映射, 注意shared_ptr
等未重写小于操作符
的类型不能作为键值 1) 单映射Map
:map
中的所有元素都是pair
,pair
的第一元素为键值,第二元素为实值。所有元素都会根据元素的键值自动被排序。不允许键值重复。- 底层实现:红黑树
- 适用场景:有序键值对不重复映射
2) 多重映射
Multimap
: multimap
中的所有元素都是pair
,pair
的第一元素被视为键值,第二元素被视为实值。所有元素都会根据元素的键值自动被排序。允许键值重复。- 底层实现:红黑树
- 适用场景:有序键值对可重复映射
3) 无序映射
unordered_map
: unordered_map
中的所有元素都是pair
,pair
的第一元素被视为键值,第二元素被视为实值。其不允许键值重复, 其不会根据键值的大小自动排序.- 底层实现:
hash
表 - 使用场景: 无排序需求的键值对不重复映射
7. vector
和list
的区别,应用,越详细越好
1) vector
: 在堆上分配空间, 连续存储的容器, 支持动态调整空间大小
- 底层实现:数组(array
)
- 容器内存空间增长:
- vector
增加(插入)新元素时,如果未超过此时的容量(还有剩余空间),那么直接添加到最后(插入指定位置), 然后调整迭代器。
- 如果没有剩余空间了,则会重新配置原有元素个数的两倍空间,然后将原空间元素通过复制的方式初始化新空间,再向新空间增加元素,最后析构并释放原空间,之前的迭代器会失效。
- 性能:
- 访问:O(1)
- 插入:
- 在最后插入(空间够):很快
- 在最后插入(空间不够):需要内存申请和释放,以及对之前数据进行拷贝。
- 在中间插入(空间够):内存拷贝
- 在中间插入(空间不够):需要内存申请和释放,以及对之前数据进行拷贝。
- 删除:
- 在最后删除:很快
- 在中间删除:内存拷贝
- 适用场景:经常随机访问,且不经常对非尾节点进行插入删除。
2) List
动态链表: 在堆上分配空间,每插入一个元数都会分配空间,每删除一个元素都会释放空间。
- 底层:双向链表
- 性能:
- 访问:随机访问性能很差,只能快速访问头尾节点。
- 插入:很快,一般是常数开销
- 删除:很快,一般是常数开销
- 适用场景:经常插入删除大量数据
3) 区别:底层
, 内存的连续性
, 插入和删除的影响
, 内存分配时机
, 随机访问性能
- vector
底层实现是数组;list
是双向 链表。
- vector
支持随机访问,list
不支持。
- vector
是连续的内存空间,list
不是。
- vector
在中间节点进行插入删除会导致内存拷贝,list
不会。
- vector
一次性分配好内存,不够时才进行2
倍扩容;list
每次插入新节点都会进行内存申请。
- vector
随机访问性能好,插入删除性能差;list
随机访问性能差,插入删除性能好。
4) 应用
- vector
拥有连续的内存空间,因此支持随机访问,如果需要高效的随即访问,而不在乎插入和删除的效率,使用vector
。
- list
拥有不连续的内存空间,如果需要高效的插入和删除,而不关心随机访问,则应使用list
。
8. STL
中迭代器的作用,有指针为何还要迭代器?
1) 迭代器Iterator
- (总结)Iterator
使用聚合对象, 使得我们在不知道对象内部表示的情况下, 按照一定顺序访问聚合对象的各个元素.
- Iterator
模式是运用于聚合对象的一种模式,通过运用该模式,使得我们可以在不知道对象内部表示的情况下,按照一定顺序(由iterator提供的方法)访问聚合对象中的各个元素。
- 由于Iterator
模式的以上特性:与聚合对象耦合,在一定程度上限制了它的广泛运用,一般仅用于底层聚合支持类,如STL
的list
、vector
、stack
等容器类及ostream_iterator
等扩展iterator
。
2) 迭代器和指针的区别 - 迭代器不是指针,是类模板,表现的像指针。他只是模拟了指针的一些功能,通过重载了指针的一些操作符,->、*、++、—等。迭代器封装了指针,是一个“可遍历STL( Standard Template Library)容器内全部或部分元素”的对象, 本质是封装了原生指针,是指针概念的一种提升(lift),提供了比指针更高级的行为,相当于一种智能指针,他可以根据不同类型的数据结构来实现不同的++,—等操作。 - 迭代器返回的是对象引用而不是对象的值。
3) 迭代器产生原因
- Iterator
类的访问方式就是把不同集合类的访问逻辑抽象出来,使得不用暴露集合内部的结构就可以实现集合的遍历,是算法和容器之间的桥梁.
9. epoll
原理
- 参考:
- 调用顺序:
int epoll_create(int size);
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
int epoll_wait(int epfd, struct epoll_event *events,int maxevents, int timeout);
- 首先调用
epoll_create
创建一个epoll
描述符, 参数表示内核要监听描述符的数量, 调用成功将返回epoch
描述符,失败时返回-1
- 然后使用
epoll_ctl
对这个epoll
描述符进行操作,把待监听的描述符添加进去, 这些监听描述符将会以epoll_event
结构体的形式组成一颗红黑树 - 接着阻塞在
epoll_wait
, 当存在监听的描述符就绪时,内核将会把其对应的结构体放入一个链表中,返回就绪事件的链表, 如果调用失败返回-1
,超市返回0
10. n
个整数的无序数组,找到每个元素后面比它大的第一个数,要求时间复杂度为O(N)
- 思考: 使用一个
vector
用于管理所有待检查的数的Id, 最开始的时候num[0]
入栈, 小于这个元素的值将被入栈, 所以栈内的最小值时始终是back
元素 - 动态规划:
- 状态:
- 待匹配数组(其一定是逆序的)
- 循环Id
- 转移:
- 如果检查数 大于 带匹配数组的最小值则,则把数组里面左右小于它的都清空掉
- 无论如何都将这个数加入到带匹配数组中
- 输出:
vector<int> findMax(vector<int>num) { if(num.size()==0)return num; vector<int>res(num.size(), 0); vector<int>s; int i=0; while(i<num.size()) { while(not s.empty() && num[s.back()] < num[i]){ res[s.back()]=num[i]; s.pop_back(); } s.push_back(i++); } return res; }
- 状态:
11. STL
里resize
和reserve
的区别
resize()
:改变当前容器内含有元素的数量eg: vectorv; v.resize(len); //v的size变为len
,- 如果原来
v
的size
小于len
,则会调用零参数构造函数
进行构造,如果没有该类型没有零参数构造函数,则运行时会报错.
reserve()
:改变当前容器的最大容量(capacity)
, 它不会生成元素,只是确定这个容器允许放入多少对象,如果reserve(len)
的值大于当前的capacity()
,那么会重新分配一块能存len
个对象的空间,然后把之前v.size()
个对象通过copy construtor
复制过来,销毁之前的内存;- 测试代码如下:
#include <iostream> #include <vector> using namespace std; int main() { vector<int> a; a.reserve(100); a.resize(50); cout<<a.size()<<" "<<a.capacity()<<endl; //50 100 a.resize(150); cout<<a.size()<<" "<<a.capacity()<<endl; //150 200 a.reserve(50); cout<<a.size()<<" "<<a.capacity()<<endl; //150 200 a.resize(50); cout<<a.size()<<" "<<a.capacity()<<endl; //50 200 }