08-C++ STL-容器

c++ STL-容器

1. 引入

• 我们想存储多个学员的信息，现在学员数量不定？
  • 我们可以创建一个 数组 存储学员的信息
  • 但是这个数组大小是多少呢?
  • 过大会导致空间浪费，小了又需要扩容
  • 对其中的数据进行操作也较为复杂
  • 每次删除数据后还要对其进行回收等操作
  • 这样我们在编写代码时将大量的时间在这种无关业务的事情上被浪费
• 为了我们能更好的关心业务操作
• 程序人员从函数(functions)，类别(classes)，函数库(function libraries)，类别库(classlibraries)、各种组件，从模块化设计，到面向对象(object oriented )，进行设计，提供了为了建立数据结构和算法的一套标准，并且降低他们之间的耦合关系，以提升各自的独立性、弹性、交互操作性(相互合作性，interoperability)，诞生了 STL 。

2. 概述

STL(Standard Template Library，标准模板库)，是惠普实验室开发的一系列软件的统

2.1 STL 六大组件

① 容器：

• 作用：容纳存储数据
• 分类：
  • 序列式容器：
    • 强调值的排序，每个元素均有固定的位置， 除非用删除或插入的操作改变这个位置，
    • 如 vector, deque/queue, list；
  • 关联式容器：
    • 非线性，更准确的说是二叉树结构，各元素之间没有严格的物理上的顺序关系;
    • 在数据中选择一个关键字key，这个key对数据起到索引的作用，方便查找。
      • 如： Set/multiset ， Map/multimap 容器
• 注意：容器可以嵌套容器

② 算法：

• 作用：操作数据，如插入数据、删除数据、修改数据、排序等
• 分类:
  • 质变算法：是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等
  • 非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等

③ 迭代器

• 作用：容器与算法之间的粘合剂
• 注意：每个容器都有自己的迭代器
• 分类：
  • 输入迭代器 提供对数据的只读访问 只读，支持++、==、！=
  • 输出迭代器 提供对数据的只写访问 只写，支持++
  • 前向迭代器 提供读写操作，并能向前推进迭代器 读写，支持++、==、！=
  • 双向迭代器 提供读写操作，并能向前和向后操作 读写，支持++、–，
  • 随机访问迭代器 提供读写操作，并能以跳跃的方式访问容器的任意数据，是功能最强的迭代器读写，支持++、-- [n]、- n、<、<=、>、>=

④ 仿函数

• 又名函数对象，是一个 重载 了函数调用运算符（operator()）的类的对象

• 作用：为算法提供策略

⑤ 适配器

• 作用：为算法提供更多的参数接口

⑥ 空间配置器

• 作用：为容器和算法管理空间

优点：

有高可重用性
高性能
高移植性
跨平台

3. 常用容器

3.1 string

作用：存储字符的容器

使用前需要导入 #include <string> 头文件。

3.1.1 构造函数

string();//创建一个空的字符串 例如: string str;
string(const string& str);//使用一个 string 对象初始化另一个 string 对象
string(const char* s);//使用字符串 s 初始化
string(int n, char c);//使用 n 个字符 c 初始化 v

示例：

#include <iostream>
#include <string>
using namespace std;

void fun01()
{
    //无参构造
    string str01;
    cout << "str01: " << str01 << endl;     //str01:

    //有参构造(字符串指针)
    char *cs = "张三";
    string str02(cs);
    cout << "str02: " << str02 << endl;     //str02: 张三

    string str03(3, 'a');
    cout << "str03: " << str03 << endl;     //str03: aaa
	
    //拷贝构造
    //string(const string& str);//使用一个 string 对象初始化另一个 string 对象
    string str04 = str03;
    cout << "str04: " << str04 << endl;     //str04: aaa
}

3.1.2 基本赋值操作

string& operator=(const char* s);//char类型字符串赋值给当前的字符串
string& operator=(const string &s);//把字符串s赋给当前的字符串
string& operator=(char c);//字符赋值给当前的字符串
string& assign(const char *s);//把字符串s赋给当前的字符串
string& assign(const char *s, int n);//把字符串s的前n个字符赋给当前的字符串 
string& assign(const string &s);//把字符串s赋给当前字符串
string& assign(int n, char c);//用n个字符c赋给当前字符串
string& assign(const string &s, int start, int n);//将s从 start开始n个字符赋值给字符串

示例：

void fun02()
{
    string str01;
    str01 = "甲乙丙丁";
    cout << "str01: " << str01 << endl;     //str01: 甲乙丙丁

    string str02;
    str02 = str01; //此处是赋值，并不是拷贝构造，str02不算老对象
    cout << "str02: " << str02 << endl;     //str02: 甲乙丙丁

    string str03;
    str03 = 'a';
    cout << "str03: " << str03 << endl;     //str03: a

    string str04;
    str04.assign("戊己庚辛");
    cout << "str04: " << str04 << endl;     //str04: 戊己庚辛

    string str05;
    str05.assign("戊己庚辛", 2);
    cout << "str05: " << str05 << endl;     //str05: 戊

    string str06;
    str06.assign(str05);
    cout << "str06: " << str06 << endl;     //str06: 戊

    string str07;
    str07.assign(5, 'a');
    cout << "str07: " << str07 << endl;     //str07: aaaaa

    string str08;
    str08.assign(str07, 2, 1);
    cout << "str08: " << str08 << endl;     //str08: a
}

3.1.3 获取字符串长度

int size();
int length();

示例：

void fun03()
{
    string str01;
    str01 = "甲乙丙丁戊己庚辛壬癸";
    //两个单位都是字节
    cout << "str01.size=" << str01.size() << endl;      //str01.size=20
    cout << "str01.length=" << str01.length() << endl;  //str01.length=20
}

