C++——STL标准模板库——容器详解——deque

2023-12-29 10:39:18

一、基本概念

deque:双端队列。和vector容器一样同属于STL中的序列式容器,相较vector容器的尾部操作,多提供了头部的快速插入和删除操作。deque的特点如下:

1、deque提供双端元素的插入和删除操作,逻辑结构是一个双端扩充的连续数组。物理结构上是由多块离散式连续存储空间(buffer)组成,由一个叫做map的数据结构存储这些buffer的地址,当deque需要扩容时,便申请一块新的buffer,将地址加入到map中即可。

2、提供双向随机访问迭代器:deque迭代器是一个智能指针,包含4个私有成员变量,分别是cur、first、last、node。cur指向当前访问元素,first指向当前访问元素所在buffer的首地址,last指向当前访问元素所在buffer的最后一个元素位置,node指向当前访问元素所在结点(封装了buffer)

3、deque底层由中控器(map结构)管理,在物理存储层面实现动态扩展。当一个缓冲区满时,中控器会自动为其分配一个新的缓冲区,并将所有元素从旧缓冲区复制到新缓冲区。同样地,当需要释放内存时,中控器会自动回收不再使用的缓冲区。这样的结构也就决定了deque没有capacity的概念。

总的来说,deque的中控器是一个高效的数据结构,它通过使用map来维护缓冲区的位置信息,使得deque可以在头部和尾部进行高效的插入和删除操作。这种设计使得deque成为在需要频繁进行前后端操作的应用中的理想选择。

二、构造函数

deque<T> d;???????????????????????????????????????????????默认构造函数

deque<T> d(int n,const T& value);? ? ? ? ? ? ?带参构造函数,含有n个元素,初始化为value

deque<T> d(deque<T>& d1);?????????????????????复制构造函数

deque<T> d(iterator first,iterator last);? ? ? ? 范围构造函数,将范围区间内元素复制到新容器

deque<T> d(deque<T>&& d1);? ? ? ? ? ? ? ? ? ?移动构造函数(c++11)

三、成员函数

(一)访问函数

T& deque<T>::operator[](int index);? ? ? ? 数组符号重载,返回该index位置的引用

T& deque<T>::at(int index);? ? ? ? ? ? ? ? ? ? ?返回该index位置的引用

T& deque<T>::front();? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 返回该该容器头元素的引用

T& deque<T>::back();? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 返回该容器尾元素的引用

(二)修改函数

相较vector,新增了头插和头删函数

void deque<T>::push_back(T& value);? ? ? ? 尾插

void deque<T>::pop_back();? ? ? ? ? ? ? ? ? ? ? ? 尾删

void deque<T>::push_front(T& value);? ? ? ? 头插

void deque<T>::pop_front();? ? ? ? ? ? ? ? ? ? ? ? 头删

void deque<T>::insert(iterator it,T& value);?在指定位置插入元素

void deque<T>::erase(iterator it);? ? ? ? ? ? ? ? 删除指定位置元素

(三)大小函数

deque双端队列没有容量的概念,但有可容纳最大元素数量,这个数量是由系统决定的

size_t deque<T>::size();? ? ? ? ????????返回当前容器中元素数量

bool deque<T>::empty();? ? ? ?????????判断当前容器是否为空

size_t deque<T>::max_size();? ? ? ?返回这个系统中双端队列deque能够容纳最大元素数量

(四)赋值操作

deque<T>& operator=(const deque<T>& other);? ? ? ? 将other内容复制到当前容器

deque<T>& operator=(initializer_list<T> init);? ? ? ? ? ? ?将初始化列表复制到当前容器

deque<T>& operator=(deque<T>&& other)noexcept;将other内容通过移动赋值给当前容器

移动赋值和移动构造函数一样,需要将参数通过move()函数转换为右值引用,本质上类似于浅拷贝,但在浅拷贝的过程中,解除了原有对象other对资源的所有权和控制权,移交给了当前容器。移动语义技术出现在c++11及以后版本,处理大量数据或资源密集型对象时,避免了大量赋值操作,优化程序性能

四、注意事项

1、越界风险。当使用下标运算符[],下标超出范围,index>size()时,行为是未定义的。at()不会存在此风险;下标越界时,at()会抛出out_of_range的异常提示。

2、迭代器失效。当容器添加或删除元素时会导致部分迭代器或者指针失效,特别是储存空间重新分配时,所有迭代器和指针都会失效。

3、内存管理。deque的内存管理比vector更复杂,当插入和删除元素时都有可能重新分配储存空间。deque能够自动释放空闲内存。

4、操作性能。deque提供双端插入或删除操作,但是从中间插入或者删除操作时,性能下降。

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