第 18.5 節
deque 容器
0瀏覽次數0訪問次數--跳出率--平均停留
deque容器
deque容器基本概念
功能：
- 雙端數組，可以對頭端進行插入刪除操作
deque與vector區別：
- vector對於頭部的插入刪除效率低，數據量越大，效率越低
- deque相對而言，對頭部的插入刪除速度回比vector快
- vector訪問元素時的速度會比deque快,這和兩者內部實現有關
deque內部工作原理:
deque內部有個中控器，維護每段緩衝區中的內容，緩衝區中存放真實數據
中控器維護的是每個緩衝區的地址，使得使用deque時像一片連續的內存空間
- deque容器的迭代器也是支持隨機訪問的
deque構造函數
功能描述：
- deque容器構造
函數原型：
deque<T>deqT; //默認構造形式deque(beg, end);//構造函數將[beg, end)區間中的元素拷貝給本身。deque(n, elem);//構造函數將n個elem拷貝給本身。deque(const deque &deq);//拷貝構造函數
示例：
#include <iostream>
#include <deque>
using namespace std;
void printDeque(const deque<int>& d)
{
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
//deque构造
void test01() {
deque<int> d1; //无参构造函数
for (int i = 0; i < 10; i++)
{
d1.push_back(i);
}
printDeque(d1);
deque<int> d2(d1.begin(),d1.end());
printDeque(d2);
deque<int>d3(10,100);
printDeque(d3);
deque<int>d4 = d3;
printDeque(d4);
}
int main() {
test01();
return 0;
}
運行結果：
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
**總結：**deque容器和vector容器的構造方式幾乎一致，靈活使用即可
deque賦值操作
功能描述：
- 給deque容器進行賦值
函數原型：
deque& operator=(const deque &deq);//重載等號操作符assign(beg, end);//將[beg, end)區間中的數據拷貝賦值給本身。assign(n, elem);//將n個elem拷貝賦值給本身。
示例：
#include <iostream>
#include <deque>
using namespace std;
void printDeque(const deque<int>& d)
{
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
//赋值操作
void test01()
{
deque<int> d1;
for (int i = 0; i < 10; i++)
{
d1.push_back(i);
}
printDeque(d1);
deque<int>d2;
d2 = d1;
printDeque(d2);
deque<int>d3;
d3.assign(d1.begin(), d1.end());
printDeque(d3);
deque<int>d4;
d4.assign(10, 100);
printDeque(d4);
}
int main() {
test01();
return 0;
}
運行結果：
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
100 100 100 100 100 100 100 100 100 100
總結：deque賦值操作也與vector相同，需熟練掌握
deque大小操作
功能描述：
- 對deque容器的大小進行操作
函數原型：
deque.empty();//判斷容器是否為空deque.size();//返回容器中元素的個數deque.resize(num);//重新指定容器的長度為num,若容器變長，則以默認值填充新位置。
//如果容器變短，則末尾超出容器長度的元素被刪除。deque.resize(num, elem);//重新指定容器的長度為num,若容器變長，則以elem值填充新位置。
//如果容器變短，則末尾超出容器長度的元素被刪除。
示例：
#include <iostream>
#include <deque>
using namespace std;
void printDeque(const deque<int>& d)
{
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
//大小操作
void test01()
{
deque<int> d1;
for (int i = 0; i < 10; i++)
{
d1.push_back(i);
}
printDeque(d1);
//判断容器是否为空
if (d1.empty()) {
cout << "d1为空!" << endl;
}
else {
cout << "d1不为空!" << endl;
//统计大小
cout << "d1的大小为：" << d1.size() << endl;
}
//重新指定大小
d1.resize(15, 1);
printDeque(d1);
d1.resize(5);
printDeque(d1);
}
int main() {
test01();
return 0;
}
運行結果：
0 1 2 3 4 5 6 7 8 9
d1不为空!
d1的大小为：10
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1
0 1 2 3 4
總結：
- deque沒有容量的概念
- 判斷是否為空 --- empty
- 返回元素個數 --- size
- 重新指定個數 --- resize
deque 插入和刪除
功能描述：
- 向deque容器中插入和刪除數據
函數原型：
兩端插入操作：
push_back(elem);//在容器尾部添加一個數據push_front(elem);//在容器頭部插入一個數據pop_back();//刪除容器最後一個數據pop_front();//刪除容器第一個數據
指定位置操作：
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位置的數據，返回下一個數據的位置。
示例：
#include <iostream>
#include <deque>
using namespace std;
void printDeque(const deque<int>& d)
{
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
//两端操作
void test01()
{
deque<int> d;
//尾插
d.push_back(10);
d.push_back(20);
//头插
d.push_front(100);
d.push_front(200);
printDeque(d);
//尾删
d.pop_back();
//头删
d.pop_front();
printDeque(d);
}
//插入
void test02()
{
deque<int> d;
d.push_back(10);
d.push_back(20);
d.push_front(100);
d.push_front(200);
printDeque(d);
d.insert(d.begin(), 1000);
printDeque(d);
d.insert(d.begin(), 2,10000);
printDeque(d);
deque<int>d2;
d2.push_back(1);
d2.push_back(2);
d2.push_back(3);
d.insert(d.begin(), d2.begin(), d2.end());
printDeque(d);
}
//删除
void test03()
{
deque<int> d;
d.push_back(10);
d.push_back(20);
d.push_front(100);
d.push_front(200);
printDeque(d);
d.erase(d.begin());
printDeque(d);
d.erase(d.begin(), d.end());
d.clear();
printDeque(d);
}
int main() {
//test01();
//test02();
test03();
return 0;
}
運行結果：
200 100 10 20
100 10 20
總結：
- 插入和刪除提供的位置是迭代器！
- 尾插 --- push_back
- 尾刪 --- pop_back
- 頭插 --- push_front
- 頭刪 --- pop_front
deque 數據存取
功能描述：
- 對deque 中的數據的存取操作
函數原型：
at(int idx);//返回索引idx所指的數據operator[];//返回索引idx所指的數據front();//返回容器中第一個數據元素back();//返回容器中最後一個數據元素
示例：
#include <iostream>
#include <deque>
using namespace std;
void printDeque(const deque<int>& d)
{
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
//数据存取
void test01()
{
deque<int> d;
d.push_back(10);
d.push_back(20);
d.push_front(100);
d.push_front(200);
for (int i = 0; i < d.size(); i++) {
cout << d[i] << " ";
}
cout << endl;
for (int i = 0; i < d.size(); i++) {
cout << d.at(i) << " ";
}
cout << endl;
cout << "front:" << d.front() << endl;
cout << "back:" << d.back() << endl;
}
int main() {
test01();
return 0;
}
運行結果：
200 100 10 20
200 100 10 20
front:200
back:20
總結：
- 除了用迭代器獲取deque容器中元素，和at也可以
- front返回容器第一個元素
- back返回容器最後一個元素
deque 排序
功能描述：
- 利用算法實現對deque容器進行排序
算法：
sort(iterator beg, iterator end)//對beg和end區間內元素進行排序
示例：
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
void printDeque(const deque<int>& d)
{
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
void test01()
{
deque<int> d;
d.push_back(10);
d.push_back(20);
d.push_front(100);
d.push_front(200);
printDeque(d);
sort(d.begin(), d.end());
printDeque(d);
}
int main() {
// 程序从 main 函数开始执行，下面的语句会按顺序运行。
test01();
// 返回 0 表示程序正常结束。
return 0;
}
運行結果：
200 100 10 20
10 20 100 200
總結：sort算法非常實用，使用時包含頭文件 algorithm即可
案例-評委打分
案例描述
有5名選手：選手ABCDE，10個評委分別對每一名選手打分，去除最高分，去除評委中最低分，取平均分。
實現步驟
- 創建五名選手，放到vector中
- 遍歷vector容器，取出來每一個選手，執行for循環，可以把10個評分打分存到deque容器中
- sort算法對deque容器中分數排序，去除最高和最低分
- deque容器遍歷一遍，累加總分
- 獲取平均分
示例代碼：
#include <iostream>
using namespace std;
//选手类
class Person
{
public:
Person(string name, int score)
{
this->m_Name = name;
this->m_Score = score;
}
string m_Name; //姓名
int m_Score; //平均分
};
void createPerson(vector<Person>&v)
{
string nameSeed = "ABCDE";
for (int i = 0; i < 5; i++)
{
string name = "选手";
name += nameSeed[i];
int score = 0;
Person p(name, score);
//将创建的person对象 放入到容器中
v.push_back(p);
}
}
//打分
void setScore(vector<Person>&v)
{
for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
{
//将评委的分数 放入到deque容器中
deque<int>d;
for (int i = 0; i < 10; i++)
{
int score = rand() % 41 + 60; // 60 ~ 100
d.push_back(score);
}
//cout << "选手： " << it->m_Name << " 打分： " << endl;
//for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
//{
// cout << *dit << " ";
//}
//cout << endl;
//排序
sort(d.begin(), d.end());
//去除最高和最低分
d.pop_back();
d.pop_front();
//取平均分
int sum = 0;
for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
{
sum += *dit; //累加每个评委的分数
}
int avg = sum / d.size();
//将平均分 赋值给选手身上
it->m_Score = avg;
}
}
void showScore(vector<Person>&v)
{
for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
{
cout << "姓名： " << it->m_Name << " 平均分： " << it->m_Score << endl;
}
}
int main() {
//随机数种子
srand((unsigned int)time(NULL));
//1、创建5名选手
vector<Person>v; //存放选手容器
createPerson(v);
//测试
//for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
//{
// cout << "姓名： " << (*it).m_Name << " 分数： " << (*it).m_Score << endl;
//}
//2、给5名选手打分
setScore(v);
//3、显示最后得分
showScore(v);
return 0;
}
運行結果（隨機數會隨運行環境變化，以下為一次運行示例）：
姓名： 选手A 平均分： 78
姓名： 选手B 平均分： 72
姓名： 选手C 平均分： 86
姓名： 选手D 平均分： 81
姓名： 选手E 平均分： 86
總結： 選取不同的容器操作數據，可以提升代碼的效率