STL部分
1.STL为什么广泛被使用
C++ STL 之所以得到广泛的赞誉，也被很多人使用，不只是提供了像vector, string, list等方便的容器，更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组，list封装了链表，map和set封装了二叉树等
2.标准关联容器 set, multiset, map, multimap内部采用数据结构是什么？简要介绍一下。
（1）都是一种非常高效的平衡检索二叉树:红黑树，也称为为RB树(Red-BlackTree)。RB树的统计性能要好于一般的平衡二叉树，
（2）红黑树的简要介绍：红黑树(一)之 原理和算法详细介绍 - 如果天空不死 - 博客园
3.STL map和set的相关问题:
(1)为何map和set的插入删除效率比用其他序列容器高?，树
答:因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。map和set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点
(2)为何每次insert之后，以前保存的iterator不会失效?
答:iterator这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说，每一次删除和插入，指针都有可能失效，调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使是push_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则:不要使用过期的iterator。
(3)为何map和set不能像vector一样有个reserve函数来预分配数据?
答:我以前也这么问，究其原理来说时，引起它的原因在于在map和set内部存储的已经不是元素本身了，而是包含元素的节点。也就是说map内部使用的Alloc并不是map声明的时候从参数中传入的Alloc。例如:
4. set 与 multiset
set和multiset会根据特定的排序准则自动将元素排序，set中元素不允许重复，multiset可以重复。
因为是排序的，所以set中的元素不能被修改，只能删除后再添加。
set与multiset有序存储元素，这两种容器的底层实现与map一样都是红黑树，所以能实现O(lgn)的查找，插入，删除操作。
5. map与multimap底层数据结构
map与multimap是STL中的关联容器、提供一对一key-value的数据处理能力； map与multimap的区别在于，multimap允许关键字重复，而map不允许重复。
这两个关联容器的底层数据结构均为红黑树，关于红黑树的理解可以参考教你透彻了解红黑树一文。
根据红黑树的原理，map与multimap可以实现O(lgn)的查找，插入和删除。
6. List的功能方法
实际上有两种List: 一种是基本的ArrayList,其优点在于随机访问元素，另一种是更强大的LinkedList,它并不是为快速随机访问设计的，而是具有一套更通用的方法。
List : 次序是List最重要的特点:它保证维护元素特定的顺序。List为Collection添加了许多方法，使得能够向List中间插入与移除元素(这只推荐LinkedList使用)一个List可以生成ListIterator,使用它可以从两个方向遍历List,也可以从List中间插入和移除元素。
ArrayList : 由数组实现的List。允许对元素进行快速随机访问，但是向List中间插入与移除元素的速度很慢。ListIterator只应该用来由后向前遍历ArrayList,而不是用来插入和移除元素。因为那比LinkedList开销要大很多。
LinkedList : 对顺序访问进行了优化，向List中间插入与删除的开销并不大。随机访问则相对较慢。(使用ArrayList代替。)还具有下列方法:addFirst(), addLast(), getFirst(),getLast(), removeFirst() 和 removeLast(), 这些方法 (没有在任何接口或基类中定义过)使得LinkedList可以当作堆栈、队列和双向队列使用
List常用操作函数：
Lst1.assign() 给list赋值 ； Lst1.back() 返回最后一个元素； Lst1.begin() 返回指向第一个元素的迭代器
Lst1.clear() 删除所有元素； Lst1.empty() 如果list是空的则返回true； Lst1.end() 返回末尾的迭代器
Lst1.erase() 删除一个元素； Lst1.front() 返回第一个元素； Lst1.get_allocator() 返回list的配置器
Lst1.insert() 插入一个元素到list中；（Lst1.insert(iter, 100)//在迭代器iter指的元素后面加入元素100
Lst1.insert(iter，2, 100) //在迭代器iter指的元素后面加如2个100）
Lst1.max_size() 返回list能容纳的最大元素数量
Lst1.merge() 合并两个list； Lst1.pop_back() 删除最后一个元素； Lst1.pop_front() 删除第一个元素
Lst1.push_back() 在list的末尾添加一个元素；Lst1.push_front() 在list的头部添加一个元素
Lst1.rbegin() 返回指向第一个元素的逆向迭代器； Lst1.remove() 从list删除元素；
Lst1.remove_if() 按指定条件删除元素； Lst1.rend() 指向list末尾的逆向迭代器； Lst1.resize() 改变list的大小
Lst1.reverse() 把list的元素倒转； Lst1.size() 返回list中的元素个数； Lst1.sort() 给list排序
Lst1.splice() 合并两个list； Lst1.swap() 交换两个list； Lst1.unique() 删除list中重复的元素
7. hash_map和map的区别在哪里?
构造函数：hash_map需要hash函数（等于函数）; map只需要比较函数(小于函数).
存储结构：hash_map采用hash表存储，map一般采用红黑树(RBTree)实现。因此其memory数据结构是不一样的。
8 .什么时候需要用hash_map，什么时候需要用map?
总体来说，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小无关，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且hash_map的构造速度较慢。
现在知道如何选择了吗?权衡三个因素: 查找速度, 数据量, 内存使用。
9. 一些容器使用上的建议（应用场景）
Level 1 - 仅仅作为Map使用:采用静态数组
Level 2 - 保存定长数据，使用时也是全部遍历:采用动态数组(长度一开始就固定的话静态数组也行)
Level 3 - 保存不定长数组，需要动态增加的能力，侧重于寻找数据的速度:采用vector
Level 3 - 保存不定长数组，需要动态增加的能力，侧重于增加删除数据的速度:采用list
Level 4 - 对数据有复杂操作，即需要前后增删数据的能力，又要良好的数据访问速度:采用deque
Level 5 - 对数据中间的增删操作比较多:采用list，建议在排序的基础上，批量进行增删可以对运行效率提供最大的保证
Level 6 - 上述中找不到适合的:组合STL容器或者自己建立特殊的数据结构来实现
10 vector, list, deque 三者比较分析
(1).vector ----- 会自动增长的数组
vector由于数组的增长只能向前，所以也只提供了后端插入和后端删除，也就是push_back和pop_back。当然在前端和中间要操作数据也是可以的，用insert和erase，但是前端和中间对数据进行操作必然会引起数据块的移动，
这对性能影响是非常大的。最大的优势就是随机访问的能力。
(2).list -------- 擅长插入删除的链表
list 的常用操作： push_back（）, pop_back（），push_front（）， pop_front（）
list是一个双向链表的实现：
为了提供双向遍历的能力，list要比一般的数据单元多出两个指向前后的指针，一个使用iterator来删除元素的例子
list stringList;
list::iterator iter;
advance(iter, 5); //将iterator指向stringList的第五个元素
stringList.erase(iterator);//删除
那么删除操作进行以后，传入erase()方法的iterator指向哪里了呢?它指向了删除操作前所指向的那个元素的后一个元素。
(3).deque ------ 拥有vector和list两者优点的双端队列
这三个模板的总结 比较和一般使用准则
这三个模板都属于序列类模板，可以看到他们有一些通用方法
size():得到容器大小
begin():得到指向容器内第一个元素的指针(这个指针的类型依容器的不同而不同)
end():得到指向容器内最后一个元素之后一个位置的指针
erase():删除传入指针指向的那个元素
clear():清除所有的元素
==运算符:判断两个容器是否相等
=运算符:用来给容器赋值
上面的三个模板有各自的特点
vector模板的数据在内存中连续的排列，所以随机存取元素(即通过[]运算符存取)的速度最快，这一点和数组是一致的。同样由于它的连续排列，所以它在除尾部以外的位置删除或添加元素的速度很慢，在使用vector时，要避免这种操作。
list模板的数据是链式存储，所以不能随机存取元素。它的优势在于任意位置添加 删除元素的速度。
deque模板是通过链接若干片连续的数据实现的，所以均衡了以上两个容器的特点
11.说说vector的底层（存储）机制
vector就是一个动态数组，里面有一个指针指向一片连续的内存空间，当空间不够装下数据时，会自动申请另一片更大的空间（一般是增加当前容量的50%或100%），然后把原来的数据拷贝过去，接着释放原来的那片空间；当释放或者删除当前vector里面的数据时，当前vector的存储空间不释放，仅仅是清空了里面的数据。
12.vector的自增长机制
当已经分配的空间不够装下数据时，分配双倍于当前容量的存储区，把当前的值拷贝到新分配的内存中，并释放原来的内存。
13.说说list的底层（存储）机制
以结点为单位存放数据，结点的地址在内存中不一定连续，每次插入或删除一个元素，就配置或释放一个元素空间
14. unordeded_map和unordeded_set的底层实现
在STL函数库里边有关map和set的总共有8个函数。
map； set；multimap；multiset；unordered_map；unordered_set；unordered_multiset；unordered_multimap
简单的做以区分：
map: K/V （键/值）结构。 set: K（键）结构。
multi: 可以冗余，如没有这个关键字，则是防冗余版本。
unordered: 底层由哈希表（哈希桶算法）来实现，如无该关键字，则底层是由红黑树来实现。
unordered_map和unordered_set & unordered_multiset 和 unordered_multimap中key为无序排列，其底层实现为hash table，因此其查找时间复杂度理论上达到了O(n)
15.什么情况下用vector，什么情况下用list
vector可以随机存储元素（即可以通过公式直接计算出元素地址，而不需要挨个查找），但在非尾部插入删除数据时，效率很低，适合对象简单，对象数量变化不大，随机访问频繁。
list不支持随机存储，适用于对象大，对象数量变化频繁，插入和删除频繁。
16. list自带排序函数的排序原理
将前两个元素合并，再将后两个元素合并，然后合并这两个子序列成4个元素的子序列，重复这一过程，得到8个，16个，...，子序列，最后得到的就是排序后的序列。
时间复杂度：O(nlgn)
17.说说deque的底层机制 STL之deque容器的实现框架 - CSDN博客
深入剖析deque容器实现 - 综合编程类其他综合 - 红黑联盟
deque动态地以分段连续空间组合而成，随时可以增加一段新的连续空间并链接起来。不提供空间保留功能。
注意：除非必要，我们尽可能选择使用vector而非deque，因为deque的迭代器比vector迭代器复杂很多。对deque排序，为了提高效率，可先将deque复制到一个vector上排序，然后再复制回deque。
deque采用一块map（不是STL的map容器）这个_Map是一个指针，指向一块特殊的内存地址，这里保存着指向deque动态申请的所有512字节内存空间的首地址。作为中控器/ 中央控制器 /主控，其为一小块连续空间，其中每个元素都是指针，指向另一段较大的连续空间（缓冲区）。
deque先用一段小的连续空间顺序存放了一个一个指针，然后这些顺序存放的指针再各自指向用来真正存放数据的512字节连续性空间。当_Map指向的这块空间不够存放内存指针的时候，就会另觅一块更大的连续性空间（是map空间重新寻找，而不是缓冲区重新寻找），然后把指针一个一个复制过去，并销毁旧的空间（销毁的是原来的map空间）。利用这种数据结构，deque就能方便地模拟自身的存储区是连续性空间的假象，并且可以实现双向插入删除的功能
deque 的迭代器
让我们思考一下，deque的迭代器应该具备什么结构，首先，它必须能够指出分段连续空间（亦即缓冲区）在哪里，其次它必须能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退就必须跳跃至下一个或上一个缓冲区。为了能够正确跳跃，deque必须随时掌握管控中心（map）。所以在迭代器中需要定义：当前元素的指针cur，当前元素所在缓冲区的起始指针first，当前元素所在缓冲区的尾指针last，指向map中指向所在缓区地址的指针node， 分别为cur, first, last, node。
deque的迭代器包含4个内容：
1）cur：迭代器当前所指元素
2）first：此迭代器所指的缓冲区的头。
3）last：缓冲区尾。
4）node：指向管控中心。
deque迭代器失效的原因：
18. deque与vector的区别
1）vector是单向开口的连续线性空间，deque是双向开口的连续线性空间。（双向开口是指可以在头尾两端分别做元素的插入和删除操作）。
2）deque没有提供空间保留功能，而vector则要提供空间保留功能。
3）deque也提供随机访问迭代器，但是其迭代器比vector迭代器复杂很多。
19.不允许有遍历行为的容器有哪些（不提供迭代器）？
1）queue，除了头部外，没有其他方法存取deque的其他元素。
2）stack（底层以deque实现），除了最顶端外，没有任何其他方法可以存取stack的其他元素。
3）heap，所有元素都必须遵循特别的排序规则，不提供遍历功能。
20.说说map底层机制
map以RB-TREE为底层机制。RB-TREE是一种平衡二叉搜索树，自动排序效果不错。
通过map的迭代器不能修改其键值，只能修改其实值。所以map的迭代器既不是const也不是mutable。
21.vector插入删除和list有什么区别？
vector插入和删除数据，需要对现有数据进行复制移动，如果vector存储的对象很大或者构造函数很复杂，则开销较大，如果是简单的小数据，效率优于list。
list插入和删除数据，需要对现有数据进行遍历，但在首部插入数据，效率很高。
22.hashtable如何避免地址冲突？
1）线性探测：先用hash function计算某个元素的插入位置，如果该位置的空间已被占用，则继续往下寻找，知道找到一个可用空间为止。
进行元素搜索的时候，如果hash function计算出来的位置上的元素值与我们搜寻目标不符，就循环往下一一寻找，直到找到吻合者，或直到遇上空格元素。
其删除采用惰性删除：只标记删除记号，实际删除操作等到表格重新整理时再进行。（因为hash table中的每一个元素不仅表述它自己，也关系到其他元素的排列。）
2）二次探测：如果计算出的位置为H且被占用，则依次尝试H+1^2，H+2^2等（解决线性探测中主集团问题）。
3）开链：每一个哈希表元素中维护一个list链表，hash function为我们分配一个list，然后在那个list执行插入、删除等操作。当发生冲突时，该位置上的数据会用链表链起来，当表中的某些位置没有结点时，该位置就为NULL！！这种方法在实现时就需要多加一个next指针，使这些结点才能链起来。
23. hashtable，hash_set，hash_map的区别
hash_set以hashtable为底层，不具有排序功能，能快速查找。其键值就是实值。（set以RB-TREE为底层，具有排序功能。）
hash_map以以hashtable为底层，没有自动排序功能，能快速查找，每一个元素同时拥有一个实值和键值。（map以RB-TREE为底层，具有排序功能。）
24 .hash_map与map的区别？什么时候用hash_map，什么时候用map？
构造函数：hash_map需要hash function和等于函数，而map需要比较函数（大于或小于）。
存储结构：hash_map以hashtable为底层，而map以RB-TREE为底层。
总的说来，hash_map查找速度比map快，而且查找速度基本和数据量大小无关，属于常数级别。而map的查找速度是logn级别。但不一定常数就比log小，而且hash_map还有hash function耗时。
如果考虑效率，特别当元素达到一定数量级时，用hash_map。
考虑内存，或者元素数量较少时，用map。
25.红黑树有什么性质？ 红黑树(一)之 原理和算法详细介绍 - 如果天空不死 - 博客园
1）每个结点是红色或者黑色。
2）根结点为黑色。
3）叶结点为黑色的NULL结点。
4）如果结点为红，其子节点必须为黑。
5）任一结点到NULL的任何路径，所含黑结点数必须相同。
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
26.map和set的3个问题
1）为何map和set的插入删除效率比其他序列容器高。
因为不需要内存拷贝和内存移动
2）为何map和set每次Insert之后，以前保存的iterator不会失效？
因为插入操作只是结点指针换来换去，结点内存没有改变。而iterator就像指向结点的指针，内存没变，指向内存的指针也不会变。
3）当数据元素增多时（从10000到20000），map和set的查找速度会怎样变化？
RB-TREE用二分查找法，时间复杂度为logn，所以从10000增到20000时，查找次数从log10000=4次到log20000=5次，多了1次而已。
set常用方法：比如先创建 set<int> s
s.begin() ,返回set容器的第一个元素
s.end() ,返回set容器的最后一个元素
s.clear() ,删除set容器中的所有的元素
s.empty() ,判断set容器是否为空
s.max_size() ,返回set容器可能包含的元素最大个数
s.size() ,返回当前set容器中的元素个数
s.rbegin ,返回的值和end()相同
s.rend() ,返回的值和rbegin()相同
map的相关操作 ： C/C++——map的基本操作总结 - CSDN博客
27.vector中begin和end函数返回的是什么？
begin返回的是第一个元素的迭代器，end返回的是最后一个元素后面位置的迭代器。
28.为什么vector的插入操作可能会导致迭代器失效？
vector动态增加大小时，并不是在原空间后增加新的空间，而是以原大小的两倍在另外配置一片较大的新空间，然后将内容拷贝过来，并释放原来的空间。由于操作改变了空间，所以迭代器失效。
29.vector、list、map、deque用erase（it）后，迭代器的变化
vector和deque是序列式容器，其内存分别是连续空间和分段连续空间，删除迭代器it后，其后面的迭代器都失效了，此时it及其后面的迭代器会自动加1，使it指向被删除元素的下一个元素。
list删除迭代器it时，其后面的迭代器都不会失效，将前面和后面连接起来即可。
map也是只能使当前删除的迭代器失效，其后面的迭代器依然有效。
30. hashtable和hashmap的区别
hashmap以hashtable为底层。主要有以下几点不同：
1）hashtable是Dictionary的子类，而hashmap是Map接口的一个实现类。
2）hashtable中的方法是同步的，而hashmap的方法不同步。
重点说 hashtable：
哈希表（hash table, 也叫散列表），是种根据关键字(Key value)而直接进行访问数据结构，它可以提供快速的插入操作和查找操作。也就是说，它通过把关键字值映射到一个位置来访问记录，以加快查找的速度。这个映射函数称为哈希函数（也称为散列函数），映射过程称为哈希化，存放记录的数组叫做哈希表（散列表）。哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。
哈希函数构造
当需要使用一个下标范围比较大的数组来存储元素时，可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素。也可以简单的理解为，按照关键字为每一 个元素“分类”，然后将这个元素存储在相应“类”所对应的地方。点击打开链接
Hashtable底层实现是通过开链法来实现的，hash table表格内的元素称为桶（bucket),而由桶所链接的元素称为节点（node),其中保存桶元素的容器为vector容器。之所以选择vector为存放桶元素的基础容器，主要是因为vector容器本身具有动态扩容能力，无需人工干预。而节点元素为自定义的结构体：
可以看到，这本身就是一种很典型的链式列表元素的表示方法，通过当前节点，我们可以很方便地通过节点自身的next指针来获取下一链接节点元素。
无序容器在存储上组织为一组桶，每个桶保存0个或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，（1）容器首先计算元素的哈希值， 它指出应该搜索哪个桶；（2）容器将具有一个特定哈希值的所有元素都保存在相同的桶中；因此，无序容器的性能依赖于哈希函数的质量和桶数量和大小。
实际工作中需视不同情况采用不同的哈希函数，通常，考虑的因素有：
（1）计算哈希函数所需时间（包括硬件指令的因素）；
（2）关键字的长度；
（3）哈希表的大小；
（4）关键字的分布情况；
（5）记录的查找频率。
31. priority_queue
priority_queue优先级队列相当于一个有权值的单向队列queue，在这个队列中，所有元素是按照优先级排列的。
priority_queue根据堆的处理规则来调整元素之间的位置，关于堆的原理，可以参考堆；
根据堆的特性，优先级队列实现了取出最大最小元素时间复杂度为O(1), 对于插入和删除，其最坏情况为O(lgn)。
32.STL 空间配置器 allocator
为什么要有空间配置器呢？这主要是从两个方面来考虑的。
1、小块内存带来的内存碎片问题
单从分配的角度来看。由于频繁分配、释放小块内存容易在堆中造成外碎片(极端情况下就是堆中空闲的内存总量满足一个请求，但是这些空闲的块都不连续，导致任何一个单独的空闲的块都无法满足这个请求)。
2、小块内存频繁申请释放带来的性能问题。
开辟空间的时候，分配器会去找一块空闲块给用户，找空闲块也是需要时间的，尤其是在外碎片比较多的情况下。如果分配器其找不到，就要考虑处理假碎片现象(释放的小块空间没有合并)，这时候就要将这些已经释放的的空闲块进行合并，这也是需要时间的。 malloc在开辟空间的时候，这些空间会带有一些附加的信息，这样的话也就造成了空间的利用率有所降低，尤其是在频繁申请小块内存的时候。
内存池的概念
为了解决上面这些问题，所以就提出有了内存池的概念。内存池最基本的思想就是一次向heap申请一块很大的内存(内存池)，如果申请小块内存的话就直接到内存池中去要。这样的话，就能够有效的解决上面所提到的问题。
下面剖析一下STL里面的空间配置器(SGI版)
STL里面的空间配置主要分为两级，一级空间配置器(__malloc_alloc_template)和二级空间配置器(__default_alloc_template)。在STL中默认如果要分配的内存大于128个字节的话就是大块内存，调用一级空间配置器直接向系统申请，如果小于等于128个字节的话则认为是小内存，则就去内存池中申请。
（1）一级空间配置器很简单，直接封装了malloc和free处理，增加_malloc_alloc_oom_handle处理机制。
（2）二级空间配置器才是STL的精华，二级空间配置器主要由 内存池+自由链表 构成。
二级空间配置器使用内存池+自由链表的形式避免了小块内存带来的碎片化，提高了分配的效率，提高了利用率。SGI的做法是先判断要开辟的大小是不是大于128，如果大于128则就认为是一块大块内存，调用一级空间配置器直接分配。否则的话就通过内存池来分配，假设要分配8个字节大小的空间，那么他就会去内存池中分配多个8个字节大小的内存块，将多余的挂在自由链表上，下一次再需要8个字节时就去自由链表上取就可以了，如果回收这8个字节的话，直接将它挂在自由链表上就可以了。
为了便于管理，二级空间配置器在分配的时候都是以8的倍数对齐。也就是说二级配置器会将任何小块内存的需求上调到8的倍数处(例如：要7个字节，会给你分配8个字节。要9个字节，会给你16个字节),尽管这样做有内碎片的问题，但是对于我们管理来说却简单了不少。因为这样的话只要维护16个free_list就可以了，free_list这16个结点分别管理大小为8,16,24,32,40,48,56,64,72,80,88,86,96,104,112,120,128字节大小的内存块就行了。
