专栏首页Visual CodexSTL学习笔记(5)常用容器 deque

STL学习笔记(5)常用容器 deque

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 虽可成长,却只能向尾端成长,而且其成长其实是一个假象,事实上是由

  • 申请更大空间
  • 原数据复制新空间
  • 释放原空间

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

deque 常用操作

1. deque 构造函数
deque<T> deqT;//默认构造形式 
deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
deque(n, elem);//构造函数将 n 个 elem 拷贝给本身。 
deque(const deque &deq);//拷贝构造函数。 
2. deque 赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。 
assign(n, elem);//将 n 个 elem 拷贝赋值给本身。 
deque& operator=(const deque &deq); //重载等号操作符 
swap(deq);// 将 deq 与本身的元素互换 
3. deque 大小操作
deque.size();//返回容器中元素的个数 
deque.empty();//判断容器是否为空 
deque.resize(num);//重新指定容器的长度为 num,若容器变长,则以默认值填充新位置。如果容器变短, 则末尾超出容器长度的元素被删除。 
deque.resize(num, elem); //重新指定容器的长度为 num,若容器变长,则以 elem 值填充新位置,如果容器变短,则末尾超出容器长度的元素被删除。
4. deque 双端插入和删除操作
push_back(elem);//在容器尾部添加一个数据 
push_front(elem);//在容器头部插入一个数据 
pop_back();//删除容器最后一个数据 
pop_front();//删除容器第一个数据 
5. deque 数据存取
at(idx);//返回索引 idx 所指的数据,如果 idx 越界,抛出 out_of_range。 
operator[];//返回索引 idx 所指的数据,如果 idx 越界,不抛出异常,直接出错。 
front();//返回第一个数据。 
back();//返回最后一个数据 
6. deque 插入操作
insert(pos,elem);//在 pos 位置插入一个 elem 元素的拷贝,返回新数据的位置。 
insert(pos,n,elem);//在 pos 位置插入 n 个 elem 数据,无返回值。 
insert(pos,beg,end);//在 pos 位置插入[beg,end)区间的数据,无返回值。
7. deque 删除操作
clear();//移除容器的所有数据 
erase(beg,end);//删除[beg,end)区间的数据,返回下一个数据的位置。 
erase(pos);//删除 pos 位置的数据,返回下一个数据的位置。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • STL学习笔记(6)常用容器 stack

    stack 是一种先进后出(First In Last Out, FILO)的数据结构,它只有一个出口,形式如图所示。stack 容器允许新增元素, 移除元素,...

    轻舞飞扬SR
  • STL学习笔记(10)常用容器 pair

    对组(pair)将一对值组合成一个值,这一对值可以具有不同的数据类型,两个值可以分别用 pair 的两个公有属性 first 和 second 访问。

    轻舞飞扬SR
  • STL学习笔记(9)常用容器 set/multiset

    Set 的特性是:所有元素都会根据元素的键值自动被排序。Set 的元素不像 map 那样可以同时拥有实值和键值,set 的元素即是键值又是实值。Set 不允许两...

    轻舞飞扬SR
  • STL学习笔记(8)常用容器 list

    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以...

    轻舞飞扬SR
  • STL学习笔记(7)常用容器 queue

    Queue 是一种先进先出(First In First Out,FIFO)的数据结构,它有两个出口,queue 容器允许从一端新增元素,从另 一端移除元素。 ...

    轻舞飞扬SR
  • STL学习笔记(11)常用容器 map/multimap

    Map 的特性是,所有元素都会根据元素的键值自动排序。Map 所有的元素都是 pair,同时拥有实值和键值,pair 的 第一元素被视为键值,第二元素被视为实值...

    轻舞飞扬SR
  • STL学习笔记(4)常用容器 vector

    vector 的数据安排以及操作方式,与 array 非常相似,两者的唯一差别在于空间的运用的灵活性。Array 是静态空间, 一旦配置了就不能改变,要换大一点...

    轻舞飞扬SR
  • STL学习笔记(3)常用容器 string

    C风格字符串(以空字符结尾的字符数组)太过复杂难于掌握,不适合大程序的开发,所以C++标准库定义了一种string 类,定义在头文件。

    轻舞飞扬SR
  • 【C++100问】深度总结STL基本容器的使用

    文章首发于本人CSDN账号:https://blog.csdn.net/tefuirnever

    我是管小亮

扫码关注云+社区

领取腾讯云代金券