大厂面试八股文——STL_stl八股

STL理解

① 长久以来，软件界一直希望建立一种可重复利用的东西。

② C++的面向对象和泛型编程思想，目的就是复用性的提升。

③ 大多数情况下，数据结构和算法都未能有一套标准，导致被迫从事大量重复工作。

④ 为了建立数据结构和算法的一套标准，诞生了STL。

STL （standard template Library ） STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。STL现在是C++的一部分，因此不用额外安装什么。

① STL大体分为六大组件，分别是：容器、算法、迭代器、仿函数、适配器(配接器)、空间配准器。

1. 容器：各种数据结构，如vector、list、deque、set、map等，用来存放数据。
2. 算法：各种常用的算法，如sort、find、copy、for_each等。
3. 迭代器：扮演了容器与算法之间的胶合剂。
4. 行为类似函数，可作为算法的某种策略。
5. 一种用来修饰容器或者仿函数或迭代器接口的东西。
6. 空间配置器：负责空间的配置与管理

STL空间适配器

空间的配置和释放分为两级，第一级配置器仅是对于malloc和free的封装，并没有对效率的强化。因此有了第二级配置器，用了内存池的思想，提高了效率

第一级配置器

1. 一级空间配置器分配的是大于128字节的空间
2. 如果分配不成功，调用句柄释放一部分内存
3. 如果还不能分配成功，抛出异常

第二级配置器

维护一个链表，链表每个节点是8的倍数大小，每一个子链表拥有相同大小的节点。

• 当用户申请的空间小于128字节时，将字节数扩展到8的倍数，然后在自由链表中查找对应大小的子链表
• 如果在自由链表查找不到或者块数不够，则向内存池进行申请，一般一次申请20块
• 如果内存池空间足够，则取出内存
• 如果不够分配20块，则分配最多的块数给自由链表，并且更新每次申请的块数
• 如果一块都无法提供，则把剩余的内存挂到自由链表，然后向系统heap申请空间，如果申请失败，则看看自由链表还有没有可用的块，如果也没有，则最后调用一级空间配置器

如果分配的区块够大，大于128bytes,就移交给第一级配置器处理，当区块小于128bytes时，以内存池管理，每次配置一大块内存，并维护对应之自由链表。下次再有相同大小的内存需求，直接从内存池中在取出即可。

二级配置器主动将所需内存调整至8的倍数。二级配置器内维护16个链表，各自管理8,16,24，。。。128大小的内存块。

sort

1.如果序列元素数量较少，那么应该采用插入排序。

n=16

插入排序在元素较少的情况下时间复杂度会趋向于O(N)，而快速排序在元素较少的情况下，也更容易出现O(NlogN)向O(N^2)退化的情况，除此之外，快速排序内部是会递归排序的，这是无可避免的，在元素较少的情况下，多次递归调用所影响的效率降低也是值得考虑的。介于此，SGI STL认为，在元素较少的情况下，插入排序会比快速排序表现更好。

2.在快速排序过程中，如果递归子区间的元素个数较少，那么就停止快速排序，转而使用插入排序

快排由于本身还需要有递归的消耗，所以插入排序在小数组的情况下效果会好一些

3.快速排序递归深度不宜过深，过深则用堆排序来替代。

快速排序是一个递归的过程，越往下递归，子区间越小，递归消耗就越大，还可能造成栈溢出。但是如果此时子区间还没有达到插入排序的阈值该怎么办呢？既然此时不能再从子区间元素数量来衡量，那么就可以从递归深度来衡量，这样还可以避免递归栈溢出。

那么如何去衡量“递归深度”呢？SGI STL用2log(N)来作为快速排序的最大递归深度。举个例子，40个元素，那么快速排序递归的最大深度就是2log(40)=2*5=10，也就是说，如果快速排序递归了10次，还没达到插入排序的阈值，那么就不应当再使用快速排序了，此时就会转为使用堆排序，对该子区间的元素进行排序。使用堆排序来代替的好处是可以让时间复杂度保持在O(NlogN)

STL六大组件

• 容器
• 算法
• 迭代器
• 仿函数
• 配接器:一种用来修饰容器或仿函数或迭代器接口的东西,如queue和stack,底层结构
• 配置器:负责空间配置与管理

STL的中心思想在于：将数据容器（containers）和算法（algorithms）分开，彼此独立设计，最后再以一贴胶着剂将它们撮合在一起。容器和算法的泛型化，可以用C++的class template 和 function template 来实现。而迭代器就是两者之间的胶着剂。

迭代器相应型别（associated types）

associated types总共有五种类型: value_type,difference_type,pointer,reference,iterator_cotegory。

其中value_type可以利用function template的argument deducation,但是它只能推导参数的型别，无法推导函数的返回值的型别。

Partial Specialization(偏特化)的意义

在泛化设计中提供了一个特化版本（将泛化版本中的某些template参数赋予明确的指定）。

