C++梁哥笔记day23 | 我的日常分享

C++梁哥笔记day23

发表于2021-01-23更新于2021-01-23字数统计14.4k阅读时长180分

常用容器

一、string 容器

1.1 string容器基本概念

C风格字符串（以空字符结尾的字符数组）太过复杂化难于掌握，不适合大程序的开发，所以C++标准库定义了一种string类，定义在头文件。

string 和 C 风格的字符串对比：

  • char *是一个指针，string是一个类，string 封装了char，管理这个字符串，是一个char型的容器

  • string封装了很多实用的成员方法，查找find、拷贝copy、删除delete、替换replace、插入insert

  • 不用考虑内存释放和越界，string管理char *所分配的内存。每一次string的复制，取值都由string类负责维护，不用担心复制越界的取值越界等。

1.2 string容器常用操作

1.2.1 string构造函数

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

1.2.2 string基本赋值操作

1
2
3
4
5
6
7
8
string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串
string& operator=(const string &s);//把字符串s赋给当前的字符串
string& operator=(char c);//把字符c赋给当前的字符串
string& assing(const char* s);//把字符串s赋给当前的字符串
string& assing(const char* s,int n)//把字符串前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个字符赋给当前字符串

1.2.3 string存取字符操作

1
2
char& operator[](int n);//通过[]的方式存取字符
char& at(int n);//通过at方法存取字符

[] 和 at 的区别：如果越界[]不会抛出异常，at会抛出异常

1.2.4 string拼接操作

1
2
3
4
5
6
7
8
string& operator+=(const string &str);//重载+= 将一个string对象拼接在另一个string对象后面
string& operator+=(const char *str);//重载+= 将一个字符串拼接在string对象后面
string& operator+=(const char c);//重载+= 将一个字符拼接在string对象后面
string& append(const char *s);//将字符串s拼接在当前字符串string对象后面
string& append(const char *s,int n);//将字符串s的前n个字符连接到当前字符串结尾
string& append(const string &s);//将一个字符串对象拼接在另一个字符串对象string结尾
string& append(const string &s,int pos,int n);//将字符串对象s从pos开始的n个字符拼接到当前字符串结尾
string& append(int n,char c);//在当前字符串后面添加n个字符c

1.2.5 string查找和替换

1
2
3
4
5
6
7
8
9
10
int find(const string &str,int pos = 0) const;//从pos开始查找str第一次出现的位置
int find(const char *s,int pos = 0) const;//从pos开始查找str第一次出现的位置
int find(const char *s,int pos = 0,int n) const;//从pos位置查找s的前n个字符第一次出现的位置
int find(const char c,int pos = 0) const;//从pos位置开始查找字符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

1.2.6 string 比较操作

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

C语言中的比较函数：

  • strcmp：遇到‘\0’结束比较

  • memcmp：内存比较函数，不会因为‘\0’，结束

1.2.7 string 子串

1
string substr(int pos = 0, int n = npos) const;//提取从pos到pos+n 返回由pos开始的前n个字符组成的字符串

strtok：C语言字符串切割。

可以利用substr实现C语言的字符串切割

1.2.8 string的插入和删除

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

1.2.9 string 和 C风格字符串的转换

1
2
3
4
5
6
7
//string 转 char *
string str = "hello world";
const char *cstr = str.c_str();
//char * string str 转string
char *s = "hello world";
string str1(s);
string str2 = s;

在C++中存在一个从const char到string的隐式类型转换，却不存在从一个string对象到Cstring的自动类型转换。对于string类型的字符串，可以通过c_str()函数返回string对象对象的Cstring。通常，程序员在整个程序中应坚持使用string类对象，直到必须将内容转化为 char 时，才将其转换为Cstring。

提示：伪类修改string字符串的内容，下标操作符[]和at都会返回字符的引用。但当字符串的内存被重新分配之后，可能会发生错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string s = "abcdefg";
char &a = s[2];
char &b = s[3];

a = '1';
b = '2';

cout<<s<<endl;
cout<<(int *)s.c_str()<<endl;

s = "ppppppppppppppppp";

//a = '1';
//b = '2';

cout<<s<<endl;
cout<<(int *)s.c_str()<<endl;

二、vector容器（单端动态数组）

vector 的数据安排以及操作方式，与array非常相似，两者的唯一差别在于空间的运用的灵活性。array是静态空间，一旦配置了就不能改变，更换大一点或者小一点的空间，可以，但是一切琐碎的操作得由自己来，首先配置一块新的空间，然后将旧空间的数据搬进新空间，再释放原来的空间。vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新的元素。因此vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必害怕空间不足而一开始就要求一个大块头的array了。vector的实现技术，关键在于对其大小的控制以及重新配置时数据移动效率，一旦vector旧空间满了，如果客户每增加一个元素，vector内部只是扩充一个元素的空间，实为不智，因为所谓的扩充空间（不论多大），一如刚所说，是“配置新空间–数据移动–释放旧空间”的大工程，时间成本很高，应该加入某种未雨绸缪的考虑，稍后我们便可以看到vector的空间配置策略。

image-20210123191743685

2.1 vector迭代器

vector维护一个线性空间，所以元素的性别如何，普通指针都可以作为vector的迭代器，因为vector迭代器所需要的的操作行为，如operator->、operator++、operator–、operator+、operator-、operator+=、operator-=，普通指针天生具备。vector支持随机存取，而普通指针正有着这样的能力，所以vector提供的是随机访问迭代器（Random Access Iterators）。

vector容器的迭代器：随机访问迭代器

随机访问迭代器：迭代器+n 可以通过编译就是随机访问迭代器

2.1.1 vector的容量（capacity）和大小（size）的区别

容量：空间能容纳元素最大个数

大小：空间实际存放元素个数

1
2
3
4
5
6
7
8
9
void test01(){
    vector<int> v;
    //插入100个元素
    for(int i = 0; i < 100; i++){
        v.push_back(i);
    }
    cout<<"v的容量："<<v.capacity()<<endl;
    cout<<"v的大小："<<v.size()<<endl;
}

运行结果：

image-20210123193712368

分析：为什么容量大于大小，因为vector有未雨绸缪机制，每次分配的空间会大于实际所需要的空间，后面会详细分析的。

2.1.2 vector 的数据结构

