千锋教育-做有情怀、有良心、有品质的职业教育机构

手机站
千锋教育

千锋学习站 | 随时随地免费学

千锋教育

扫一扫进入千锋手机站

领取全套视频
千锋教育

关注千锋学习站小程序
随时随地免费学习课程

当前位置:首页  >  应聘面试  >  物联网面试题  > STL教程(五):C++ STL常用容器之deque

STL教程(五):C++ STL常用容器之deque

来源:千锋教育
发布人:syq
时间: 2022-07-11 17:18:00 1657531080

  1、deque容器的基本概念

  Vector容器是单向开口的连续内存空间,deque则是一种双向开口的连续线性空间,又称双端动态数组。所谓的双向开口,意思是可以在头尾两端分别做元素的插入和删除操作,当然,vector容器也可以在头尾两端插入元素,但是在其头部操作效率奇差,无法被接受。

11

  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的存储空间的主体。

12

  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;}

13

  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;}

 

14

  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;

 }

 

15

  更多关于物联网培训的问题,欢迎咨询千锋教育在线名师,如果想要了解我们的师资、课程、项目实操的话可以点击咨询课程顾问,获取试听资格来试听我们的课程,在线零距离接触千锋教育大咖名师,让你轻松从入门到精通。

tags:
声明:本站稿件版权均属千锋教育所有,未经许可不得擅自转载。
10年以上业内强师集结,手把手带你蜕变精英
请您保持通讯畅通,专属学习老师24小时内将与您1V1沟通
免费领取
今日已有369人领取成功
刘同学 138****2860 刚刚成功领取
王同学 131****2015 刚刚成功领取
张同学 133****4652 刚刚成功领取
李同学 135****8607 刚刚成功领取
杨同学 132****5667 刚刚成功领取
岳同学 134****6652 刚刚成功领取
梁同学 157****2950 刚刚成功领取
刘同学 189****1015 刚刚成功领取
张同学 155****4678 刚刚成功领取
邹同学 139****2907 刚刚成功领取
董同学 138****2867 刚刚成功领取
周同学 136****3602 刚刚成功领取
相关推荐HOT