C++系列-STL容器之deque

2024-08-30 07:20
文章标签 c++ 系列 容器 stl deque

本文主要是介绍C++系列-STL容器之deque，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

STL容器之deque

  • deque概括
    • deque与vector内存管理的区别
      • vector内存分配方式
      • deque内存分配方式
    • deque与vector随机访问效率的区别
    • deque与vector插入和删除操作的区别
    • deque与vector适用场景
  • deque的构造函数
    • deque的构造函数举例
  • deque的赋值操作
  • deque容器的大小操作
  • deque容器的插入和删除
    • 两端插入和删除
    • 指定位置
    • 删除操作
  • deque容器的数据存取
  • deque容器排序

deque概括

  • deque是一种序列容器。
  • deque维护双端数组，头尾都可以直接插入和删除操作。
    在这里插入图片描述

deque与vector内存管理的区别

vector内存分配方式

vector采用连续的线性内存空间，当需要增加容量时，通常会重新分配一块更大的连续内存空间，并将原有元素复制到新空间，然后释放旧空间。这可能会导致较高的时间开销，特别是当容器中元素数量较大时。

deque内存分配方式

  • deque有一系列固定大小的块组成，这些块可以在不连续的内存空间中，deque这些固定大小的块称为缓冲区。
  • 在两端进行插入或删除操作时，deque可以更高效的管理内存，不像vector那样进行大量的元素移动。
  • 为了有效的管理这些缓冲区，deque使用中控器(通常是指针数组)的结构，中控器记录每个缓冲器的地址和大小，以及deque的当前size和capacity。
  • 当在deque的两端插入操作时，如果当前的存储块还有足够的空间，新元素就会被插入到相应的空间，否则，deque会分配一个新的缓冲区，并将其添加到合适的位置。
  • 当deque在中间进行插入或删除操作时，deuqe调整涉及到的缓冲区中的元素，并可能需要重新分配或释放一些存储块。
    在这里插入图片描述

deque与vector随机访问效率的区别

  • vector支持高效的随机访问。
  • 也支持随机访问，但是由于其内部结构的复杂性，随机访问的效率略低于vector。

deque与vector插入和删除操作的区别

  • vector在尾部插入和删除操作通常是高效的。但在头部或中部插入和删除操作需要移动大量元素。
  • 在两端插入和删除数据都非常高效。在中间插入和删除的效率相对较低，但是比vertor在中间进行插入和删除的操作要快。

deque与vector适用场景

  • vector适用于需要高效的随机访问和在尾部进行频繁插入和删除的场景。例如，存储一组整数并进行频繁的遍历和在尾部添加元素。
  • deque适用于在两端进行高效插入和删除的场景，例如，实现一个队列或栈结构。或者在容器的两端进行频繁的插入和删除操作。

deque的构造函数

  • 默认构造函数，创建一个新的deque。
deque<T> d1;
  • 拷贝构造函数，从一个deque对象创建一个副本。
deque<T> d2(const vector<T> &d1);
  • 使用迭代器范围构造函数，从两个迭代器指定的范围创建deque。
deque<T> d2(obj.begin(), obj.end());
  • 将n个elem拷贝给deque
deque<T> d1(n, elem);

deque的构造函数举例

