STL 容器小结

落日映苍穹つ 2022-07-27 14:50 241阅读 0赞

顺序容器：为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器是的位置相对应。

顺序容器几乎可以保存任意类型的元素。Eg: vector<vector<string>> lines; //vector的vector

标准库还定义了三个顺序容器适配器：stack、queue、priority\_queue，适配器（adaptor）是个标准库中的通用概念，容器、迭代器、函数都有适配器。本质上，一个适配器是一种机制，能使某种事物的行为看起来想起他另外一种事物一样。

关联容器：其中的元素是按照关键字来保存和访问的。

<table> 
 <tbody> 
 <tr> 
 <td> vector </td> 
 <td> 唯一可以和C兼容的stl容器。 可变大小数组，支持快速随机访问，可任意位置进行插入删除。在尾部之外位置插删元素可能很慢 </td> 
 <td> 优点：内存和C完全兼容、高效随机访问、节省空间 缺点：内部插入删除元素代价巨大、动态大小查过自身容量需要申请大量内存做大量拷贝。 </td> 
 </tr> 
 <tr> 
 <td> deque </td> 
 <td> 双端队列，支持快速随机访问，在头尾插删速度很快 </td> 
 <td> 优点：高效随机访问、内部插入删除元素效率方便、两端push&nbsp;pop 缺点：内存占用比较高 </td> 
 </tr> 
 <tr> 
 <td> list </td> 
 <td> 双向链表，只支持双向顺序访问。任意位置插删速度都很快 </td> 
 <td> 优点：任意位置插入删除元素常量时间复杂度、两个容器融合是常量时间复杂度 缺点：不支持随机访问、比vector占用更多的存储空间 </td> 
 </tr> 
 <tr> 
 <td> Forward_list </td> 
 <td> 单向链表。 </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> array </td> 
 <td> 固定大小数组，支持快速随机访问，不能添加或删除元素 </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> string </td> 
 <td> 与vector类似，但专门保存字符，随机访问快，尾部插删速度快 </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> map </td> 
 <td> 关联数组：保存关键字-值对 </td> 
 <td> 数据结构模型是红黑树 优点：元素会按照键值排序、查找是对数时间复杂度、通过键值查元素、map提供了下标访问。 查找速度快O(logn) </td> 
 </tr> 
 <tr> 
 <td> set </td> 
 <td> 关键字即值，即只保存关键字的容器 </td> 
 </tr> 
 <tr> 
 <td> multimap </td> 
 <td> 关键字可重复出现的map </td> 
 </tr> 
 <tr> 
 <td> multiset </td> 
 <td> 关键字可重复出现的set </td> 
 </tr> 
 <tr> 
 <td> 前面加上unordered_&nbsp;就成了无序集合 </td> 
 <td> 用哈希函数组织 </td> 
 <td> &nbsp; </td> 
 </tr> 
 </tbody> 
</table>

顺序容器选择基本原则：

●除非有很好的理由选择其他容器，否则应使用vector

●若程序有很多小的元素，且空间的额外开销很重要，则 不要 用list或者forward\_list.

●若程序要求随机访问元素，应使用vector和deque

●若真的不确定该使哪种，可以在程序中只是用vector和list公共的操作：使用迭代器，不适用下标操作，避免随机访问。这样，在有必要的时候选择使用vector或list都很方便。