[数据结构与算法]STL-常用容器：string，vector，deque，list

STL-常用容器

string容器

1. string基本概念

本质：string是C++风格的字符串，而string本质上是一个类

string和char*区别：

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

特点： string类内部封装了很多成员方法
例如：查找find，拷贝copy，删除delete，替换replace，插入insert
string管理char*所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责

2. string构造函数

构造函数原型

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

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

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

void test01()
{
    string s1;  // 默认构造， 相当于创建了一个string对象，会调用构造函数
    
    const char* str = "hello world";
    string s2(str);
    cout << "s2 = " << s2 << endl;

    string s3(s2);
    cout << "s3 = " << s3 << endl;

    string s4(5,'s');
    cout << "s4 = " << s4 << endl;
}
int main()
{
    test01();
    return 0;
}

3. string赋值操作

功能描述： 给string字符串进行赋值
赋值的函数原型：

• 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赋给当前字符串

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

// 赋值
void test01()
{
    string str1;

    // 赋值char*类型字符串
    str1 = "hello world";
    cout<< "str1 = " << str1 << endl;      // str1 = hello world

    string str2;
    // 赋值字符串str1
    str2 = str1;
    cout << "str2 = " << str2 << endl;      // str2 = hello world

    string str3;
    // 赋值char字符
    str3 = 'a';
    cout << "str3 = " << str3 << endl;      // str3 = a

    string str4;
    // 把字符串s的前n个字符赋给当前的字符串   
    str4 = str4.assign("hello world", 5);
    cout << "str4 = " << str4 << endl;      // str4 = hello

    string str5;
    // 赋值n个字符
    str5 = str5.assign(5,'a');
    cout << "str5 = " << str5 << endl;         // str5 = aaaaa
}
int main()
{
    test01();
    return 0;
}

4. 字符串拼接

功能描述： 实现在字符串末尾拼接字符串

函数原型：

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

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

void test01()
{
    string str1 = "我";

    // 追加char*字符串
    str1 += "爱玩游戏";
    cout << str1 << endl;           // 我爱玩游戏

    // 追加字符
    str1 += '1';
    cout << str1 << endl;            // 我爱玩游戏1

    // 追加string类型数据
    string str2 = "LOL";
    str1 += str2;
    cout << str1 << endl;           // 我爱玩游戏1LOL

    // 追加字符串s的前n个字符
    str1.append("hello world", 5);
    cout << str1 << endl;              // 我爱玩游戏1LOLhello

    // 追加字符串s从pos开始的n个字符， pos从0开始
    string str3 = "want to play";
    string str4 = "I ";
    str4.append(str3,5, 5);
    cout << str4 << endl;               // I to pl
}
int main()
{
    test01();
    return 0;
}

5. 字符串查找和替换

功能描述：

• 查找：查找指定字符串是否存在
• 替换：在指定的位置替换字符串

后面加 const表示函数不可以修改class的成员

函数原型：

• 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

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

// 字符串查找
void test01()
{
    string str1 = "abfcdefcg";

    int pos = str1.find("fc");
    (pos == -1)? (cout << "未找到字符串" << endl):(cout << "找到字符串，pos = " << pos << endl);
    // 找到字符串，pos = 2 找到“fc”在字符串str1中的第一次出现位置

    // rfind 和 find 区别
    // rfind从右往左查找  find从左往右找
    pos = str1.rfind("fc");
    (pos == -1)? (cout << "未找到字符串" << endl):(cout << "找到字符串，pos = " << pos << endl);
     // 找到字符串，pos = 6  找到“fc”在字符串str1中的最后一次出现位置
}
// 字符串替换
void test02()
{
    string st1 = "abcdefg";

    st1.replace(1,3,"1111");    // 将pos=1开始起3个字符替换为后面的字符串
    cout<<"st1 = " << st1 << endl;  // st1 = a1111efg
}

int main()
{
    test01();
    test02();
    return 0;
}

总结

• find查找字符串第一次出现位置，rfind查找字符串最后一次出现位置
• find找到字符串后返回查找的第一个字符位置，找不到返回-1
• replace在替换时，要指定从哪个位置起，多少字符，替换成什么样的字符串。如上例，“1111”可以替换进3个字符中

6. string字符串比较