3.1.4 存取字符操作

char& operator[](int n);//通过[]方式取字符,下标越界不会抛出异常,会得到随机值
char& at(int n);//通过at方法获取字符,下标越界会抛出异常

示例：

void fun04()
{
    string str01;
    str01 = "hello";
    cout << "str01[1]=" << str01[1] << endl;      //str01[1]=e
    cout << "str01.at(1)=" << str01.at(1) << endl;  //str01.at(1)=e
    
    //修改字符
    str01[0] = 'H';
    str01.at(1) = 'E';
    cout << "str01[0]=" << str01[0] << endl;      //str01[0]=H
    cout << "str01.at(1)=" << str01.at(1) << endl;  //str01.at(1)=E
    
    cout << "str01[10]=" << str01[10] << endl;      //str01[10]=a  下标越界，获得随机值
    cout << "str01.at(10)=" << str01.at(10) << endl; 
}

下标越界如下：

3.1.5 拼接操作

string& operator+=(const string& str);//重载+=操作符
string& operator+=(const char* str);//重载+=操作符
string& operator+=(const char c);//重载+=操作符
string& append(const char *s);//把字符串s连接到当前字符串结尾
string& append(const char *s, int n);//把字符串s的前n个字符连接到当前字符串结尾
string& append(const string &s);//同operator+=()
string& append(const string &s, int pos, int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾
string& append(int n, char c);//在当前字符串结尾添加n个字符c

示例：

void fun05()
{
    string str01;
    str01 = "hello";
    string str02;
    str02 = "world";
    str01 += str02;
    cout << "str01 = " << str01 << endl;    //str01 = helloworld

    str01 += " 你好世界";
    cout << "str01 = " << str01 << endl;    //str01 = helloworld 你好世界

    str01 += 'A';
    cout << "str01 = " << str01 << endl;    //str01 = helloworld 你好世界A

    str01.append("BC");
    cout << "str01 = " << str01 << endl;    //str01 = helloworld 你好世界ABC
}

3.1.6 查找和替换

• 查找：找到返回找到的下标，找不到返回 -1 。

• 查找和替换结合使用。

int find(const string& str, int pos = 0) const; //查找str第一次出现位置,从pos开始查找
int find(const char* s, int pos = 0) const; //查找s第一次出现位置,从pos开始查找
int find(const char* s, int pos, int n) const; //从pos位置查找s的前n个字符第一次位置
int find(const char c, int pos = 0) const; //查找字符c第一次出现位置
int rfind(const string& str, int pos = npos) const;//查找str最后一次位置,从pos开始查找
int rfind(const char* s, int pos = npos) const;//查找s最后一次出现位置,从pos开始查找
int rfind(const char* s, int pos, int n) const;//从pos查找s的前n个字符最后一次位置
int rfind(const char c, int pos = 0) const; //查找字符c最后一次出现位置
string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str
string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串s

示例：

void fun06()
{
    string str("xxxabcacdcabcccllla");
    int index = str.find("abc");
    cout << "abc在字符串中第一次出现的位置是:" << index << endl;  //abc在字符串中第一次出现的位置是:3
    int i = str.rfind("abc");
    cout << "abc在字符串中最后一次出现的位置是:" << i << endl; //abc在字符串中最后一次出现的位置是:10
}

void fun07()
{
    string str("abcabcabc");
    str.replace(3,1,"ABC");
    cout << "str = " << str << endl;    //str = abcABCbcabc
}

void fun08()
{
    //多次替换，循环
    string str("2023/11/23");
    int i = str.find("/");
    while(i != -1)
    {
        str.replace(i,1,"-");
        i = str.find("/");
    }
    cout << str << endl;       //2023-11-23
}

3.1.7 比较操作

/**
*compare函数在>时返回1，<时返回-1，==时返回0。
*比较区分大小写，比较时参考字典顺序，排越前面的越小。大写的A比小写的a小。
**/
int compare(const string &s) const;//与字符串s比较
int compare(const char *s) const;//与字符串s比较

示例：

void fun09()
{
    string str01;
    str01 = "Hello";
    string str02;
    str02 = "hello";
    string str03;
    str03 = "hello";
    //0相同,非0不同
    cout << "str01 == str02:" << str01.compare(str02) << endl; //str01 == str02:-1
    cout << "str02 == str03:" << str02.compare(str03) << endl; //str02 == str03:0
}

3.1.8 截取

不影响被截取的字符串。

string substr(int pos = 0, int n = npos) const;//返回由pos开始的n个字符组成的字符串

示例：

void fun10()
{
    string str01;
    str01 = "Hello";
    string str02 = str01.substr(2,3);
    cout << str01 << endl;  //Hello
    cout << str02 << endl;  //llo
}

3.1.9 插入和删除

string& insert(int pos, const char* s); //插入字符串
string& insert(int pos, const string& str); //插入字符串
string& insert(int pos, int n, char c);//在指定位置插入n个字符c
string& erase(int pos, int n = npos);//删除从Pos开始的n个字符

示例：

void fun11()
{
    string str01;
    str01 = "Hello";
    str01.insert(0, "world");
    cout << "str01 = " << str01 << endl;  //str01 = worldHello

    str01.erase(0,5);
    cout << "str01 = " << str01 << endl;  //str01 = Hello
}

3.1.10 string* 和c-style字符串转换

一般用于：

• 函数中传进来的是字符指针，但是需要的是字符串，此时就需要转换；
• 返回值要的是字符指针，此时就要将字符串转换成字符指针。

//string转char*
string str = "itcast";
const char* cstr = str.c_str();

//char*转string
char* s = "itcast";
string str(s);

示例：

void fun12()
{
    string str;
    str = "abc";
    //将string转换为char*
    const char * cs = str.c_str();
    cout << cs << endl;			//abc
    //将char*转换为string
    string str02(cs);
    cout << str02 << endl;		//abc
}

3.2 vector

3.2.1 特点

连续开辟，单向开口，随机访问迭代器，有容量，每次扩容是原来的2倍

底层数据结构：数组

3.2.2 与数组的区别

• vector的结构类同于数组，数组是静态的，在定义时确定的数组的大小；

• 而vector是动态的，添加元素时如果空间不足时，则会自动扩容器（2^n)；这被称为vector的 未雨绸缪 机制