vector所采用的数据结构非常简单，线性连续空间，它以两个迭代器myfirst和mylast分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器_myend指向整块连续内存空间的尾端。为了降低空间配置时的速度成本，vector实际配置的大小可能会比客户端需求带一些，以备将来可能的扩充，这边是容量的概念。换句话说，一个vector的容量永远大于或等于其大小，一旦容量等于大小，便是满载，下次再有新增元素，整个vector容器就得另觅居所。

注意：所谓动态增加大小，并不是在原空间之后续接新空间（因为无法保证原空间之后尚有可配置的空间），而是重新申请一块更大的内存空间，然后将原数据拷贝到新空间中，并释放原空间。因此，对vector的任何操作，一旦引起空间的重新配置，指向原vector的所有迭代器就都失效了。这是程序员容易犯的一个小错误，务必小心。

2.1.3 vector另寻空间的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void test02(){
    vector<int> v;
    int *p = nullptr;
    int count = 0;//记录另寻空间的次数
    for(int i = 0; i < 1000; i++){
        v.push_back(i);
        if(p != &v[0]){
            count++;
            p = &v[0];
        }
    }
    cout<<"v的容量："<<v.capacity()<<endl;
    cout<<"v的大小："<<v.size()<<endl;
    cout<<"v另寻空间次数："<<count<<endl;
}

运行结果：

image-20210123195907730

只要空间满了 就会另寻空间

2.1.4 vector的未雨绸缪机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void test03(){
    vector<int> v;
    int *p = nullptr;
    int count = 0;//记录另寻空间的次数
    for(int i = 0; i < 1000; i++){
        if(p != &v[0]){
            count++;
            p = &v[0];
            cout<<"--------"<<count<<"--------"<<endl;
        }
        v.push_back(i);
        cout<<"v的容量："<<v.capacity()<<",v的大小："<<v.size()<<endl;
    }
}

运行结果：

image-20210123200930718

2.1.5 vector常用api操作

  • vector构造函数

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

    案例：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    void printVectorInt(vector<int> v){
        for(vector<int>::iterator it = v.begin();it!=v.end();it++){
            cout<<*it<<" ";
        }
        cout<<endl;
    }
    void test04(){
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        v1.push_back(5);
        printVectorInt(v1);
        cout<<"*********"<<endl;
        vector<int> v2 = vector<int>(v1.begin()+1,v1.end()-2);
        printVectorInt(v2);
        int arr[]={12,13,14,15,16};
        vector<int> v3(arr,arr+sizeof(arr)/sizeof(int));
        printVectorInt(v3);
        cout<<"*********"<<endl;
        vector<int> v4(5,59);
        printVectorInt(v4);
        cout<<"*********"<<endl;
        vector<int> v5 = v4;
        vector<int> v6(v4);
        printVectorInt(v5);
        printVectorInt(v6);
    }

    运行结果：

image-20210123203345456

  • vector常用赋值操作

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

  • vector大小操作

    1
    2
    3
    4
    5
    6
    size();//返回容器中元素的个数
    empty();//判断容器是否为空
    resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值(0)填充新位置。如容器变短，则末尾超出容器长度的元素被删除。
    resize(int num,elem);//重新指定容器的长度为num，若容器变长，则以elem填充新位置。如容器变短，则末尾超出容器长度的元素被删除。
    capacity();//返回容器的容量
    reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问

注意：resize只是作用于容器的size，不会更改容器的容量capacity，除非resize大于原来容器的容量。

案例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void test01(){
    vector<int> v(5,10);
    printVectorInt(v);
    cout<<"size:"<<v.size()<<",capacity:"<<v.capacity()<<endl;
    cout<<"***********************"<<endl;

    v.resize(10);
    printVectorInt(v);//10 10 10 10 10 0 0 0 0 0
    cout<<"size:"<<v.size()<<",capacity:"<<v.capacity()<<endl;
    cout<<"***********************"<<endl;

    v.resize(12,59);
    printVectorInt(v);//10 10 10 10 10 0 0 0 0 0 59 59
    cout<<"size:"<<v.size()<<",capacity:"<<v.capacity()<<endl;
    cout<<"***********************"<<endl;

    v.resize(7);
    printVectorInt(v);//10 10 10 10 10 0 0
    cout<<"size:"<<v.size()<<",capacity:"<<v.capacity()<<endl;
    cout<<"***********************"<<endl;
}

运行结果：

image-20210124232927175

vector v(5,10); v.resize();这两个函数vector容器容量的增长规律好像不是2的n次方了。反正容量肯定比大小大。

利用resize和swap收缩容器容量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void test02(){
    vector<int> v;
    for(int i=0;i<1000;i++){
        v.push_back(i);
    }
    cout<<"size:"<<v.size()<<",capacity:"<<v.capacity()<<endl;
    //需求：开始插入了1000个元素 现在我感觉用不上这么多空间 要删掉一些空间
    //1、使用resize
    v.resize(12);
    cout<<"size:"<<v.size()<<",capacity:"<<v.capacity()<<endl;//大小变为12，当时容量仍然是1024
    //2、利用resize和swap收缩容器容量
    v.resize(13);
    vector<int>(v).swap(v);
    cout<<"size:"<<v.size()<<",capacity:"<<v.capacity()<<endl;
}

运行结果：

image-20210124233729436

分析：vector<int>(v).swap(v);——> vector(v)是一个匿名对象，调用拷贝构造，因为v的size为13，所以匿名对象的size和capacity都为13，然后匿名对象调用swap与v交换，所以最后的v变为了匿名对象，即最后的v的size和capacity都为13，起到了收缩容量的功能。

reserve预留空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//一次性给够空间 叫空间预留
void test03(){
    vector<int> v;
    int count = 0;
    int *p = NULL;
    for(int i=0;i<1000;i++){
        v.push_back(i);
        if(p!=&v[0]){
            count++;
            p=&v[0];
        }
    }
    cout<<"另寻空间次数为："<<count<<endl;

    vector<int> v1;
    int count1 = 0;
    int *p1 = NULL;
    v1.reserve(1000);
    for(int i=0;i<1000;i++){
        v1.push_back(i);
        if(p1!=&v1[0]){
            count1++;
            p1=&v1[0];
        }
    }
    cout<<"另寻空间次数为："<<count1<<endl;
}

运行结果：

image-20210124235244686

