STL notes (VII): container deque

STL note （ 7、 ... and ）： Containers ——deque

function

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

// deque Containers  -  deque 

void Display(deque<int> d)
{
    for (deque<int>::iterator it = d.begin(); it != d.end(); it++) { //  Random iterator 
        cout << *it << " ";
    }
    cout << endl;
}

void rDisplay(deque<int> d)
{
    for (deque<int>::reverse_iterator it = d.rbegin(); it != d.rend(); it++) { //  Random iterator 
        cout << *it << " ";
    }
    cout << endl;
}

//  Definition and initialization 
void test1()
{
    deque<int> d1;
    deque<int> d2(2); // 0 0
    deque<int> d3(4, 3); // 3 3 3 3

    int a[] = {10, 20, 30};
    deque<int> d4(a, a + sizeof(a)/sizeof(int));
    deque<int> d5(d4.begin(), d4.end());
    deque<int> d6(d5);

    Display(d5);
    rDisplay(d5);
}

//  Access data 
void test2()
{
    //  Save the data 
    deque<int> d;
    d.push_back(20);  // 20
    d.push_front(10); // 10 20
    d.push_back(30);  // 10 20 30
    Display(d);

    //  Take the data 
    cout << d[0] << endl; // 10
    cout << d.at(0) << endl; // 10 | Detect out of bounds |
    cout << d.front() << endl; // 10
    cout << d.back() << endl; // 30
    cout << *(d.begin() + 1) << endl; // 20
}

//  Size attribute 
void test3()
{
    // max_size -  System size 
    deque<int> d;
    cout << d.max_size() << endl;

    // size
    d.push_back(10);
    d.push_back(20);
    cout << d.size() << endl; // 2

    // resize
    d.resize(6, 2);
    Display(d); // 10 20 2 2 2 2 | If there is no second argument , Default zero filling |
}

//  The quotation is related to vector identical , That is, the return type of the access value is reference , It can increase itself directly 、 Since the reduction of operating 

//  Insert deletion 
void test4()
{
    //  Insert 
    deque<int> d;
    d.push_back(20);
    d.push_front(10);
    Display(d); // 10 20
    d.insert(d.begin() + 1, 15); // 10 15 20
    d.insert(d.begin(), 5); // 5 10 15 20
    int a[] = {25, 30};
    d.insert(d.end(), a, a + sizeof(a)/sizeof(int)); // 5 10 15 20 25 30
    d.insert(d.end(), 1, 35); // 5 10 15 20 25 30 35
    Display(d);

    //  Delete 
    d.pop_back(); // 5 10 15 20 25 30
    d.pop_back(); // 5 10 15 20 25
    d.pop_front(); // 10 15 20 25
    d.erase(d.begin() + 3); // 10 15 20
    d.erase(d.begin() + 1, d.begin() + 2); // 10 20
    Display(d);

    d.clear();
    Display(d);
}

// vector And deque The difference between  —— push_back
void test5()
{
    vector<int> v(2); // 0 0
    v[0] = 8; // 8 0
    int * p = & v[0]; //  Take the first address of the array 
    cout << "The value of * p before push_back: " << *p << endl; // 8
    v.push_back(25);
    cout << "The value of * p after push_back: " << *p << endl; //  Not sure  | Pointer failure |

    deque<int> d(2); // 0 0
    d[0] = 8; // 8 0
    p = & d[0]; //  Take the first address of the array 
    cout << "The value of * p before push_back: " << *p << endl; // 8
    d.push_back(25);
    cout << "The value of * p after push_back: " << *p << endl; // 8
}

// vector And deque The difference between  —— insert/erase
void test6()
{
    int a[] = {10, 20, 30, 40, 50};
    vector<int> v(a, a + 5);
    int  * p = & v[3];
    cout << "The value of * p before erase: " << *p << endl; // 40
    v.erase(v.begin() + 1);
    cout << "The value of * p after erase: " << *p << endl; // 50

    deque<int> d(a, a + 5);
    p = & d[3];
    cout << "The value of * p before erase: " << *p << endl; // 40
    d.erase(d.begin() + 1);
    cout << "The value of * p after erase: " << *p << endl; // 40

    //  about vector To delete an element, you can only move forward , And for deque In other words, elements can be moved not only forward but also backward , The result depends on the number of elements to be moved 
}

