大话STL第三期——deque（双端动态数组）

书接上期，这一期我们来聊聊vector同父异母的兄弟deque双端数组，完整系列可以订阅本文专栏<STL>

什么是deque

deque容器为一个给定类型的元素进行线性处理，像向量一样，它能够快速地随机访问任一个元素，并且能够高效地插入和删除容器的尾部元素，也可以根据需要修改自身的容量和大小。但它又与vector不同，deque支持高效插入和删除容器的头部元素，因此也叫做双端队列。

deuqe底层

与vector 容器采用连续的线性空间不同，deque容器存储数据的空间是由一段一段等长的连续空间构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域，使用一个中控器(指针数组)map来指向这些一段一段的空间，如果当前段空间用完了，就添加一个新的空间并将它链接在头部或尾部。 换句话说，像vector那样"旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间"这样的事情在deque上不会发生。因此deque没有必须要提供所谓的空间保留功能reserve

deque常用的API

deque的创建遍历等等基本使用与vector大同小异，也可以进行初始化列表创建，和vector同样支持随机迭代器，对于迭代器的功能使用可以转到大话STL第一期——初识相见恨晚下面我不再分功能示例，基本使用不太清楚的可以看看我上一期 大话STL第二期——机械先驱—vector​​​​​​_

deque的构造函数
deque<T> deqT;//默认构造形式
deque(beg,end);//将【beg，end】区间中的元素拷贝给自身
deque(n,elem);//将n个elem拷贝给自身
deque(const deque& deq);//拷贝构造函数

deque赋值操作
assign(beg,end);//将【beg，end】区间中数据拷贝赋值给本身
assgin(n,elem);//将n个elem拷贝赋值给本身
deque& operator=(const deque &deq);//重载等号操作符
swap(deq);/将deq与本身元素互换

deque大小操作
deque.size();//返回容器元素个数
deque.empty();//判断容器是否为空
deque.resize(num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置如果容器变短，则末尾超出容器长度的元素被删除
deque(int num, elem);//更改大小，重新指定容器的长度为num，若容器变长，则以elem填充新位置
如果容器变短，则末尾超出容器长度的元素被删除

deque双端插入和删除操作
push_back(elem);//尾部插入元素elem
push_front(elem);//头部插入元素elem
pop_back();//删除最后一个元素
pop_front();//删除第一个元素

deque数据存取
at(index);//返回索引index所指的数据，如果index越界，跑出out of range异常
operator[];//返回索引idx所指的数据，越界时，直接报错
front();//返回容器中第一个数据元素
back();//返回容器中最后一个元素

deque插入删除操作
insert(const iterator pos, int count, ele);//迭代器指向pos位置插入count个元素ele
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值
insert(pos,beg,end);//在pos位置插入[beg,end]区间的数据，无返回
push_back(elem);//尾部插入元素elem
pop_back();//删除最后一个元素
erase(const iterator start, const iterator end);//删除迭代器start到end间的元素
erase(const iterator pos);//删除迭代器指向的元素
clear();//删除容器中所有元素

和 vector 常用的API相比，额外增加了实现在容器头部添加和删除元素的成员函数，同时删除了 capacity()、reserve()

利用STL库的排序算法进行排序：注意list有着内置的sort，因此对于list调用sort可以有两种不同的写法（功能都是一样）

//从小到大 
sort(q.begin(), q.end())
//从大到小排序
sort(q.begin(), q.end(), greater<int>());//deque里面的类型需要是int型 
sort(q.begin(), q.end(), greater());//高版本C++才可以用

基本使用：

void Print(deque<int> &d)
{
    deque<int>::iterator it;
    for(it=d.begin();it!=d.end();it++)
    {
        cout<<*it<<" ";
    }
    cout<<endl;
}
void test01()
{
    deque<int> d1;
    d1.push_back(1);//尾插
    d1.push_back(2);
    d1.push_back(3);
    d1.push_front(4);//头插
    d1.push_front(5);
    d1.push_front(6);
    Print(d1);//6 5 4 1 2 3
    cout<<"大小: "<<di.size()<<endl;//d1.capacity()错误没有容量概念
    d1.pop_front();
    Print(d1);//5 4 1 2 3
    d1.pop_back();
    Print(d1);//5 4 1 2
    d1.insert(d1.begin()+1,3,10);//如果迭代器能+1，那么该迭代器为随机访问迭代器
    Print(d1);//5 10 10 10 4 1 2
}
int main()
{
    test01();
    return 0;
}

对于deque以及vector的综合使用案例：

对于deque和vector的实际使用中

• vector存放的数据没有多大的规律，只是用来记录数据
• deque一般用于类似：竞技的数据(最高分，最低分，平均分等等)

案例描述：

有5名选手：ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委最低分，取平均分

1.创建5名选手，放到vector中

2.遍历vector容器，取出来每一个选手，执行for循环，可以把10个评分打分存到deque容器中

3.sort算法对deque容器中分数排序，pop_back pop_front去除最高分，最低分

4.deque容器遍历一遍，累加分数

5.取平均分

class Player
{
public:
    string name;
    float score;
public:
    Player(){}
    Player(string isname,float iscore=0.0f):name(isname),score(iscore){}

};
void createPlayer(vector<Player>& v)
{
    string sumname = "ABCDE";
    for (int i = 0; i < 5; ++i)
    {
        string tepname = "选手:";
        tepname+=sumname[i];
        v.push_back(Player(tepname));
    }
}
void playGame(vector<Player>& v)
{
    //设置随机数种子
    srand(time(NULL));
    //每名选手都要参加
    vector<Player>::iterator it;
    for (it = v.begin(); it != v.end(); it++)
    {
        //10个评委打分
        deque<float> de;
        int i = 0;
        for (i = 0; i < 10; ++i)
        {
            int score = rand() % 41 + 60;//随机数
            de.push_back(score);
        }
        //对de容器排序
        sort(de.begin(), de.end());
        //去掉最高分
        de.pop_back();
        //去掉最低分
        de.pop_front();
        //求总分
        float sum = accumulate(de.begin(), de.end(), 0);//#include<numeric>
        //平均成绩
        (*it).score = sum / de.size();
    }
}
void showscore(vector<Player>& v)
{
    vector<Player>::iterator it;
    for (it = v.begin(); it != v.end(); it++)
    {
        cout << (*it).name<<"所得分数:"<<(*it).score << endl;
    }
}
void test()
{
    //创建5名选手
    vector<Player> v;
    createPlayer(v);
    //开始比赛
    playGame(v);
    //显示成绩
    showscore(v);
}
int main()
{
    test();
    return 0;
}

上述案例综合了vector和deque的常用api可以根据题目自己练习一下。

感谢观看！有兴趣可以订阅浏览！