分析：如果不预留空间，当空间不足时，会自动另寻空间；而我要插入1000个元素，开始我就直接预留了1000个元素，告诉编译器我等下要插入1000个数据，你不用一个试探我要开多少，我就是要开1000，你直接给我开辟1000个元素所需空间，所以寻空间次数为1；

  • vector数据存取操作

    1
    2
    3
    4
    at(int idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range异常
    operator[];//返回索引idx所指的数据，越界时不会抛出异常，程序会报错
    front();//返回容器中第一个数据元素
    back();//返回容器中最后一个数据元素

    与string容器类似，下标越界，at会抛出异常，而[]不会抛出异常。

  • vector 插入和删除操作

    1
    2
    3
    4
    5
    6
    insert(const_iterator pos,int count,elem);//迭代器指向的位置pos插入count个元素elem
    push_back(ele);//尾部插入元素ele
    pop_back();//删除末尾一个元素
    erase(const_iterator start,const_iterator end);//删除迭代器从start到end之间的元素
    erase(const_iterator pos);//删除迭代器指向位置pos的元素
    clear();//删除容器中所有元素

    pop_back erase clear 不会更改容器的容量，只会更改容器的大小

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    void test04(){
        vector<int> v1(5,9);
        printVectorInt(v1);
        cout<<"size:"<<v1.size()<<",capacity:"<<v1.capacity()<<endl;
        cout<<"***********************"<<endl;

        v1.push_back(12);//尾部插入12
        printVectorInt(v1);
        cout<<"size:"<<v1.size()<<",capacity:"<<v1.capacity()<<endl;
        cout<<"***********************"<<endl;

        v1.pop_back();//删除尾部一个元素
        printVectorInt(v1);
        cout<<"size:"<<v1.size()<<",capacity:"<<v1.capacity()<<endl;
        cout<<"***********************"<<endl;

        v1.erase(v1.begin()+1,v1.end()-2);//删除v1.begin()+1与v1.end()-2之间的元素
        printVectorInt(v1);
        cout<<"size:"<<v1.size()<<",capacity:"<<v1.capacity()<<endl;
        cout<<"***********************"<<endl;

        v1.erase(v1.begin()+1);//删除迭代器v1.begin()+1位置的元素
        printVectorInt(v1);
        cout<<"size:"<<v1.size()<<",capacity:"<<v1.capacity()<<endl;
        cout<<"***********************"<<endl;

        v1.clear();//删除容器中所有元素
        cout<<"#";
        printVectorInt(v1);
        cout<<"#"<<endl;
        cout<<"size:"<<v1.size()<<",capacity:"<<v1.capacity()<<endl;
        cout<<"***********************"<<endl;
    }

    运行结果：

    image-20210125000523647

三、deque容器（双端动态数组）

3.1 deque容器基本概念

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

image-20210125181946475

deque容器和vector容器最大差异，一在于deque允许使用常数项时间（固定的时间，不会因为数据的多少而变化）对头部进行元素的插入和删除。二在于deque没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新空间并连接起来，换句话说，像vector那样，“旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque身上是不会发生的。也因此，deque没有必须要提供所谓的空间预留(reserve)功能，虽然deque容器也提供了Random Access Iterator（随机访问迭代器），但是它的迭代器并不是普通的指针，其复杂度和vector不是一个量级，这当然影响各个运算的层面。因此，除非有必要，我们应该尽可能的使用vector，而不是deque。对deque进行的排序操作，为了最高效率，可将deque先完整的复制到vector中，对vector容器进行排序，在复制回deque。

3.2 deque容器实现原理

deque容器是连续的空间，至少逻辑上看来如此，连续线性空间总是令我们联想到array和vector，array是无法成长的，vector虽可成长，却只能像尾端成长，而且其成长其实是一个假象，事实上是三大步骤：

1、申请更大空间

2、原数据复制到新空间

3、释放原空间

如果不是vector每次配置新的空间时都留有余裕，其成长所带来的代价是非常大的。deque是由一段一段的定量的连续空间构成的。一旦有必要在deque容器的前端或者尾端增加新的空间，便配置一段连续定量的空间，串联在deque的头端或者尾端。deque最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机读取的接口，避开了重新配置空间、复制、释放的轮回，代价就是复杂的迭代器架构。既然deque是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象，数据结构的设计及迭代器的前进后退操作颇为繁琐。deque代码实现远比vector或list多得多。deque采取一块所谓的map（注意，不是STL的map容器）作为主控，这里所谓的map是一小块连续的内存空间，其中每一个元素（此处称为一个节点）都是一个指针，指向另一端连续性内存空间，称作缓冲区。缓冲区才是deque的存储空间的主体。

image-20210125184535630

3.3 deque常用API

3.3.1 deque构造函数

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

3.3.2 deque赋值操作

1
2
3
4
assign(beg,end);//将区间[beg,end)区间中的元素赋值给本身
assign(n,elem);//将n个elem赋值给本身
deque& operator=(const deque &deq);//重载= 拷贝函数
swap(deq);//将deq与本身交换

3.3.3 deque大小操作

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

3.3.4 deque双端插入和删除操作

1
2
3
4
push_back(elem);//在容器尾部添加一个数据
push_front(elem);//在容器头部添加一个数据
pop_back(elem);//在容器尾部删除一个数据
pop_front(elem);//在容器头部删除一个数据

3.3.5 deque数据存取

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

3.3.6 deque插入操作

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

3.3.7 deque删除操作

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

3.4 案例：

有5名选手，选手A、B、C、D、E，10个评委分别对每一个选手打分，去除最高分，去除评委中最低分，取平均分。

  1. 创建无名选手，放到vector容器中
  2. 遍历vector容器，取出来每一个选手，执行for循环，可以把10个评分打分存到deque容器中
  3. sort算法对deque容器中的分数排序，pop_back pop_front 去除最高和最低分
  4. deque容器遍历一遍，累加分数，累加分数/d.size()
  5. person.score = 平均分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <time.h>
#include <algorithm>
using namespace std;
class Person{
private:
    string name;
    int score;
public:
    friend void printVectorPerson(vector<Person> &v);
    friend void playGame(vector<Person> &v);
    Person(string name,int score){
        this->name = name;
        this->score = score;
    }

};
void createPerson(vector<Person> &v){
    //5名选手ABCDE
    string nameTmp="ABCDE";
    for(int i=0;i<5;i++){
//        string name = "选手"+nameTmp[i];
        string name = "选手";
        name+=nameTmp[i];
        //将选手姓名和分数0 放入vector容器中
//        Person obTmp(name,0);
//        v.push_back(obTmp);
        v.push_back(Person(name,0));//可以使用匿名对象
    }
}
void printVectorPerson(vector<Person> &v){
    for(vector<Person>::iterator it=v.begin();it!=v.end();it++){
        cout<<(*it).name<<","<<(*it).score<<endl;
    }
    cout<<endl;
}
void playGame(vector<Person> &v){
    //设置 随机数种子
    srand(time(NULL));
    for(vector<Person>::iterator it=v.begin();it!=v.end();it++){
        //评委打分
        deque<int> d;
        for(int i=0;i<10;i++){
            d.push_back(rand()%41+60);
        }
        // 排序
        sort(d.begin(),d.end());
        //去掉最高分
        d.pop_back();
        //去掉最低分
        d.pop_front();
        //记录总分
        int sum=accumulate(d.begin(),d.end(),0);
        (*it).score = sum/d.size();
    }
}

int main(int argc, char *argv[])
{
    //1.定义一个vector容器存放person
    vector<Person> v;
    createPerson(v);
    //3.开始比赛
    playGame(v);
    //3.遍历vector容器
    printVectorPerson(v);
    return 0;
}

运行结果：

image-20210125210922040

四、stack容器（栈特点）

4.1 stack容器基本概念

stack是一种先进后出（First In Last Out,FILO）的数据结构，它只有一个出口，形式如图所示。stack容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端外，没有任何其他方法可以存取stack的其他元素。换言之，stack不允许有遍历行为。有元素推入栈的操作称为：push，将元素退出stack的操作称为pop。top()永远指向栈顶元素。

image-20210125213522544

image-20210125213544393

白画了一张图-_- 提供图片了….

4.2 stack没有迭代器

stack所有元素的进出都必须符合“先进后出”的条件，只有stack顶端的元素才有机会被外界取用。stack不提供遍历功能，也不提供迭代器。

4.3 stack常用API

4.3.1 stack构造函数

1
2
stack<T> stkT;//stack 采用模板类实现，stack对象的默认构造形式
stack(const stack &stk);//拷贝构造函数

4.3.2 stack赋值操作

1
stack& operator=(const stack &stk);//重载= 运算符

4.3.3 stack数据存取操作

1
2
3
push(elem);//向栈顶添加元素elem
pop();//从栈顶移除一个元素
top();//返回栈顶元素

4.3.4 stack大小操作

1
2
empty();//判断栈是否为空
size();//返回栈的大小

案例：打印栈中所有元素

1
2
3
4
5
6
7
8
9
10
11
void test01(){
    stack<int> s;
    s.push(12);
    s.push(32);
    s.push(36);
    s.push(66);
    while (!s.empty()) {
        cout<<s.top()<<endl;
        s.pop();
    }
}

image-20210125215128505

五、queue 队列容器

5.1 queue容器基本概念

queue是一种先进先出（First In First Out,FIFO）的数据结构，它有两个出口，queue容器允许从一端新增元素，从另一端移除元素。

image-20210125215403369

5.2 queue没有迭代器

queue所有元素的进出都必须符合“先进先出”的条件，只有queue的顶端元素，才有机会被外界取用。queue不提供遍历功能，也不提供迭代器。

5.3 queue常用API

5.3.1 queue构造函数

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

5.3.2 queue存取、插入和删除操作

1
2
3
4
push(elem);//往队尾添加元素
pop();//从队头移除第一个元素
back();//返回最后一个元素
front();//返回第一个元素

5.3.3 queue赋值操作

1
queue& operator=(const queue &que);//重载=运算符

5.3.4 queue大小操作

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

六、list容器（链表）

6.1 list容器的概念

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。链表由一系列节点（链表中每一个元素称为节点）组成，节点可以在运行时动态生成、每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。相较于vector的连续线性空间，list就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或释放一个元素空间，因此，对于任何位置的元素插入或元素的移除，list永远是常数项时间。list和vector是两个最常被使用的容器。list容器是一个双向链表。

image-20210126152718603

采用动态存储分配，不会造成内存浪费和溢出，链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素，链表灵活，但是空间和时间额外耗费较大。

6.2 list容器的迭代器

list容器不能像vector一样以普通指针作为迭代器，因为其节点不能保证在同一块连续的内存空间上，list迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓“list递增、递减、取值、成员取用”是指，递增时指向下一个节点、递减时指向上一个节点、取值时取得是节点的数据值、成员取用时取的是节点的成员。由于list是一个双向链表，迭代器必须能够具备前移、后移的能力，所以list容器提供的是Bidirectional Iterator（双向迭代器）。list有一个重要的性质，插入操作和删除操作都不会造成原来的迭代器失效。这在vector是不成立的，因为vector的插入操作可能造成内存的重新配置，导致原有的迭代器全部失效，甚至list元素的删除，也只有被删除的那个元素的迭代器失效，其他迭代器不受影响。

注意：list迭代器不支持+，但是支持++，++被重载了p=p->next;

image-20210126154912407

6.3 list容器的数据结构

list容器不仅是一个双向链表，还是一个循环的双向链表

image-20210126155816719

6.4 list常用API

6.4.1 list构造函数

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

6.4.2 list数据元素插入和删除操作

1
2
3
4
5
6
7
8
9
10
11
push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除一个元素
insert(pop,elem);//在pos位置插入元素elem，返回新数据的位置
insert(pop,n,elem);//在pos位置插入n个elem，无返回值
insert(pos,beg,end);//在pos位置插入区间[beg,end)的数据，无返回值
clear();//移除容器中所有数据
erase(beg,end);//删除区间[beg,end)的数据，返回下一个数据的位置
erase(pos);//删除pos位置的数据，返回下一个数据的位置
remove(elem);//删除容器中所有与elem值匹配的元素

6.4.3 list大小操作

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

6.4.4 list赋值操作

1
2
3
4
assign(beg,end);//将[beg,end)区间中的数据拷贝给本身
assign(n,elem);//将n个elem元素拷贝赋值给本身
list& operator=(const list &lst);//重载=运算符
swap(lst);//将lst与本身元素互换

6.4.5 list数据的存取

1
2
front();//返回第一个元素
back();//返回最后一个元素

6.4.6 list反转排序

1
2
reverse();//反转链表
sort();//list排序

注意：list 不支持系统提供的排序算法sort，系统提供的排序算法sort只支持随机访问迭代器。

6.5 list使用remove()删除自定义数据

如果使用remove删除某个节点必须重载==运算符，因为对于自定义数据类型，是不知道如何进行比较的。

image-20210126225832540

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Person{
private:
    string name;
    int age;
public:
    friend void printListPerson(list<Person> &L);
    Person(string name,int age){
        this->name = name;
        this->age = age;
    }
    //利用成员函数重载 少写一个参数
    bool operator ==(const Person &ob){
        if(this->name == ob.name && this->age == ob.age)
            return true;
        return false;
    }
};
void printListPerson(list<Person> &L){
    for(list<Person>::iterator it=L.begin();it!=L.end();it++){
        cout<<(*it).name<<" "<<(*it).age<<endl;
    }
}
void test02(){
    list<Person> L;
    L.push_back(Person("xiaohua",18));
    L.push_back(Person("xiaoming",19));
    L.push_back(Person("lucy",23));
    L.push_back(Person("jack",22));
    printListPerson(L);
    L.remove(Person("lucy",23));
    cout<<"--------------"<<endl;
    printListPerson(L);
}

运行结果：

image-20210126230404350

6.6 list对自定义数据进行sort()排序

image-20210126230517051

1、方法一：必须重载<运算符。因为对于自定义数据，sort不知道如何进行大小比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Person{
private:
    string name;
    int age;
public:
    friend void printListPerson(list<Person> &L);
    Person(string name,int age){
        this->name = name;
        this->age = age;
    }
    //重载<
    bool operator <(const Person &ob){
        return this->age < ob.age;
    }
};
void printListPerson(list<Person> &L){
    for(list<Person>::iterator it=L.begin();it!=L.end();it++){
        cout<<(*it).name<<" "<<(*it).age<<endl;
    }
}
void test03(){
    list<Person> L;
    L.push_back(Person("xiaohua",18));
    L.push_back(Person("xiaoming",19));
    L.push_back(Person("lucy",23));
    L.push_back(Person("jack",22));
    printListPerson(L);
    L.sort();
    cout<<"--------------"<<endl;
    printListPerson(L);
}

运行结果：

image-20210126230814854

2、方法二：指定排序规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Person{
private:
    string name;
    int age;
public:
    friend void printListPerson(list<Person> &L);
    friend bool myComparePerson(const Person &ob1,const Person &ob2);
    Person(string name,int age){
        this->name = name;
        this->age = age;
    }
};
bool myComparePerson(const Person &ob1,const Person &ob2){
    return ob1.age < ob2.age;
}
void printListPerson(list<Person> &L){
    for(list<Person>::iterator it=L.begin();it!=L.end();it++){
        cout<<(*it).name<<" "<<(*it).age<<endl;
    }
}
void test04(){
    list<Person> L;
    L.push_back(Person("xiaohua",18));
    L.push_back(Person("xiaoming",19));
    L.push_back(Person("lucy",23));
    L.push_back(Person("jack",22));
    printListPerson(L);
    L.sort(myComparePerson);//似乎不支持
    cout<<"--------------"<<endl;
    printListPerson(L);
}

vector容器进行自定义数据排序，也是一样的。要么重载运算符，要么指定排序规则。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Person{
private:
    string name;
    int age;
public:
    friend bool myComparePerson(const Person &ob1,const Person &ob2);
    friend void printVectorPerson(vector<Person> &v);
    Person(string name,int age){
        this->name = name;
        this->age = age;
    }
};
bool myComparePerson(const Person &ob1,const Person &ob2){
    return ob1.age < ob2.age;
}
void printVectorPerson(vector<Person> &v){
    for(vector<Person>::iterator it=v.begin();it!=v.end();it++){
        cout<<(*it).name<<" "<<(*it).age<<endl;
    }
}
void test05(){
    vector<Person> v;
    srand(time(NULL));
    for(int i=0;i<5;i++){
        string str="ABCDEFGHIJKL";
        string name="成员";
        name += str[i];
        v.push_back(Person(name,rand()%20+17));
    }
    printVectorPerson(v);
    //指定排序规则
    sort(v.begin(),v.end(),myComparePerson);
    cout<<"--------------"<<endl;
    printVectorPerson(v);
}

运行结果：

image-20210126235039695

6.7 仿函数指定排序规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Person{
public:
    string name;
    int age;
public:
    Person(string name,int age){
        this->name = name;
        this->age = age;
    }
};
void printVectorPerson(vector<Person> &v){
    for(vector<Person>::iterator it=v.begin();it!=v.end();it++){
        cout<<(*it).name<<" "<<(*it).age<<endl;
    }
}
class myComparePerson1{
public:
    bool operator()(const Person &ob1,const Person &ob2){
        return ob1.age < ob2.age;
    }
};
void test06(){
    vector<Person> v;
    srand(time(NULL));
    for(int i=0;i<5;i++){
        string str="ABCDEFGHIJKL";
        string name="成员";
        name += str[i];
        v.push_back(Person(name,rand()%20+17));
    }
    printVectorPerson(v);
    //使用匿名对象
    //sort(v.begin(),v.end(),myComparePerson1());
    //不使用匿名对象
    myComparePerson1 ob1;
    sort(v.begin(),v.end(),ob1);
    cout<<"--------------"<<endl;
    printVectorPerson(v);
}

运行结果：

image-20210126235331400

6.8 lambda表达式

lambda表达式是一个匿名函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void test07(){
    vector<Person> v;
    srand(time(NULL));
    for(int i=0;i<5;i++){
        string str="ABCDEFGHIJKL";
        string name="成员";
        name += str[i];
        v.push_back(Person(name,rand()%20+17));
    }
    printVectorPerson(v);
    //lambda表达式
    //[]函数名 ()参数列表 {}函数体
    sort(v.begin(),v.end(),[](const Person &ob1,const Person &ob2){
        return ob1.age < ob2.age;
    });
    cout<<"--------------"<<endl;
    printVectorPerson(v);
}

运行结果：

image-20210126235553470

类似js中，传入匿名函数（即没有名字的函数）作为回调函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function doSomething(args,callback){
   somethingComplicated(args);
   callback();
}
//第一个参数如果不需要bai传递,可设置为dunull
//function onEnd(){} 这种方法通常是声明一个函数, 将函数作为参数传递可直接传递函数名称,或者传递匿名函数
//传递函数名称
function onEnd(){
//code
}
doSomething(null, onEnd);
//传递匿名函数
doSomething(null,function(){
   compute();
});

七、set/multiset容器

7.1 set/multiset容器基本概念

set的特性是，所有元素都会根据元素的键值自动被排序。set的元素不像map那样可以同时拥有实值和键值，set元素即是键值又是实值。set不允许两个元素有相同的键值。我们可以通过set的迭代器改变set元素的值吗？不行，因为set元素值就是其键值，关系到set元素的排序规则。如果任意改变set元素值，会严重破坏set组织。换句话说，set的iterator是一种const_iterator。set拥有和list某些相同的性质，当对容器中的元素进行插入操作或者删除操作的时候，操作之前所有的迭代器，在操作完成之后依然有效，被删除的那个元素的迭代器必然是一个例外。

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

树的简单知识：二叉树就是任何节点最多只允许有两个子节点，分别是左子节点和右子节点。

set容器的键值不允许相同；set容器提供的迭代器是只读迭代器（不允许修改元素的值）

image-20210127160647149

7.2 set容器常用API

7.2.1 set构造函数

1
2
3
set<T> st;//set 默认构造函数
multiset<T> mst;//multiset 默认构造函数
set(const set &st);//拷贝构造函数

7.2.2 set赋值操作

1
2
set& operator=(const set &st);//重载=运算符
swap(st);//交换两个集合容器

7.2.3 set大小操作

1
2
size();//返回容器中元素的数目
empty();//判断容器是否为空

7.2.4 set插入和删除操作

1
2
3
4
5
insert(elem);//在容器中插入元素
clear();//清楚容器中所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器
erase(beg,end);//删除区间[beg,end)的所有元素，返回下一个元素的迭代器
erase(elem);//删除容器中值为elem的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void test08(){
    set<int> s;
    srand(time(NULL));
    for(int i=0;i<5;i++){
        //insert插入元素 会自动排序
        s.insert(rand()%101);
    }
    s.insert(59);
    for_each(s.begin(),s.end(),[](int val){
        cout<<val<<" ";
    });
    cout<<endl;

    //删除第一个元素
    s.erase(s.begin());
    for_each(s.begin(),s.end(),[](int val){
        cout<<val<<" ";
    });
    cout<<endl;

    //删除59
    s.erase(59);
    for_each(s.begin(),s.end(),[](int val){
        cout<<val<<" ";
    });
    cout<<endl;
}