• 整体来说，vector比较灵活的，而且vector是类模板，可以存放任意类型的元素。

3.2.3 迭代器

本质 是vector中一个元素的指针

示例：定义一个迭代器

void printVector(vector<int> vs)
{
    //定义一个迭代器，将容器的开始位置赋值给迭代器
    vector<int>::iterator it = vs.begin();
    //只要开始位置不等于结束位置，就一直循环
    while(it != vs.end())
    {
        //输出，it是个指针，所以*it取值
        cout << *it << " ";
        //指针++，后移
        it++;
    }
    //循环结束，换行
    cout << endl;
}

3.2.4 构造函数

vector<T> v; //采用模板实现类实现，默认构造函数
vector(v.begin(), v.end());//将 v[begin(), end())区间中的元素拷贝给本身。
vector(n, elem);//构造函数将 n 个 elem 拷贝给本身。
vector(const vector &vec);//拷贝构造函数

示例：

void fun01()
{
    //无参构造
    vector<int> vs01;
    cout << "vs01:";
    printVector(vs01);  //vs01:

    //有参构造1,将10个2添加到容器中
    vector<int> vs02(10,2);
    cout << "vs02:";
    printVector(vs02);  //vs02:2 2 2 2 2 2 2 2 2 2

    //有参构造2,将一个容器中指定位置开始到指定位置结束的数据复制
    vector<int> vs03(vs02.begin()+2,vs02.begin()+5);
    cout << "vs03:";
    printVector(vs03);  //vs03:2 2 2

    int nums[10] = {1,2,3,4,5,6,7,8,9,0};
    vector<int> vs04(nums+2,nums+5);
    cout << "vs04:";
    printVector(vs04);  //vs04:3 4 5

    vector<int> vs05 = vs04;
    cout << "vs05:";
    printVector(vs05);  //vs05:3 4 5
}

3.2.5 赋值操作

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将 n 个 elem 拷贝赋值给本身。
vector& operator=(const vector &vec);//重载等号操作符
swap(vec);// 将 vec 与本身的元素互换

示例：

void fun02()
{
    int nums[10] = {1,2,3,4,5,6,7,8,9,0};
    vector<int> vs;
    vs.assign(nums,nums+10);
    //vs.assign(3,5);
    cout << "vs:";
    printVector(vs);    //vs:1 2 3 4 5 6 7 8 9 0

    vector<int> newVs;
    newVs = vs;
    cout << "newVs:";
    printVector(newVs); //newVs:1 2 3 4 5 6 7 8 9 0

    vector<int> vs02;
    //互换
    vs02.swap(vs);
    cout << "vs:";
    printVector(vs); //vs:
    cout << "vs02:";
    printVector(vs02); //vs02:1 2 3 4 5 6 7 8 9 0
}

3.2.6 插入与删除

push_back(ele); //尾部插入元素 ele
insert(const_iterator pos, int count, T ele); //迭代器指向位置 pos 插入count个元素ele.
pop_back();//删除最后一个元素
erase(const_iterator start, const_iterator end); //删除迭代器从 start到 end 之间的元素,删除[start, end)区间的所有元素
erase(const_iterator pos); //删除迭代器指向的元素
clear(); //删除容器中所有元素

示例：

void fun03()
{
    vector<int> vs01;
    vs01.push_back(1);
    vs01.push_back(3);
    vs01.push_back(4);
    vs01.push_back(2);
    cout << "vs01:";
    printVector(vs01); //vs01:1 3 4 2

    vs01.insert(vs01.begin(), 3, 9);
    cout << "vs01:";
    printVector(vs01);  //vs01:9 9 9 1 3 4 2

    vs01.pop_back();
    cout << "vs01:";
    printVector(vs01);  //vs01:9 9 9 1 3 4 

    vs01.erase(vs01.begin(), vs01.begin()+2);
    cout << "vs01:";
    printVector(vs01);  //vs01:9 1 3 4 

    vs01.erase(vs01.begin());
    cout << "vs01:";
    printVector(vs01);  //vs01:1 3 4 

    vs01.clear();
    cout << "vs01:";
    printVector(vs01);  //vs01:
}

3.2.7 取值操作

at(int idx); //返回索引 idx 所指的数据，如果 idx 越界，抛出 out_of_range异常。
operator[](int idx); //返回索引 idx 所指的数据
front(); //返回容器中第一个数据元素
back(); //返回容器中最后一个数据元素

void fun04()
{
    vector<int> vs;
    vs.push_back(9);
    vs.push_back(1);
    vs.push_back(8);
    vs.push_back(2);

    cout << "vs.at(0) = " << vs.at(0) << endl;  //vs.at(0) = 9
    cout << "vs[0] = " << vs[0] << endl;        //vs[0] = 9

    cout << "vs.front = " << vs.front() << endl;    //vs.front = 9
    cout << "vs.back = " << vs.back() << endl;      //vs.back = 2

    cout << "vs[10] = " << vs[10] << endl;        //vs[10] = 0
    cout << "vs.at(10) = " << vs.at(10) << endl;    //报错，如下图
}

3.2.8 大小 相关

