纵有疾风起,人生不言弃。本文篇幅较长,如有错误请不吝赐教,感谢支持。
一.deque容器的基本概念
vector容器是单向开口的连续内存空间,deque(['dek])则是一种双向开口的连续线性空间。所谓的双向开口,意思是可以在头尾两端分别做元素的插入和删除操作,可以理解为数据结构的双端队列。当然,vector容器也可以在头尾两端插入元素,但是在其头部操作效率奇差,全部元素都要后移,无法被接受。
✅deque容器和vector容器的差异:
- ①deque是双端队列,可在容器的头部和尾部插入或删除元素。
- ②deque没有容量的概念,因为它是动态的以分段连续空间组合而成,随时可以增加一段新的空间并链接起来,换句话说,deque不会像vector那样,”旧空间不足而重新配置一块更大空间,然后复制元素,再释放旧空间”这样的事情在deque身上是不会发生的。deque可以随时将空间串接在首部或尾部,也因此,deque没有必须要提供所谓的空间保留(reserve)功能。
✅deque容器内部实现原理:
deque容器在逻辑上是一片连续的空间,但这只是一种假象,实际deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间,便配置一段连续定量的空间,串接在deque的头端或者尾端。deque最大的工作就是维护这些分段连续的内存空间的整体性的假象,并提供随机存取的接口,避开了(1)重新配置空间申请更大空间 (2)原数据复制新空间 (3)释放原空间三步骤,代价就是复杂的迭代器架构。
既然deque是分段连续内存空间,那么就必须有中央控制,维持整体连续的假象。deque内部存在中央控制器,记录与维护每段数据缓冲区(存储数据的空间)的内存地址,缓冲区中存储真实数据,保证可从容器的头部与尾部插入或删除元素。缓冲区才是deque的存储空间主体。
deque容器的迭代器:
支持随机访问的迭代器,可跳跃式访问容器元素。
二.deque容器常用操作
①deque构造函数
作用:创建deque容器。
注:使用deque容器时,需包含头文件#include <deque>
函数原型 | 解释 |
---|---|
deque<T> deq T; |
默认构造形式(显示实例化) |
deque(beg, end); | 构造函数将[beg, end)区间中的元素拷贝给本身。 |
deque(n, elem); | 有参构造函数,使用n个elem元素进行初始化。 |
deque(const deque &deq); | 拷贝构造函数,使用已有deque对象初始化新的对象。 |
实例:deque构造函数
#include <iostream>
using namespace std;
#include <deque>//包含头文件
void printdeque(const deque<int>& deq)//形参使用const,避免被修改
{ //const_iterator只读迭代器
for (deque<int>::const_iterator it = deq.begin(); it != deq.end(); ++it)
{
cout << *it<<"|";
}
cout << endl;
}
void test()
{
deque<int> v1 = { 1,2,3 };//采用模板实现类实现(显示实例化),默认构造函数,
deque<int> v2(6, 1);//构造函数将n个elem拷贝给本身。
int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
deque<int> v3(arr, arr + sizeof(arr) / sizeof(arr[0]));//将v[begin(), end())区间中的元素拷贝给本身
deque<int> v4(v1);//拷贝构造函数,拿另一个vector对象初始化本身
printdeque(v1);
printdeque(v2);
printdeque(v3);
printdeque(v4);
}
int main()
{
test();
return 0;
}
②deque元素操作
作用:通过重载赋值运算符operator[]和成员函数at(int index),对deque容器的单个元素进行读(作为右值)或写(作为左值)。
函数原型 | 解释 |
---|---|
T &operator[](size_t n); | 通过[]访问元素,如果越界,不抛异常,程序直接挂掉 |
T &at(size_t n); | 通过at方法获取下标为n的元素,如果n越界,抛出out_of_range异常。 |
T *data(); | 返回容器中动态数组的首地址。 |
const T *data() const; | 返回容器中动态数组的首地址。 |
T &front(); | 返回第一个元素。 |
T &back(); | 返回,最后一个元素。 |
③deque赋值操作
作用:通过重载赋值运算符operator=和成员函数assign(),对deque容器进行赋值。
函数原型 | 解释 |
---|---|
assign(beg, end); | 拷贝目标deque容器中[begin(), end())区间的元素,对当前deque容器赋值。 |
assign(n, elem); | 将n个elem拷贝赋值给本身。 |
deque&operator=(const deque &deq); | 重载等号操作符 |
swap(deq); | 将deq与本身的元素互换 |
实例:deque赋值操作
#include <iostream>
using namespace std;
#include <deque>//包含头文件
void printdeque(const deque<int>& deq)//形参使用const,避免被修改
{ //const_iterator只读迭代器
for (deque<int>::const_iterator it = deq.begin(); it != deq.end(); ++it)
{
cout << *it<<"|";
}
cout << endl;
}
void test()
{
deque<int> deq;
//尾插法插入元素
for (int i = 0; i < 5; i++) {
deq.push_back(i);
}
//遍历
printdeque(deq); //0 1 2 3 4
/* 1.重载运算符=赋值 */
deque<int> d1;
d1 = deq;
printdeque(d1); //0 1 2 3 4
/* 2.assign()函数,区间拷贝 */
deque<int> d2;
d2.assign(deq.begin(), deq.end());
printdeque(d2); //0 1 2 3 4
/* 3.assign()函数,n个elem元素赋值 */
deque<int> d3;
//5个整型元素6
d3.assign(5, 6);
printdeque(d3); //6 6 6 6 6
}
int main()
{
test();
return 0;
}
④deque交换操作
💬表格一览:
函数原型 | 解释 |
---|---|
void swap(deque &deq); | 把当前容器与deq交换。 |
实例:deque交换操作
#include <iostream>
using namespace std;
#include <deque>//包含头文件
void printdeque(const deque<int>& deq)//形参使用const,避免被修改
{ //const_iterator只读迭代器
for (deque<int>::const_iterator it = deq.begin(); it != deq.end(); ++it)
{
cout << *it<<"|";
}
cout << endl;
}
void test()
{
deque<int> deq;
//尾插法插入元素
for (int i = 0; i < 5; i++) {
deq.push_back(i);
}
//遍历
printdeque(deq); //0 1 2 3 4
deque<int> d1;
d1.swap(deq);//将deq与本身的元素互换
printdeque(d1);
}
int main()
{
test();
return 0;
}
⑤deque大小操作
作用:操作deque容器的大小(即元素个数)。
函数原型 | 解释 |
---|---|
bool empty() const; | 判断容器是否为空。 |
size_t size() const; | 返回容器的实际大小(已使用的空间)。 |
resize(int num); | 重新指定容器的长度为num。若容器变长,则以默认值0填充新位置;若容器变短,则容器末尾超出新长度的元素被删除。 |
resize(int num, elem); | 重新指定容器的长度为num。若容器变长,则以指定值elem填充新位置;若容器变短,则容器末尾超出新长度的元素被删除。 |
实例:deque大小操作
#include <iostream>
using namespace std;
#include <deque>//包含头文件
void printdeque(const deque<int>& deq)//形参使用const,避免被修改
{ //const_iterator只读迭代器
for (deque<int>::const_iterator it = deq.begin(); it != deq.end(); ++it)
{
cout << *it<<"|";
}
cout << endl;
}
void test()
{
deque<int> deq;
//尾插法插入元素
for (int i = 0; i < 5; i++) {
deq.push_back(i);
}
printdeque(deq); //0 1 2 3 4
//empty():判断容器是否为空
cout << (deq.empty() ? "deq为空" : "deq不为空") << endl; //deq不为空
//size(); :获取容器的大小,即元素个数。
cout << "deq的大小/元素个数:" << deq.size() << endl; //5
//resize(int num);:重新指定容器的长度为num
//若容器变长,则以默认值0填充新位置;若容器变短,则容器末尾超出新长度的元素被删除。
deq.resize(10); //长度变大时,使用默认值0填充
printdeque(deq); //0 1 2 3 4 0 0 0 0 0
deq.resize(3); //长度变小时,容器末尾超出新长度的元素被删除
printdeque(deq); //0 1 2
//resize(int num, elem); :重新指定容器的长度为num。
//若容器变长,则以指定值elem填充新位置;若容器变短,则容器末尾超出新长度的元素被删除。
deq.resize(8, 6); //长度变大时,使用指定值6填充
printdeque(deq); //0 1 2 6 6 6 6 6
}
int main()
{
test();
return 0;
}
注:deque容器不存在容量的概念,即不存在capacity()成员函数。可随时开辟缓冲区存储数据。
⑥deque插入和删除
💬表格一览:
函数原型 | 解释 |
---|---|
iterator insert(iterator pos, const T& ele); | 在指定位置插入一个元素ele 返回指向插入元素的迭代器。 |
iterator insert(const_iterator pos, int count,ele); | 迭代器指向位置pos插入count个元素ele.返回指向插入元素的迭代器。 |
void push_front(const T& ele); | 在容器头部插入一个数据 |
void push_back(const T& ele); | 尾部插入元素ele |
void pop_front(); | 删除容器第一个数据 |
void pop_back(); | 删除最后一个元素 |
void clear(); | 清空容器。 |
iterator erase(const_iterator start, const_iterator end); | 删除迭代器从start到end之间的元素,返回下一个有效的迭代器。 |
iterator erase(const_iterator pos); | 删除迭代器指向的元素,返回下一个有效的迭代器。 |
实例:deque插入和删除文章来源:https://www.toymoban.com/news/detail-653437.html
#include <iostream>
using namespace std;
#include <deque>//包含头文件
void printdeque(const deque<int>& deq)//形参使用const,避免被修改
{ //const_iterator只读迭代器
for (deque<int>::const_iterator it = deq.begin(); it != deq.end(); ++it)
{
cout << *it<<"|";
}
cout << endl;
}
void test()
{
deque<int> v;
for (int i = 0; i < 5; i++)
{
v.push_back(i + 1);//尾部插入元素
}
printdeque(v);//1 2 3 4 5
v.insert(v.begin() + 1, 2, 100);//在第二个元素插入2个100
printdeque(v);//1 100 100 2 3 4 5
v.pop_front();//头部删除一个元素
v.pop_back();//尾部删除一个元素
printdeque(v);//100 100 2 3 4
cout << "-------------" << endl;
v.erase(v.begin());//删除第一个元素
printdeque(v);//100 2 3 4
deque<int>::const_iterator it = v.erase(v.begin() + 1, v.end() - 1);//删除从第二个元素到倒数第二个元素,返回下一个有效迭代器
printdeque(v);//100 4
v.insert(it, 66);
printdeque(v);//100 66 4
v.clear();//清空容器
}
int main()
{
test();
return 0;
}
文章来源地址https://www.toymoban.com/news/detail-653437.html
到了这里,关于C++STL——deque容器详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!