C++面试总结之STL（一）

1. 什么是STL？

标准模板库（STL），它的基本概念就是把数据和操作分离，含有容器、算法、迭代器组件等。迭代器是容器和算法之间的粘合剂，使任何算法都可以和任何容器进行交互操作。

在STL中体现了泛型程序设计的思想，是以类型参数化的方式实现的（模板）。

STL中的容器：

序列容器：vector   string   deque   list

关联容器：set   map   multiset   multimap

适配容器：stack   queue   priority_queue（优先队列）

2.Vector的底层是怎样的

vector就是动态数组.

在堆中分配内存,元素连续存放,有保留内存,如果减少大小后，内存也不会释放.如果新值>当前大小时才会再分配内存.当该数组后的内存空间不够时，需要重新申请一块足够大的内存并进行内存的拷贝。内部使用allocator类进行内存管理，程序员不需要自己操作内存。对 vector 的任何操作，一旦引起空间重新配置，指向原 vector 的所有迭代器就都失效了。

注：size_t是无符号整数！！！！

template<class _Ty, class _Ax>

class vector: public _Vector_val<_Ty, _Ax> {  //varying size array of values
    public:
    protected:
        pointer _Myfirst;   // pointer to beginning of array
        pointer _Mylast;    // pointer to current end of sequence
        pointer _Myend; // pointer to end of array
};

Vector提供的函数：

v.begin()  v.end()  v.size()  v.capacity()  
v.push_back()  v.pop_back()
v.erase(iterator position)  v.erase(iterator begin, end)  ：执行后后面元素自动前移
v.clear()
v.insert(position, size_type n, const &x) 

3. list的实现，vector和list的区别 

list和vector的区别：

（1）实现方式：vector是基于动态数组，内存空间是连续的，因此支持下标访问；list是基于双向链表，内存是不连续的，不支持下标访问，支持指针访问。

（2）如果需要高效的存取，而不在乎插入和删除的效率，选取vector。如果需要大量的插入删除而关心随机存取，选用list。

List.erase(it)执行后，迭代器it指向的内存已失效，再访问违规

List提供的函数： 

push_back   push_front  front  back  insert

4. Deque

Deque支持随机访问和存取，支持下标访问，插入删除的效率也很高。是由一段一段定量的连续空间组成的。

实现：map+buffer

插入元素时随时可以重新增加一段新的空间并连接起来。

提供的函数：

Push_back()  pop_back()  push_front()  pop_front()
Clear()  erase()  insert()
Deque.at()  deque.front()  deque.back()
Deque.begin()  deque.end()  deque.rbegin()  deque.rend()

Deque的迭代器：

首先，它必须能够指出分段连续空间（亦即缓冲区）在哪里，其次它必须能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退就必须跳跃至下一个或上一个缓冲区。为了能够正确跳跃，deque必须随时掌握管控中心（map）。所以在迭代器中需要定义：当前元素的指针，当前元素所在缓冲区的起始指针，当前元素所在缓冲区的尾指针，指向map中指向所在缓区地址的指针，分别为cur, first, last, node。

5.Stack queue

Stack和 queue是基于deque实现的 。stack和 queue没有迭代器，不提供走访功能。

//Stack： 
top()  
push()  
pop()

//Queue： 
front()  
back()  
push()  
pop()

6.heap

Heap不属于STL容器组件，它扮演priority queue的助手，作为其底层机制。Heap分为max_heap和min_heap两种，STL提供max_heap，底层以vector实现。

提供的函数有：

make_heap(vector.begin(), vector.end());
vector.push_back(a);
push_heap(vector.begin(), vector.end());
pop_heap(vector.begin(), vector.end());
vector.back();//return but not remove
vector.pop_back(); //remove last elem and no return
sort_heap(vector.begin(), vector.end());

7. priority_queue、slist

带有权值观念，缺省情况下利用max_heap实现。不提供便利功能，也不提供迭代器。

priority_queue.top();
priority_queue.pop();

list是双向链表，slist是双向链表。

8. 红黑树

二叉搜索树 

平衡二叉搜索树：AVL_Tree (单旋、双旋)

  RB-Tree（STL源码分析 P208）

外侧插入：单旋操作

内侧插入：双旋操作（由两次单旋组成）

9. Map, Set, multiset, multimap 等实现原理

