STL

STL #

零、STL总体 #

1、STL包含什么? #

  1. 容器
  2. 迭代器:不暴露容器内部结构,对容器遍历。
  3. 算法:排序等常用算法。

2、常用的STL/容器? #

  • 顺序容器
    1. array - 固定大小
    2. vector - 动态数组
    3. list - 双向链表
    4. forward_list - 单向链表
    5. deque - 双端队列
  • 关联型
    1. map、multimap、unordered_map、unordered_multimap
    2. set、multiset、unordered_set、unordered_multiset
  • 容器适配器
    1. stack - 栈
    2. queue - 队列
    3. priority_queue - 优先队列

3、容器内部怎么删除一个元素? #

  • 顺序型:it = erase(it) 返回下一个有效的it
  • 关联型:erase(it++) 返回 void

一、vector #

1、底层原理是什么? #

是一个动态数组,装不下的时候->自动申请一片更大地空间,VS 下 1.5 倍或 GCC 下 2 倍,然后复制,释放,原来的迭代器失效。

2、为什么是1.5倍或2倍扩容? #

  • 为什么是成倍增长,而不一个固定大的值?
    1. 复杂度:均摊后可以达到O(1) vs O(n)
    2. 内存的角度:1.5倍的方式可以更好地对内存进行重复利用。因为如果2倍,下一次申请内存会大于之前分配的内存之和,无法再重用。
  • 为什么不是以 3 倍或者 4 倍增长呢? - 可能产生堆空间浪费

3、size()和capacity()的区别 #

  • size: 有多少个元素 finish - start
  • capacity: 可以容纳多少个元素 end_of_storage - start

4、扩容的两种方式reserve()和resize()的区别? #

  • reserve
    1. 预留空间,没有创建元素对象,
    2. 只改变 capacity(), 比如不能用[]下标去访问。
    3. 只有1个参数。
  • resize
    1. 改变容器大小,有创建对象
    2. 改变 capacity(),也改变了size(),可以用[]访问。
    3. 多个参数。

5、迭代器失效的情况遇到过吗? #

  1. 如果插入元素后,改变大小,引起内存重新分配,那就会全部失效
  2. 指向的那个元素被删除了,会返回下一个有效的 it = vec.erase(it)

6、怎么释放vector的内存? #

方法1:

  1. vec.clear() - 先清空内容 size() 为 0
  2. vec.shrink_to_fit(): 让 capacity 和 size 匹配,也就达到目的了。

方法2:直接vector().swap(foo)

二、list #

1、list 的底层原理知道吗? #

底层是一个双向链表,很方便插入和删除。

三、deque #

1、deque 的底层原理知道吗? #

底层是一个双端队列,方便在头部和尾部插入和删除。2、什么时候用 vector ? 什么时候用 list ? 什么时候用 deque ?

  • vector:随机存取的场景。
  • list:插入删除频繁
  • deque:需要在头部和尾部操作的时候

四、map #

1、map 底层是什么? #

底层是红黑树。

2、map 插入方式有哪几种? #

  1. insert()插入 pair 数据:map.insert( pair<int, string>(1, “xxx”))
  2. insert()使用make_pair()函数:map.insert( make_pair(1, “xxx”) )
  3. insert()插入value_type数据:map.insert( map<int, string>::value_type(1, “xxx” ))
  4. 用类似数组的方式直接插入:map[1] = “xx”

3、count 和 find 方法有什么区别? #

都可以用来判断一个key是否存在。

  • count()>0 统计出现的次数,要么 0,要么1
  • find() != end() 表示 key 存在。

4、map 与 multimap #

允不允许重复。

5、map 与 set 区别是什么? #

set相当于只有 key 没有 value,因为它的value就是key。6、map与unordered_map的区别是什么?怎么选?

  1. 查找速度:lgN与O(1)的区别,特别是大数量的情况下。
  2. 内存:若要尽量少用内存,用map。
  3. hash_map需要考虑hash函数的消耗。

五、unordered_map #

1、底层原理是什么? #

是一个哈希表。

  • 用开链法解决hash冲突。

  • 在设计bucket 数组长度的时候,内置了28个质数,创建时,选择大于等于元素个数的质数,所谓长度(或者说容量)。如果插入的个数超了,就找下一个质数,并重新计算hash值。

  • 概念

  • 用法

    1. 把所有元素变为0:直接clear(),下次[]访问的时候自动默认为0。
    2. 参考:C++ STL unordered_map容器用法详解 (biancheng.net)

六、迭代器 #

1、迭代器的底层原理 #

  • 萃取技术
  • 模板piantehua

2、迭代器失效的情形 #

  1. 插入时 - vector重新分配内存空间
  2. 删除时