C++基础——STL常见问题总结

1. STL由哪些组件组成

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

2. vector的底层实现机制

vector是一个动态数组，里面有一个指针指向一片连续的内存空间，当空间不够装下数据时，会自动申请另一片更大的空间（一般是增加当前容量的50%或100%），然后把原来的数据拷贝过去，接着释放原来的那片空间；当释放或者删除里面的数据时，其存储空间不释放，仅仅是清空了里面的数据。

3. vector中 resize()扩容和reserve()的区别

resize()扩容的默认构造的方式是0， 之后插入按照一定的倍数扩容（GCC是2倍扩容，VS是1.5倍扩容）；扩容后重新申请一片新的内存，需要把旧内存空间中的所有元素都拷贝进新内存空间中去，然后在新内存中进行操作；同时释放旧内存空间，此时会导致旧vector的所有迭代器都失效了。

reserve()只是保证vector的空间大小(_capacity)最少达到它的参数所指定值n；在区间[0, n)范围内,预留了内存但是并未初始化只有当所申请的容量大于vector的当前容量capacity时才会重新为vector分配存储空间；小于当前容量则没有影响，reserve方法对于vector元素大小没有任何影响，不创建对象。

vector的初始的扩容方式代价太大,初始扩容效率低， 需要频繁增长，不仅操作效率比较低，而且频繁的向操作系统申请内存容易造成过多的内存碎片，所以这个时候需要合理使用resize()和reserve()方法提高效率减少内存碎片的。

4. vector的扩容为何按倍数进行，而不是固定值

扩容以倍数进行增长，当申请频繁时相对于固定值的方式可以减少申请的次数；假设vector初始的capacity=10，size=0，总共有100个元素，以2倍的形式增长，需4次，如果以固定值的方式按10的话需要10次。

5. STL常用容器以及他们的特点

• vector:底层数据结构为数组 ，支持快速随机访问。
• list:底层数据结构为双向链表，支持快速增删。
• deque:底层数据结构为一个中央控制器和多个缓冲区，支持首尾（中间不能）快速增删，也支持随机访问。
• stack:底层一般用list 或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
• queue:底层一般用list 或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时（stack和queue其实是适配器,而不叫容器，因为是对容器的再封装）
• priority_queue:的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现
• set:底层数据结构为红黑树，有序，不重复。
• multiset:底层数据结构为红黑树，有序，可重复。 
• map:底层数据结构为红黑树，有序，不重复。
• multimap:底层数据结构为红黑树，有序，可重复。
• hash_set:底层数据结构为hash表，无序，不重复。
• hash_multiset:底层数据结构为hash表，无序，可重复 。
• hash_map :底层数据结构为hash表，无序，不重复。
• hash_multimap:底层数据结构为hash表，无序，可重复。

6. list的底层实现机制

以结点为单位存放数据，结点内部包含数据和指向前后结点的指针；结点的地址在内存中不一定连续，每次插入或删除一个元素，就配置或释放一个元素空间。

7. STL容器迭代器非法化

• 只读方法决不非法化迭代器或引用；
• 修改容器内容的方法可能非法化迭代器和/或引用，如下：

类别	容器	插入后……		擦除后……		条件
		迭代器合法？	引用合法？	迭代器合法？	引用合法？
顺序容器	array	N/A		N/A
	vector	否		N/A		插入更改容量
		是		是		被修改元素前
		否		否		于被修改元素或其后
	deque	否	是	是，除了被擦除元素		修改首或尾元素
			否	否		仅修改中部
	list	是		是，除了被擦除元素
	forward_list	是		是，除了被擦除元素
关联容器	set multiset map multimap	是		是，除了被擦除元素
无序关联容器	unordered_set unordered_multiset unordered_map unordered_multimap	否	是	N/A		插入导致重哈希
		是		是，除了被擦除元素		无重哈希

此处插入指代任何添加一或多个元素到容器的方法，而擦除指代任何从容器移除一或多个元素的方法。

• 插入方法是： std::set::insert 、 std::map::emplace 、 std::vector::push_back 和 std::deque::push_front ；另外 std::unordered_map::operator[] 也是，因为它可能插入元素到 map 中。
• 擦除方法是： std::set::erase 、 std::vector::pop_back 、 std::deque::pop_front 和 std::map::clear ；clear 非法化所有迭代器和引用，因为它擦除所有元素。

8. STL容器的线程安全

