STL容器

STL容器

[TOC]

1. std::vector的底层存储机制

vector是一个动态数组,里面有一个指针指向一片连续的内存空间,当空间不够装下数据时,会自动申请另一片更大的空间。(通常是当前容量的50%或者100%),然后把原来的数据拷贝过去,接着释放原来的那片空间;当释放或者删除里面的数据时,其存储空间不释放,仅仅是清空了里面的数据。

2. std::vector的自增长机制

同一

3. std::list的底层存储机制

以节点为单位存放数据,节点的地址在内存中不一定连续,每次插入或者删除一个元素,就配置或者删除一个元素空间。

4. 什么时候用vector,什么时候用list

vector可以随机存储元素(可以通过公式直接计算出元素地址,而不需要挨个查找),但在非尾部插入或者删除数据时,效率很低,适合对象简单,对象数量变化不大,随机访问频繁的数据。

list不是随机存储,适用于对象大,对象数量变化频繁,插入和删除频繁的数据操作

5. list自带的排序函数的排序原理

6. vector和list的插入删除有啥区别

vector的插入和删除,需要对现有数据进行复制移动,如果vector存储的对象很大或者构造函数很复杂,则开销较大,若是简单的小数据,则效率比list高。

list插入和删除,都需要对现有数据进行遍历,在首部插入的效率比较高。

7. std::deque的底层机制


deque动态地以分段连续空间组合而成,随时可以增加一段新的连续空间并链接起来。不提供空间保留功能。

注意:除非必要,我们尽可能选择使用vector而非deque,因为deque的迭代器比vector迭代器复杂很多。对deque排序,为了提高效率,可先将deque复制到一个vector上排序,然后再复制回deque。

deque采用一块map(不是STL的map容器)作为主控,其为一小块连续空间,其中每个元素都是指针,指向另一段较大的连续空间(缓冲区)。

deque的迭代器包含4个内容:

1)cur:迭代器当前所指元素

2)first:此迭代器所指的缓冲区的头。

3)last:缓冲区尾。

4)node:指向管控中心。


8.std::map底层机制

map以红黑树为底层机制。这是一个平衡二叉搜索树,自动排序的效果好。

通过map的迭代器不能修改其键值,只能修改其实值。所以map的迭代器既不是const也不是mutable。


9. hashtable如何避免地址冲突

  • 线性探测:先用hash function计算某个元素的插入位置,则继续向下寻找,直到找到一个可用位置。其删除采用惰性删除:只标记删除记号,实际删除操作等到表格重新整理时再进行
  • 二次探测:

10. hash_map和map的区别

构造函数:hash_map需要hash_function和等于函数,而map需要比较函数

存储结构:hash_map以hashtable为底层,而map以RB-TREE为底层

hash_map查找速度比map快,而且速度基本与数据量无关,属于常数级别。而map的查找速度时logn级别。

如果考虑效率,尤其是元素达到一定数量级的时候,用hash_map

考虑内存,或者元素数量较小的时候,用map

11. hashtable,hash_set,hash_map的区别

hash_set以hashtable为底层,不具有排序功能,能快速查找。其键值就是实际的值。(set以红黑树为底层,有排序功能。)

hash_map以hashtable为底层,没有自动排序功能,能快速查找,每一个元素同时拥有一个键值和实值。(map以红黑树为底层,有排序功能。)

12. 红黑树性质

1)每个结点是红色或者黑色。

2)根结点为黑色。

3)叶结点为黑色的NULL结点。

4)如果结点为红,其子节点必须为黑。

5)任一结点到NULL的任何路径,所含黑结点数必须相同。

13. map和set的3个问题

1)为何map和set的插入删除效率比其他序列容器高

因为不需要内存拷贝和内存移动

2)为何map和set每次insert之后,以前保存的iterator不会失效

因为插入操作只是节点指针变换,节点内存没有改变。而iterator就像指向节点的指针,内存没变,指向内存的指针也不会变

3)当数据元素增多时,例如10000到20000,map的set查找速度如何变化

红黑书使用二分查找法,时间复杂度为logn,所以从10000增大到20000,查找次数从log10000=14变为log20000=15,多了一次而已

14. vector中begin和end函数返回啥

​ begin返回的是第一个元素的迭代器,end返回的时最后一个元素后面位置的迭代器

15. vector的插入操作可能会导致迭代器失效

插入操作可能导致vector动态增加大小,此时并不是在原空间后增加新的空间,而是以原大小的两倍配置一片空间并将原内容拷贝过来,释放原来的空间。由于操作改变了空间,所以迭代器失效

16. vector,list,map,deque,用了erase(it)后迭代器的变化

vector和deque是序列式容器,其内存分别是连续空间和分段连续空间,删除迭代器it后,其后面的迭代器都失效了,此时it及其后面的迭代器会自动加1,使it指向被删除元素的下一个元素。

list删除迭代器it时,其后面的迭代器都不会失效,将前面和后面连接起来即可。

map也是只能使当前删除的迭代器失效,其后面的迭代器依然有效。

17. hashtable和hashmap的区别

hashtable以hashmap为底层。有几点不同

1)hashtable是Dictionary的子类,而hashmap是map接口的一个实现类

2)hashtable中的方法是同步的,而hashmap的方法不同步

JSRUN notes