运行结果：

image-20210127172329374

7.2.5 set查找操作

1
2
3
4
5
find(key);//查找键值key是否存在，若存在，返回键的元素的迭代器；若不存在，返回set.end();
count(key);//查找键key的元素个数 只会返回0/1 
lower_bound(keyElem);//返回第一个key>=keyElem的元素的迭代器 若不存在，返回set.end();
upper_bound(keyElem);//返回第一个key>keyElem的元素的迭代器 若不存在，返回set.end();
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器 若不存在，返回set.end();

image-20210127163117888

end()；指向最后一个元素的下一个位置

案例1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void test09(){
    set<int> s;
    srand(time(NULL));
    for(int i=0;i<5;i++){
        //insert插入元素 会自动排序
        s.insert(rand()%101);
    }
    s.insert(59);
    for_each(s.begin(),s.end(),[](int val){
        cout<<val<<" ";
    });
    cout<<endl;

    set<int>::iterator ret = s.find(59);
    if(ret == s.end()){
        cout<<"没有查到"<<endl;
    }else{
        cout<<"查到元素:"<<*ret<<endl;
    }

    if(s.find(100) == s.end()){
        cout<<"没有查到"<<endl;
    }else{
        cout<<"查到元素:"<<*(s.find(100))<<endl;
    }

    cout<<"count(59)="<<s.count(59)<<endl;
    cout<<"count(100)="<<s.count(100)<<endl;


}

