C++ STL容器 (Containers)

作为面试常见问题对应的知识点整理,深入的话可以研究源码,最近时间比较紧张就不过于深入了。以后一定补上。

C++ STL(标准模版库)是一套功能强大的C++模版类,提供了通用的模版类和函数,可以实现多种常用算法和数据结构。

C++ STL容器主要有序列式容器(Sequential Containers)和关联式容器(Associative Containers)两种。容器类自动申请和释放内存,因此无需new和delete操作。

序列式容器

序列式容器以线性排列(类似于普通数组的存储方式)来存储某一指定类型。这个顺序不依赖于元素的值,而是与元素加入容器时的位置相对应。

序列式容器有向量(vector)、双端队列(deque)、双向链表(list)、单向链表(forward_list)、固定大小数组(array)和字符串(string)

  • 向量 vector

可变大小数组,在存储空间不足时,会自动申请更多内存。在尾部增加或删除元素时间为O(1),在其他位置为O(n)。支持快速随机访问。

vector将元素保存在连续的内存空间中。由于元素是连续存储的,通过下标来计算地址非常快,但中间位置增加/删除元素比较耗时,因为要移动位置受影响的元素,才能继续保持连续存储。而且添加新元素可能需要分配额外的存储空间,所有元素都必须移动到新的存储空间中。

reserve()函数可以增加分配的内存空间,resize()将容器大小改大时,分配新内存空间,改小时只改变容器中元素的数目,而不是容器的容量。

  • 双端队列 deque

类似vector,在头尾增加删除时间复杂度都为O(1),其他位置为O(1)。支持随机访问。

  • 双向链表 list

只支持双向顺序访问,在任何位置增加/删除时间复杂度都是O(1)。但访问容器中任意元素的速度要比array、vector、deque慢,因为必须从头或尾开始访问。

额外内存开销比较大。list没有capacity函数,因为它无需分配指定的内存大小且可以任意伸缩,这是因为它存储在非连续的内存空间中,并且由指针将有序的元素链接起来。

  • 单向链表 forward_list

只支持点想顺序访问,在任何位置增加/删除时间复杂度都是O(1)。比list容器快、更节省内存。

额外内存开销比较大。设计目标是达到与最好的手写单向链表相当的性能,所以没有size操作,否则保存或计算大小会有额外的开销。

  • 固定大小数组 array

在deque基础上改变,更多被称为容器适配器。不能添加或删除元素。支持快速随机访问。

  • 字符串 string

在deque基础上改变,更多被称为容器适配器。与vector相似,随机访问快。在尾部增加/删除速度快。

string和vector类似,将元素保存在连续的内存空间中。由于元素是连续存储的,通过下标来计算地址非常快,但中间位置增加/删除元素比较耗时,因为要移动位置受影响的元素,才能继续保持连续存储。而且添加新元素可能需要分配额外的存储空间,所有元素都必须移动到新的存储空间中。

  • 迭代器 iterator

迭代器范围由一对迭代器表示,分别指向同一个容器重的元素或者是尾元素之后的位置,通常被称为begin和end。

对构成范围迭代器的要求:指向同一个容器中的元素,或者是容器最后一个元素之后的位置。并且可以通过反复递增begin到达end,end不在begin之前。

容器操作可能使迭代器失效。

  • 容器适配器 adaptor

常见顺序容器适配器有栈(stack)、队列(queue)和优先队列(priority_queue)。适配器让某种事物的行为看起来像另外一种事物一样。

stack:默认基于deque实现,也可以在list或vector上实现。

queue:默认基于deque实现,也可以用list或vector实现。

priority_queue:默认基于vector实现,也可以用deque实现。

关联式容器

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

关联容器分为有序和无序两种。有序的有map、set、multimap、multiset,适用红黑树实现,是一种非常搞笑的平衡搜索二叉树。无序的有unordered_map、unordered_set、unordered_multimap、unordered_multiset。无序的情况是用哈希函数或哈希组织实现的。

  • map

键唯一,元素默认按升序排列。

  • set

键和值一样,且唯一,元素默认按升序排列。

set的迭代器是const类型,只允许访问set中的元素,不能修改。

  • unordered_map

元素不一定按键值排序,而是按照哈希函数分派,可以提供更快的搜索速度。

  • unordered_set

元素不一定经过排序,而是按照哈希函数分派,提供更快的搜索速度。

  • 为什么关联式容器插入、删除效率比其他序列容器高?

因为对于关联容器来说,元素采用节点的方式存储,不需要做内存拷贝和内存移动。

  • 无序容器

无序容器在存储上位一组桶,每个桶保存0或多个元素。无序容器用一个哈希函数将元素映射到桶。为了访问一个元素,容器先计算它的哈希值,找到应该搜索哪个桶。因此无序容器的性能依赖于哈希函数的质量和桶的大小。

About the Author: 雪球

一个在读的工科研究生 一个努力追赶时代脚步的人 Github: https://github.com/xueqiwang0v0 LinkedIn: https://www.linkedin.com/in/xueqi-wang-0939b51a6/

发表评论

邮箱地址不会被公开。 必填项已用*标注