code:
#include <iostream>
#include <deque>
using namespace std;void print_deque(const deque<int>& deq)		// 如果这里传参为const &，下面的迭代器也要用const_iterator
{for (deque<int>::const_iterator it = deq.begin(); it < deq.end(); it++){cout << *it << " ";}cout << endl;
}void test01()
{int num = 0;deque<int> d1;			// 默认构造函数d1.push_front(11);d1.push_front(22);d1.push_front(33);cout << "---------- 默认构造函数举例 ----------" << endl;print_deque(d1);d1.push_back(666);deque<int> d2(d1);			// 拷贝构造函数cout << "---------- 拷贝构造函数举例 ----------" << endl;print_deque(d2);deque<int>d3(10, 888);		// n个elem初始化举例cout << "---------- n个elem初始化构造函数举例 ----------" << endl;print_deque(d3);deque<int>d4{1, 2, 3, 4, 5, 6, 7, 8, 9};	// 花括号初始化cout << "---------- 花括号初始化构造函数举例 ----------" << endl;print_deque(d4);deque<int>d5(d4.begin(), d4.end()-3);cout << "---------- 迭代器范围初始化构造函数举例 ----------" << endl;print_deque(d5);
}
int main()
{test01();system("pause");return 0;
}result:
---------- 默认构造函数举例 ----------
33 22 11
---------- 拷贝构造函数举例 ----------
33 22 11 666
---------- n个elem初始化构造函数举例 ----------
888 888 888 888 888 888 888 888 888 888
---------- 花括号初始化构造函数举例 ----------
1 2 3 4 5 6 7 8 9
---------- 迭代器范围初始化构造函数举例 ----------
1 2 3 4 5 6

deque的赋值操作

  • = 赋值，函数原型 deque& operator=(const deque&vec), 重载等号运算符。
  • deq1.assign(beg迭代器，end迭代器), 将[beg迭代器，end迭代器) 之间的数据拷贝给被赋值的对象。
  • deq1.assign(n，elem), 将n个elem的数据拷贝给被赋值的对象。
code:
#include <iostream>
#include <deque>
using namespace std;void print_deque(const deque<int>& deq)		// 如果这里传参为const &，下面的迭代器也要用const_iterator
{for (deque<int>::const_iterator it = deq.begin(); it < deq.end(); it++){cout << *it << " ";}cout << endl;
}void test01()
{int num = 0;deque<int> d1;			// 默认构造函数d1.push_front(11);d1.push_front(22);d1.push_front(33);cout << "---------- =赋值 ----------" << endl;deque<int> d2 = d1;print_deque(d2);deque<int> d3;cout << "---------- deq.assign(n, elem)赋值 ----------" << endl;d3.assign(5, 555);print_deque(d3);deque<int> d4;d3.push_back(666);cout << "---------- deq.assign(deq)赋值 ----------" << endl;d4.assign(d3.begin(), d3.end());print_deque(d4);
}
int main()
{test01();system("pause");return 0;
}result:
---------- =赋值 ----------
33 22 11
---------- deq.assign(n, elem)赋值 ----------
555 555 555 555 555
---------- deq.assign(deq)赋值 ----------
555 555 555 555 555 666

deque容器的大小操作

  • 没有capacity，因为它的容量是动态的，随时扩展。
    | 函数原型 | 用途 |
    |:--------😐 :-------------|
    |empty()| 判断容器是否为空|
    |size() | 返回容器中元素的个数|
    |resize(int num) | 重新指定容器的长度(size)为num，若容器变长，则以默认数值填充新位置，如果容器变短，则末尾超出容器长度的元素被删除|
    |resize(int num，elem) | 重新指定容器的长度(size)为num，若容器变长，则以elem填充新位置，如果容器变短，则末尾超出容器长度的元素被删除|
