C++ STL第三篇(搞清楚deque原理和有多少用法)

这篇具有很好参考价值的文章主要介绍了C++ STL第三篇(搞清楚deque原理和有多少用法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

deque

Vector容器是单向开口的连续内存空间,deque则是一种双向开口的连续线性空间。所谓的双向开口,意思是可以在头尾两端分别做元素的插入和删除操作,当然,vector容器也可以在头尾两端插入元素,但是在其头部操作效率奇差,无法被接受。

C++ STL第三篇(搞清楚deque原理和有多少用法)

Deque容器和vector容器最大的差异,一在于deque允许使用常数项时间对头端进行元素的插入和删除操作。二在于deque没有容量的概念,因为它是动态的以分段连续空间组合而成,随时可以增加一段新的空间并链接起来,换句话说,像vector那样,”旧空间不足而重新配置一块更大空间,然后复制元素,再释放旧空间”这样的事情在deque身上是不会发生的。也因此,deque没有必须要提供所谓的空间保留(reserve)功能.

虽然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指针,其复杂度和vector不是一个量级,这当然影响各个运算的层面。因此,除非有必要,我们应该尽可能的使用vector,而不是deque。对deque进行的排序操作,为了最高效率,可将deque先完整的复制到一个vector中,对vector容器进行排序,再复制回deque.

实现原理

Deque容器是连续的空间,至少逻辑上看来如此,连续现行空间总是令我们联想到array和vector,array无法成长,vector虽可成长,却只能向尾端成长,而且其成长其实是一个假象,事实上(1) 申请更大空间 (2)原数据复制新空间 (3)释放原空间 三步骤,如果不是vector每次配置新的空间时都留有余裕,其成长假象所带来的代价是非常昂贵的。

Deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间,便配置一段连续定量的空间,串接在deque的头端或者尾端。Deque最大的工作就是维护这些分段连续的内存空间的整体性的假象,并提供随机存取的接口,避开了重新配置空间,复制,释放的轮回,代价就是复杂的迭代器架构。

既然deque是分段连续内存空间,那么就必须有中央控制,维持整体连续的假象,数据结构的设计及迭代器的前进后退操作颇为繁琐。Deque代码的实现远比vector或list都多得多。

Deque采取一块所谓的map(注意,不是STL的map容器)作为主控,这里所谓的map是一小块连续的内存空间,其中每一个元素(此处成为一个结点)都是一个指针,指向另一段连续性内存空间,称作缓冲区。缓冲区才是deque的存储空间的主体。

C++ STL第三篇(搞清楚deque原理和有多少用法)

声明方法

  1. 默认构造形式:使用默认构造函数创建一个空的deque容器。
deque<T> deqT;
deque<int> r1;//默认构造形式:创建一个空的deque容器
  1. 范围构造函数:使用指定范围内的元素创建deque容器,将[beg, end)区间中的元素拷贝给本身。
deque<T> deqT(beg, end);
int arr[] = { 1,2,3,4,5 };
deque<int> r2(arr, arr + 5);// 范围构造函数:将指定范围内的元素拷贝给本身

其中,beg是指向范围起始位置的迭代器,end是指向范围结束位置的迭代器。

  1. 值构造函数:使用指定值创建deque容器,将n个elem拷贝给本身。
deque<T> deqT(n, elem);
deque<int> r3(3, 100);// 创建包含3个值为10的元素的deque

其中,n是要创建的元素数量,elem是要拷贝的元素值。

  1. 拷贝构造函数:使用另一个deque容器进行拷贝构造,创建一个新的deque容器。
deque<T> deqT(deq);
deque<int> deq4(deq2);

其中,deq是要进行拷贝的deque容器。

赋值操作

  1. assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。

  2. assign(n, elem);//将n个elem拷贝赋值给本身。

  3. deque&operator=(const deque &deq); //重载等号操作符

  4. swap(deq);// 将deq与本身的元素互换

template <typename T>
void print(const T& r1, const T& r2){
	std::cout << "r1: ";
	for (const auto& elem : r1) {
		std::cout << elem << " ";
	}
	std::cout << std::endl;

	std::cout << "r2: ";
	for (const auto& elem : r2) {
		std::cout << elem << " ";
	}
	std::cout << std::endl;
	cout << "-------------" << endl;
}
deque<int> r1, r2;
deque<int> data = { 1,2,3,4,5 };
r1.assign(data.begin(), data.end());
print(r1, r2);
r2.assign(3, 100);
print(r1, r2);
r2 = r1;
print(r1, r2);
r1.swap(r2);
print(r1, r2);

C++ STL第三篇(搞清楚deque原理和有多少用法)

容量大小

deque.size();//返回容器中元素的个数

deque.empty();//判断容器是否为空

deque.resize(num);//重新指定容器的长度为num,若容器变长,则以默认值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。

deque.resize(num, elem); //重新指定容器的长度为num,若容器变长,则以elem值填充新位置,如果容器变短,则末尾超出容器长度的元素被删除。

	deque<int> r1, r2;
	deque<int> data = { 1,2,3,4,5 };
	r1.assign(data.begin(), data.end());
	cout << "r2.empty:" << r2.empty() << endl;
	print(r1, r2);
	r2.assign(3, 100);
	print(r1, r2);
	cout << "r1 size: " << r1.size() << endl;
	r1.resize(8);
	r2.resize(8, 100);
	print(r1, r2);

C++ STL第三篇(搞清楚deque原理和有多少用法)

插入和删除

push_back(elem);//在容器尾部添加一个数据

push_front(elem);//在容器头部插入一个数据

pop_back();//删除容器最后一个数据

pop_front();//删除容器第一个数据

at(idx);//返回索引idx所指的数据,如果idx越界,抛出out_of_range。

operator[];//返回索引idx所指的数据,如果idx越界,不抛出异常,直接出错。

front();//返回第一个数据。

back();//返回最后一个数据

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)区间的数据,返回下一个数据的位置。