功能描述: 字符串之间的比较
比较方式： 字符串比较是按字符的ASCII码进行对比
= 返回 0
> 返回 1
< 返回 -1

函数原型：

• int compare(const string& s) const; // 与字符串s比较
• int compare(const char* s) const; // 与字符串s比较

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

// 字符串查找
// 主要是用于比较两个字符串是否相等，相等返回0
void test01()
{
  string str1 = "hello";
  string str2 = "aello";
  string str3 = str1;
  
  cout << str1.compare(str2) << endl;  // 1   str1>str2 所以返回1
  cout << str1.compare(str3) << endl;  // 0
}

int main()
{
    test01();
    return 0;
}

7. string字符存取

string中单个字符存取方式有两种

• char& operator[] (int n); // 通过【】方式取字符
• char& at(int n); // 通过at方法获取字符

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

void test01()
{
    string str = "hello";

    cout << str[0] << endl;           // h
    cout << str.at(0) << endl;       // h
    for(int i=0; i< str.size(); i++)
    {
         cout << str[i] << endl;   
    }
}

int main()
{
    test01();
    return 0;
}

8. string插入和删除

功能描述：

• 对string字符串进行插入和删除字符操作

函数原型：

• 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个字符

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

// 字符串插入和删除
void test01()
{
    string str = "hello";
    str.insert(3,"11");
    cout << str << endl;    // hel11lo

    str.erase(1, 4);        // 从1号位置起开始4个字符
    cout << str << endl;    // hlo
}

int main()
{
    test01();
    return 0;
}

9. string子串

功能描述： 从字符串中获取想要的子串

函数原型：

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

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

// 字符串插入和删除
void test01()
{
    string str = "hello@qq.com";
    string str1 = str.substr(0,str.find('@'));  
    // str.find('@')是5，获取从0开始的5个字符组成的字符串
    cout << str1 << endl;       // hello
}

int main()
{
    test01();
    return 0;
}

vector容器

1. 基本概念

vector称为单端数组
vector与普通数组区别：

• 不同之处在于数组是静态空间，而vector可以动态扩展

动态扩展：

• 并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间（因为不能确定原空间之后的空间是否被占用了，所以不能直接续接）
  
• vector容器的迭代器是支持随机访问的迭代器
• push_back() 在尾部插入数据 pop_back() 在尾部删除数据
• vector::iterator v 是vector容器的迭代器，v.begin()指向第一个数据，v.end() 指向最后一个数据的下一个位置

2. 构造函数

功能描述：

• 创建vector容器

函数原型:

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

示例:

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

