黑马C++视频笔记《STL之deque容器》

deque
deque内部工作原理

/* deque容器
 * 双端数组，可以对头端和尾端进行插入操作.(链表式储存).
 *
 * deque与vector区别：
 *  - vector对于头部的插入效率低，数据量越大，效率越低；
 *  - deque相对而言，对头部的插入删除速度会比vector快；
 *  - vector访问元素时的速度会比deque快，这和两者内部实现有关.
 *
 * deque内部工作原理：
 *  deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据。中控器维护的是每个缓冲区的地址，
 *  使得使用deque时像一片连续的内存空间.
 *
 * deque构造函数：
 *  - `deque<T> deq;`，默认构造形式；
 *  - `deque(iterator_begin, iterator_end);`，构造函数将[iterator_begin, iterator_end)间的元素拷贝给本身；
 *  - `deque(n, elem);`，构造函数将n个elem拷贝给本身；
 *  - `deque(const deque &deq);`，拷贝构造函数.
 *
 * 赋值操作：
 *  - `deque(& operator=(const deque &deq);`， 重载等号操作符；
 *  - `assign(iterator_begin, iterator_end);`，将[iterator_begin, iterator_end)区间内的元素赋值给本身；
 *  - `assign(n, elem);`，将n个elem赋值给本身.
 *
 * 大小操作：
 *  - `deque.empty();`，判断容器是否为空；
 *  - `deque.size();`，返回容器中元素的个数；
 *  - `deque.resize(int num);`，重新指定容器的大小，变长则填充默认值，变短则删除多出来的末端值；
 *  - `deque.resize(int num, elem);`，重新指定容器的大小，变长则填充elem，变短则删除多出来的末端值；
 *
 * 插入删除操作：
 *  - `push_back(elem);`，在容器尾部添加一个数据；
 *  - `push_front(elem);`，在容器头部插入一个数据；
 *  - `pop_back();`，删除容器最后一个数据；
 *  - `pop_front();`，删除容器第一个数据；
 *  - `insert(iterator_pos, elem);`，在指定位置插入元素；
 *  - `insert(iterator_pos, n, elem);`，在指定位置插入n个元素；
 *  - `insert(iterator_pos, iterator_begin, iterator_end);`，在指定位置插入区间[begin, end)间的数据，无返回值；
 *  - `clear();`，清空容器的所有数据；
 *  - `erase(iterator_begin, iterator_end);`，删除[begin, end)区间的数据，【返回下一个数据的位置】；
 *  - `erase(iterator_pos);`，删除pos位置的数据，【返回下一个数据的位置】；
 *
 * 数据存取：
 *  - `at(int idx);`，返回索引idx所指的数据；
 *  - `operator[];`，返回索引idx所指的数据；
 *  - `front();`，返回容器中第一个数据元素；
 *  - `back();`，返回容器中最后一个数据元素.
 *
 * deque排序：
 *  - `sort(iterator begin, iterator end);`，对beg和end区间内的元素进行排序.
 *  vector也可用sort进行排序。
 *
 */

实战案例

#include <iostream>
#include <string>
#include <deque>
#include <vector>
#include <ctime>
using namespace std;

/* 实战案例：
 * 10个评委分别对5个选手打分，去除一个最高分一个最低分然后计算平均分.
 */

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 persons = "ABCDE";
    for (int i=0; i<5; i++){
        string name = "选手";

        name += persons[i];
        int score = 0;
        Person p(name, score);
        v.push_back(p);
        // 下面代码会报错，因为v[i]当前没有元素，因此不能索引赋值
        // v[i] = Person(name, score);
    }
}


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);
        }
        // 排序取出最高分和最低分
        //deque<int>::iterator dt;
        sort(d.begin(),d.end());
        d.pop_front();
        d.pop_front();

        // 取平均分
        int sum=0;
        for (deque<int>::iterator it=d.begin();it!=d.end();it++){
            sum += *it;
        }

        int score = sum/d.size();
        it->m_score = score;
    }
}

int main(){
    srand((unsigned int)time(NULL));
    // 创建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;
    }

    // 评委打分并计算平均分
    setScore(v);
    for (vector<Person>::iterator it=v.begin();it!=v.end();it++){
        cout << it->m_name << " " << it->m_score << endl;
    }
}