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。

相关文章

Windows下C++使用SQLitede的操作过程

Windows下C++使用SQLitede的操作过程

《Windows下C++使用SQLitede的操作过程》本文介绍了Windows下C++使用SQLite的安装配置、CppSQLite库封装优势、核心功能（如数据库连接、事务管理）、跨平台支持及性能优... 目录Windows下C++使用SQLite1、安装2、代码示例CppSQLite：C++轻松操作SQ
阅读更多...
C++中RAII资源获取即初始化

C++中RAII资源获取即初始化

《C++中RAII资源获取即初始化》RAII通过构造/析构自动管理资源生命周期,确保安全释放,本文就来介绍一下C++中的RAII技术及其应用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、核心原理与机制二、标准库中的RAII实现三、自定义RAII类设计原则四、常见应用场景1. 内存管理2. 文件操
阅读更多...
C++中零拷贝的多种实现方式

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri
阅读更多...
C++高效内存池实现减少动态分配开销的解决方案

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现：TCMalloc与Jemalloc1. TCM
阅读更多...
C++ 函数 strftime 和时间格式示例详解

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五
阅读更多...
C++作用域和标识符查找规则详解

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域（Scope）和标识符查找（IdentifierLookup）是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找（Ordinary Lookup）2. 限定查找（Qualif
阅读更多...
C/C++ chrono简单使用场景示例详解

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》：本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示
阅读更多...
C++/类与对象/默认成员函数@构造函数的用法

C++/类与对象/默认成员函数@构造函数的用法

《C++/类与对象/默认成员函数@构造函数的用法》：本文主要介绍C++/类与对象/默认成员函数@构造函数的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录名词概念默认成员函数构造函数概念函数特征显示构造函数隐式构造函数总结名词概念默认构造函数：不用传参就可以
阅读更多...
C++类和对象之默认成员函数的使用解读

C++类和对象之默认成员函数的使用解读

《C++类和对象之默认成员函数的使用解读》：本文主要介绍C++类和对象之默认成员函数的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、默认成员函数有哪些二、各默认成员函数详解默认构造函数析构函数拷贝构造函数拷贝赋值运算符三、默认成员函数的注意事项总结一
阅读更多...
C/C++中OpenCV 矩阵运算的实现

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算（标量与矩阵）、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2