C++——STL标准模板库——容器详解——deque
一、基本概念
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提供双端插入或删除操作,但是从中间插入或者删除操作时,性能下降。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!