// 打印数据
void printfvector(vector<int>& c)
{
    for(vector<int>::iterator it = c.begin(); it != c.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}

// vector容器构造
void test01()
{
    vector<int> v;      // 默认构造 无参构造
    // 输入数据
    for(int i=0; i<10; i++)
    {
        v.push_back(i);
    }
    printfvector(v);

    // 将v[begin(), end())区间中的元素拷贝给本身
    vector<int> v1(v.begin(), v.end());
    printfvector(v1);

    // 构造函数将n个elem拷贝给本身
    vector<int> v2(10, 100);
    printfvector(v2);

    // 拷贝构造函数
    vector<int> v3(v);
    printfvector(v3);
}

int main()
{
    test01();
    return 0;
}

3. 赋值操作

功能描述： 给vector容器进行赋值
函数原型：

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

示例：

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

// 打印数据
void printfvector(vector<int>& c)
{
    for(vector<int>::iterator it = c.begin(); it != c.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}

// vector容器构造
void test01()
{
    vector<int> v1;      // 默认构造 无参构造
    
    for(int i=0; i<10; i++)
    {
        v1.push_back(i);
    }
    printfvector(v1);

    // 等号赋值
    vector<int> v2 = v1;
    printfvector(v2);
    
    //assign
    vector<int> v3;
    v3.assign(v1.begin(), v1.end());
    printfvector(v3);

    // n个elem
    vector<int> v4;
    v4.assign(10, 100);
    printfvector(v4);
}

int main()
{
    test01();
    return 0;
}

总结：vector赋值方式比较简单，使用operator=, 或者assign都可以

4. 容量和大小

函数原型：

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

示例:

    vector<int> v1;      // 默认构造 无参构造
    
    cout << v1.empty() << endl;  // 是空，为1
    // 插入数据
    for(int i=0; i<10; i++)
    {
        v1.push_back(i);
    }

    cout << v1.empty() << endl; // 非空, 为0
    cout << "v1的容量为：" << v1.capacity() << endl;       // 16
    cout << "v1容器中的元素个数：" << v1.size() << endl;    // 10

    // 重新指定元素个数
    v1.resize(15, 100);    // 指定容器中的个数为15，如果变长，用值100填充
    cout << "v1的容量为：" << v1.capacity() << endl;       // 16
    cout << "v1容器中的元素个数：" << v1.size() << endl;    // 15
    printfvector(v1);

    v1.resize(5);
    printfvector(v1);    // 短了，会删除多余的元素

总结：

• 判断是否为空 – empty
• 返回元素个数 – size
• 返回容器容量 – capacity
• 重新指定大小 – resize

5. 插入和删除

函数原型：

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

示例：

 	vector<int> v1;      // 默认构造 无参构造
    // 尾插
    v1.push_back(10); 
    v1.push_back(20); 
    v1.push_back(30); 
    v1.push_back(40); 
    // 尾删
    v1.pop_back();   // 删去40
    // 插入
    v1.insert(v1.begin(), 100); // 迭代器指向位置pos插入元素100
    // 删除
    v1.erase(v1.begin());   // 删除迭代器指向的元素

    // 插入count个数据
    v1.insert(v1.begin(), 10, 100);  // 迭代器指向位置pos插入10个100
    // 删除从strat到end之间的元素
    v1.erase(v1.begin(), v1.begin()+10);

    v1.clear();  // 全清

6. vector数据存取

函数原型：

• operator[idx]; // 返回索引idx所指的数据
• at(int idx); // 同上
• front(); // 返回容器中第一个数据元素
• back(); // 返回容器中最后一个数据元素

示例：

    vector<int> v1;      // 默认构造 无参构造
    // 尾插
    v1.push_back(10); 
    v1.push_back(20); 
    v1.push_back(30); 
    v1.push_back(40); 
    
    cout << v1[0] << endl;               // 10
    cout << v1.at(0) << endl;            // 10
    cout << v1.front() << endl;          // 10   
    cout << v1.back() << endl;           // 40

7. vector互换容器

功能描述：实现两个容器内元素进行互换
函数原型：

• swap(vec); // 将vec与本身的元素互换

示例：

    vector<int> v1;
    for(int i=0; i<10; i++)
    {
        v1.push_back(i);
    }
    printfvector(v1); // 0 1 2 3 4 5 6 7 8 9 

    vector<int> v2;
    for(int i=10; i>0; i--)
    {
        v2.push_back(i);
    }
    printfvector(v2); // 10 9 8 7 6 5 4 3 2 1

    v2.swap(v1);
    printfvector(v1);   // 10 9 8 7 6 5 4 3 2 1
    printfvector(v2);   // 0 1 2 3 4 5 6 7 8 9 

实际用途： 巧用swap可以收缩内存空间

 	vector<int> v;
    for(int i=0; i<100000; i++)
    {
        v.push_back(i);
    }
    cout << "v的容量为：" << v.capacity() << endl;   // 131072
    cout << "v中元素个数为：" << v.size() << endl;   // 100000

    v.resize(3); // 重新设定元素个数
    cout << "v的容量为：" << v.capacity() << endl;  // 131072
    cout << "v中元素个数为：" << v.size() << endl;  // 3
    // 这样容器的容量太大，个数确很少，造成了浪费

    // 巧用swap收缩内存
    // 匿名对象，vector<int> (v)拷贝构造v
    // 匿名对象只存在于该行代码，离开这行代码后立即调用析构函数
    vector<int> (v).swap(v); 
    cout << "v的容量为：" << v.capacity() << endl;  // 3
    cout << "v中元素个数为：" << v.size() << endl;  // 3

8. vector预留空间

功能描述： 减少vector在动态扩展容量时的扩展次数
函数原型：

• reserve(int len); // 容器预留len个元素长度，预留位置不初始化，元素不可访问

示例：

    vector<int> v;
    int num = 0;  // 记录开辟的次数
    int* p = NULL;
    for(int i=0; i<100000; i++)
    {
        v.push_back(i);
        if(p != &v[0])
        {
            p = &v[0];
            num++;
        }  
    }
    cout << num << endl;    // 18

    // 预留空间
    vector<int> v1;
    num = 0;
    v1.reserve(100000);  
    for(int i=0; i<100000; i++)
    {
         v1.push_back(i);
        if(p != &v1[0])
        {
            p = &v1[0];
            num++;
        }  
    }
    cout << num << endl;  // 1

总结：如果数据量较大，可以一开始利用reserve预留空间

deque容器

1. deque基本概念

功能：

• 双端数组，可以对头端进行插入删除操作

duque与vector区别：

• vector对于头部的插入删除效率低，数据量越大，效率越低.(在头部插入一个数，vector后面的数要移动)
• deque相对而言，对头部的插入删除速度会比vector快
• vector访问元素时的速度会比deque快，这和两者内部实现有关

deque内部工作原理：
deque内部有个中控器， 就是一段连续的内存空间存放一大堆指针，每个指针都指向一段定量连续空间，也叫作缓冲区，缓冲区才是 deque 的主体。
中控器维护的是每个缓存区的地址，使得使用deque时像一片连续的内存空间

• deque容器的迭代器也是支持随机访问的

2. deque构造函数

函数原型：

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

示例：

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

void printfDeque(const deque<int>& q)
{
    for(deque<int>::const_iterator it = q.begin(); it != q.end(); it++)
    {
        // *it = 100;       容器中的数据不可以修改了
        cout << *it << " "; 
    }
    cout << endl;
}

void test01()
{
    deque<int> d1;
    for(int i=0; i<10; i++)
    {
        d1.push_back(i);
    }
    printfDeque(d1);

    deque<int> d2(d1.begin(), d1.end());
    deque<int> d3(10, 100);
    deque<int> d4(d1);
}

3. deque赋值操作

函数原型：

• deque& operator=(const deque &deq); //重载等号操作符
• assign(beg, end); // 将【beg，end）区间中的数据拷贝赋值给本身
• assign(n, elem); // 将n个elem拷贝赋值给本身

	deque<int> d1;
    for(int i=0; i<10; i++)
    {
        d1.push_back(i);
    }
    
    deque<int> d2 = d1;
    deque<int> d3;
    d3.assign(d1.begin(), d1.end());
    d3.assign(10, 100);

4. deque大小操作

函数原型：

• deque.empty(); // 判断容器是否为空
• deque.size(); // 返回容器中元素的个数
• deque.resize(num); // 重新指定容器的长度为num，若容器变长，则以默认值填充新位置，如果容器变短，则末尾超出容器长度的元素被删除
• deque.resize(num, elem); // 同上，不过用elem值填充新位置
• deque没有容量的概念

示例：

 	deque<int> d1;
    cout << d1.empty() << endl;  // 1
    for(int i=0; i<10; i++)
    {
        d1.push_back(i);
    }
    cout << d1.empty() << endl;   // 0
    cout << "deque的大小为：" << d1.size() << endl;  // 10
    d1.resize(5); // 重新指定大小为5

5. deque插入和删除

函数原型：
两端插入操作：

• push_back(elem); // 在容器尾部添加一个数据
• push_front(elem); // 在容器头部插入一个数据
• pop_back(); // 删除容器最后一个数据
• 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位置的数据，返回下一个数据的位置

6. deque数据存取

函数原型：

• operator[idx]; // 返回索引idx所指的数据
• at(int idx); // 返回索引idx所指的数据
• front(); // 返回容器中第一个数据元素
• back(); // 返回容器中最后一个数据元素

7. deque排序

功能描述：利用算法实现对deque容器进行排序
算法：

• sort(iterator beg, iterator end); // 对beg和end区间内元素进行排序

示例：

#include<iostream>
#include<algorithm>
using namespace std;
#include<deque>

void printfDeque(const deque<int>& q)
{
    for(deque<int>::const_iterator it = q.begin(); it != q.end(); it++)
    {
        // *it = 100;       容器中的数据不可以修改了
        cout << *it << " "; 
    }
    cout << endl;
}

void test01()
{
   deque<int> d1;
   d1.push_back(10);
   d1.push_back(20);
   d1.push_back(15);
   d1.push_front(1);
   d1.push_front(2);

   sort(d1.begin(), d1.end()); // 从小到大
   printfDeque(d1);  // 1 2 10 15 20 
}   

int main()
{
    test01();
    return 0;
}

案例-评委打分

1. 案例描述

有5名选手：选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委中最低分，取平均分

2. 实现步骤

1. 创建五名选手，放到vector中
2. 遍历vector容器，取出来每一名选手，执行for循环，可以把10个评分打分存到deque容器中
3. sort算法对deque容器中分数排序，去除最高分和最低分
4. deque容器遍历一遍，累加总分
5. 获取平均分

示例：

#include<iostream>
#include<vector>
#include<deque>
#include<string>
#include<algorithm>
#include<time.h>
using namespace std;

// 选手类
class Person
{
public:

    Person(string name, int score)
    {
        this->m_name = name;
        this->m_score = score;
    }
    string m_name;  // 姓名
    int m_score;    // 平均分
};

// 创建person对象，并放到vector容器中
void createPerson(vector<Person>& v1)
{
    string nameSeed = "ABCDE";
    for(int i=0; i<5; i++)
    {
        string name = "选手";
        name += nameSeed[i];

        int score = 0;
        Person p(name, score);
        v1.push_back(p);
    }
}

//  打分
void setScore(vector<Person>& v)
{
    for(vector<Person>::iterator it = v.begin(); it!= v.end(); it++)
    {
        cout <<  (*it).m_name << " 打分： " << endl; 
        // 将评委的分数，放入到deque容器中
        deque<int> d;
        for(int i=0; i<10; i++)
        {
            int score = rand()%41 + 60;   // 60~100
            d.push_back(score); 
            cout << score << " ";
        }
        cout << endl;
        
        // 排序
        sort(d.begin(), d.end());
        d.pop_front();
        d.pop_back();

        // 取平均分
        int sum = 0;
        for(deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
        {
            sum += *dit;
        }
        int avg = sum / d.size();
        //将平均分 赋值给选手身上
        it->m_score = avg;
    }
}

// 展示
void showScore(vector<Person>& p)
{
    for(vector<Person>::iterator it = p.begin(); it != p.end(); it++)
    {
        cout << "姓名： " << it->m_name << " 平均分： " << it->m_score << endl;
    }
}
int main()
{
    // 随机数种子 让每次的数不同
    // 用系统时间算随机数
    srand((unsigned int)time(NULL));
    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);
    // 展示
    showScore(v);
    return 0;
}

list容器

1. 基本概念

功能：将数据进行链式存储
链表（list）是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的

链表的组成：链表由一系列结点组成
结点的组成：

• 存储数据元素的数据域
• 存储下一个结点地址的指针域

STL中的链表是一个双向循环链表

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器

list的优点：

• 采用动态存储分配，不会造成内存浪费和溢出
• 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素

list的缺点：

• 链表灵活，但是空间(指针域）和时间（遍历）额外耗费较大，不方便查找

List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的（因为如果vector容器插入的数超过，会重新找一个更大的空间，将原来的数拷贝过去，这样原来迭代器的指向就失效了）

总结：STL中list和vector是两个最常被使用的容器，各有优缺点

2. list构造函数

函数原型：

• list<T> lst; // 默认构造
• list(beg, end);// 将【beg，end）区间中的元素拷贝给本身
• list(n, elem); // 将n个elem拷贝给本身
• list(const list& lst); // 拷贝构造函数

#include<iostream>
#include<list>
using namespace std;
void printlist(const list<int>& L)
{
    for(list<int>::const_iterator it = L.begin(); it != L.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
void test()
{
    list<int> lst;

    lst.push_back(10);
    lst.push_back(20);
    lst.push_back(30);
    lst.push_back(40);
    
    printlist(lst);

    list<int> L2(lst.begin(), lst.end());

    list<int> L3(lst);

    list<int> L4(10, 100);
   
}
int main()
{
    test();
    return 0;
}

3. list赋值和交换

函数原型：

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

4. list大小操作

函数原型：

• size(); // 返回容器中元素的个数
• empty(); // 判断容器是否为空
• resize(num); // 重新指定容器的长度为num
• resize(num, elem); // 若容器变长，则以elem值填充新位置

5. list插入和删除

函数原型：

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

insert和erase中的pos要用迭代器

    list<int> lst;

    lst.push_back(10);
    lst.push_back(20);
    lst.push_back(30);
    lst.push_back(40);
    
    // 插入
    list<int>::iterator it = lst.begin();
    lst.insert(it, 100); // 在开头插入100

    // 删除
    lst.erase(it); // 删除it指向的数据
    lst.remove(10); // 删除所有与10相同的数据

6. list数据存取

函数原型：

• 不可以用【】访问list容器中的元素，迭代器不支持随机访问
• front(); // 返回第一个元素
• back(); // 返回最后一个元素

	list<int> L1;
	//迭代器不支持随机访问
	list<int>::iterator it = L1.begin();
	it = it +4; // 报错，不支持随机访问
	it++;	// 支持双向
	it--;

7. list反转和排序

函数原型：

• reverse(); // 反转链表
• sort(); // 链表排序

#include<iostream>
#include<list>
using namespace std;
void printlist(const list<int>& L)
{
    for(list<int>::const_iterator it = L.begin(); it != L.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
bool mycompare(int a, int b)
{
    return a>b;
}
void test()
{
    list<int> lst;

    lst.push_back(30);
    lst.push_back(20);
    lst.push_back(10);
    lst.push_back(40);
    printlist(lst);

    // 反转容器的元素
    lst.reverse();
    printlist(lst);

    // 排序
    // 所有不支持随机访问迭代器的容器，不可以用标准算法
    // sort(lst.begin(), lst.end());  报错
    // 不支持随机访问迭代器的容器，内部会提供对应一些算法
    lst.sort(); // 默认的排序规则，从小到大
    printlist(lst);

    lst.sort(mycompare);  // 指定规则，从大到小
    printlist(lst);
}
int main()
{
    test();
    return 0;
}

8. 排序案例

案例描述：将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高
排序规则：按照年龄进行升序，如果年龄相同按照身高进行降序

示例：

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

class Person
{
public:
    Person(string name, int age, int height)
    {
        this->m_name = name;
        this->m_height = height;
        this->m_age = age;
    }

    string m_name; // 姓名
    int m_age;     // 年龄
    int m_height;  // 身高
};

// 打印
void print(list<Person>& L)
{
    for(list<Person>::iterator it = L.begin(); it != L.end(); it++)
    {
        cout << "姓名： " << it->m_name 
            << " 年龄： "<< it->m_age 
            << " 身高： " << it->m_height
            << endl;
    }
}

// 制定排序规则
bool comparePerson(Person& p1, Person& p2)
{
    if(p1.m_age == p2.m_age)
    {
        return p1.m_height > p2.m_height;
    }
    // 按照年龄排序, 降序
    return p1.m_age < p2.m_age;
}

int main()
{
    // 创建容器
    list<Person> L;
    // 准备数据
    Person p1("w", 35, 134);
    Person p2("e", 44, 234);
    Person p3("r", 22, 876);
    Person p4("t", 44, 126);
    // 插入数据
    L.push_back(p1);
    L.push_back(p2);
    L.push_back(p3);
    L.push_back(p4);
    // 打印
    print(L);
    
    //排序
    L.sort(comparePerson);
    // 打印
    print(L);
    return 0;
}

vector、list、deque三者的比较

下图描述了vector 、list 、deque 在内存结构上的特点：

vector 是一段连续的内存块，而deque 是多个连续的内存块， list 是所有数据元素分开保存，可以是任何两个元素没有连续。

vector 的查询性能最好，并且在末端增加数据也很好，除非它重新申请内存段；适合高效地随机存储。

list 是一个链表，任何一个元素都可以是不连续的，但它都有两个指向上一元素和下一元素的指针。所以它对插入、删除元素性能是最好的，而查询性能非常差；适合 大量地插入和删除操作而不关心随机存取的需求。

deque 是介于两者之间，它兼顾了数组和链表的优点，它是分块的链表和多个数组的联合。所以它有被list 好的查询性能，有被vector 好的插入、删除性能。 如果你需要随即存取又关心两端数据的插入和删除，那么deque 是最佳之选。