Map和set是基于红黑树实现的

Set中所有元素都会根据元素键值自动排序，不允许两个元素有相同键值，企图通过迭代器来改变set的元素是不被允许的。

Set提供的函数有： 

begin()   clear()  count()  empty()  end()  
equal_range()  erase()  find()

get_allocator()  insert()  
lower_bound()  upper_bound()  
value_comp()   key_comp()  
max_size()  size() 
rbegin()  rend()  swap()

set和map的插入调用的是红黑树的insert_unique()

multiset和multiset的插入调用的是红黑树的insert_euqal()

10.Unordered_map（补充）

Unordered_map是哈希表，各项操作的平均时间复杂度接近常数。

可以自定义hash函数和比较函数

哈希函数：线性探测：H+i

                  二次探测：H+i^2

                  开链法

哈希函数用质数取模这就是为了使得有特征的数据集也能均匀映射到映射空间。 在这种情况下，有时hash函数还要结合数据特征，让出现概率较大的数据集有较小的碰撞概率，出现概率较小的数据集有较大的碰撞概率。这样，就可以减少整体数据集的碰撞概率。

Hsh_set  hash_map 都是调用的hashtable实现的

11.空间适配器 （重要！！）

构造和析构基本工具：construct()  destroy()

空间的配置和释放：std::alloc。SGI设计了双层级配置器，第一级配置器直接使用malloc()和free()，第二级配置器设计如下，采用不同的策略。

当请求的内存大于128b时，就用第一层配置器分配内存，当请求的内存小于等于128b时就调用第二层配置器。

第一级配置器相对简单，因为使用的正是我们平常使用的malloc，dealloc，free等，如果调用不成功，则会调用oom_malloc()和oom_realloc()，这两个函数内循环调用“内存不足处理样例”，期望在某次调用之后，获得足够内存圆满完成任务。但是“内存不足处理样例”没有设置时，返回_THROW_BAD_ALLOC。

第二层配置器维护16个自由链表（free lists），负责16种小型区块的次配置能力。有一个内存池，以malloc()配置而得。用一个union obj数组free_list来存储内存的地址，数组的每一个元素都指向一个obj链表，也就是内存链表。数组从小到大表示负责8b,16b,24b,...,120b,128b内存请求。当请求的内存为n时，会将请求上条至2的指数大小，并从数组相应位置获取内存。例如如果请求为20b，则请求会上调至24b 。（伙伴算法）

内存池模型：

这个图展示了当有内存请求到达时，先找到负责这个内存大小的数组元素指向的内存链表，取出第一块内存，然后把数组元素(obj指针)指向第二块内存的首地址。

当程序释放这块内存时，第二级配置器还负责回收这块内存，等下次有请求时，可以直接使用这块内存。示意图如下，从《STL源码剖析》摘取:

先计算机这块内存属于哪个数组元素负责，然后将这块回收的内存放置链表的第一个位置，这块内存的下一块内存为这个链表原先的第一块内存。

之前分析分配内存时，当free_list没有可用的内存时，会调用refill来从内存池分配内存。例如，如果请求内存为32b，此时内存链表中没有足够的内存了，那么refill会分配20块32b的内存块，然后把第一块返回给程序，其他19块由数组相应链表管理。

当free_list没有内存返回给用户时，refill函数会调用chunk_alloc从内存池获取内存，如果内存池剩余的内存(end_free-start_free)满足需求的内存(size*nobjs)，则直接从从内存池获取内存，返回给程序；当内存池的块不能满足20块时，返回一个以上的内存块；当内存池一块都不能满足时，先是回收剩余的内存，然后调用malloc从系统获取内存。如果系统内存不足，则先从数组其他链表获取内存，如果其他链表也不足够内存的话，就调用第一级内存来分配，因为第一级内存分配失败，有处理函数来解决。

12.萃取器

如何让编译器推导出返回值？普通的做法是使用typedef，但直接将迭代器传入的类型做typedef并不能解决泛型算法对裸指针的兼容。

13. STL算法

Reversr< vector<string>::iterator>(v.begin(), v.end());

For_each()泛型算法

Find()函数

14.函数对象

函数对象就是冲在了“()”运算符的类的对象，他可以像一个函数一样使用。

STL分为一元和二元函数两种函数对象。

15. 函数适配器

Bind1st    bind2nd