C++STL库的 deque、stack、queue、list、set/multiset、map/multimap

2023-12-13 04:11:00

deque 容器

????????Vector 容器是单向开口的连续内存空间， deque 则是一种双向开口的连续线性空 间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然， vector 容器也可以在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。
????????Deque 容器和 vector 容器最大的差异，一在于 deque 允许使用常数项时间对头端 进行元素的插入和删除操作。二在于 deque 没有容量的概念，因为它是动态的以 分段连续空间组合而成，随时可以增加一段新的空间并链接起来，换句话说，像 vector 那样， ” 旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间” 这样的事情在 deque 身上是不会发生的。也因此 deque 没有必须要提供所谓的空间保留(reserve) 功能 .
????????虽然 deque 容器也提供了 Random Access Iterator, 但是它的迭代器并不是普通的指针，其复杂度和 vector 不是一个量级，这当然影响各个运算的层面。因此，除非 有必要，我们应该尽可能的使用 vector ，而不是 deque 。对 deque 进行的排序操作，为了最高效率，可将 deque 先完整的复制到一个 vector 中，对 vector 容器进行排序，再复制回 deque.

deque 容器实现原理

????????Deque 容器是连续的空间，至少逻辑上看来如此，连续现行空间总是令我们联想 到 array 和 vector,array 无法成长， vector 虽可成长，却只能向尾端成长，而且其 成长其实是一个假象，事实上(1) 申请更大空间 (2) 原数据复制新空间 (3) 释放原空间 三步骤，如果不是 vector 每次配置新的空间时都留有余裕，其成长假象所带来 的代价是非常昂贵的。
????????Deque 是由一段一段的定量的连续空间构成。一旦有必要在 deque 前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在 deque 的头端或者尾端。
????????Deque 最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随 机存取的接口，避开了重新配置空间，复制，释放的轮回，代价就是复杂的迭代器架构。
????????既然 deque 是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象， 数据结构的设计及迭代器的前进后退操作颇为繁琐。Deque 代码的实现远比 vector 或 list 都多得多。 ????????Deque 采取一块所谓的 map( 注意，不是 STL 的 map 容器 ) 作为主控，这里所谓map 是一小块连续的内存空间，其中每一个元素 ( 此处成为一个结点 ) 都是一个指针， 指向另一段连续性内存空间，称作缓冲区。缓冲区才是 deque 的存储空间的主体。

deque 构造函数

deque<T> deqT; // 默认构造形式
deque(beg, end); // 构造函数将 [beg, end) 区间中的元素拷贝给本身。
deque(n, elem); // 构造函数将 n 个 elem 拷贝给本身。
deque( const deque &deq); // 拷贝构造函数。

deque 赋值操作

assign(beg, end); // 将 [beg, end) 区间中的数据拷贝赋值给本身。
assign(n, elem); // 将 n 个 elem 拷贝赋值给本身。
deque& operator =( const deque &deq); // 重载等号操作符
swap(deq); // 将 deq 与本身的元素互换

deque 大小操作

deque.size(); // 返回容器中元素的个数
deque.empty(); // 判断容器是否为空
deque.resize(num); // 重新指定容器的长度为 num, 若容器变长，则以默认值填充新位 置。如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem); // 重新指定容器的长度为 num, 若容器变长，则以 elem 值 填充新位置 , 如果容器变短，则末尾超出容器长度的元素被删除。

deque 双端插入和删除操作

push_back(elem); // 在容器尾部添加一个数据
push_front(elem); // 在容器头部插入一个数据
pop_back(); // 删除容器最后一个数据
pop_front(); // 删除容器第一个数据

deque 数据存取

at(idx); // 返回索引 idx 所指的数据，如果 idx 越界，抛出 out_of_range 。
operator []; // 返回索引 idx 所指的数据，如果 idx 越界，不抛出异常，直接出错。
front(); // 返回第一个数据。
back(); // 返回最后一个数据

deque 插入操作

insert(pos,elem); // 在 pos 位置插入一个 elem 元素的拷贝，返回新数据的位置。
insert(pos,n,elem); // 在 pos 位置插入 n 个 elem 数据，无返回值。
insert(pos,beg,end); // 在 pos 位置插入 [beg,end) 区间的数据，无返回值。

deque 删除操作

clear(); // 移除容器的所有数据
erase(beg,end); // 删除 [beg,end) 区间的数据，返回下一个数据的位置。
erase(pos); // 删除 pos 位置的数据，返回下一个数据的位置。

stack 容器

