说一说STL 中常见容器的实现原理

[问答题]

说一说STL 中常见容器的实现原理

查看答案及解析

得分点

vector、deque、stack、queue、list、set、map

参考答案

标准回答

vector

vector 是一种动态数组，在内存中具有连续的存储空间，支持快速随机访问，由于具有连续的存储空间，所以在插入和删除操作方面，效率比较慢。
deque

deque 是一种双向开口的连续线性空间，元素在内存连续存放，随机存取任何元素都在常数时间完成，在两端增删元素具有较佳的性能。
stack

stack 是一种先进后出（First In Last Out，FILO）的数据结构，它只有一个出口。stack 容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端外，没有任何其他方法可以存取 stack 的其他元素，stack 不允许有遍历行为。
queue

queue 是一种先进先出（First In First Out，FIFO）的数据结构，它有两个出口，queue 容器允许从一端新增元素，从另一端移除元素。
list

list 内部实现的是一个双向链表，元素在内存不连续存放，在任何位置增删元素都能在常数时间完成，不支持随机存取。
map
map内部自建一棵红黑树（一种自平衡二叉树），这棵树具有数据自动排序的功能，所以在map内部所有的数据都是有序的，以二叉树的形式进行组织。
set

set 底层使用红黑树实现，插入删除操作时仅仅移动指针即可，不涉及内存的移动和拷贝，所以效率比较高。set 中的元素都是唯一的，而且默认情况下会对元素进行升序排列。不能直接改变元素值，因为那样会打乱原本正确的顺序，要改变元素值必须先删除旧元素，再插入新元素。不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取。

编辑于 2021-09-15 11:26:11 回复(0)

烂_俗_人

stl容器分为关联型容器和序列性容器

序列性容器分为vector,list,deque,queue,stack,slist,hea[,prior_queue

vector由数组实现，当现有容量不足时，申请新的内存，每次新增一倍当前的容量的内存

deque翻译为双端队列，但他有一个中央控制器map实现，deque的数据零零散散的储存在多个数组中，而map中保存着一个指针，指针分别指向这些数组

,deque先从map的中间位置获取指针，然后移到具体的数组存放数据

stack,queue基于deque

heap，完全二叉树，使用大顶堆实现，然后进行排序，以vector形式存放

prior_queue,优先队列，基于heap

list,双向环形链表

slisi,单链表

关联式容器：set,map,mutiset,mutimap-基于红黑树（增加额外条件的平衡二叉数）

发表于 2022-07-06 16:59:54 回复(0)

我只想做个好人

STL（Standard Template Library，标准模板库）是C++编程语言中的一个重要组成部分。

STL共有六大组件，容器、算法、迭代器、仿函数、适配器和空间配置器。

容器指的是存放数据的各种数据结构，比如vector、list、deque、set、map等。

vector也称单端数组，连续的内存空间，可以动态扩展（不是在原空间上续接新空间，而是寻找更大的空间，拷贝原数据到新空间，释放原空间）。

list原理是双向链表，常量性能的增删，不支持随机访问。

deque是双端队列。底层结构是【一段段连续的小空间】拼接而成。类似动态二维数组，每个小空间可以看作是一个节点，节点间通过指针相连，形成了一个分段连续的空间。支持在两端进行插入和删除操作，时间复杂度为O（1）.通过中控器的两个指针实现，指针分别指向空间起始位和结束位。插入和删除操作通过调整指针位置来实现快速访问和修改。比vector减少内存的浪费。其迭代器需要能遍历整个deque，包括所有分段，同时还需要支持随机访问操作。

set原理是红黑树。

map原理是以Key建立的红黑树。

所有无序容器的底层实现都是hash map，序容器存储键值对时，会先申请一整块连续的存储空间，此空间用来存储各个链表的头指针，称其为桶。各键值对的存储位置是各个链表的节点。

发表于 2024-09-05 17:13:35 回复(0)