运行结果：

image-20210127173200646

案例2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
void test10(){
    set<int> s;
    s.insert(20);
    s.insert(10);
    s.insert(40);
    s.insert(60);
    for_each(s.begin(),s.end(),[](int val){
        cout<<val<<" ";
    });
    cout<<endl;

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

    set<int>::const_iterator ret1 = s.lower_bound(20);
    if(ret1 == s.end()){
        cout<<"没有查到下限"<<endl;
    }else{
        cout<<"查到下限:"<<*ret1<<endl;
    }
    set<int>::const_iterator ret2 = s.upper_bound(20);
    if(ret2 == s.end()){
        cout<<"没有查到上限"<<endl;
    }else{
        cout<<"查到上限:"<<*ret2<<endl;
    }

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

    ret1 = s.lower_bound(25);
    if(ret1 == s.end()){
        cout<<"没有查到下限"<<endl;
    }else{
        cout<<"查到下限:"<<*ret1<<endl;
    }
    ret2 = s.upper_bound(25);
    if(ret2 == s.end()){
        cout<<"没有查到上限"<<endl;
    }else{
        cout<<"查到上限:"<<*ret2<<endl;
    }

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

    ret1 = s.lower_bound(60);
    if(ret1 == s.end()){
        cout<<"没有查到下限"<<endl;
    }else{
        cout<<"查到下限:"<<*ret1<<endl;
    }
    ret2 = s.upper_bound(60);
    if(ret2 == s.end()){
        cout<<"没有查到上限"<<endl;
    }else{
        cout<<"查到上限:"<<*ret2<<endl;
    }

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

    ret1 = s.lower_bound(80);
    if(ret1 == s.end()){
        cout<<"没有查到下限"<<endl;
    }else{
        cout<<"查到下限:"<<*ret1<<endl;
    }
    ret2 = s.upper_bound(80);
    if(ret2 == s.end()){
        cout<<"没有查到上限"<<endl;
    }else{
        cout<<"查到上限:"<<*ret2<<endl;
    }
}