code:#include <iostream>
#include <deque>
using namespace std;void print_deque(const deque<int>& deq)		// 如果这里传参为const &，下面的迭代器也要用const_iterator
{for (deque<int>::const_iterator it = deq.begin(); it < deq.end(); it++){cout << *it << " ";}cout << endl;
}void test01()
{int num = 0;deque<int> d1;d1.push_front(11);d1.push_front(22);d1.push_front(33);deque<int> d2;if (!d1.empty()){cout << "d1 is not empty" << endl;cout << "d1 size: " << d1.size() << endl;}if (d2.empty())		// 判断容器是否为空{cout << "d2 is empty" << endl;}deque<int> d3 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};	// 花括号初始化cout << "---------- d3 ----------" << endl;print_deque(d3);cout << "d3 size: " << d3.size() << endl;d3.resize(12);		// resize，默认填充0cout << "---------- d3.resize(12) ----------" << endl;print_deque(d3);cout << "d3 size: " << d3.size() << endl;d3.resize(15, 666);	// resize，填充指定数据cout << "---------- d3.resize(15, 666) ----------" << endl;print_deque(d3);cout << "d3 size: " << d3.size() << endl;d3.resize(5);		// resize，长度截短cout << "---------- d3.resize(5) ----------" << endl;print_deque(d3);cout << "d3 size: " << d3.size() << endl;
}
int main()
{test01();system("pause");return 0;
}result:
d1 is not empty
d1 size: 3
d2 is empty
---------- d3 ----------
0 1 2 3 4 5 6 7 8 9
d3 size: 10
---------- d3.resize(12) ----------
0 1 2 3 4 5 6 7 8 9 0 0
d3 size: 12
---------- d3.resize(15, 666) ----------
0 1 2 3 4 5 6 7 8 9 0 0 666 666 666
d3 size: 15
---------- d3.resize(5) ----------
0 1 2 3 4
d3 size: 5

deque容器的插入和删除

两端插入和删除

函数原型用途
push_back(elem)尾部插入元素elem
push_front(elem)头部插入元素elem
pop_back()删除尾部元素
pop_front(elem)删除头部元素
code:
#include <iostream>
#include <deque>
using namespace std;void print_deque(const deque<int>& deq)		// 如果这里传参为const &，下面的迭代器也要用const_iterator
{for (deque<int>::const_iterator it = deq.begin(); it < deq.end(); it++){cout << *it << " ";}cout << endl;
}void test01()
{int num = 0;deque<int> d1{0,1,2,3,4,5};d1.push_front(111);d1.push_back(222);cout << "---------- push front and push back ----------" << endl;print_deque(d1);d1.pop_back();cout << "---------- d1.pop_back() ----------" << endl;print_deque(d1);d1.pop_front();cout << "---------- d1.pop_front() ----------" << endl;print_deque(d1);
}
int main()
{test01();system("pause");return 0;
}result:
---------- push front and push back ----------
111 0 1 2 3 4 5 222
---------- pop_back ----------
111 0 1 2 3 4 5
---------- pop_front ----------
0 1 2 3 4 5

指定位置

函数原型用途
insert(const_iterator pos, elem)迭代器指向位置pos插入元素elem，返回新数据的位置，iterator类型
insert(const_iterator pos, int count, elem)迭代器指向位置pos插入count元素elem，返回的是插入的最后一个元素的位置，iterator类型
insert(const_iterator pos, iterator pos begin, iterator pos end)迭代器指向位置pos插入迭代器begin到迭代器end范围内的数据，返回插入的最后一个元素的位置，iterator
erase(const_iterator pos)删除迭代器指向的元素，返回下一个元素的位置
erase(const_iterator start, const_iterator end)删除迭代器从[start, end)之间的元素，包头不包尾，返回下一个元素的位置
clear()删除容器中所有元素，返回下一个元素的位置

关于insert的例子