int size(); // 返回容器中元素的个数
bool empty(); //判断容器是否为空， 返回bool值（0， 1）
void resize(int num); //重新指定容器的长度为 num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
void resize(int num, elem); //重新指定容器的长度为 num，若容器变长，则以elem 值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
int capacity(); //容器的容量
void reserve(int len); //容器预留 len 个元素长度

示例：

void fun05()
{
    vector<int> vs;
//    vs.reserve(4); //预留为4，当数据个数不超过4个时，容量一直为4
    cout << "vs中元素的个数:" << vs.size() << endl;   //vs中元素的个数:0
    cout << "vs当前容量:" << vs.capacity() << endl;   //vs当前容量:0
    vs.push_back(1);
    cout << "vs中元素的个数:" << vs.size() << endl;   //vs中元素的个数:1
    cout << "vs当前容量:" << vs.capacity() << endl;   //vs当前容量:1
    vs.push_back(2);
    cout << "vs中元素的个数:" << vs.size() << endl;   //vs中元素的个数:2
    cout << "vs当前容量:" << vs.capacity() << endl;  //vs当前容量:2
    vs.push_back(3);
    cout << "vs中元素的个数:" << vs.size() << endl;   //vs中元素的个数:3
    cout << "vs当前容量:" << vs.capacity() << endl;  //vs当前容量:4
    vs.push_back(4);
    cout << "vs中元素的个数:" << vs.size() << endl;   //vs中元素的个数:4
    cout << "vs当前容量:" << vs.capacity() << endl;   //vs当前容量:4
    vs.push_back(5);
    cout << "vs中元素的个数:" << vs.size() << endl;   //vs中元素的个数:5
    cout << "vs当前容量:" << vs.capacity() << endl;   //vs当前容量:8

    cout << "vs是否为空:" << vs.empty() << endl;        //vs是否为空:0
    //vs.clear();
    //cout << "vs是否为空:" << vs.empty() << endl;

    cout << "vs:";
    printVector(vs);        //vs:1 2 3 4 5

    //vs.resize(3);
    vs.resize(7,10);
    cout << "vs:";
    printVector(vs);        //vs:1 2 3 4 5 10 10
}

3.2.9 存放自定义对象

注意：函数访问权限，设置友元。

#include <iostream>
#include <vector>
#include<string>
class Person{
    friend void fun06();
    string name;
    int age;
public:
    Person(){}
    Person(string name,int age)
    {
        this->name = name;
        this->age = age;
    }
};

void fun06()
{
    vector<Person> ps;
    Person p1("张三",18);
    ps.push_back(p1);
    ps.push_back(Person("张彪1",22));
    ps.push_back(Person("张彪2",22));
    ps.push_back(Person("张彪3",22));
    ps.push_back(Person("张彪4",22));

    vector<Person>::iterator it = ps.begin();
    while(it != ps.end())
    {
        cout << (*it).name << " " << (*it).age << endl;
        it++;
    }
}
//张三 18
//李四 19
//王五 23
//钱六 43
//赵七 15

3.2.10 容器嵌套

容器 v中存放着容器： v1，v2，v3

两层for循环遍历

void fun07()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(40);
    v1.push_back(50);

    vector<int> v2;
    v2.push_back(100);
    v2.push_back(200);
    v2.push_back(300);
    v2.push_back(400);
    v2.push_back(500);

    vector<int> v3;
    v3.push_back(1000);
    v3.push_back(2000);
    v3.push_back(3000);
    v3.push_back(4000);
    v3.push_back(5000);

    vector<vector<int>> v;
    v.push_back(v1);
    v.push_back(v2);
    v.push_back(v3);

    vector<vector<int>>::iterator it = v.begin();
    for(;it != v.end();it++)
    {
        vector<int>::iterator it2 = (*it).begin();
        for(;it2 != (*it).end(); it2++)
        {
            cout << *it2 << endl;
        }
    }
}

3.2.11 小技巧：使用swap缩小空间

void fun08()
{
    vector<int> vs;
    vs.reserve(1000);
    vs.push_back(1);
    vs.push_back(2);
    vs.push_back(3);

    cout << "vs存储的元素个数:" << vs.size() << endl;  //vs存储的元素个数:3
    cout << "vs的容量:" << vs.capacity() << endl;     //vs的容量:1000

    //vector<int>(vs)表示匿名创建对象，将vs拷贝过去，
    //然后再和vs进行交换，vs容量为3，其中也只有3个数据，匿名对象一行过后就会销毁。
    vector<int>(vs).swap(vs);
    cout << "vs存储的元素个数:" << vs.size() << endl;  //vs存储的元素个数:3
    cout << "vs的容量:" << vs.capacity() << endl;      //vs的容量:3
}

3.3 deque

3.3.1 特点

deque 是一种 双向开口的连续线性空间 。

所谓的双向开口，意思是可以在 头尾两端 分别做元素的 插入 和 删除 操作。但是在其头部操作效率奇差。

3.3.2 与vector的区别

• 一在于 deque 允许使用常数项时间对头端进行元素的插入和删除操作。
• 二在于 deque 没有容量的概念，因为它是 **动态的以 分段连续 空间 **组合而成，随时可以增加一段新的空间并链接起来。

3.3.3 deque 常用 API

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

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

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

//双端插入和删除操作
push_back(elem);//在容器尾部添加一个数据
push_front(elem);//在容器头部插入一个数据
pop_back();//删除容器最后一个数据
pop_front();//删除容器第一个数据

//数据存取
at(idx);//返回索引 idx 所指的数据，如果 idx 越界，抛出 out_of_range。
operator[];//返回索引 idx 所指的数据，如果 idx 越界，不抛出异常，直接出错。
front();//返回第一个数据。
back();//返回最后一个数据

//插入操作
insert(pos,elem);//在 pos 位置插入一个 elem 元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在 pos 位置插入 n 个 elem 数据，无返回值。
insert(pos,beg,end);//在 pos 位置插入[beg,end)区间的数据，无返回值。