运行结果：

image-20210127174113687

案例3：equal_range()

  • 存在返回上下限，对组pair<set::const_iterator,set::const_iterator>
  • 不存在返回end();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
void test11(){
    set<int> s;
    s.insert(20);
    s.insert(10);
    s.insert(40);
    s.insert(60);
    for_each(s.begin(),s.end(),[](int val){
        cout<<val<<" ";
    });
    cout<<endl;

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

    pair<set<int>::const_iterator,set<int>::const_iterator> ret = s.equal_range(20);
    if(ret.first == s.end()){
        cout<<"没有查到下限"<<endl;
    }else{
        cout<<"查到下限:"<<*ret.first<<endl;
    }

    if(ret.second == s.end()){
        cout<<"没有查到上限"<<endl;
    }else{
        cout<<"查到上限:"<<*ret.second<<endl;
    }

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

    ret = s.equal_range(25);
    if(ret.first == s.end()){
        cout<<"没有查到下限"<<endl;
    }else{
        cout<<"查到下限:"<<*ret.first<<endl;
    }

    if(ret.second == s.end()){
        cout<<"没有查到上限"<<endl;
    }else{
        cout<<"查到上限:"<<*ret.second<<endl;
    }

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

    ret = s.equal_range(60);
    if(ret.first == s.end()){
        cout<<"没有查到下限"<<endl;
    }else{
        cout<<"查到下限:"<<*ret.first<<endl;
    }

    if(ret.second == s.end()){
        cout<<"没有查到上限"<<endl;
    }else{
        cout<<"查到上限:"<<*ret.second<<endl;
    }

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

    ret = s.equal_range(80);
    if(ret.first == s.end()){
        cout<<"没有查到下限"<<endl;
    }else{
        cout<<"查到下限:"<<*ret.first<<endl;
    }

    if(ret.second == s.end()){
        cout<<"没有查到上限"<<endl;
    }else{
        cout<<"查到上限:"<<*ret.second<<endl;
    }
}

