STL教程（五）：C++ STL常用容器之deque
1、deque容器的基本概念
Vector容器是单向开口的连续内存空间，deque则是一种双向开口的连续线性空间，又称双端动态数组。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，vector容器也可以在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。
2、与vector区别不同
Deque容器和vector容器最大的差异。
一在于deque允许使用常数项时间对头端进行元素的插入和删除 操作。
二在于deque没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，换句话说，像vector那样，”旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque身上是不会发生的。也因此，deque没有必须要提供所谓的空间保留(reserve)功能. 虽然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指针， 其复杂度和vector不是一个量级，这当然影响各个运算的层面。
因此，除非有必要，我们应该尽可能的 使用vector，而不是deque。对deque进行的排序操作，为了最高效率，可将deque先完整的复制到一个vector中，对vector容器进行排序，再复制回deque。
3、deque容器的实现原理
Deque容器是连续的空间，至少逻辑上看来如此，连续现行空间总是令我们联想到array和vector,array 无法成长，vector虽可成长，却只能向尾端成长，而且其成长其实是一个假象，事实上(1) 申请更大空间 (2)原数据复制新空间 (3)释放原空间 三步骤，如果不是vector每次配置新的空间时都留有余裕，其成长假象所带来的代价是非常昂贵的。 Deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在deque的头端或者尾端。Deque最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间，复制，释放的轮回，代价就是复杂的迭代器架构。 既然deque是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象，数据结构的设计及迭代器的前进后退操作颇为繁琐。Deque代码的实现远比vector或list都多得多。 Deque采取一块所谓的map(注意，不是STL的map容器)作为主控，这里所谓的map是一小块连续的内存空间，其中每一个元素(此处成为一个结点)都是一个指针，指向另一段连续性内存空间，称作缓冲区。缓冲区才是deque的存储空间的主体。
4、deque容器常用API
4.1deque构造函数
deque<T> deqT;//默认构造形式 deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。 deque(n, elem);//构造函数将n个elem拷贝给本身。 deque(const deque &deq);//拷贝构造函数
4.2deque赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。 assign(n, elem);//将n个elem拷贝赋值给本身。
deque& operator=(const deque &deq); //重载等号操作符 swap(deq);// 将deq与本身的元素互换
案例：
#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<deque>
using namespace std;void printDequeInt(deque<int> &d)
{
deque<int>::iterator it = d.begin();
for(;it!=d.end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;}
void test01(){
deque<int> d1(5,100);
printDequeInt(d1);
deque<int> d2;
d2.assign(d1.begin(), d1.begin()+2);
printDequeInt(d2);
deque<int> d3(5,10);
printDequeInt(d1);
printDequeInt(d3);
d1.swap(d3);
printDequeInt(d1);
printDequeInt(d3);}int main(){
test01() ;
return EXIT_SUCCESS;}
4.3deque大小操作
deque.size();//返回容器中元素的个数
deque.empty();//判断容器是否为空
deque.resize(num);//重新指定容器的长度为num,若容器变长，则以默认值填充新位置。如果容器变 短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置,如果 容器变短，则末尾超出容器长度的元素被删除
4.4deque双端插入和删除操作
push_back(elem);//在容器尾部添加一个数据 push_front(elem);//在容器头部插入一个数据 pop_back();//删除容器最后一个数据 pop_front();//删除容器第一个数据
案例：
#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<deque>
using namespace std;void printDequeInt(deque<int> &d)
{
deque<int>::iterator it = d.begin();
for(;it!=d.end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;}
void test01(){
deque<int> d1;
d1.push_back(10);
d1.push_back(20);
d1.push_back(30);
d1.push_front(40);
d1.push_front(50);
d1.push_front(60);
printDequeInt(d1);
//尾部删除
d1.pop_back();
printDequeInt(d1);//60 50 40 10 20
d1.pop_front();
printDequeInt(d1);//50 40 10 20
cout<<d1[2]<<endl;//10
cout<<d1.at(2)<<endl;//10
d1.insert(d1.begin()+2, 3, 100);
printDequeInt(d1);//50 40 100 100 100 10 20
d1.erase(d1.begin()+2, d1.begin()+5);
printDequeInt(d1);//50 40 10 20
}int main(){
test01() ;
return EXIT_SUCCESS;}
4.5deque数据存取
at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。 operator[];//返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。 front();//返回第一个数据。back();//返回最后一个数据。
4.6deque插入操作
insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。 insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。 insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
4.7deque删除操作
clear();//移除容器的所有数据 erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。 erase(pos);//删除pos位置的数据，返回下一个数据的位置。
5、deque容器使用案例
有5名选手：选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委中最低分，取平均分。 1. 创建五名选手，放到vector中 2. 遍历vector容器，取出来每一个选手，执行for循环，可以把10个评分打分存到deque容器中 3. sort算法对deque容器中分数排序，pop_back pop_front去除最高和最低分 4. deque容器遍历一遍，累加分数，累加分数/d.size() 5. person.score = 平均分
#include <iostream>#include <string>#include <vector>#include <deque>#include <stdlib.h>//srand rand#include <time.h>//time#include <algorithm>//sortusing namespace std;
class Person
{
private:
string name;
int score;
public:
Person(){}
Person(string name, int score)
{
this‐>name = name;
this‐>score = score;
}
void showPerson(void)
{
cout<<"姓名:"<<name<<", 分数:"<<score<<endl;
}
void setScore(int score)
{
this‐>score = score;
}
};
void ceatePlayer(vector<Person> &v)
{
int i=0;
string tmp="ABCDE";
for(i=0;i<5;i++)
{
string name="选手";
name += tmp[i];
v.push_back(Person(name, 0));
}
}
void printVectorPerson(vector<Person> &v)
{
vector<Person>::iterator it=v.begin();
for(;it!=v.end();it++)
{
(*it).showPerson();
}
}
void playGame(vector<Person> &v)
{
//设置随机数种子
srand(time(NULL));
vector<Person>::iterator it=v.begin();
for(; it!=v.end();it++)
{
//*it代表的就是每位选手
//定义一个deque容器存放评委的分数
deque<int> d;
int i=0;
for(i=0;i<10;i++)
{
int score = 0;
score = rand()%41+60;//60~100
//将评委的分数放入 d容器中
d.push_back(score);
}
//对容器排序(默认从小‐‐‐>大排序)
sort(d.begin(), d.end());
//去掉一个最高分
d.pop_back();
//去掉一个最低分
d.pop_front();
//求总分数
int sum = accumulate(d.begin(), d.end(), 0);
//求平均成绩
int avg = sum/d.size();
//将平均成绩赋值给选手
(*it).setScore(avg);
}
}
int main(int argc, char *argv[])
{
vector<Person> v;
//创建5名选手
ceatePlayer(v);
//遍历容器
printVectorPerson(v);
//参加比赛
playGame(v);
cout<<"------------"<<endl;
//遍历容器
printVectorPerson(v);
return 0;
}
更多关于物联网培训的问题，欢迎咨询千锋教育在线名师，如果想要了解我们的师资、课程、项目实操的话可以点击咨询课程顾问，获取试听资格来试听我们的课程，在线零距离接触千锋教育大咖名师，让你轻松从入门到精通。