//删除操作
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除 pos 位置的数据，返回下一个数据的位置。

3.3.4 练习

题目：

有 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 <ctime>
#include <cstdlib>
#include <deque>
#include <algorithm>
using namespace std;

//创建人类
class Person{
    friend void printPs(vector<Person>& ps);
    friend void game(vector<Person> &ps);
    string name;
    double score;
public:
    Person(){}
    Person(string name, double score)
    {
        this->name = name;
        this->score = score;
    }
};
//创建5名选手
void createPerson(vector<Person>& ps)
{
    string str = "ABCDE";
    for(int i = 0; i < 5; i++)
    {
        string name = "选手";
        name += str[i];
        Person p(name, 0);
        ps.push_back(p);
    }
}

//打印选手
void printPs(vector<Person>& ps)
{
    vector<Person>::iterator it = ps.begin();
    for(; it != ps.end(); it++)
    {
        cout << (*it).name << "\t" << (*it).score << endl;
    }
}

//开始评分
void game(vector<Person> &ps)
{
    //设置随机数种子
    srand(time(NULL));

    for(int i = 0; i < ps.size(); i++)
    {
        //获取选手
        Person& p = ps.at(i);
        //创建一个deque存放分数
        deque<double> ss;
        cout << "请给" << p.name << "打分" << endl;
        for(int y = 0; y < 10; y++)
        {
            int s = rand() % 41 + 60;
            cout << "评委" << y << "给出的分数是" << s << endl;
            ss.push_back(s);
        }
        //排序，默认从小到大
        sort(ss.begin(), ss.end());
        //删除最高分、最低分
        ss.pop_back();
        ss.pop_front();
        //计算总分
        int sum = accumulate(ss.begin(), ss.end(), 0);
        //计算平均分
        double score = sum * 1.0 /ss.size();
        p.score = score;
    }
}

int main(int argc, char *argv[])
{
    vector<Person> ps;
    createPerson(ps);
    game(ps);
    printPs(ps);
    return 0;
}

结果：

请给选手A打分
评委0给出的分数是78
评委1给出的分数是65
评委2给出的分数是100
评委3给出的分数是77
评委4给出的分数是95
评委5给出的分数是82
评委6给出的分数是73
评委7给出的分数是61
评委8给出的分数是81
评委9给出的分数是78
请给选手B打分
评委0给出的分数是71
评委1给出的分数是83
评委2给出的分数是63
评委3给出的分数是89
评委4给出的分数是83
评委5给出的分数是69
评委6给出的分数是73
评委7给出的分数是100
评委8给出的分数是65
评委9给出的分数是78
请给选手C打分
评委0给出的分数是70
评委1给出的分数是87
评委2给出的分数是100
评委3给出的分数是75
评委4给出的分数是84
评委5给出的分数是78
评委6给出的分数是61
评委7给出的分数是60
评委8给出的分数是94
评委9给出的分数是80
请给选手D打分
评委0给出的分数是74
评委1给出的分数是80
评委2给出的分数是97
评委3给出的分数是89
评委4给出的分数是80
评委5给出的分数是89
评委6给出的分数是73
评委7给出的分数是69
评委8给出的分数是100
评委9给出的分数是65
请给选手E打分
评委0给出的分数是63
评委1给出的分数是61
评委2给出的分数是62
评委3给出的分数是79
评委4给出的分数是100
评委5给出的分数是60
评委6给出的分数是93
评委7给出的分数是73
评委8给出的分数是62
评委9给出的分数是84
选手A   78.625
选手B   76.375
选手C   78.625
选手D   81.375
选手E   72.125

3.4 stack

3.4.1 特点

先进后出，单向开口，没有迭代器

3.4.2 常用函数

//构造函数
stack<T> stkT;//stack 采用模板类实现， stack 对象的默认构造形式：
stack(const stack &stk);//拷贝构造函数赋值操作
stack& operator=(const stack &stk);//重载等号操作符

//数据存取操作
push(elem);//向栈顶添加元素
pop();//从栈顶移除第一个元素
top();//返回栈顶元素

//大小操作
empty();//判断堆栈是否为空
size();//返回堆栈的大小

3.4.3 示例

#include <iostream>
#include <stack>
using namespace std;
void fun01()
{
    stack<int> s;
    s.push(1);
    s.push(4);
    s.push(3);
    s.push(2);
    while (s.empty() != 1)
    {
        cout << s.top() << endl;
        s.pop();
    }
}
//2
//3
//4
//1

3.5 queue

3.5.1 特点

先进先出，双向开口，没有迭代器

• 队头：出数据
• 队尾：入数据

3.5.2 常用函数

//构造函数
queue<T> queT;//queue 采用模板类实现，queue 对象的默认构造形式：
queue(const queue &que);//拷贝构造函数

//存取、插入和删除操作
push(elem);//往队尾添加元素
pop();//从队头移除第一个元素
back();//返回最后一个元素
front();//返回第一个元素

//赋值操作
queue& operator=(const queue &que);//重载等号操作符

//大小操作
empty();//判断队列是否为空
size();//返回队列的大小

3.5.3 示例

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

void fun02()
{
    queue<int> q;
    q.push(1);
    q.push(5);
    q.push(2);
    q.push(4);
    q.push(3);
    while(q.empty() != 1)
    {
        cout << q.front() << endl;
        q.pop();
    }
}
//1
//5
//2
//4
//3

3.6 list

3.6.1 特点

双向链表，双向迭代器，元素可重复

1）采用动态存储分配，不会造成内存浪费和溢出

2）链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素

3）链表灵活，但是 空间和时间额外耗费较大

注意：双向迭代器不支持 +n 操作

3.6.2 list与vector的比较