万一value_type必须用于函数传回值，模板参数推导机制只能推断参数，而无法推断函数的回返值型别。我们需要其他的方法：声明内嵌。

引入萃取之后，不论面对的是迭代器MyIter，或是原生指针int或是const int,都可以通过traits取出正确的value_type。

1.vetcor

vetcor维护连续线性空间,自行扩充新的元素

protected:
    iterator start;
    iterator finish;
    iterator end_of_storage;
1
2
3
4

如果备用空间容量不足，容量会扩充至2倍

动态扩容是只分配原来大小两倍的新空间，然后将源数据拷贝到新空间，再将新空间构造新元素，最后释放原空间，指向原vector的所有迭代器指针失效。

2.list双向链表

底层数据结构为双向环形链表，支持快速增删。插入和删除一个元素，就配置一个或删除一个元素空间，插入和删除，常数时间。

每次插入和删除一个元素,就配置和释放一个元素空间,插入和删除,时间为常数

链表进行排序，不能使用STL的sort函数，必须使用自己。
STL算法sort()函数只接受RamdonAccesslterator

迭代器具有前移和后移的能力.

插入和结合(splice)不会造成迭代器的失效,但vector的插入可能造成迭代器的失效

3.deque双向队列

双向开口的数据结构，可以在两端进行插入和删除操作。deque表象连续，内部不连续,
中控器map提供多个缓冲区（节点）,每个缓冲区有3个迭代器指针

deque不是普通的指针

deque没有容量的概念,随时可以增加一个新的空间并连接起来,没有vector空间保留的

first指向缓冲区的头
end  指向缓冲区的尾
cur  指向缓冲区所指的现行元素
1
2
3

map前端与尾端节点的备用空间不足，引发缓冲区重新配置

map中控器是一小块连续空间,其中每个元素都是一个指针,指向一个连续线性空间,称为缓冲区.,缓冲区的大小为8

push_back()
push_front()
pop_back()
pop_front()
clear()//deque最初状态保留一个缓冲区
erase()
1
2
3
4
5
6

3.1.stack()堆

先进先出，以容器deque()为底层结构，封闭其头部端口形成一个stack，没有迭代器，也不允许遍历

pop()
push()
top()
empty()
size()
1
2
3
4
5

3.2.queue队列

先进先出的数据结构，底端插入，顶端删除，不允许遍历
以deque()或list()为底层结构，封闭底部出口，顶部的入口，形成queue

queue<Type>M 定义一个queue的变量 
M.empty()    查看是否为空范例 是的话返回1，不是返回0;
M.push()     从已有元素后面增加元素 
M.size()     输出现有元素的个数
M.front()    显示第一个元素      
M.back()     显示最后一个元素
M.pop()      清除第一个元素 
1
2
3
4
5
6
7

4.红黑树RB-tree

二叉搜索树

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值
• 若它的右子树不空 ，则右子树上所有结点的值均大于它的根结点的值
• 它的左、右子树也分别为二叉排序树

通过中序遍历即可得出有序的序列， 构造一棵二叉搜索树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度

红黑树是一颗二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是红色和黑色

4.1 set、multiset

set/multiset以rb_tree为底层结构，具有自动排序特性，排序依据是key，set/multiset元素的value和key合一，value就是key

• set不允许键值重复，插入操作采用的是底层RB-tree的insert_unique()

• multiset允许键值重复，插入操作采用的是底层RB-tree的insert_equal()

begin()--返回指向第一个元素的迭代
end()--返回指向最后一个元素的迭代器
clear()--清除所有元素
size()--集合中元素的数目
max_size()--返回集合能容纳的元素的最大限值
empty()--如果集合为空，返回true
swap()--交换两个集合变量
insert()--在集合中插入元素
erase()--删除集合中的元素
find()--返回一个指向被查找到元素的迭代器
count()--返回某个值元素的个数
lower_bound()--返回指向大于（或等于）某值的第一个元素的迭代器
upper_bound()--返回指向小于（或等于）某值的第一个元素的迭代器
equal_range()--返回集合中与给定值相等的上下限的两个迭代器
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.2 map、multimap

map/multimap以rb_tree为底层结构，根据元素的键值key自动排序，所有的元素都是pair，都具有实值value和键值key。pair<键值，实值>

map

• 下标取值的算法是先查找是否有此key，没有就插入一个默认值作为该key的value

• 使用find函数对键进行查找，返回指向键的迭代器，若不存在，则返回map的尾端

数组和链表优缺点

• 数组：固定长度，减小内存浪费，方便遍历(通过下标存取)，删除操作后面依次前移，插入操作依次后移
• 链表：动态分配存储，方便增减\插入\删除操作、遍历通过指针依次进行，堆分配空间

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-k2N2aQg0-1649155130672)(/home/xiaohu/.config/Typora/typora-user-images/image-20200807112703817.png)]

5 hashtable

STL源码剖析——hashtable
二叉搜索树具有对数平均时间，但这样的表现构造在一个假设上：输入数据有足够的随机性
hashtable（散列表）的数据结构，插入、删除、搜寻等操作具有常数平均时间,最坏的情况下:O(n)