容器基本概念

????????stack 是一种先进后出 (First In Last Out,FILO) 的数据结构，它只有一个出口，形式 如图所示。stack 容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端 外，没有任何其他方法可以存取 stack 的其他元素。换言之， stack 不允许有遍历 行为。
有元素推入栈的操作称为 :push, 将元素推出 stack 的操作称为 pop

stack 没有迭代器

????????Stack 所有元素的进出都必须符合 ” 先进后出 ” 的条件，只有 stack 顶端的元素，才有机会被外界取用。Stack 不提供遍历功能，也不提供迭代器。

stack 构造函数

stack<T> stkT; //stack 采用模板类实现， stack 对象的默认构造形式：
stack( const stack &stk); // 拷贝构造函数

stack 赋值操作

stack& operator =( const stack &stk); // 重载等号操作符

stack 数据存取操作

push(elem); // 向栈顶添加元素
pop(); // 从栈顶移除第一个元素
top(); // 返回栈顶元素

stack 大小操作

empty(); // 判断堆栈是否为空
size(); // 返回堆栈的大小

queue 容器

容器基本概念
????????Queue 是一种先进先出 (First In First Out,FIFO) 的数据结构，它有两个出口， queue 容器允许从一端新增元素，从另一端移除元素。
queue 没有迭代器
????????Queue 所有元素的进出都必须符合 ” 先进先出 ” 的条件，只有 queue 的顶端元素，才 有机会被外界取用。Queue 不提供遍历功能，也不提供迭代器。

queue 构造函数

queue<T> queT; //queue 采用模板类实现， queue 对象的默认构造形式：
queue( const queue &que); // 拷贝构造函数

queue 存取、插入和删除操作

push(elem); // 往队尾添加元素
pop(); // 从队头移除第一个元素
back(); // 返回最后一个元素
front(); // 返回第一个元素

queue 赋值操作

queue& operator =( const queue &que); // 重载等号操作符

queue 大小操作

empty(); // 判断队列是否为空
size(); // 返回队列的大小

list 容器

list 容器基本概念

????????链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通 过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点） 组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素 的数据域，另一个是存储下一个结点地址的指针域。
????????相较于 vector 的连续线性空间， list 就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list 对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list 永远是常数时间。
? ? ? ? ?List 和 vector 是两个最常被使用的容器。
List 容器是一个双向链表。
????????采用动态存储分配，不会造成内存浪费和溢出
????????链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
????????链表灵活，但是空间和时间额外耗费较大
list 容器的迭代器
????????List 容器不能像 vector 一样以普通指针作为迭代器，因为其节点不能保证在同一 块连续的内存空间上。List 迭代器必须有能力指向 list 的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list 正确的递增，递减、取值、成员 取用” 是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点 的数据值，成员取用时取的是节点的成员。
????????由于 list 是一个双向链表，迭代器必须能够具备前移、后移的能力，所以 list 容器 提供的是 Bidirectional Iterators.
????????List 有一个重要的性质，插入操作和删除操作都不会造成原有 list 迭代器的失效。
????????这在 vector 是不成立的，因为 vector 的插入操作可能造成记忆体重新配置，导致 原有的迭代器全部失效，甚至 List 元素的删除，也只有被删除的那个元素的迭代 器失效，其他迭代器不受任何影响。
list 容器的数据结构
list 容器不仅是一个双向链表，而且还是一个循环的双向链表。

list 构造函数

list<T> lstT; //list 采用采用模板类实现 , 对象的默认构造形式：
list(beg,end); // 构造函数将 [beg, end) 区间中的元素拷贝给本身。
list(n,elem); // 构造函数将 n 个 elem 拷贝给本身。
list( const list &lst); // 拷贝构造函数。

list 数据元素插入和删除操作

push_back(elem); // 在容器尾部加入一个元素
pop_back(); // 删除容器中最后一个元素
push_front(elem); // 在容器开头插入一个元素
pop_front(); // 从容器开头移除第一个元素
insert(pos,elem); // 在 pos 位置插 elem 元素的拷贝，返回新数据的位置。
insert(pos,n,elem); // 在 pos 位置插入 n 个 elem 数据，无返回值。
insert(pos,beg,end); // 在 pos 位置插入 [beg,end) 区间的数据，无返回值。
clear(); // 移除容器的所有数据
erase(beg,end); // 删除 [beg,end) 区间的数据，返回下一个数据的位置。

文章来源:https://blog.csdn.net/weixin_50963877/article/details/134897457
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。