本文主要是介绍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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