运行结果：

image-20210127175005606

7.3 对组（pair）

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

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

如何创建对组？

1
2
3
4
5
6
//第一种方法
pair<string,int> pair(string("name"),20);
//第二种方法
pair<string,int> pair = make_pair("name",30);
//pair赋值
pair<string,int> pair3 = pair2;

7.4 仿函数修改set容器排序规则

因为set<>中<>只能写类型，所以只能使用仿函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class mySort{
public:
    bool operator ()(const int &a,const int &b){
        return a>b;//从大到小
    }

};
void test12(){
    set<int,mySort> s;
    srand(time(NULL));
    for(int i=0;i<7;i++){
        //insert插入元素 会自动排序
        s.insert(rand()%101);
    }
    for_each(s.begin(),s.end(),[](int val){
        cout<<val<<" ";
    });
    cout<<endl;
}

运行结果：

image-20210127175622501

7.5 set容器存放自定义数据

1、必须指定排序规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class mySortPerson{
public:
    bool operator ()(const Person &ob1,const Person &ob2){
        return ob1.age > ob2.age;
    }
};
void test13(){
    set<Person,mySortPerson> s;
    s.insert(Person("xiaohua",18));
    s.insert(Person("xiaoming",23));
    s.insert(Person("jack",20));
    s.insert(Person("lucy",25));
    s.insert(Person("bob",19));
    for_each(s.begin(),s.end(),[](const Person &ob){
       cout<<"name:"<<ob.name<<",age:"<<ob.age<<endl;
    });
    cout<<endl;
}

运行结果：

image-20210127180433296

2、重载<运算符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Person{
public:
    string name;
    int age;
public:
    Person(string name,int age){
        this->name = name;
        this->age = age;
    }
	//重载<
    bool operator <(const Person &ob)const{
        return this->age < ob.age;
    }
};
void test14(){
    set<Person> s;
    s.insert(Person("xiaohua",18));
    s.insert(Person("xiaoming",23));
    s.insert(Person("jack",20));
    s.insert(Person("lucy",25));
    s.insert(Person("bob",19));
    for_each(s.begin(),s.end(),[](const Person &ob){
       cout<<"name:"<<ob.name<<",age:"<<ob.age<<endl;
    });
    cout<<endl;
}

运行结果：

image-20210127180559187

7.6 multiset允许存放重复的键值

1、set容器不允许插入重复的键值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void test15(){
    set<int> s;
    pair<set<int>::const_iterator,bool> ret1,ret2;
    ret1 = s.insert(10);
    if(ret1.second == true){
        cout<<"第一次插入成功"<<endl;
    }else{
        cout<<"第一次插入失败"<<endl;
    }
    ret2= s.insert(10);
    if(ret2.second == true){
        cout<<"第二次插入成功"<<endl;
    }else{
        cout<<"第二次插入失败"<<endl;
    }
    for_each(s.begin(),s.end(),[](const int val){
        cout<<val<<" ";
    });
    cout<<endl;
}

运行结果：

image-20210127181010151

分析：第一次插入10成功第二次插入10失败，最后遍历出来也只有一个10；

2、multiset容器允许插入重复的键值

1
2
3
4
5
6
7
8
9
10
void test16(){
    multiset<int> s;
    s.insert(10);
    s.insert(10);
    s.insert(10);
    for_each(s.begin(),s.end(),[](const int val){
        cout<<val<<" ";
    });
    cout<<endl;
}

运行结果：

image-20210127181249557

八、map/multimap容器

8.1 map/multimap容器基本概念

map的特性是，所有元素都会根据元素的键值自动排序。map所有的元素都是pair，同时拥有实值和键值，pair的第一元素被视为键值，第二元素被视为实值，map不允许两个元素有相同的键值。我们可以通过map的迭代器改变map的键值吗？答案是不行的，因为map的键值关系到map元素的排序规则，任意改变map键值将会严重破坏map组织。如果要修改元素的实值，那么是可以的。map和list拥有相同的某些性质，当对它的容器进行新增操作或者删除操作时，操作之前的所有迭代器在操作完成之后依然有效，当然被删除的那个元素的迭代器必然是个例外。multimap和map的操作类似，唯一区别multimap键值可以重复。

map和multimap都是以红黑树为底层实现机制。

image-20210127193001802

总结：

  1. 所有元素都会根据元素的键值自动排序
  2. 所有元素都是pair，同时拥有实值和键值，第一个参数是键值，第二个元素是实值。
  3. map容器的键值唯一不可变，实值可以变
  4. 迭代器是只读迭代器