erase(pos);//删除pos位置的数据,返回下一个数据的位置。insert 函数的参数 pos 实际上是一个迭代器(iterator)类型,而不是简单的整数类型
deque<int> r1;
r1.push_back(27);
print(r1);
r1.push_front(12);
print(r1);
// 返回索引idx所指的数据,如果idx越界,抛出out_of_range。
try {
	int v = r1.at(12);
	cout << "Value at index 12: " << v << std::endl;
	v = r1.at(127);
}
catch (const out_of_range& e) {
	cerr << "Out of range error: " << e.what() << std::endl;
}
// 返回索引idx所指的数据,如果idx越界,不抛出异常,直接出错。
int value = r1[1]; // 可能会直接出错,因为不会抛出异常

cout << "First value: " << r1.front() << std::endl;// 返回第一个数据
cout << "Last value: " << r1.back() << std::endl;// 返回最后一个数据

//在pos位置插入一个elem元素的拷贝,返回新数据的位置。
auto it = r1.insert(r1.begin() + 2, 99);
/*在代码中使用 auto 关键字的作用是让编译器根据等号右边表达式的类型推导出左边变量的类型,从而简化代码书写。
r1.insert(r1.begin() + 2, 99) 这个表达式的返回类型是一个迭代器(iterator),它指向插入的元素位置。
由于迭代器的类型可能很复杂且并非显式指定,因此可以使用 auto 让编译器自动推导出正确的类型。*/
// 在pos位置插入n个elem数据
r1.insert(r1.begin() + 2, 3, 88);
print(r1);
// 在pos位置插入[beg,end)区间的数据
deque<int> r2 = { 1,2,3 };
r1.insert(r1.begin() + 2, r2.begin(), r2.end());
r2 = r1;
print(r1);
r1.clear();
r1 = r2;
r1.erase(r1.begin() + 2, r1.begin() + 5);
print(r1);
r1.erase(r1.begin()+2);

C++ STL第三篇(搞清楚deque原理和有多少用法)文章来源地址https://www.toymoban.com/news/detail-840740.html