int main()
{
    // test1(); //  Definition and initialization 
    // test2(); //  Access data 
    // test3(); //  Size attribute 
    test4(); //  Insert deletion 
    // test5(); // vector And deque The difference between  —— push_back
    // test6(); // vector And deque The difference between  —— insert/erase

    return 0;
}

Case study

#include <iostream>
#include <string>
#include <deque>
#include <vector>
#include <algorithm>

using namespace std;

//  Three players , Five judges , Take out the highest and lowest marks , Calculate the average score , Rank by grades （ High to the end ）

class Player
{
private:
    string playerName;
    deque<double> playerScores;
    double averageScore;
public:
    Player(string name):playerName(name){}
    void showPlayer()
    {
        cout << playerName << '\t' << averageScore << endl;
    }
    void writeScores()
    {
        cout << "-------- Please be a contestant " + playerName + " score --------" << endl;
        for (int i = 0; i < 5; i++) {
            double score;
            cout << " Please enter the first " << (i + 1) << " The ratings of the judges ：";
            cin >> score;
            playerScores.push_back(score);
        }
    }
    void calculateAverageScore()
    {
        sort(playerScores.begin(), playerScores.end()); //  From small to large 
        playerScores.pop_front();
        playerScores.pop_back();
        double sum = 0;
        for (deque<double>::iterator it = playerScores.begin(); it != playerScores.end(); it++) {
            sum += *it;
        }
        averageScore = sum / playerScores.size();
    }
    bool operator<(Player p)
    {
        return averageScore < p.averageScore;
    }
};

class playersMS
{
private:
    vector<Player> playerSet;
public:
    void addPlayer(Player p)
    {
        playerSet.push_back(p);
    }
    void judgePlayer()
    {
        for (vector<Player>::iterator it = playerSet.begin(); it != playerSet.end(); it++) {
            it->writeScores();
        }
    }
    void computeAverageScore()
    {
        for (vector<Player>::iterator it = playerSet.begin(); it != playerSet.end(); it++) {
            it->calculateAverageScore();
        }
    }
    void sortPlayer()
    {
        sort(playerSet.begin(), playerSet.end()); //  heavy load '<' Operator 
    }
    void showResult()
    {
        cout << endl;
        cout << "-------- final result --------" << endl;
        cout << "Name" << '\t' << "Score" << endl;
        cout << "------------------------" << endl;
        for (vector<Player>::reverse_iterator it = playerSet.rbegin(); it != playerSet.rend(); it++) {
            it->showPlayer(); //  Because the sorting result defaults from small to large , So use a reverse iterator 
        }
        cout << endl;
    }
};

int main()
{
    Player p1("Reyn");
    Player p2("Lisa");
    Player p3("Lena");

    playersMS MS;

    cout << "**************************** Scoring system ****************************" << endl << endl;

    MS.addPlayer(p1);
    MS.addPlayer(p2);
    MS.addPlayer(p3);

    MS.judgePlayer();

    MS.computeAverageScore();

    MS.sortPlayer();

    MS.showResult();

    cout << "****************************************************************" << endl << endl;

    return 0;
}

summary

• deque Container ratio vector There are more operations on the starting bit of the array , for example push_front()、pop_front(), Obviously, compared with vector Come on ,deque Is more powerful in function
• deque It looks like an array on the surface , But its internal implementation and variable length array （vector） There is a big difference , That is, the array is mainly composed of several pointers to the array , And its data is stored in these arrays , So it's OK to deque Add or delete the start and end of , Random access is also possible
• Due to different implementations of containers , When the size inside the container is insufficient , If you continue to add elements to the inside of the container , that vector May cause address changes , however deque Will not cause address changes
• about vector To delete an element, you can only move forward , And for deque In other words, elements can be moved not only forward but also backward , The result depends on the number of elements to be moved
• In object-oriented thinking , Each method involves the operation of other objects , It is best to implement it inside the class where this object is located , Instead of writing a method outside the class , On the one hand, this is conducive to the separation of functions , Form a low coupling state between modules , On the other hand, it is conducive to the maintenance of the program , Reduce workload , Besides , You also need to pay attention to the use of operator overloading

In the next article , We will introduce C++ In the container ——list