• 能同时在不同容器上由不同线程调用所有容器函数。更广泛而言， C++ 标准库函数不读取能通过其他线程访问的对象，除非这些对象能直接或间接地经由函数参数，包含 this 指针访问。
• 能同时在同一容器上由不同线程调用 const 成员函数。而且，成员函数 begin() 、 end(), rbegin() 、 rend() 、 front() 、 back() 、 data() 、 find() 、 lower_bound() 、 upper_bound() 、 equal_range() 、 at() 和除了关联容器中的 operator[] 对于线程安全的目标表现如同 const （即它们亦能同时在同一容器上由不同线程调用）。更广泛而言， C++ 标准库函数不修改对象，除非这些对象能直接或间接地经由函数参数，包含 this 指针访问。
• 同一容器中不同元素能由不同线程同时修改，除了 std::vector<bool> 的元素（例如， std::future 对象的 vector 能从多个线程接收值）。
• 迭代器操作（例如自增迭代器）读但不修改底层容器，而且能与同一容器上的其他迭代器操作同时由 const 成员函数执行。非法化任何迭代器的容器操作修改容器，且不能与任何在既存迭代器上的操作同时执行，即使这些迭代器未被非法化。
• 同一容器上的元素可以同时由不指定为访问这些元素的函数修改。更广泛而言， C++ 标准库函数不间接读取能从其参数访问的对象（包含容器的其他对象），除非其规定要求如此。
• 任何情况下，容器操作（还有算法，或其他 C++ 标准库函数）可于内部并行化，只要不更改用户可见的结果（例如 std::transform 可并行化，但指定了按顺序观览序列的每个元素的 std::for_each 不行）

大体上讲STL的线程安全的情况如下：

• 多个线程可以同时读取一个容器中的内容； 即此时多个线程调用 容器的不涉及到写的接口都可以 eg find, begin, end 等.
• 对不同容器的多个写入者是安全的，即多个线程对不同容器的同时写入合法。 但是对于同一容器当有线程写,有线程读时,如何保证正确? 需要程序员自己来控

9. STL中vector和list的区别和联系

联系：
      均为序列式容器，其中的元素不一定有序，但都可以被排序。

区别：

a. 使用的选择：

vector可以随机存储元素（即可以通过公式直接计算出元素地址，而不需要挨个查找），但在非尾部插入删除数据时，效率很低，适合对象简单，对象数量变化不大，随机访问频繁。

list不支持随机存储，适用于对象大，对象数量变化频繁，插入和删除频繁。

b. 时间复杂度      

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

10. STL中deque的实现原理

deque系由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器架构。

deque采用一块所谓的map（注意，不是STL的map容器，map的默认大小为8，如果分配大小大于8,会在前后个预留一个结点）作为主控。这里所谓map是一小块连续空间，其中每个元素（此处称为一个节点，node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是deque的储存空间主体。SGI STL 允许我们指定缓冲区大小，默认值0表示将使用512 bytes 缓冲区。

11. STL中vector与deque的区别

• vector是单向开口的连续线性空间，deque是双向开口的连续线性空间；双向开口是指可以在头尾两端分别做元素的插入和删除操作，vector当然可以在头尾两端进行操作，但是其在头部的操作效率奇差，所以把vector当作单向开口的连续空间。
• deque没有提供空间保留功能，而vector则要提供空间保留功能。
• deque也提供随机访问迭代器，但是其迭代器比vector迭代器复杂很多。
• deque没有容量的观念，它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并连接起来，并不会出现vector中的“因旧空间不足而重新配置一块更大的空间，然后复制元素，再释放旧空间”

12. 哪些容器不能遍历，其各自的特点

• queue，除了头部外，没有其他方法存取deque的其他元素。
• stack（底层以deque实现），除了最顶端外，没有任何其他方法可以存取stack的其他元素。
• heap，所有元素都必须遵循特别的排序规则，不提供遍历功能。

stack是一种先进后出的数据结构，它只有一个出口；stack允许新增元素、移除元素、取得最顶端的元素；但是除了顶端外不可以存取其他元素；stack没有迭代器；stack在缺省的情况下是以deque作为底部容器来完成所有的工作，元素的操作只有push 和 pop 两个接口；stack也可以使用vector 、 list  作为底部容器。

queue是一种先进先出的数据结构，他有两个接口；queue允许新增元素、移除元素、从最低端加入元素、从最顶端取得元素；queue也没有迭代器；queue缺省的情况下以deque作为底部容器实现；queue可以使用 deque 、 list 作为底部实现容器。注意的是queue的底层实现不可以用vector，因为queue要在头部进行元素操作，其效率奇差。

13. vector中erase方法与algorithn中的remove方法区别

vector中erase方法真正删除了元素，迭代器不能访问了

remove只是简单地将元素移到了容器的最后面，迭代器还是可以访问到。因为algorithm通过迭代器进行操作，不知道容器的内部结构，所以无法进行真正的删除。

14. 红黑树有什么性质

• 每个结点是红色或者黑色。
• 根结点为黑色。
• 叶结点为黑色的NULL结点。
• 如果结点为红，其子节点必须为黑。
• 任一结点到NULL的任何路径，所含黑结点数必须相同。

15. set、map的区别与联系

联系：

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

区别：

• map适合存储一个数据字典，并要求方便地根据key找value；set适合查找一个元素是否在某集合内存中
• Set节点只含有Key，Key不重复；Map节点有一个Key和Value两个元素,Key不重复,Value可以重复也可不重复
• set不能直接改变元素值。因为这样会打乱原有的顺序，影响红黑树的结构。改变元素值的方法是：先删除旧元素，再插入新元素。存取元素只能通过迭代器，从迭代器的角度看，元素值是常数。map可以通过key改变value的值

