stl容器底层数据结构 (STL容器底层实现)

STL（标准模板库）是C++中常用的库之一，其中的容器是程序员在日常开发中经常使用的重要工具。而每种STL容器都有其底层数据结构，这些底层数据结构直接影响了容器的性能、特性和使用场景。在文章中，我们将深入探讨STL容器的底层数据结构，了解它们是如何实现的。

1. vector（向量）

vector是一种动态数组，底层数据结构通常是一个连续的内存块。当vector需要扩容时，会重新分配更大的内存块，并将原有数据复制到新的内存块中。这样做的好处是通过指针的偏移可以快速访问元素，但插入和删除操作会导致数据的搬移，影响性能。

2. list（链表）

list是一个双向链表，每个节点包含指向前驱节点和后继节点的指针。由于是链表结构，插入和删除操作非常高效，时间复杂度为O(1)。由于需要额外的指针存储前后关系，使得list占用的内存空间相对较大，且随机访问效率较低。

3. deque（双端队列）

deque是一种双端队列，底层通常是一个动态数组的数组，每个动态数组称为一个块，块内部是一个固定大小的数组。deque在两端都支持高效的插入和删除操作，时间复杂度为O(1)，同时也支持随机访问。当需要在两端频繁插入和删除元素时，deque是一个不错的选择。

4. set（集合）/map（映射）

set和map底层通常是基于红黑树实现的。红黑树是一种自平衡的二叉搜索树，保证了插入、删除和查找操作的时间复杂度都是O(log n)。红黑树的平衡性使得set和map在处理有序数据和动态数据集合时表现优异。

5. unordered_set（无序集合）/unordered_map（无序映射）

unordered_set和unordered_map是基于哈希表实现的，底层数据结构通常是一个哈希表数组，每个桶存储一个链表或红黑树。哈希表通过哈希函数将元素映射到对应桶内，从而实现高效的插入、删除和查找操作。在无序数据集合和对查找效率要求较高的情况下，unordered_set和unordered_map是更好的选择。

不同的STL容器底层数据结构在性能、内存占用和使用场景上各有优劣。在实际编程中，根据具体需求选择合适的容器非常重要，以提高程序的效率和性能。

c++ STL 中 ，什么叫stack以vector作为底层数据结构？

std::stack只是一个适配器，需要实际的容器（第二个参数）来实现它的功能.这个容器必须提供一下的函数：emptysizebackpush_backpop_backstack以vector作为底层数据结构就是说你对stack做的任何操作都会转接到vector，比如调用stack的push 压入一个值，实际是调用vector的push_back将值保存到vector里面。

C++的STL是如何实现算法和数据结构分离的？

STL看起来是使用了面向对象，但实际上是大部分都是面向过程了。 STL的很多算法，就拿sort函数来说吧。 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp);只要数据结构的跌代器是随机访问的就可以使用。 比如vector,list，同时也兼容普通数组int[]。 这里说到跌代器，STL有一整套跌代器的实现标准：1、实现begin和end函数，是要全局的如vecotr：vecotr<T>::Iterator begin(vecotr<T>);而不是vecotr<T>的成员函数begin，这点要区分。 2、跌代器实现前至++运算3、跌代器实现*运算4、跌代器实现!=运算基本这四点就可以完成了，可以根据这个规则自己实现一个跌代器。 有了跌代器后，那么对于算法来说他们基本就一样了，开头，结尾，自增，以次访问就可以了。 所以一个sort就可以vecotr<int> a;string b;list<float> c;sort((), ());sort((),());sort((),());static bool less(int a1, int a2){return a1 < a2;}sort((), ()+5, less); // 对前5个排序sort((), (), less);sort((), (), [](int a1, int a2) {return a1 <= a2; // 匿名函数});结论就是算法跟数据结构是通过跌代器进行沟通的，所以学好跌代器，STL才算学好，要会用，也要懂为原理。

STL的容器

在实际的开发过程中，数据结构本身的重要性不会逊于操作于数据结构的算法的重要性，当程序中存在着对时间要求很高的部分时，数据结构的选择就显得更加重要。 经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所出入。 STL容器就为我们提供了这样的方便，它允许我们重复利用已有的实现构造自己的特定类型下的数据结构，通过设置一些模板类，STL容器对最常用的数据结构提供了支持，这些模板的参数允许我们指定容器中元素的数据类型，可以将我们许多重复而乏味的工作简化。 容器部分主要由头文件<vector>,<list>,<deque>,<set>,<map>,<stack>和<queue>组成。 对于常用的一些容器和容器适配器（可以看作由其它容器实现的容器），可以通过下表总结一下它们和相应头文件的对应关系。 序列式容器向量(vector) 连续存储的元素<vector>列表(list) 由节点组成的双向链表，每个结点包含着一个元素<list>双端队列(deque) 连续存储的指向不同元素的指针所组成的数组<deque>容器适配器栈(stack) 后进先出的值的排列 <stack>队列(queue) 先进先出的值的排列 <queue>优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列 <queue>关联式容器集合(set) 由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序 <set>多重集合(multiset) 允许存在两个次序相等的元素的集合 <set>映射(map) 由{键，值}对组成的集合，以某种作用于键对上的谓词排列 <map>多重映射(multimap) 允许键对有相等的次序的映射 <map>

若对本页面资源感兴趣，请点击下方或右方图片，注册登录后

搜索本页相关的【资源名】【软件名】【功能词】或有关的关键词，即可找到您想要的资源

如有其他疑问，请咨询右下角【在线客服】，谢谢支持！