注意马叉虫

2019-07-26 08:54 已编辑北京理工大学 C++

关注

STL简介和常见的面试题

STL概念

STL：（standard template libaray --标准模板库）：是C++标准库的重要组成部分，不仅是一个可复用的组件库，而且是一个包罗数据结构和算法的软件框架。

中心思想

将数据容器和算法分隔开，彼此独立设计，最后再用黏合剂将它们撮合在一起。容器和算法的泛型化，可以用C++的class template和function template来实现，而二者的黏合剂就是迭代器了。

六大组件

      1. 容器（Containers）：各种数据结构，如：vector、list、deque、set、map。用来存放数据。从实现的角度来看，STL容器是一种class template。
      2. 算法（algorithms）：各种常用算法，如：sort、search、copy、erase。从实现的角度来看，STL算法是一种 function template。
      3. 迭代器（iterators）：容器与算法之间的胶合剂，是所谓的“泛型指针”。共有五种类型，以及其他衍生变化。从实现的角度来看，迭代器是一种将 operator*、operator->、operator++、operator- - 等指针相关操作进行重载的class template。所有STL容器都有自己专属的迭代器，只有容器本身才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。
      4. 仿函数（functors）：行为类似函数，可作为算法的某种策略（policy）。从实现的角度来看，仿函数是一种重载了operator()的class或class template。一般的函数指针也可视为狭义的仿函数。
      5. 适配器（配接器 adapters）：一种用来修饰容器、仿函数、迭代器接口的东西。例如：STL提供的queue 和 stack，虽然看似容器，但其实只能算是一种容器配接器，因为它们的底部完全借助deque，所有操作都由底层的deque供应。改变 functors接口者，称为function adapter；改变 container 接口者，称为container adapter；改变iterator接口者，称为iterator adapter。
      6. 配置器（allocators）：负责空间配置与管理。从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的class template。

      容器，即存放数据的地方。

      在STL中，容器分为两类：序列式容器和关联式容器。
      序列式容器
      vector list(双向链表) deque(双端队列) 等。。
      关联式容器
      set map multiset multimap （底层结构红黑树）
      hash_set hash_map hash_multiset hash_multimap （底层结构 Hash 表）

      特点：
      序列式容器，其中的元素不一定有序，但都可以被排序。
      关联式容器，内部结构基本上是一颗平衡二叉树。所谓关联，指每个元素都有一个键值和一个实值，元素按照一定的规则存放。

迭代器是STL的精髓，我们这样描述它：迭代器提供了一种方法，使它能够按照顺序访问某个容器所含的各个元素，但无需暴露该容器的内部结构。它将容器和算法分开，好让这二者独立设计。

常见的面试题

       题目0：vector的resize和reserve操作的区别
      1、resize(n)
      调整容器的长度大小，使其能容纳n个元素。
      如果n小于容器的当前的size，则删除多出来的元素。
      否则，添加采用值初始化的元素。
      2、 resize(n，t)
      多一个参数t，将所有新添加的元素初始化为t。

      reserve()的用法只有一种reserve(n)
      预分配n个元素的存储空间。
      resize是改变容器的大小，并且创建对象，因此，调用这个函数之后，就可以引用容器内的对象了，因此当加入新的元素时，用operator[]操作符，或者用迭代器来引用元素对象。

reserve是容器预留空间，但并不真正创建元素对象，在创建对象之前，不能引用容器内的元素，因此当加入新的元素时，需要用push_back()/insert()函数。

再者，两个函数的形式是有区别的，reserve函数之后一个参数，即需要预留的容器的空间；resize函数可以有两个参数，第一个参数是容器新的大小，第二个参数是要加入容器中的新元素，如果这个参数被省略，那么就调用元素对象的默认构造函数。

       capacity（容量）与size（长度）
      capacituy()函数指容器在必须分配新存储空间之前可以存储的元素总数.
      可以说是预分配存储空间的大小。
      size()函数返回实际元素的数量

vector怎么实现动态空间分布?
vector容器基于数组实现，其元素在内存中连续存放，vector容器除了容器尾部之外，在其他任意位置插入或删除元素时，都需要移动该元素后面的所有元素。

题目1：unordered_map和map的实现机制，性能差异
运行效率方面：unordered_map最高，hash_map其次，而map效率最低单提供了有序的序列。