到了这里,关于C++ STL第三篇(搞清楚deque原理和有多少用法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++高级编程——STL:deque容器、stack容器和queue容器

    本专栏记录C++学习过程包括C++基础以及数据结构和算法,其中第一部分计划时间一个月,主要跟着黑马视频教程,学习路线如下, 不定时更新,欢迎关注 。 当前章节处于: ---------第1阶段-C++基础入门 ---------第2阶段实战-通讯录管理系统, ---------第3阶段-C++核心编程, -----

    2024年01月24日
    浏览(45)
  • 【C++】STL之适配器---用deque实现栈和队列

    目录 前言 一、deque  1、deque 的原理介绍  2、deque 的底层结构  3、deque 的迭代器  4、deque 的优缺点   4.1、优点   4.2、缺点 二、stack 的介绍和使用  1、stack 的介绍  2、stack 的使用  3、stack 的模拟实现 三、queue 的介绍和使用  1、queue 的介绍   2、queue 的使用  3、queue 的模

    2024年02月07日
    浏览(54)
  • 【C++】STL之容器适配器——使用deque适配stack和queue

    个人主页:🍝在肯德基吃麻辣烫 分享一句喜欢的话:热烈的火焰,冰封在最沉默的火山深处。 本文章主要介绍容器适配器的功能,以及一个适配的场景。 容器适配器,按字面意思理解的话,就是用来对一个容器进行匹配的。在C++STL中,容器有:vector,list,deque,map,set等。

    2024年02月16日
    浏览(56)
  • C++练级之初级:第三篇

    🤔首先我们先解决一下为什么C++支持函数重载,而C语言不支持? 这里就不得不提起编译链接了😁; 👉这是编译链接篇 以这三个简单的文件为例: 预处理阶段: 头文件的展开,条件编译,宏的替换,注释的删除等,最终处理完这些后test.c就会变成test.i,add.c就会变成add.i;

    2023年04月23日
    浏览(56)
  • 【C++】STL中stack,queue容器适配器的模拟实现(使用deque容器)

    🌏博客主页: 主页 🔖系列专栏: C++ ❤️感谢大家点赞👍收藏⭐评论✍️ 😍期待与大家一起进步! 虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和

    2024年02月15日
    浏览(53)
  • C++知识第三篇之继承

    继承是 面向对象编程 的重要特征,是对类设计层次的复用 1.继承定义 Parent :是父类,也称作基类(base class); Student :是子类,也称作派生类(derived class) public :表示继承方式为公共继承 2.继承方式 子类继承父类,有3种继承方式 继承方式的作用是: 对于父类非private的成员

    2024年02月06日
    浏览(71)
  • C++中deque的用法(超详细,入门必看)

    博主简介: Hello大家好呀,我是陈童学,一个与你一样正在慢慢前行的人。 博主主页: @陈童学哦 所属专栏: C++STL 如果本文对你有所帮助的话,希望可以点赞👍收藏📂支持一下哦! 期待你的关注,一起成长哟! 前言: Hello各位小伙伴们好!欢迎来到 本专栏C++STL 的学习,

    2024年02月07日
    浏览(33)
  • 第一百二十四天学习记录:C++提高:STL-deque容器(上)(黑马教学视频)

    功能: 双端数组,可以对头端进行插入删除操作 deque与vector区别 vector对于头部的插入删除效率低,数据量越大,效率越低 deque相对而言,对头部的插入删除速度比vector快 vector访问元素的速度会比deque快,这和两者内部实现有关 deque内部工作原理: deque内部有个中控器,维护

    2024年02月13日
    浏览(46)
  • 第一百二十五天学习记录:C++提高:STL-deque容器(下)(黑马教学视频)

    功能描述: 向deque容器中插入和删除数据 函数原型: 两端插入操作: 指定位置操作: 这里有个坑需要避一下,就是当重复执行d1.erase(it);后程序运行会崩溃。 崩溃的原因是在执行d1.erase(it)之后,迭代器it失效了,不能再继续使用。在C++的STL中,当执行erase操作后,如果要继续

    2024年02月13日
    浏览(45)
  • 从零开始c++精讲:第三篇——内存管理

    为什么要有内存区域的划分呢? 因为不同数据有不同的存储需求,各区域满足不同的需求。 栈(堆栈) :一般存放临时用的,比如非静态局部变量/函数参数/返回值等,栈是向下增长的。 堆 :有动态使用的需求,需要的时候你给我,不需要的时候你释放。也就是出了函数作

    2024年01月21日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包