8.2 map容器常用API

8.2.1 map构造函数

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

8.2.1 map赋值操作

1
2
map& operator=(const map &mp);//重载等号运算符
swap(mp);//交换两个集合容器

8.2.2 map大小操作

1
2
size();//返回容器中元素的数目
empty();//判断容器是否为空

8.2.3 map插入数据元素操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
map.insert();//往容器插入元素 返回pair<iterator,bool>

map<int,string> mapStu;
//方式一 通过pair插入对象
mapStu.insert(pair<int,string>(3,"lucy"));
//方式二 通过make_pair插入对象(推荐)
mapStu.insert(make_pair(5,"bob"));
//方式三 通过value_type插入对象
mapStu.insert(map<int,string>::value_type(4,"jack"));
//方式四 通过数据的方式插入值 （读map容器数据时候推荐使用这种方式）
//如果容器中没有key为6，将会创建一个key为6实值为空的对组元素
//如果容器中key为6存在，那么m[6]代表key=6的value。
//如果不存在将创建 这将有风险
mapStu[6] = "mick";//等价于mapStu.insert(make_pair(6,"mick"));

案例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void test01(){
    map<int,string> m;
    //insert 方式一
    m.insert(pair<int,string>(1,"小明"));
    //方式二
    m.insert(make_pair(2,"小花"));
    //方式三
    m.insert(map<int,string>::value_type(3,"lucy"));
    //方式四
    m[4]="bob";

    for_each(m.begin(),m.end(),[](const pair<int,string> &ob){
        cout<<ob.first<<" "<<ob.second<<endl;
    });
}

运行结果：

image-20210127220101576

8.2.4 map删除操作

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

8.2.5 map查找操作

1
2
3
4
5
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相等的上下限两个迭代器

8.3 map和vector容器配合使用

四个队伍参加比赛，随机产生出场顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void test02(){
    //定义一个map容器存放四个队伍
    map<int,string> m;;
    m.insert(make_pair(1,"队伍A"));
    m.insert(make_pair(2,"队伍B"));
    m.insert(make_pair(3,"队伍C"));
    m.insert(make_pair(4,"队伍D"));

    //定义一个vector容器存放队伍编号
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    srand(time(NULL));
    random_shuffle(v.begin(),v.end());//打乱标号顺序

    cout<<"出场顺序：";
    for(vector<int>::iterator it=v.begin();it!=v.end();it++){
        cout<<m[*it]<<" ";
    }
    cout<<endl;

    cout<<"出场顺序：";
    for_each(v.begin(),v.end(),[&](int val){
        cout<<m[val]<<" ";
    });
    cout<<endl;
}

8.4 multimap允许相同的键值

1
2
3
4
5
6
7
8
9
10
void test03(){
    multimap<int,string> mlmp;
    mlmp.insert(make_pair(1,"lucy"));
    mlmp.insert(make_pair(1,"bob"));
    mlmp.insert(make_pair(1,"mick"));

    for_each(mlmp.begin(),mlmp.end(),[](const pair<int,string> &ob){
        cout<<ob.first<<" "<<ob.second<<endl;
    });
}

运行结果：

image-20210127222621262

8.4 五个员工加入三个不同部门

公司招聘了5名员工，5名员工进入公司之后，需要指派员工在哪个部门工作，人员信息有：姓名、年龄、电话等组成，通过multimap进行信息的插入保存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Person{
public:
    string name;
    int age;
    long int tel;
public:
    Person(string name,int age,long int tel){
        this->name = name;
        this->age = age;
        this->tel = tel;
    }
};

void test04(){
    vector<Person> v;
    v.push_back(Person("员工A",18,1234567));
    v.push_back(Person("员工B",19,1124252));
    v.push_back(Person("员工C",21,4231455));
    v.push_back(Person("员工D",20,4213584));
    v.push_back(Person("员工E",25,3672548));

    multimap<int,Person> mlmp;
    cout<<"1：编辑部  2：研究部  3：售后部"<<endl;
    for(vector<Person>::iterator it=v.begin();it!=v.end();it++){
        int n=0;
        cout<<"请输入"<<(*it).name<<"要指派的部门：";
        cin>>n;
        mlmp.insert(make_pair(n,*it));
    }

    for_each(mlmp.begin(),mlmp.end(),[](const pair<int,Person> &ob){
        cout<<ob.first<<" "<<ob.second.name<<" "<<ob.second.age<<" "\
           <<ob.second.tel<<endl;
    });

    //要查询某个部门先统计某个部门的人个数 在利用find（因为multimap会自动排序 key一样的元素是连着在一起的）
    cout<<"请输入要查询的部门:"<<endl;
    int n1=0;
    cin>>n1;
    int count=mlmp.count(n1);
    multimap<int,Person>::const_iterator ret = mlmp.find(n1);
    for(int i=0;i<count;i++,ret++){
        cout<<(*ret).first<<" "<<(*ret).second.name<<" "<<(*ret).second.age<<" "\
           <<(*ret).second.tel<<endl;
    }
}

运行结果：

image-20210127224842171

image-20210127210859264

image-20210127210948391

九、STL容器使用时机

image-20210127211629800

image-20210127211600202

vector容器的使用场景：比如软件历史操作记录的存储，我们经常要查看历史记录，比如上一次记录，上上次记录，但却不会去删除记录，因为记录是事实的描述。

deque的使用场景：比如排队购票系统，对排队者的存储可以采用deque，支持头端的快速移除，尾端的快速添加。如采用vector，则头端移除时，会移动大量的数据，速度慢。

vector和deque的比较：

  1. vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的开始位置却不是固定的。
  2. 如果有大量释放操作的话，vector花的时间更少，这跟两者的内部实现有关
  3. deque支持头部的快速插入和快速移除，这是deque的优点。

list使用场景：比如公交车乘客的存储，随时可能有乘客下车，支持频繁的不确实位置的移除和插入。

set的使用场景：比如对手机游戏的个人得分记录的存储，存储要求从高分到低分的顺序排列。

map的使用场景：比如按ID号存储十万个用户，想要快速通过ID查找对应的用户。二叉树的查找效率，这时候就体现出来了。如果是vector容器，最坏情况下可能要遍历完整个容器才能找到该用户。

于2021.1.27 22:50 写完