code:
#include <iostream>
#include <deque>
using namespace std;void print_deque(const deque<int>& deq)		// 如果这里传参为const &，下面的迭代器也要用const_iterator
{for (deque<int>::const_iterator it = deq.begin(); it < deq.end(); it++){cout << *it << " ";}cout << endl;
}void test01()
{int num = 0;deque<int> d1{0,1,2,3,4,5};cout << "---------- d1 ----------" << endl;print_deque(d1);// insert(const_iterator pos, elem)deque<int>::iterator it = d1.insert(d1.begin(), 111);	// 返回插入的数据对应的位置cout << "---------- d1.insert(d1.begin(), 111) ----------" << endl;print_deque(d1);cout << "d1.insert(d1.begin(), 111)返回的iter指示的内容: " << * it << endl;// insert(const_iterator pos, int count, elem)it = d1.insert(d1.begin(), 3, 333);		// 在pos处插入count个elemcout << "---------- d1.insert(d1.begin(), 3, 333) ----------" << endl;print_deque(d1);cout << "*it(it是d1.insert(d1.begin(), 3, 333)的返回值): " << *it << endl;// 判断返回值指向的位置d1.insert(it, 666);cout << "---------- d1.insert(it, 666)，it是d1.insert(d1.begin(), 3, 333)的返回值 ----------" << endl;print_deque(d1);// insert(const_iterator pos, iterator pos begin, iterator pos end)deque<int> d2 {11, 22, 33};cout << "---------- d2 ----------" << endl;print_deque(d2);it = d2.insert(d2.begin(), d1.begin()+6, d1.end());cout << "---------- d2.insert(d2.begin(), d1.begin()+6, d1.end()) ----------" << endl;print_deque(d2);cout << "*it(it是d2.insert(d2.begin(), d1.begin()+6, d1.end()): " << *it << endl;
}
int main()
{test01();system("pause");return 0;
}result:
---------- d1 ----------
0 1 2 3 4 5
---------- d1.insert(d1.begin(), 111) ----------
111 0 1 2 3 4 5
d1.insert(d1.begin(), 111)返回的iter指示的内容: 111
---------- d1.insert(d1.begin(), 3, 333) ----------
333 333 333 111 0 1 2 3 4 5
*it(it是d1.insert(d1.begin(), 3, 333)的返回值): 333
---------- d1.insert(it, 666)，it是d1.insert(d1.begin(), 3, 333)的返回值 ----------
666 333 333 333 111 0 1 2 3 4 5
---------- d2 ----------
11 22 33
---------- d2.insert(d2.begin(), d1.begin()+6, d1.end()) ----------
1 2 3 4 5 11 22 33
*it(it是d2.insert(d2.begin(), d1.begin()+6, d1.end()): 1

删除操作

code:
#include <iostream>
#include <deque>
using namespace std;void print_deque(const deque<int>& deq)		// 如果这里传参为const &，下面的迭代器也要用const_iterator
{for (deque<int>::const_iterator it = deq.begin(); it < deq.end(); it++){cout << *it << " ";}cout << endl;
}void test01()
{int num = 0;deque<int> d1{0, 1, 2, 3, 4, 5};cout << "---------- d1 ----------" << endl;print_deque(d1);deque<int>::iterator it = d1.erase(d1.begin() + 2);		// 删除d1.begin()+2处的元素，it返回begin()+3处的元素cout << "---------- d1.erase(it)(it = d1.begin() + 2) ----------" << endl;print_deque(d1);cout << "*it(d1.erase(d1.begin() + 2)的返回值): " << *it << endl;it = d1.erase(d1.begin(), d1.begin() + 2);		// 删除[d1.begin(), d1.begin() + 2)前闭后开区间的元素，it返回begin()+2处的元素cout << "---------- d1.erase(d1.begin(), d1.begin() + 2) ----------" << endl;print_deque(d1);cout << "*it(it是d1.erase(d1.begin(), d1.begin() + 2)的返回值): " << *it << endl;d1.clear();cout << "---------- d1.clear() ----------" << endl;print_deque(d1);	cout << "d1 size: " << d1.size() << endl;
}
int main()
{test01();system("pause");return 0;
}result:
---------- d1 ----------
0 1 2 3 4 5
---------- d1.erase(it)(it = d1.begin() + 2) ----------
0 1 3 4 5
*it(d1.erase(d1.begin() + 2)的返回值): 3
---------- d1.erase(d1.begin(), d1.begin() + 2) ----------
3 4 5
*it(it是d1.erase(d1.begin(), d1.begin() + 2)的返回值): 3
---------- d1.clear() ----------d1 size: 0

deque容器的数据存取

函数原型用途
deq.at(int idx)返回索引idx所指的元素
deq[idx]返回索引idx所指的元素
deq.front()返回容器中的第一个元素
deq.back()返回容器中的最后一个元素
code:
#include <iostream>
#include <deque>
using namespace std;void print_square(const deque<int> &deq)
{for (int i_loop = 0; i_loop < deq.size(); i_loop++){cout << deq[i_loop] << " ";}cout << endl;
}void print_at(const deque<int>& deq)
{for (int i_loop = 0; i_loop < deq.size(); i_loop++){cout << deq.at(i_loop) << " ";}cout << endl;
}void test01()
{int num = 0;deque<int> d1{0, 1, 2, 3, 4, 5};cout << "---------- print_square ----------" << endl;print_square(d1);cout << "---------- print_at ----------" << endl;print_at(d1);cout << "---------- deq.front() ----------" << endl;cout << d1.front() << endl;cout << "---------- deq.back() ----------" << endl;cout << d1.back() << endl;
}
int main()
{test01();system("pause");return 0;
}result:
---------- print_square ----------
0 1 2 3 4 5
---------- print_at ----------
0 1 2 3 4 5
---------- deq.front() ----------
0
---------- deq.back() ----------
5

deque容器排序

  • sort(iterator begin, iterator end)可以对容器进行排序。
  • 默认升序排序，支持随机访问的迭代器的容器，都可用sort排序。
  • 要#include 
code:
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;void print_deque(const deque<int>& deq)
{for (deque<int>::const_iterator it = deq.begin(); it < deq.end(); it++){cout << *it << " ";}cout << endl;
}void test01()
{int num = 0;deque<int> d1{10, 55, 24, 79, 36, 5};cout << "---------- d1 ----------" << endl;print_deque(d1);cout << "---------- sort(d1.begin(), d1.end()) ----------" << endl;sort(d1.begin(), d1.end());		// d1会被排序，默认升序排序，支持随机访问的迭代器的容器，都可用sort排序print_deque(d1);
}
int main()
{test01();system("pause");return 0;
}result:
---------- d1 ----------
10 55 24 79 36 5
---------- sort(d1.begin(), d1.end()) ----------
5 10 24 36 55 79

这篇关于C++系列-STL容器之deque的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/1120162。

相关文章

c++日志库log4cplus快速入门小结

c++日志库log4cplus快速入门小结

《c++日志库log4cplus快速入门小结》文章浏览阅读1.1w次，点赞9次，收藏44次。本文介绍Log4cplus，一种适用于C++的线程安全日志记录API，提供灵活的日志管理和配置控制。文章涵盖... 目录简介日志等级配置文件使用关于初始化使用示例总结参考资料简介log4j 用于Java，log4c
阅读更多...
C++归并排序代码实现示例代码

C++归并排序代码实现示例代码

《C++归并排序代码实现示例代码》归并排序将待排序数组分成两个子数组,分别对这两个子数组进行排序,然后将排序好的子数组合并,得到排序后的数组,：本文主要介绍C++归并排序代码实现的相关资料,需要的... 目录1 算法核心思想2 代码实现3 算法时间复杂度1 算法核心思想归并排序是一种高效的排序方式，需要用
阅读更多...
C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...
C++中detach的作用、使用场景及注意事项

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()？它的作用是什么？类比一下：二、join()的作用总结三、join()怎么
阅读更多...
C++中全局变量和局部变量的区别

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域
阅读更多...
C++中assign函数的使用

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)
阅读更多...
SpringBoot结合Docker进行容器化处理指南

SpringBoot结合Docker进行容器化处理指南

《SpringBoot结合Docker进行容器化处理指南》在当今快速发展的软件工程领域,SpringBoot和Docker已经成为现代Java开发者的必备工具,本文将深入讲解如何将一个SpringBo... 目录前言一、为什么选择 Spring Bootjavascript + docker1. 快速部署与
阅读更多...
c++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
C++中NULL与nullptr的区别小结

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2