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

STL（Standard Template Library）是C++标准库的一部分，提供了丰富的数据结构和算法，其中包括多种容器。STL容器是一种数据结构，用于存储和管理数据，它们支持各种操作，例如插入、删除、查找等。STL容器是C++中非常重要的组成部分，可以帮助开发者更高效地管理数据，并提供了不同的底层数据结构以满足不同的需求。

STL容器可以分为多种类型，如顺序容器、关联容器、无序关联容器、容器适配器等。每种容器都有其独特的特点和适用场景。不同类型的容器使用不同的底层数据结构来实现其功能，下面将对几种常见的STL容器及其底层数据结构进行详细分析。

1. 顺序容器

顺序容器是一种按照元素在内存中的顺序来组织和存储数据的容器，包括vector、deque、list等。这些容器通常使用数组或链表作为底层数据结构。

1.1 vector

vector是一种动态数组，它使用连续的内存存储元素，可以快速随机访问元素，并且支持在尾部进行高效的插入和删除操作。vector的底层实现通常是一个连续的数组，当元素数量超过当前容量时，vector会重新分配更大的内存空间，将原有元素复制到新的位置，以实现动态扩容。

1.2 deque

deque（双端队列）是一种双端开口的序列容器，可以在头部和尾部高效地进行插入和删除操作。deque的底层实现通常是一个由多个定长数组组成的结构，它在插入和删除元素时可以在两端进行操作，因此在一定程度上避免了重新分配内存，提高了性能。

1.3 list

list是一种双向链表，每个节点存储一个元素以及指向前一个节点和后一个节点的指针。list支持高效的插入和删除操作，但不支持随机访问，需要通过指针遍历整个链表。list的底层数据结构是由节点组成的链表，插入和删除操作的时间复杂度为O(1)。

2. 关联容器

关联容器是一种通过键值对来存储和访问元素的容器，包括set、map、multiset、multimap等。这些容器通常使用二叉搜索树或哈希表作为底层数据结构。

2.1 set

set是一种有序的容器，其中存储的元素按照键值自动排序，且不允许重复。set的底层实现通常是一棵红黑树，它保证了元素的有序性，插入和查找操作的平均时间复杂度为O(log n)。

2.2 map

map是一种键值对映射的容器，每个键关联一个值，且键不允许重复。map的底层实现通常也是一棵红黑树，可以高效地进行元素的插入、删除和查找操作，时间复杂度为O(log n)。

3. 无序关联容器

无序关联容器是一种不维护元素顺序的容器，包括unordered_set、unordered_map、unordered_multiset、unordered_multimap等。这些容器通常使用哈希表作为底层数据结构。

3.1 unordered_set

unordered_set是一种无序的容器，其中存储的元素不按照键值排序，且不允许重复。unordered_set的底层实现通常是一个哈希表，可以高效地进行元素的插入、删除和查找操作，平均时间复杂度为O(1)。

3.2 unordered_map

unordered_map是一种键值对映射的无序容器，每个键关联一个值，且键不允许重复。unordered_map的底层实现通常也是一个哈希表，可以高效地进行元素的插入、删除和查找操作，平均时间复杂度为O(1)。

4. 容器适配器

容器适配器是一种封装了不同底层容器的接口，包括stack、queue、priority_queue等。这些适配器提供了特定类型的接口，使得开发者可以方便地使用特定功能的容器，而不用关心底层数据结构。

4.1 stack

stack是一种后进先出（LIFO）的容器适配器，通常基于deque或list实现。stack提供了push、pop、top等操作，使得元素的插入和删除更加简单高效。

4.2 queue

queue是一种先进先出（FIFO）的容器适配器，通常基于deque或list实现。queue提供了push、pop、front、back等操作，可以用于实现队列的功能。

4.3 priority_queue

priority_queue是一种优先级队列，它按照元素的优先级顺序进行插入和删除操作。priority_queue通常基于vector实现，提供了push、pop、top等操作，使得具有最高优先级的元素始终处于队首位置。

STL容器提供了丰富的数据结构和算法，可以帮助开发者高效地管理和操作数据。不同类型的容器使用不同的底层数据结构来实现其功能，开发者可以根据需求选择合适的容器来提高程序的性能和可维护性。

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

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

C++ STL中的各个容器分别对应什么数据结构，求详细陈列出来

名字不就是对应的数据结构吗？vector是动态数组，unordered_set是散列表，map是红黑树。 其他的像array就是数组，stack是栈等等，很容易就看出来了。

STL六大组件

1、 容器 （containers）：STL内部封装好的数据结构，一种class template，常用的包括vector、list、deque、set、map、multiset、multimap等2、 算法 （algorithm）：一种function template，常用的有sort、search、copy、erase等 3、 迭代器 (iterator)：泛型指针，是一种智能指针，是一种将operator*，operator->，operator++，operator–等指针相关操作予以重载的class template。 所有STL容器都附带自己的迭代器 4、 配接器 (adapter)：一种用来修饰容器(container)或仿函数(functor)或迭代器(iterator)接口的东西。 如queue和stack。 它们的底部完全借助deque，所有操作都由底层的deque供应。 改变functor接口者，称为functor adapter，改变container接口者，称为container adapter；改变iterator接口者，称为iterator adapter。 5、 配置器 (allocator)：负责空间配置与管理。 是一个实现了动态空间配置、空间管理、空间释放的class template。 一般SGI STL为每一个容器都指定其缺省的空间配置器为alloc（SGI配置器） 6、 仿函数 (functor)：行为类似函数，就是使一个类的使用看上去象一个函数，具有可配接性。 它的具体实现就是通过在类中重载了operator()，使这个类具有了类似函数的行为，就是一个仿函数类了。 一般函数指针、回调函数可视为狭义的仿函数。 以操作数的个数划分，可分为一元和二元仿函数；以功能划分，可分为算术运算、关系运算、逻辑运算三大类。 这部分内建的仿函数，均放在头文件里，使用时需引入头文件 STL内建仿函数分类包括： 1）算术类仿函数 加：plus 减：minus 乘：multiplies 除：divides 模取：modulus 否定：negate 2）关系运算类仿函数 等于：equal_to 不等于：not_equal_to 大于：greater 大于等于：greater_equal 小于：less 小于等于：less_equal 3）逻辑运算仿函数 逻辑与：logical_and 逻辑或：logical_or 逻辑否：logical_no

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

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

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