1） 相对于vector 的连续线性空间，list 就显得负责许多，每次插入或者删除一个元素，就是配置或者释放一个元素的空间。不浪费多余的空间，且插入与移除元素的操作是常数时间（稳定）。

2）list和vector 是两个最常被使用的容器，但list是由双向链表实现的。

3）list 插入操作 和 删除操作 都 不会造成原有 list 迭代器的失效。 【重要特性】

3.6.3 双向迭代器

List 不能像 vector 一样以普通指针作为迭代器，因为其节点不能保证在同一块连续的内存空间上。List迭代器必须有能力指向 list 的节点，并有能力进行正确的递增、递减、取值、成员存取操作。

• 递增时指向下一个节点，
• 递减时指向上一个节点，
• 取值时取的是节点的数据值，
• 成员取用时取的是节点的成员。

另外，list 是一个双向链表，迭代器必须能够具备前移、后移的能力，所以 list 容器提供的是Bidirectional Iterators.（双向的迭代器）。

List 有一个重要的性质，插入操作和删除操作都不会造成原有 list 迭代器的失效。

3.6.4 常用API

//构造函数
list<T> lstT;//list 采用采用模板类实现,对象的默认构造形式：
list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem);//构造函数将 n 个 elem 拷贝给本身。
list(const list &lst);//拷贝构造函数。

//数据元素插入和删除操作
push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除第一个元素
insert(pos,elem);//在 pos 位置插 elem 元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在 pos 位置插入 n 个 elem 数据，无返回值。
insert(pos,beg,end);//在 pos 位置插入[beg,end)区间的数据，无返回值。
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除 pos 位置的数据，返回下一个数据的位置。
remove(elem);//删除容器中所有与 elem 值匹配的元素。

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

//赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将 n 个 elem 拷贝赋值给本身。
list& operator=(const list &lst);//重载等号操作符
swap(lst);//将 lst 与本身的元素互换。

//数据的存取
front();//返回第一个元素。
back();//返回最后一个元素。

//反转排序
reverse();//反转链表，比如 lst 包含 1,3,5 元素，运行此方法后，lst 就包
sort(); //list 排序

3.6.5 示例

#include <iostream>
#include <list>
#include<ctime>
#include<cstdlib>
using namespace std;
void fun01()
{
    list<int> nums;
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(3);
    nums.push_back(4);
    nums.push_back(1);

    //移除所有1
    nums.remove(1);
    list<int>::const_iterator it = nums.begin();
    for(; it != nums.end(); it++)
    {
        cout << *it << endl;
    }
}