16. set、multiset 容器的insert的区别

set的insert：
      pair<iterator,bool> insert(const value_type& elem);
      iterator insert(iterator pos_hint, const value_type& elem);

multiset的insert：
      iterator insert(const value_type& elem);
      iterator insert(iterator pos_hint, const value_type& elem);

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

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

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

17. 当数据元素增多时（10000和20000个比较），map和set的插入和搜索速度变化如何

map和set的底层实现是RB-TREE，而红黑树的查找是使用二分查找法，时间复杂度为logn，所以从10000增到20000时，查找次数从log10000=14次到log20000=15次，多了1次而已。

18. map和set每次Insert之后，iterator是否失效

不会失效，因为插入操作只是结点指针换来换去，结点内存没有改变。而iterator就像指向结点的指针，内存没变，指向内存的指针也不会变。

19. 为何map和set不能像vector一样有个reserve函数来预分配数据

map和set内部存储的已经不是元素本身了，而是包含元素的节点。也就是说map内部使用的Alloc并不是map声明的时候从参数中传入的Alloc；如下map源码中定义的红黑树_Rb_tree，它的分配器是一个_Pair_alloc_type，并不是初始化map时传进来的allocator了。

      typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
    rebind<value_type>::other _Pair_alloc_type;

      typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
               key_compare, _Pair_alloc_type> _Rep_type;

20 .hashtable，hash_set，hash_map的区别

• hash_set以hashtable为底层，不具有排序功能，能快速查找。其键值就是实值。（set以RB-TREE为底层，具有排序功能。）
• hash_map以hashtable为底层，没有自动排序功能，能快速查找，每一个元素同时拥有一个实值和键值。（map以RB-TREE为底层，具有排序功能。）

21. unordered_map、hash_map和map的区别

unordered_map和hash_map底层是散列，所以理论上操作的平均复杂度是常数时间，map底层是红黑树，理论上平均复杂度是O(logn)：

• hash_map需要hash函数，等于函数；map只需要比较函数(小于函数).
• hash_map采用hash表存储，map采用红黑树实现。因此内部使用的数据结构是不一样的。

hash_map 查找速度会比map快，而且查找速度基本和数据量大小无关，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n) 小，hash还有hash函数的耗时，如果考虑效率，特别是在元素达到一定数量级时，可以考虑hash_map。但对内存使用特别严格，希望程序尽可能少消耗内存，需要考虑hash_map对内存的消耗，另外 hash_map的构造速度较慢，因为要处理hash冲突的问题。

22. auto_ptr是否可以作为vector的元素

不能。因为STL的标准容器规定它所容纳的元素必须是可以拷贝构造和拷贝赋值的。而auto_ptr不能，可以用shared_ptr智能指针代替。

23. stl对于小内存块请求与释放的处理

STL考虑到小型内存区块的碎片问题，设计了双层级配置器，第一级配置直接使用malloc()和free()；第二级配置器则视情况采用不同的策略，当配置区大于128bytes时，直接调用第一级配置器；当配置区块小于128bytes时，便不借助第一级配置器，而使用一个memory pool来实现。究竟是使用第一级配置器还是第二级配置器，由一个宏定义来控制。

SGI STL中默认使用第二级配置器；二级配置器会将任何小额区块的内存需求量上调至8的倍数，(例如需求是30bytes,则自动调整为32bytes)，并且在它内部会维护16个free-list， 各自管理大小分别为8， 16， 24，…，128bytes的小额区块，这样当有小额内存配置需求时，直接从对应的free list中拔出对应大小的内存(8的倍数)；当客户端归还内存时，将根据归还内存块的大小，将需要归还的内存插入到对应free list的最顶端。

当需求的内存在free-list中找不到时，必须向内存池申请支持20个结点，1. 如果内存池足够申请成功，2. 如果内存池空间不足，就分配最大数目的结点数，3. 如果内存池不足分配一个结点，那么将零头分配到相应的free-list中 4.内存池无空间时，配置heap空间，来补充内存池 5。如果heap空间也不足，那么就搜索适当的free-list结点使用 6. 实现没空间抛出异常。

 目的：

• 小对象的快速分配和释放。当一次性预先分配好一块固定大小的内存池后，对小于128字节的小块内存分配和释放的操作只是一些基本的指针操作，相比于直接调用malloc/free，开销小。
• 避免内存碎片的产生；零乱的内存碎片不仅会浪费内存空间，而且会给OS的内存管理造成压力。
• 尽可能最大化内存的利用率。当内存池尚有的空闲区域不足以分配所需的大小时，分配算法会将其链入到对应的空闲列表中，然后会尝试从空闲列表中寻找是否有合适大小的区域，

这种内存分配器局限于STL容器中使用，并不适合一个通用的内存分配。因为它要求在释放一个内存块时，必须提供这个内存块的大小，以便确定回收到哪个free list中，而STL容器是知道它所需分配的对象大小的。