占用内存方面：hash_map内存占用最低，unordered_map其次(数量少时优于hash_map），而map
占用最高

序列：对map进行遍历（中序遍历）的话，输出的结果是有序的。顺序就是按照operator< 定义的大小排序。而对unordered_map进行遍历，结果是无序的。

用法的区别就是，stl::map 的key需要定义operator< 。而unordered_map需要定义hash_value函数并且重载operator==（必须要自定义operator== 和hash_value。重载operator== 是因为，如果两个元素的hash_value的值相同，并不能断定这两个元素就相同，必须再调用operator==。当然，如果hash_value的值不同，就不需要调用operator==）。

对于内置类型，如string，这些都不用操心。
 对于自定义的类型做key，就需要自己重载operator< 或者hash_value()了。
 当不需要结果排好序时，最好用unordered_map。

      实现机制：
      map的内部实现是二叉平衡树(红黑树）
      unordered_map的实现是hash_table；

hash_map在unordered_map实现之前先实现，但是unordered_map作为STL的标准被加入；hash_map和c++ stl的api不兼容，c++ tr1(C++ Technical Report1)作为标准的扩展，实现了hash map,提供了和stl兼容一致的api,称为unorder_map.在头文件 <tr1/unordered_map>中。

使用unordered_map，尽量不使用hash_map。

题目2：STL中排序算法sort的实现是什么
答：STL中的sort()，在数据量大时，采用快排quicksort，分段递归；一旦分段后的数量小于某个门限值，改用插入排序Insertion sort，避免quicksort深度递归带来的过大的额外负担，如果递归层次过深，还会改用heapsort(堆排序)。

深度递归的危害：

可能造成栈溢出。因为每次递归的函数调用都会在栈中分配空间，而每个进程的栈的容量是有限的。当递归调用的层次太多时，可能会超出栈容量（栈容量似乎是8M，可设置）。

题目3：vector list的区别与联系
 答：联系：
 均为序列式容器，其中的元素不一定有序，但都可以被排序。
 区别：

      1.适用对象
      vector适用：对象数量变化少，简单对象，随机访问元素频繁
      list适用：对象数量变化大，对象复杂，插入和删除频繁

2.存储方式

vector：连续的内存空间进行存储
list：非连续的内存空间进行存储

3.时间复杂度

      vector：随机读取O(1)
      中间位置插入和删除操作时间复杂度为O(N);
      尾部push_back, pop_back操作时间复杂度为O(1)
      list：随机读取O(n) 插入O(1) 删除O(1)
      deque：push_back, push_front, pop_back, pop_front操作时间复杂度为O(1);

原因：
1. vector和数组类似，拥有一段连续的内存空间，并且起始地址不变，这样对随机的读取很有效率（就是我们所有的[]运算符了）。

2. 因为内存是连续的如果我们想要插入或者删除元素的时候就需要对当前的元素进行复制和移动，如果vector存储的对象较大，或者构造函数较复杂，那么对现有对象进行拷贝的开销就会很大（拷贝对象需要调用拷贝构造函数），vector每次扩张容量的时候将容量扩张2倍（由于vector中的元素是连续存放，所以不能随便找个地方存放，于是vector会重新分配一块大的内存，将原来的数据拷贝过来再将原来的空间释放掉，而这部分内存一般情况下比需要存储的数据所需要的内存大，这样当再有元素需要存储时就不需要在开辟内存了）。

3. list的对象是离散存储的（就是内存不是连续的），想要随机访问某个元素就需要遍历list，但是在插入元素的效率很高（只需要改变元素的指针）。

题目4：vector list deque优点缺点

      使用场景：
       1 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
       2 如果你需要大量的插入和删除，而不关心随即存取，则应使用list
       3 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque

vector：
STL内部实现时，首先分配一个内存空间预备进行存储，即capacituy（）函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储，这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。

分配内存： 0 1 2 4 8 16… 2倍速度增长

       优点：
       (1) 不用指定内存大小，即可以像数组一样的连续存储，对此数组进行动态操作。通常体现在push_back() pop_back()
       (2) 随机访问方便，即支持[ ]操作符和vector.at()
       (3) 节省空间。

       缺点：
      (1) 在内部进行插入删除操作效率低。
       (2) 只能在vector的最后进行push和pop，不能在vector的头进行push和pop。
       (3) 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放

      list：
       双向链表
       每一个结点都包括一个信息块Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。
       优点：
       (1) 不使用连续内存完成动态操作。
       (2) 在内部方便的进行插入和删除操作
       (3) 可在两端进行push、pop

       缺点：
       (1) 不能进行内部的随机访问，即不支持[ ]操作符和vector.at()
       (2) 相对于verctor占用内存多

      deque：
       双端队列 double-end queue
       deque是在功能上合并了vector和list。

       优点：
       (1) 随机访问方便，即支持[ ]操作符和vector.at()
       (2) 在内部方便的进行插入和删除操作
       (3) 可在两端进行push、pop

缺点：
(1) 占用内存多

题目5：set map的区别与联系

联系：
 1.Map,Set属于标准关联容器，底层数据结构使用红黑树
 2.时间复杂度均为红黑树的时间复杂度，插入删除查找近似为O(logN)

区别：
 1.适用对象
 map适合存储一个数据字典，并要求方便地根据key找value
 set适合查找一个元素是否在某集合内存中

      2.存储方式
      Set节点只含有Key，Key不重复.
      Map节点有一个Key和Value两个元素,Key不重复,Value可以不重复。

      3.元素改变
      set不能直接改变元素值。因为这样会打乱原有的顺序。
      改变元素值的方法是：先删除旧元素，再插入新元素。
      存取元素只能通过迭代器，从迭代器的角度看，元素值是常数。
      map可以通过key改变value的值

题目6：Map Hash_map 的区别与联系
 联系：
 Map,Hash_map 属于标准关联容器
 区别：
 1.适用对象
 关键是看关键字查询操作次数，以及你所需要保证的是查询总体时间还是单个查询的时间。
hash_map：很多次的操作，要求其整体效率，平均处理时间短。
 map：少数次的操作，应使用平均处理时间相对较慢、单次处理时间恒定的map
 考虑整体稳定性应该要高于整体效率，因为前提在操作次数较少。如果在一次流程中，使用hash_map的少数操作产生一个最坏情况O(N)，那么hash_map的优势也因此丧尽了。

      2.存储方式
      Map底层数据结构为红黑树，有序。
      Hash_map底层数据结构为哈希表，无序。

      3.时间复杂度
      Map为红黑树的时间复杂度，插入删除查找近似为O(logN)
      Hash_map 为哈希表的时间复杂度

      插入:O(1)，最坏情况O(N)。
      查看:O(1)，最坏情况O(N)。
      删除:O(1)，最坏情况O(N)。

题目7：set multiset map multimap的区别与联系
 联系：
 底层数据结构均为红黑树
 区别：
 1.适用对象
 map适合存储一个数据字典，并要求方便地根据key找value
 set适合查找一个元素是否在某集合内存中

      2.存储方式
      Set和multiset 的区别在于Set不包含重复的数据,multiset 允许有重复数据。
      map multimap的区别在于map 不包含重复的key,multiset 允许有重复key。

题目8：set multiset 重复数据是怎么实现的？

set提供的插入函数：

pair<iterator,bool> insert(const value_type& elem);
 iterator insert(iterator pos_hint, const value_type& elem);
 multiset提供的插入函数：
 iterator insert(const value_type& elem);
 iterator insert(iterator pos_hint, const value_type& elem);

      返回值型别不同的原因是set不允许元素重复，而multiset允许。当插入的元素在set中已经包含有同样值的元素时，插入就会失败。所以set的返回值型别是由pair组织起来的两个值：
      第一个元素返回新元素的位置，或返回现存的同值元素的位置。
      第二个元素表示插入是否成功。

set的第二个insert函数，如果插入失败，就只返回重复元素的位置！

但是，所有拥有位置提示参数的插入函数的返回值型别是相同的。这样就确保了至少有了一个通用型的插入函数，在各种容器中有共通接口。

题目9：map list 的使用场景优势对比
答：Map适用：是为了更快的从关键字查找到相关的对象。

      与使用list这样的线性表容器相比：
      一可以简化查找的算法
      二可以使任意的关键字做索引，并与目标对象配对，优化查找算法。

在C++的STL中map是使用树来做查找算法，这种算法差不多相当与list线性容器的折半查找的效率一样，都是O (log2N)，而list就没有map这样易定制和操作了。

题目10：为何关联容器的插入删除效率一般比用其他序列容器高？
答：因为对于关联容器来说，不需要做内存拷贝和内存移动。

题目11：STL的底层实现对比

序列式容器

      1.vector 底层数据结构为数组，支持快速随机访问
      2.list 底层数据结构为双向链表，支持快速增删
      3.deque 底层数据结构为一个中央控制器和多个缓冲区，详细见STL源码剖析P146，支持首尾（中间不能）快速增删，也支持随机访问

deque是一个双端队列(double-ended queue)，也是在堆中保存内容的.它的保存形式如下:
[堆1] --> [堆2] -->[堆3] --> …

每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品.

      4.stack 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
      5.queue 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
（stack和queue其实是适配器,而不叫容器，因为是对容器的再封***r>       6.priority_queue 的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现

关联式容器

      7.set 底层数据结构为红黑树，有序，不重复
      8.multiset 底层数据结构为红黑树，有序，可重复
      9.map 底层数据结构为红黑树，有序，不重复
      10.multimap 底层数据结构为红黑树，有序，可重复

      11.hash_set 底层数据结构为hash表，无序，不重复
      12.hash_multiset 底层数据结构为hash表，无序，可重复
      13.hash_map 底层数据结构为hash表，无序，不重复
      14.hash_multimap 底层数据结构为hash表，无序，可重复

题目12：选择容器需要注意的地方
在使用的过程中，需要考虑的问题有元素顺序、标准的一致性、迭代器能力、内存布局和C的兼容性、查找速度这些，考虑了这些问题你选择的容器应该会非常适合你当前的情景。

      1.需要大量添加新元素：
　　vector在大量添加元素的时候问题最大，因为他的一种最常见的内存分配实现方法是当前的容量(capacity)不足就申请一块当前容量2倍的新内存空间，然后将所有的老元素全部拷贝到新内存中，添加大量元素的时候的花费的惊人的大。如果由于其他因素必须使用vector，并且还需要大量添加新元素，那么可以使用成员函数reserve来事先分配内存，这样可以减少很多不必要的消耗。
　　list对这种情况的适应能力就非常好，都是常数时间的插入消耗。deque前面说过了，他是vector和list的折衷形式，内存不够了就申请一块新的内存，但并不拷贝老的元素。
　　
      2.查找速度：
　　这个因素主要取决于算法，而算法最终是作用在容器中元素上的，所以这里的查找速度指的是容器能够达到的最好查找效率。
　　对于序列容器需要分两种情况，区分依据是元素是否排序，1)对于已经排序的序列容器，使用binary_search、lower_bound、upper_bound、equal_range可以获得对数时间复杂度的查找速度(O(logN));2)而未排序的序列容器二分查找肯定是用不了，能达到的最好的时间复杂度是线性的(O(n))。
　　对于关联容器，存储的时候存储的是一棵红黑树(一种更为严格的平衡二叉树,文档最后有介绍)，总是能达到对数时间复杂度(O(logN))的效率，因为关联容器是按照键值排好序的。
　　
      3.是否是连续内存：
　　连续内存的容器有个明显的缺点，就是有新元素插入或老元素删除的时候，为了给新元素腾出位置或者填充老元素的空缺，同一块内存中的其他数据需要进行整体的移位，这种移位的拷贝代价有时是非常巨大的。标准容器中的vector、deque是连续内存的，其中vector是完全连续内存，而deque是vector和list的折衷实现，是多个内存块组成的，每个块中存放的元素连续内存，而内存块又像链表一样连接起来。
　　所以需要考虑在操作的过程中是否有在任意位置插入元素的需求，有这种需求的话尽量避免使用连续内存的vector、deque
      4.元素的排序：
　　序列容器中的元素不会自动排序，程序员插入什么顺序内存中就是什么顺序，而关联容器不是这样的，他会以自己的键值按照某种等价关系(equivalence)进行排序。所以默认情况下序列容器中的元素是无序的，而关联容器中的元素是有序的。
　　所以容器在遍历元素的时候序列容器输出的顺序和插入的顺序式一致的，关联容器就不一定了。下面给出两个例子：
　　通过例子看到序列容器vector遍历的顺序和插入的顺序是一样的，而关联容器set把插入的元素按照某种顺序重新组织了，所以选择容器的时候如果很在意插入顺序的话就选择序列容器。