void print(list<char> &str)
{
    list<char>::const_iterator it = str.begin();
    for(; it != str.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
void fun02()
{
    list<char> str;
    char cs[] = "hello";
    str.assign(cs,cs+5);
    print(str);
    str.reverse();
    print(str);
}

void print(list<int> &ns)
{
    list<int>::const_iterator it = ns.begin();
    for(; it != ns.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
void fun03()
{
    list<int> nums;
    srand(time(NULL));
    for(int i = 0; i < 10; i++)
    {
        int x = rand() % 100;
        nums.push_back(x);
    }
    print(nums);

    nums.sort();
    print(nums);
}
int main(int argc, char *argv[])
{
    fun01();
    cout << "----------------" << endl;
    fun02();
    cout << "----------------" << endl;
    fun03();
    return 0;
}

结果：

2
3
4
----------------
h e l l o 
o l l e h 
----------------
12 94 6 82 36 10 6 18 54 26 
6 6 10 12 18 26 36 54 82 94 

3.7 set/multiset

3.7.1 set概念

set (集合)的特性是所有元素都会根据元素的键值自动被排序。

set 的元素即是键值（key）又是实值(value)， 不允许两个元素有相同的键值。

set 的 iterator 是一种 const_iterator， 不允许修改set的键值。

set 拥有和 list 某些相同的性质，当对容器中的元素进行插入操作或者删除操作的时候，操作之前的迭代器，在操作完成之后依然有效，被删除的那个元素的迭代器必然是一个例外。

3.7.2 set数据结构

multiset 特性及用法和 set 完全相同，唯一的差别在于它允许键值重复。set 和multiset 的 底层实现是红黑树，红黑树为平衡二叉树的一种。

二叉树 就是任何节点最多只允许有两个字节点。分别是左子结点和右子节点：

二叉搜索树，是指二叉树中的节点按照一定的规则进行排序，使得对二叉树中元素访问更加高效:

二叉搜索树的 放置规则 是：

任何节点的元素值一定大于其左子树中的每一个节点的元素值，并且小于其右子树的值。因此从根节点一直向左走，一直到无路可走，即得到最小值，一直向右走，直至无路可走，可得到最大值。那么在二叉搜索树中找到最大元素和最小元素是非常简单的事情。

如上图所示：那么当一个二叉搜索树的左子树和右子树不平衡的时候，那么搜索依据上图表示，搜索 9所花费的时间要比搜索 17 所花费的时间要多，由于我们的输入或者经过我们插入或者删除操作，二叉树失去平衡，造成搜索效率降低。

所以我们有了一个平衡二叉树的概念，所谓的平衡不是指的完全平衡。

3.7.3 常用API

//构造函数
set<T> st;//set 默认构造函数：
mulitset<T> mst; //multiset 默认构造函数:
set(const set &st);//拷贝构造函数

//赋值操作
set& operator=(const set &st);//重载等号操作符
swap(st);//交换两个集合容器大小操作
size();//返回容器中元素的数目
empty();//判断容器是否为空

//插入和删除操作
insert(elem);//在容器中插入元素。
clear();//清除所有元素
erase(pos);//删除 pos 迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(elem);//删除容器中值为 elem 的元素。

//查找操作
find(key);//查找键 key 是否存在,若存在，返回该键的元素的迭代器；若不存在，返回 set.end();
count(key);//查找键 key 的元素个数
lower_bound(keyElem);//下限返回第一个 key>=keyElem 元素的迭代器。
upper_bound(keyElem);//上限返回第一个 key>keyElem 元素的迭代器。
equal_range(keyElem);//返回容器中 key 与 keyElem 相等的上下限的两个迭代器。

3.7.4 示例

#include <iostream>
#include <set>
#include <string>
using namespace std;
void print(set<int> sets)
{
    set<int>::const_iterator it = sets.begin();
    while(it != sets.end())
    {
        cout << *it << " ";
        it++;
    }
    cout << endl;
}
void fun01()
{
    set<int> sets;
    sets.insert(1);
    sets.insert(4);
    sets.insert(3);
    sets.insert(2);
    sets.insert(1);
    //set中数据不可重复
    print(sets);
}
void print(multiset<int> sets)
{
    multiset<int>::const_iterator it = sets.begin();
    while(it != sets.end())
    {
        cout << *it << " ";
        it++;
    }
    cout << endl;
}
void fun02()
{
    multiset<int> sets;
    sets.insert(1);
    sets.insert(4);
    sets.insert(3);
    sets.insert(2);
    sets.insert(1);

    //multiset中可以重复
    print(sets);
}

void fun03()
{
    set<int> sets;
    sets.insert(1);
    sets.insert(4);
    sets.insert(3);
    sets.insert(2);
    sets.insert(1);

    //查找1，返回set.end()
    set<int>::const_iterator it = sets.find(1);
    cout << *it << endl;
    //查找key的个数
    int count = sets.count(10);
    cout << count << endl;
}

void fun04()
{
    set<int> sets;
    sets.insert(10);
    sets.insert(20);
    sets.insert(30);
    sets.insert(40);
    sets.insert(50);

    cout << "寻找30时的下限的值" << *(sets.lower_bound(30)) << endl;
    cout << "寻找30时的上限的值" << *(sets.upper_bound(30)) << endl;

    cout << "寻找35时的下限的值" << *(sets.lower_bound(35)) << endl;
    cout << "寻找35时的上限的值" << *(sets.upper_bound(35)) << endl;
    //寻找30时的上下限
    //pair 对组
    //对组:一组中存储两个元素,一个成员是键,一个成员是值
    //键对应的成员是first
    //值对应的成员是second
    pair<set<int>::const_iterator, set<int>::const_iterator> p = sets.equal_range(30);
    cout << *(p.first) << " " << *(p.second) << endl;
}
//1,定义一个类
class Com{
public:
    //2,在该类中重载()运算符
    bool operator()(int v1,int v2)
    {
        return v1 > v2;
    }
};

void fun05()
{
    //3创建set对象时传入定义的类
    set<int,Com> sets;
    sets.insert(1);
    sets.insert(4);
    sets.insert(3);
    sets.insert(5);
    sets.insert(2);

    set<int,Com>::const_iterator it = sets.begin();
    for(; it != sets.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}

class Person{
    friend void fun06();
    string name;
    int age;
public:
    Person(){}
    Person(string name,int age)
    {
        this->name = name;
        this->age = age;
    }
    int getAge(){
        return age;
    }
    string getName()
    {
        return name;
    }
};
class ComPerson{
public:
    bool operator()(Person p1,Person p2)
    {
        if(p1.getAge() == p2.getAge())
        {
            int tag = p1.getName().compare(p2.getName());
            if(tag == 0)
            {
                return false;//此时表示姓名与年龄都相同,返回flase,set将不在存储
            }
            else{
                return true;//此时表示姓名不相同,年龄相同,返回true,set将存储
            }

        }
        return p1.getAge() > p2.getAge();
    }
};
void fun06()
{
    set<Person,ComPerson> ps;
    Person p1("张三1",18);
    Person p2("张三",38);
    Person p3("张三",12);
    Person p4("张三",22);
    Person p5("张三2",18);
    ps.insert(p1);
    ps.insert(p2);
    ps.insert(p3);
    ps.insert(p4);
    ps.insert(p5);

    set<Person,ComPerson>::const_iterator it = ps.begin();
    for(; it != ps.end(); it++)
    {
        cout << (*it).name << " " << (*it).age << endl;
    }
}
int main(int argc, char *argv[])
{
    fun01();
    cout << "---------------------" << endl;
    fun02();
    cout << "---------------------" << endl;
    fun03();
    cout << "---------------------" << endl;
    fun04();
    cout << "---------------------" << endl;
    fun05();
    cout << "---------------------" << endl;
    fun06();
    return 0;
}

结果：

1 2 3 4 
---------------------
1 1 2 3 4 
---------------------
1
0
---------------------
寻找30时的下限的值30
寻找30时的上限的值40
寻找35时的下限的值40
寻找35时的上限的值40
30 40
---------------------
5 4 3 2 1 
---------------------
张三 38
张三 22
张三2 18
张三1 18
张三 12

3.8.5 对组(pair)

对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用 pair 的两个公有属性 first 和 second 访问。

类模板：template <class T1, class T2> class pair

用法1：隐式调用有参构造

pair<string, int> pair1(string("name"), 20);
cout << pair1.first << endl;
cout << pair1.second << endl;

//name
//20

用法2：显式调用有参构造

pair<string, int> pair2 = make_pair("name", 30);
cout << pair2.first << endl;
cout << pair2.second << endl;

用法3：拷贝构造

pair<string, int> pair3 = pair2; // 拷贝构造函数
cout << pair3.first << endl;
cout << pair3.second << endl;

示例：

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int main(int argc, char *argv[])
{
    pair<int, string> p1(1, "张三");
    pair<int, string> p2 = make_pair(2, "lucy");
    cout << "id=" << p1.first << ",name=" << p1.second << endl;
    cout << "id=" << p2.first << ",name=" << p2.second << endl;
    return 0;
    return 0;
}

//id=1,name=张三
//id=2,name=lucy

3.8 map/multmap

3.8.1 map概念

map 的特性是所有元素都会根据元素的 键值自动排序。

map 所有的元素都是pair，同时拥有实值和键值，pair 的第一元素被视为键值，第二元素被视为实值，map 不允许两个元素有相同的键值。 【map键值是唯一的】

multimap 和 map 的操作类似，唯一区别 multimap 键值可重复。map 和 multimap 都是以红黑树为底层实现机制。

注意：map迭代器的元素是pair对组，通过pair对象获取键值(first)和实值(second)。

3.8.2 常用API

//构造函数
map<T1, T2> mapTT;//map 默认构造函数:
map(const map &mp);//拷贝构造函数

//赋值操作
map& operator=(const map &mp);//重载等号操作符
swap(mp);//交换两个集合容器

//大小操作
size();//返回容器中元素的数目
empty();//判断容器是否为空
//插入数据元素操作
map.insert(...); //往容器插入元素，返回 pair<iterator,bool>
map<int, string> mapStu;
// 第一种 通过 pair 的方式插入对象
mapStu.insert(pair<int, string>(3, "小张"));
// 第二种 通过 pair 的方式插入对象
mapStu.inset(make_pair(-1, "校长"));
// 第三种 通过 value_type 的方式插入对象
mapStu.insert(map<int, string>::value_type(1, "小李"));
// 第四种 通过数组的方式插入值
mapStu[3] = "小刘";
mapStu[5] = "小王";

//删除操作
clear();//删除所有元素
erase(pos);//删除 pos 迭代器所指的元素，返回下一个元素的迭代器。
erase(beg,end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(keyElem);//删除容器中 key 为 keyElem 的对组。

//查找操作
find(key);//查找键 key 是否存在,若存在，返回该键的元素的迭代器； /若不存在，返回 map.end();
count(keyElem);//返回容器中 key 为 keyElem 的对组个数。 对 map 来说，要么是 0，要么是 1。对 multimap 来说，值可能大于 1。
lower_bound(keyElem);//返回第一个 key>=keyElem 元素的迭代器。
upper_bound(keyElem);//返回第一个 key>keyElem 元素的迭代器。
equal_range(keyElem);//返回容器中 key 与 keyElem 相等的上下限的两个迭代器

3.8.3 示例

#include <iostream>
#include <map>
#include <string>
using namespace std;
void fun01()
{
    map<int,string> maps;
    //map 存储方式1
    maps.insert(pair<int,string>(10086,"移动"));
    //map 存储方式2
    maps.insert(make_pair(10000,"电信"));
    //map 存储方式3
    maps.insert(map<int,string>::value_type(10010,"联通"));
    //map 存储方式4
    maps[95588] = "ICBC";

    map<int,string>::const_iterator it = maps.begin();
    for(; it != maps.end(); it++)
    {
        cout << (*it).first << " " << (*it).second << endl;
    }

}

class Person{
    friend void fun02();
    friend void fun03();
    string name;
    int age;
public:
    Person(){}
    Person(string name,int age)
    {
        this->name = name;
        this->age = age;
    }
};
void fun02()
{
    map<int,Person> classes;
    classes[1] = Person("张三1",18);
    classes[2] = Person("张三2",19);
    classes[3] = Person("张三3",21);
    classes[4] = Person("张三4",17);
    classes[1] = Person("张三5",16);//键相同则为替换

    map<int,Person>::const_iterator it = classes.begin();
    for(; it != classes.end(); it++)
    {
        cout << (*it).first << " " << (*it).second.name << " " << (*it).second.age << endl;
    }
}

void fun03()
{
    multimap<int,Person> classes;
    classes.insert(make_pair(1,Person("张三",18)));
    classes.insert(make_pair(1,Person("张三",19)));

    multimap<int,Person>::const_iterator it = classes.begin();
    for(; it != classes.end(); it++)
    {
        cout << (*it).first << " " << (*it).second.name << " " << (*it).second.age << endl;
    }
}
int main(int argc, char *argv[])
{
    fun01();
    cout << "--------------" << endl;
    fun02();
    cout << "--------------" << endl;
    fun03();
    return 0;
}

结果：

10000 电信
10010 联通
10086 移动
95588 ICBC
--------------
1 张三5 16
2 张三2 19
3 张三3 21
4 张三4 17
--------------
1 张三 18
1 张三 19

4. 总结

• vector ：单端动态数组 随机访问迭代器

  • 比如软件历史操作记录的存储，我们经常要查看历史记录，比如上一次的记录，上上次的记录，但却不会去删除记录，因为记录是事实的描述。
  • 数据结构：数组

• deque：双端动态数组 随机访问迭代器

  • 比如排队购票系统，对排队者的存储可以采用 deque，支持头端的快速移除，尾端的快速添加

• stack 栈容器

  • 没有迭代器 先进后出

• queue 队列容器

  • 没有迭代器 先进先出

• list 链表容器

  • 双向迭代器
  • 比如公交车乘客的存储，随时可能有乘客下车，支持频繁的不确实位置元素的移除插入
  • 数据结构：双链表

• set 容器

  • 只有键值 键值不能重复 自动排序 只读迭代器
  • 比如对手机游戏的个人得分记录的存储，存储要求从高 分到低分的顺序排列。
  • 数据结构：红黑树

• map容器： 键值-实值成对出现 键值不能重复 自动排序 只读迭代器

  • 比如按 ID 号存储十万个用户，想要快速要通过 ID 查找对应的用户。
  • 数据结构：红黑树