C++——STL标准模版库——容器知识归纳汇总

一、vector动态数组

(一)概念和特性:动态数组,能够自动调整大小,支持快速随机访问,插入和删除操作可能会移动大量元素。

(二)优势:内存连续,访问效率高,能够自动调整大小。尾插、尾删效率较高。

(三)劣势:因为储存空间连续,非尾部的插入或者删除需要频繁移动数据,效率较低。

(四)使用场景:适用于需要频繁进行随机访问的需求和不确定需要维护数据量的场景。

(五)注意事项:在使用[]和at()访问数据时需要特别注意越界风险;vector容器不会自减capacity

二、string字符串

(一)概念和特性:本质上是指定了char类型的vector模板类,长度可变,增加了自动缩减容量的功能,适用于各种字符。

(二)优势:和C风格的字符数组相比,具备自动管理内存的优势,集成了字符串的链接、截取、查找、删除等更方便的操作方式。更方便文本处理和分析。

(三)使用场景:需要进行文本操作;需要动态管理字符串。

三、deque双端队列

(一)概念和特性:双端队列,底层是分散式存储结构,一般使用定长数组(缓冲区)来存储数据,使用每个缓冲区的指针作为关键字形成map结构,维护储存的数据。

(二)优势:两端插入或者删除效率较高,支持随机访问。

(三)劣势:中间插入或者删除的效率较低。

(四)使用场景:适合双端数据维护比较频繁的需求。

(五)注意事项:deque没有capacity限制;能够自动缩减多余空间。

四、list双向链表

(一)概念和特性:双向链表,分散式存储结构。每个元素包含两个指针,一个指向前驱节点,一个指向后续节点。提供了双向迭代器,不支持随机访问。

(二)优势:任意位置插入和删除元素效率高,速度快。

(三)劣势:不支持随机访问,查找效率较低。

(四)使用场景:适用于需要频繁插入或者删除元素的需求。

(五)注意事项:插入元素时自动申请内存,删除元素时自动释放内存。list封装了list<T>::sort()排序,用法和algorithm中的sort算法类似。

五、set集合

(一)概念和特性:包含唯一元素的有序集合。能够自动排序,元素唯一。底层结构为红黑树。

(二)优势:实现快速查找、插入或删除,时间复杂度为O(logn)。

(三)劣势:无法直接修改元素,只能通过先删除后插入的方法;存储空间通常较大,可能会占用较多的内存空间。

(四)使用场景:适用于需要快速查找元素是否存在的需求。

(五)注意事项:想要存储相同元素需要用multiset容器。

六、map映射

(一)概念和特性:映射。基于红黑树的储存键值对(对组)的集合。支持快速查找键对应的值,键是唯一的,值可以重复。

(二)优势:自动排序。实现快速查找、插入或删除,时间复杂度为O(logn)。

(三)劣势:如果关键字存在,无法更新关键字,需要删除后重新插入;存储空间通常较大,可能会占用较多的内存空间。

(四)使用场景:需要用关键字快速查找对应的信息,例如查字典或者户籍系统

(五)注意事项:无法修改存在的键,只有先删除后插入。