hashtable(哈希表）

基本原理是：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶

了避免哈希表太大，需要用到某种映射函数，将大数映射为小数，这种函数称为散列函数hash function。但hash function会带来碰撞问题，即不同的元素被映射到相同位置。

线性探测：在哈希表的连续空间上，当发生冲突的时候，向后存储。

hashtable存取过程

hash_map，首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。其插入过程是：

• 得到key
• 通过hash函数得到hash值
• 得到桶号(一般都为hash值对桶数求模)
• 存放key和value在桶内。

hashtable 中桶子的大小一般设计为一个质数，至于为什么大家需要自行百度，这里我讲不明白。SGI STL 中先把 28 个质数准备好，以备随时访问，同时提供一个函数，用来查询在这 28 个质数之中，“最接近某数并大于某数” 的质数：

*当桶内的元素总个数大于桶子个数时，就会使桶子个数增长到其两倍附近的质数，所以桶子数一定比元素个数多。例子中为97，然后所有元素再执行H=hashcode%桶子数*

SGI STL中 hashtable容器的内部实现就是使用的【开链】方法。

其中键值序列，使用的是vector，而vector的大小，取的是一个质数集合，一共28个常数，大于53，且相邻质数的关系为：2的倍数中最接近的质数。

如果传入的键大小为50，那么hashtable建立的时候，就会取出__stl_prime_list的53，并建立vector。

• hashtable的迭代器没有后退操作，也没有逆向迭代器。
• 桶子维护的linked list(可单向可双向）,并不是标准库中的list,而是自行维护hash table node

哈希函数构造主要有以下几种：

1：直接寻址法；

2：取模法；

3：数字分析法；

4：折叠法；

5：平方取中法；

6：除留余数法；

7：随机数法。

处理冲突主要方法有：

• 线性探查。该元素的哈希值对应的桶不能存放元素时，循序往后一一查找，直到找到一个空桶为止，在查找时也一样，当哈希值对应位置上的元素与所要寻找的元素不同时，就往后一一查找，直到找到吻合的元素，或者空桶。

• 二次探查。该元素的哈希值对应的桶不能存放元素时，就往后寻找1^2,22,3^2,42…i^2个位置。

• 双散列函数法。当第一个散列函数发生冲突的时候，使用第二个散列函数进行哈希，作为步长。

• 开链法。在每一个桶中维护一个链表，由元素哈希值寻找到这个桶，然后将元素插入到对应的链表中，STL的hashtable就是采用这种实现方式。

• 建立公共溢出区。当发生冲突时，将所有冲突的数据放在公共溢出区。

vector和list的区别

vector和数组类似，拥有一段连续的内存空间。vector申请的是一段连续的内存，当插入新的元素内存不够时，通常以2倍重新申请更大的一块内存，将原来的元素拷贝过去，释放旧空间。因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为o(n)。

list是由双向链表实现的，因此内存空间是不连续的。只能通过指针访问数据，所以list的随机存取非常没有效率，时间复杂度为o(n); 但由于链表的特点，能高效地进行插入和删除。

vector拥有一段连续的内存空间，能很好的支持随机存取，因此vector::iterator支持“+”，“+=”，“<”等操作符。

list的内存空间可以是不连续，它不支持随机访问，因此list::iterator则不支持“+”、“+=”、“<”等

vector::iterator和list::iterator都重载了“++”运算符。

总之，如果需要高效的随机存取，而不在乎插入和删除的效率，使用vector;

如果需要大量的插入和删除，而不关心随机存取，则应使用list。

unordered_map和map的区别

unordered_map是使用哈希实现的，占用内存比较多，查询速度比较快，是常数时间复杂度。它内部是无序的，需要实现==操作符。

map底层是采用红黑树实现的，插入删除查询时间复杂度都是O(log(n))，它的内部是有序的，因此需要实现比较操作符(<)。

算法equal

equal：判断两个序列是否相等 ，要求序列2的元素个数大于等于序列1的元素个数

// 如果序列在[first, last)内相等, 则返回true, 如果第二个序列有多余的元素,
// 则不进行比较, 直接忽略. 如果第二个序列元素不足, 会导致未定义行为
template <class InputIterator1, class InputIterator2>
inline bool equal(InputIterator1 first1, InputIterator1 last1,
		  InputIterator2 first2)
{
  for ( ; first1 != last1; ++first1, ++first2)
    if (*first1 != *first2)     // 只要有一个不相等就判定为false
      return false;
  return true;
}
 
// 进行比较的操作改为用户指定的二元判别式, 其余同上
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
inline bool equal(InputIterator1 first1, InputIterator1 last1,
		  InputIterator2 first2, BinaryPredicate binary_pred)
{
  for ( ; first1 != last1; ++first1, ++first2)
    if (!binary_pred(*first1, *first2))
      return false;
  return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22