C++提高编程（一）

本文章是本人黑马程序员 C++| 匠心之作从0到1入门学编程的学习笔记

前置文章：

本阶段主要针对C++泛型编程 和STL技术做详细讲解，探讨C++更深层的使用

1 模板

1.1 模板的概念

模板就是建立通用的模具，大大提高复用性

生活中的模板：一寸照片模板、PPT模板……

模板的特点：

模板不可以直接使用，它只是一个框架
模板的通用并不是万能的

1.2 函数模板

C++另一种编程思想称为泛型编程，主要利用的技术就是模板
C++提供两种模板：函数模板和类模板

1.2.1 函数模板语法

函数模板作用：建立一个通用函数，其函数返回值类型和形参类型可以不具体定制，用一个虚拟的类型来代表

语法

template<typename T>
函数声明或定义

解释：

template --- 声明创建模板

typename --- 表明其后面的符号是一种数据类型，可以用'class'代替

T --- 通用的数据类型，名称可以替换，通常为大写字母

示例：

#include <iostream>

using namespace std;

//交换整形函数
void mySwapInt(int &a, int &b) {
  int temp = a;
  a = b;
  b = temp;
}

//交换浮点型函数
void mySwapDouble(double &a, double &b) {
  double temp = a;
  a = b;
  b = temp;
}

//利用模板提供通用的交换函数
template<typename T>
void mySwap(T &a, T &b) {
  T temp = a;
  a = b;
  b = temp;
}

void test01() {
  //两种方式使用函数模板
  //1、自动类型推导
  int a = 10;
  int b = 20;
  cout << "a = " << a << ", b = " << b << endl;
  mySwap(a, b);
  cout << "a = " << a << ", b = " << b << endl;

  //2、显示指定类型
  a = 10;
  b = 20;
  cout << "a = " << a << ", b = " << b << endl;
  mySwap<int>(a, b);
  cout << "a = " << a << ", b = " << b << endl;
}

int main() {
  test01();
  system("pause");
  return 0;
}

总结：

函数模板利用关键字template
使用函数模板有两种方式：自动类型推导、显示指定类型
模板的目的是为了提高复用性，将类型参数化

1.2.2 函数模板注意事项

注意事项：

自动类型推导，必须推导出一致的数据类型T，才可以使用
模板必须要确定出T的数据类型，才可以使用

示例：

#include <iostream>

using namespace std;

//利用模板提供通用的交换函数
template<class T>
  void mySwap(T &a, T &b) {
  T temp = a;
  a = b;
  b = temp;
}

void test01() {
  //自动类型推导，必须推导出一致的数据类型T，才可以使用
  int a = 10;
  int b = 20;
  char c = 'c';
  mySwap(a, b);
  cout << "a = " << a << ", b = " << b << endl;
  //    mySwap(a, c);     //推导不出一致的T的类型
}

//模板必须要确定出T的数据类型，才可以使用
template<typename T>
void func() { cout << "func()函数调用！" << endl; }
void test02(){
  //    func();
  func<int>();
}

int main() {
  test01();
  test02();
  system("pause");
  return 0;
}

总结：

使用模板时必须确定出通用数据类型T，并且能够推导出一致的类型

1.2.3 函数模板案例

案例描述：

利用函数模板封装一个排序的函数，可以对不同数据类型数组进行排序
排序规则从大到小，排序算法为选择排序
分别利用char数组和int数组进行测试

示例：

#include <iostream>

using namespace std;

//交换的函数模板
template<typename T>
void mySwap(T &a, T &b) {
  T temp = a;
  a = b;
  b = temp;
}

//利用选择排序，进行对数组从达到小的排序
template<typename T>
void mySort(T &arr) {
  int len = sizeof(arr) / sizeof(arr[0]);
  for (int i = 0; i < len; ++i) {
    int max = I;
    for (int j = i + 1; j < len; ++j) {
      if (arr[max] < arr[j]) {
        max = j;
      }
    }
    if (max != i) { mySwap(arr[max], arr[i]); }
  }
}

template<typename T>
void printArray(T &arr) {
  int size = sizeof(arr) / sizeof(arr[0]);
  for (int i = 0; i < size; i++) {
    cout << arr[i];
    i != (size - 1) ? cout << ", " : cout << endl;
  }
}

int main() {
  //测试char数组
  char charArr[] = "abkjyfie";
  printArray(charArr);
  mySort(charArr);
  printArray(charArr);

  cout << endl;

  int intArr[] = {3, 7, 25, 85, 36, 234, 987, 37, 13, 98};
  printArray(intArr);
  mySort(intArr);
  printArray(intArr);

  system("pause");
  return 0;
}

1.2.4 普通函数与函数模板的区别

普通函数与函数模板的区别：

普通函数调用时可以发生自动类型转换（隐式类型转换）
函数模板调用时，如果利用自动类型推导，不会发生隐式类型转换
如果利用显示指定类型的方式，可以发生隐式类型转换

示例：

#include <iostream>

using namespace std;

//普通函数
int myAdd01(int a, int b) { return a + b; }

//函数模板
template<typename T>
int myAdd02(T a, T b) { return a + b; }

int main() {
  //普通函数调用时可以发生自动类型转换（隐式类型转换）
  cout << "myAdd01(10.99, 'C') = " <<  myAdd01(10.99, 'C') << endl;

  //函数模板调用时，如果利用自动类型推导，不会发生隐式类型转换
    //cout << "myAdd02(10.99, 'C') = " <<  myAdd02(10.99, 'C') << endl;

  //如果利用显示指定类型的方式，可以发生隐式类型转换
  cout << "myAdd02<int>(10.99, 'C') = " <<  myAdd02<int>(10.99, 'C') << endl;
  system("pause");
  return 0;
}

总结：

建议使用显示指定类型的方式调用函数模板，因为可以自己确定通用类型T

1.2.5 普通函数与函数模板的调用规则

调用规则如下：

如果函数模板和普通函数都可以实现，优先调用普通函数
可以通过空模板参数列表来强制调用函数模板
函数模板也可以发生重载
如果函数模板可以产生更好的匹配优先调用函数模板

示例：

#include <iostream>

using namespace std;

void myPrint(int a, int b) {
  cout << "普通函数调用 myPrint(int a, int b)" << endl;
}

template<typename T>
void myPrint(T a, T b) {
  cout << "调用函数模板 myPrint(T a, T b)" << endl;
}

//函数模板也可以发生重载
template<typename T>
void myPrint(T a, T b, T c) {
  cout << "调用函数模板 myPrint(T a, T b, T c)" << endl;
}

int main() {
  int a = 10;
  int b = 20;

  //1. 如果函数模板和普通函数都可以实现，优先调用普通函数
  myPrint(a, b);

  //2. 可以通过空模板参数列表来强制调用函数模板
  myPrint<>(a, b);

  //3. 函数模板也可以发生重载
  myPrint(a, b, 30);

  //4. 如果函数模板可以产生更好的匹配优先调用函数模板
  char c1 = a;
  char c2 = b;
  myPrint(c1, c2);

  system("pause");

  return 0;
}

总结：既然提供了函数模板，最好就不要提供普通函数，否则容易出现二义性

1.2.6 模板的局限性

局限性：模板的通用性并不是万能的

例如：

template<typename T>
void f(T a, T b) {
  a = b;
}

在上述代码中提供的赋值操作，如果传入的a和b是数组，就无法实现了

再例如：

template<typename T>
void f(T a, T b) {
  if (a > b) {
    ...
  }
}

在上述代码中，如果T的数据类型传入的是像Person这样的自定义数据类型，也无法正常运行

因此C++为了解决这种问题，提供模板的重载，可以为这些特定的类型提供具体化的模板

示例：

#include <iostream>
#include <string>

using namespace std;

class Person {
  public:
  Person(string name, short age, short height_cm) {
    this->m_name = name;
    this->m_age = age;
    this->m_height_cm = height_cm;
  }

  void showInfo() {
    cout << m_name << " is " << m_age << " years old, and is " << m_height_cm << "cm tall. " << endl;
  }

  string getName() { return m_name; }

  short getAge() { return m_age; }

  short getHeight() { return m_height_cm; }

  private:
  //姓名
  string m_name;
  //年龄
  short m_age;
  //身高
  short m_height_cm;
};

//对比两个数据是否相等
template<typename T>
bool isEqual(T &a, T &b) {
  if (a == b) {
    return true;
  } else {
    return false;
  }
}

//利用具体化的Person版本实现代码，具体化有限调用
template<>
bool isEqual(Person &p1, Person &p2) {
  return (p1.getName() == p2.getName()) && (p1.getAge() == p2.getAge()) && (p1.getHeight() == p2.getHeight());
}

void test01() {
  int a = 10;
  int b = 20;
  cout << a << " = " << b << " is " << (isEqual(a, b) ? "true" : "false") << ". " << endl;
}

void test02() {
  Person p1("Elaine", 17, 159);
  Person p2("Elaine", 17, 159);

  cout << p1.getName() << " = " << p2.getName() << " is " << (isEqual(p1, p2) ? "true" : "false") << ". " << endl;
}

int main() {
  test01();
  test02();

  system("pause");

  return 0;
}

总结：

利用具体化的模板，可以解决自定义类型的通用化

学习模板并不是为了写模板，而是在STL能够运用系统提供的模板

1.3 类模板

1.3.1 类模板语法

类模板作用：建立一个通用类，类中的成员数据类型可以不具体制定，用一个虚拟的类型来表示

语法：

template<class T>
class 类 {};

解释：

template -- 声明创建模板

class -- 表明其后面的符号是一种数据类型，可以用typename代替

T -- 通用的数据类型，名称可以替换，通常为大写字母

示例：

#include <iostream>
#include <string>

using namespace std;

//类模板
template<class NameType, class AgeType>
  class Person {
    public:
    Person(NameType name, AgeType age) {
      m_name = name;
      m_age = age;
    }

    void showInfo() {
      cout << m_name << " is " << m_age << (m_age == 1 ? " year" : " years") << " old. " << endl;
    }

    NameType m_name;
    AgeType m_age;
  };

void test01() {
  //指定 NameType 为 string 类型， AgeType 为 short 类型
  Person<string, short> p1("Addy", 18);
  p1.showInfo();
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：类模板和函数模板语法类似，在声明模板temlpate后面加类，此类成为类模板

1.3.2 类模板与函数模板区别

类模板与函数模板主要区别有两点：

类模板没有自动类型推导的方式
类模板在模板参数列表中可以有默认参数

示例：

#include <iostream>
#include <string>

using namespace std;

//类模板
//类模板在模板参数列表中可以有默认参数
template<class NameType, class AgeType = short>
  class Person {
    public:
    Person(NameType name, AgeType age) {
      m_name = name;
      m_age = age;
    }

    void showInfo() {
      cout << m_name << " is " << m_age << (m_age == 1 ? " year" : " years") << " old. " << endl;
    }

    NameType m_name;
    AgeType m_age;
  };

void test01() {
  //类模板没有自动类型推导的使用方式
  // Person p("悟空", 1000);
  Person<string, short> p1("悟空", 1000);
  p1.showInfo();

  //类模板在模板参数列表中可以有默认参数
  Person<string> p2("八戒", 999);
  p2.showInfo();
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：

类模板只能使用指定类型方式

类模板中的函数列表可以有默认参数

1.3.3 类模板中成员函数创建时机

类模板中成员函数和普通类中成员函数创建时机是有区别的：

普通类中的成员函数一开始就可以创建
类模板中的成员函数在调用时才创建

示例：

#include <iostream>
#include <string>

using namespace std;

class Person1 {
  public:
  void showPerson1() { cout << "This is person1. " << endl; }
};

class Person2 {
  public:
  void showPerson2() { cout << "This is person2. " << endl; }
};

template<class T>
  class MyClass {
    public:
    //类模板中的成员函数
    void func1() { obj.showPerson1(); }

    void func2() { obj.showPerson2(); }

    T obj;
  };

void test01() {
  MyClass<Person1> m1;
  m1.func1();
  //m.func2();
  MyClass<Person2> m2;
  //m.func1();
  m2.func2();
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：类模板中的成员函数并不是一开始就创建的，在调用时才去创建

1.3.4 类模板对象做函数参数

学习目标：

类模板实例化出的对象，向函数传参的方式

一共有三种传入方式：

指定传入的类型 --- 直接显示对象的数据类型
参数模板化 --- 将对象中的参数变为模板进行传递
整个类模板化 --- 将这个对象类型模板化进行传递

示例：

#include <iostream>
#include <string>

using namespace std;

template<class NameType=string, class AgeType=short>
  class Person {
    public:
    Person(NameType name, AgeType age) {
      m_name = name;
      m_age = age;
    }

    void showInfo() {
      cout << m_name << " is " << m_age << (m_age == 1 ? " year" : " years") << " old. " << endl;
    }

    NameType m_name;
    AgeType m_age;
  };

//1. 指定传入的类型
void printPerson1(Person<string, short> &p) {
  p.showInfo();
}

//2. 参数模板化
template<class NameType, class AgeType>
  void printPerson2(Person<NameType, AgeType> &p) {
  p.showInfo();
  cout << "\tNameType的类型为：" << typeid(NameType).name() << endl
    << "\tAgeType的类型为：" << typeid(AgeType).name() << endl;
}

//3. 整个类模板化
template<typename T>
void printPerson3(T &p) {
  p.showInfo();
  cout << "\tT的类型为：" << typeid(T).name() << endl;
}

void test01() {
  Person<string, short> p1("孙悟空", 1000);
  printPerson1(p1);

  Person<string, short> p2("猪悟能", 999);
  printPerson2(p2);

  Person<string, short> p3("沙悟净", 998);
  printPerson3(p3);
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：

通过类模板创建的对象，可以有三种方式向函数中进行传参

使用比较广泛的是第一种：指定传入的类型

1.3.5 类模板与继承

当类模板碰到继承时，需要注意一下几点：

当子类继承的父类是一个类模板时，子类在声明的时候，要指定出父类中T的类型
如果不指定，编译器无法给子类分配内存
如果想灵活指定出父类中T的类型，子类也需变为类模板

示例：

#include <iostream>
#include <string>

using namespace std;

template<class T>
  class Base {
    public:
    T m;
  };

//1.当子类继承的父类是一个类模板时，子类在声明的时候，要指定出父类中`T`的类型
class Son1 : public Base<int> {
};
//2. 如果不指定，编译器无法给子类分配内存
//class Son : public Base {};

//3. 如果想灵活指定出父类中T的类型，子类也需变为类模板
template<class T1, class T2>
  class Son2 : public Base<T2> {
    public:
    T1 obj;
  };

void test01() {
  Son1 s1;
  cout << "s1.obj is " << typeid(s1.m).name() << endl;
  Son2<int, char> s2;
  cout << "s2.m is " << typeid(s2.m).name() << ", s2.obj is " << typeid(s2.obj).name() << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：如果父类是类模板，子类需要制定出父类中T的数据类型

1.3.6 类模板成员函数类外实现

示例：

#include <iostream>
#include <string>

using namespace std;

template<class NameType, class AgeType>
  class Person {
    public:
    Person(NameType name, AgeType age);

    void showPerson();

    NameType m_Name;
    AgeType m_Age;
  };

//构造函数类外实现
template<class NameType, class AgeType>
  Person<NameType, AgeType>::Person(NameType name, AgeType age) {
    this->m_Name = name;
    this->m_Age = age;
  }

//成员函数类外实现
template<class NameType, class AgeType>
  void Person<NameType, AgeType>::showPerson() {
    cout << this->m_Name << " is " << this->m_Age << (this->m_Age == 1 ? " year " : " years ") << "old. " << endl;
  }

void test01() {
  Person<string, short> p1("孙悟空", 1000);
  p1.showPerson();
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：类模板中成员函数类外实现时，需要加上模板参数列表

1.3.7 类模板分文件编写

问题：

类模板中成员函数创建时机是在调用阶段，导致分文件编写时链接不到

解决：

解决方式1：直接包含.cpp源文件
解决方式2：将声明和实现写到同一个文件中，并更改后缀名为.hpp，.hpp是约定的名字，并不是强制

示例：

//person.hpp
#pragma once

#include <iostream>
#include <string>

using namespace std;

template<class NameType, class AgeType>
  class Person {
    public:
    Person(NameType name, AgeType age);

    void showPerson();

    private:
    NameType m_Name;
    AgeType m_Age;
  };

template<class NameType, class AgeType>
  Person<NameType, AgeType>::Person(NameType name, AgeType age) {
    this->m_Name = name;
    this->m_Age = age;
  }

template<class NameType, class AgeType>
  void Person<NameType, AgeType>::showPerson() {
    cout << this->m_Name << " is " << this->m_Age << (this->m_Age == 1 ? " year " : " years ") << "old. " << endl;
  }

//main.cpp
#include <iostream>
#include <string>
#include "person.hpp"

using namespace std;

void test01() {
  Person<string, short> p1("孙悟空", 1000);
  p1.showPerson();
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：主流的解决方案是第二种，将类模板成员函数写到一起，并将后缀改名为.hpp

1.3.8 类模板与友元

全局函数类内实现 - 直接在类内声明友元即可

全局函数类外实现 - 需要提前让编译器知道全局函数的存在

示例：

#include <iostream>
#include <string>

using namespace std;

//全局函数配合友元，类外实现 - 先做函数模板声明，下方再做函数模板定义，再做友元
template<class Name, class Age>
  class Person;

//如果声明了函数模板，可以将实现写到后面，否则需要将实现体写到类的前面让编译器提前看到
template<typename NameType, typename AgeType>
void printPersonOutClass(Person<NameType, AgeType> &p);

template<class NameType, class AgeType>
  class Person {
    //全局函数类内实现
    friend void printPersonInClass(Person<NameType, AgeType> &p) {
      cout << p.m_Name << " is " << p.m_Age << (p.m_Age == 1 ? " year" : " years") << " old" << endl;
    }

    //全局函数类外实现
    //加空模板参数列表
    friend void printPersonOutClass<>(Person<NameType, AgeType> &p);

    public:
    Person(NameType name, AgeType age) {
      this->m_Name = name;
      this->m_Age = age;
    }

    private:
    NameType m_Name;
    AgeType m_Age;
  };

template<typename NameType, typename AgeType>
void printPersonOutClass(Person<NameType, AgeType> &p) {
  cout << p.m_Name << " is " << p.m_Age << (p.m_Age == 1 ? " year" : " years") << " old" << endl;
}

void test01() {
  //全局函数类内实现
  Person<string, short> p1("Tom", 20);
  printPersonInClass(p1);
  //全局函数类外实现
  printPersonOutClass(p1);

}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：建议全局函数做类内实现，用法简单，而且编译器可以直接识别

1.3.9 模板案例

案例描述：实现一个通用的数组类，要求如下

可以对内置数据类型以及自定义数据类型的数据进行存储
将数组中的数据存储到堆区
构造函数中可以传入数组的容量
提供对应的拷贝构造函数以及operator=防止浅拷贝问题
提供尾插法和尾删法对数组中的数据进行增加和删除
可以通过下标的方式访问数组中的元素
可以获取数组中当前元素个数和数组的容量

//myarray.hpp
#pragma once

#include <iostream>

using namespace std;

template<class T>
  class MyArray {
    public:
    //有参构造
    MyArray(int capacity) {
      this->m_Capacity = capacity;
      this->m_Size = 0;
      //按照容量开辟空间
      this->pAddress = new T[this->m_Capacity];
      cout << "有参构造" << endl;
    }

    //拷贝构造
    MyArray(MyArray &array) {
      this->m_Capacity = array.m_Capacity;
      this->m_Size = array.m_Size;
      //this.pAddress = arr.pAddress;
      //深拷贝
      this->pAddress = new T[array.m_Capacity];
      //拷贝array中的数据
      for (int i = 0; i < this->m_Size; ++i) {
        this->pAddress[i] = array.pAddress[I];
      }
      cout << "拷贝构造" << endl;
    }

    //重载operator=
    MyArray &operator=(const MyArray &array) {
      //如果堆区有数据，释放
      if (this->pAddress != nullptr) {
        this->m_Capacity = 0;
        this->m_Size = 0;
        delete[]this->pAddress;
        this->pAddress = nullptr;
      }
      //深拷贝
      this->m_Capacity = array.m_Capacity;
      this->m_Size = array.m_Size;
      this->pAddress = new T[array.m_Capacity];
      for (int i = 0; i < this->m_Size; ++i) {
        this->pAddress[i] = array.pAddress[I];
      }
      cout << "operator=重载" << endl;
      return *this;
    }

    //显示所有元素
    void show() {
      for (int i = 0; i < this->m_Size; ++i) {
        cout << this->pAddress[i] << (i == this->m_Size - 1 ? "\n" : ", ");
      }
    }

    //尾插法
    void append(const T &val) {
      if (this->m_Size == this->m_Capacity) { return; }
      //在数组末尾插入数据
      this->pAddress[this->m_Size] = val;
      //更新数组大小
      this->m_Size++;
    }

    //尾删法
    void pop() {
      if (this->m_Size == 0) { return; }
      //逻辑删除
      this->m_Size--;
    }

    //通过下标访问数组元素
    T &operator[](int index) {
      return this->pAddress[index];
    }

    //返回数组容量
    int getCapacity() { return this->m_Capacity; }

    //返回数组大小
    int getSize() { return this->m_Size; }

    ~MyArray() {
      if (this->pAddress != nullptr) {
        delete[]this->pAddress;
        this->pAddress = nullptr;
      }
      cout << "析构" << endl;
    }

    private:
    //数组的指针
    T *pAddress;
    //容量
    int m_Capacity;
    //大小
    int m_Size;
  };

//main.cpp
#include <iostream>
#include "MyArray.hpp"
#include <math.h>

using namespace std;

//测试内置数据类型
void test01() {
  //有参构造函数
  MyArray<int> array1(5);
  //拷贝构造函数
  MyArray<int> array2(array1);
  //operator=重载
  MyArray<int> array3(100);
  array3 = array1;

  //尾插法
  for (int i = 0; i < array1.getCapacity(); ++i) { array1.append(pow(i, 2)); }
  array1.show();
  //尾删法
  array1.pop();
  //通过下标返回数组元素
  for (int i = 0; i < array1.getSize(); ++i) {
    cout << array1[i] << (i == array1.getSize() - 1 ? "\n" : ", ");
  }
  //返回数组容量
  cout << "array1.getCapacity() = " << array1.getCapacity() << endl;
  //返回数组大小
  cout << "array1.getSize() = " << array1.getSize() << endl;
}

//测试自定义数据类型
class Person {
  public:
  Person() {};

  Person(string name, short age) {
    this->m_Name = name;
    this->m_Age = age;
  }

  string m_Name;
  short m_Age;
};

void test02() {
  MyArray<Person> array(10);
  Person p1("唐三藏", 30);
  Person p2("孙悟空", 1000);
  Person p3("猪悟净", 999);
  Person p4("沙悟净", 998);
  Person p5("白龙马", 997);
  //尾插法
  array.append(p1);
  array.append(p2);
  array.append(p3);
  array.append(p4);
  array.append(p5);
  for (int i = 0; i < array.getSize(); ++i) {
    cout << array[i].m_Name << "的年龄为" << array[i].m_Age << "岁。" << endl;
  }
  //尾删法
  cout << "array.pop();" << endl;
  array.pop();
  //通过下标返回数组元素
  for (int i = 0; i < array.getSize(); ++i) {
    cout << array[i].m_Name << "的年龄为" << array[i].m_Age << "岁。" << endl;
  }
  //返回数组容量
  cout << "array.getCapacity() = " << array.getCapacity() << endl;
  //返回数组大小
  cout << "array.getSize() = " << array.getSize() << endl;
}


int main() {
  test01();
  test02();

  system("pause");

  return 0;
}

2 STL 初识

2.1 STL 的诞生

长久以来，软件界一直希望建立一种可重复利用的东西
C++的面向对象和泛型编程思想，目的就是复用性的提升
大多情况下，数据结构和算法都未能有一套标准导致被迫从事大量重复工作
为了建立数据结构和算法的一套标准诞生了STL

2.2 STL 基本概念

STL（Standard Template Library，标准模板库）
ST从广义上分为：容器（container），算法（algorithm）和迭代器（iterator）
容器和算法之间通过迭代器进行无缝连接。
STL几乎所有的代码都采用了模板类或者模板函数

2.3 STL 六大组件

STL大体分为六大组件，分别是容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器

容器：各种数据结构，如vector、list、deque、set、map等，用来存放数据。
算法：各种常用的算法，如sort、find、copy、for_each等。
迭代器：扮演了容器与算法之间的胶合剂。
仿函数：行为类似函数，可作为算法的某种策略。
适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。
空间配置器：负责空间的配置与管理。

2.4 STL 中容器、算法、迭代器

容器：置物之所也

STL容器就是将运用最广泛的一些数据结构实现出来

常用的数据结构：数组链表树，栈，队列，集合，映射表等

这些容器分为序列式容器和关联式容器两种

序列式容器：强调值的排序，序列式容器中的每个元素均有固定的位置
关联式容器：二叉树结构，各元素之间没有严格的物理上的顺序关系

算法：问题之解法也

有限的步骤，解决逻辑或数学上的问题，这一门学科我们叫做算法（Algorithms）

算法分为：质变算法和非质变算法。

质变算法：是指运算过程中会更改区间内的元素的内容例如拷贝，替换，删除等等
非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等

迭代器：容器和算法之间粘合剂

提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。

每个容器都有自己专属的迭代器

迭代器使用非常类似于指针，初学阶段我们可以先理解代器为指针

迭代器种类：

种类	功能	支持运算
输入迭代器	对数据的只读访问	只读，支持`++`、`==`、`!=`
输出迭代器	对数据的只写访问	只写，支持`++`
前向迭代器	读写操作，并能向前推进迭代器	读写，支持`++`、`==`、`!=`
双向迭代器	读写操作，并能向前和向后操作	读写，支持`++`、`--`
随机访问迭代器	读写操作，可以以跳跃的方式访问任意数据，功能最强的迭代器	读写，支持`++`、`--`、`[n]`、`-n`、`<`、`<=`、`>`、`>=`

常用的容器中迭代器种类为双向迭代器，和随机访问迭代器

2.5 容器算法迭代器初识

了解STL中容器、算法、迭代器概念之后，我们利用代码感受STL的魅力

STL中最常用的容器为Vector，可以理解为数组，下面我们将学习如何向这个容器中插入数据、并遍历这个容器

2.5.1 vector 存放内置数据类型

容器：vector

算法：for_each

迭代器：vector<int>::iterator

示例：

#include <iostream>
//容器头文件
#include <vector>
//标准算法头文件
#include <algorithm>

using namespace std;

void myPrint(int val) {
  cout << val << ", ";
}

void test01() {
  //创建一个vector容器（数组）
  vector<int> v;
  //向容器中插入数据
  for (int i = 0; i < 10; ++i) {
    v.push_back((i + 1) * 10);
  }
  //通过迭代器访问容器中的数据
  vector<int>::iterator itBegin = v.begin();  //起始迭代器，指向元素中第一个元素
  vector<int>::iterator itEnd = v.end();      //结束迭代器，指向元素中最后一个元素的下一个位置

  //第一种遍历方式
  cout << "第一种遍历方式：" << endl;
  while (itBegin != itEnd) {
    cout << *itBegin << (itBegin == itEnd - 1 ? "\n" : ", ");
    itBegin++;
  }
  //第二种遍历方式
  cout << "第二种遍历方式：" << endl;
  for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
  //第三种遍历方式
  cout << "第三种遍历方式：" << endl;

  for_each(v.begin(), v.end(), myPrint);
}

int main() {
  test01();

  system("pause");

  return 0;
}

2.5.2 vector 存放自定义数据类型

示例：

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

using namespace std;

class Person {
  public:
  Person(string name, short age) {
    this->m_Name = name;
    this->m_Age = age;
  }

  string m_Name;
  short m_Age;
};

//存放自定义数据类型
void test01() {
  //创建容器
  vector<Person> v;
  //人物信息
  Person p1("唐三藏", 30);
  Person p2("孙悟空", 1000);
  Person p3("猪悟净", 999);
  Person p4("沙悟净", 998);
  Person p5("白龙马", 997);
  //向容器中添加数据
  v.push_back(p1);
  v.push_back(p2);
  v.push_back(p3);
  v.push_back(p4);
  v.push_back(p5);
  //遍历容器中的数据
  for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
    //解引用访问
    cout << (*it).m_Name << "的年龄是"
      //箭头访问
      << it->m_Age << "岁。" << endl;
  }
}

//存放自定义数据类型的指针
void test02() {
  //创建容器
  vector<Person *> v;
  //人物信息
  Person p1("唐三藏", 30);
  Person p2("孙悟空", 1000);
  Person p3("猪悟净", 999);
  Person p4("沙悟净", 998);
  Person p5("白龙马", 997);
  //向容器中添加数据
  v.push_back(&p1);
  v.push_back(&p2);
  v.push_back(&p3);
  v.push_back(&p4);
  v.push_back(&p5);
  //遍历容器中的数据
  for (vector<Person *>::iterator it = v.begin(); it != v.end(); it++) {
    //解引用访问
    cout << (**it).m_Name << "的年龄是"
      //箭头访问
      << (*it)->m_Age << "岁。" << endl;
  }
}

int main() {
  test01();
  test02();

  system("pause");

  return 0;
}

2.5.3 vector 容器嵌套容器

示例：

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

using namespace std;

void test01() {
  vector<vector<int>> v;
  //创建小容器
  vector<int> v1;
  vector<int> v2;
  vector<int> v3;
  vector<int> v4;
  //向小容器中添加数据
  for (int i = 0; i < 4; ++i) {
    v1.push_back(i + 1);
    v2.push_back((i + 1) * 2);
    v3.push_back((i + 1) * 3);
    v4.push_back((i + 1) * 4);
  }
  //将小容器插入到大容器中
  v.push_back(v1);
  v.push_back(v2);
  v.push_back(v3);
  v.push_back(v4);
  //通过大容器，把所有数据遍历
  for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++) {
    //(*it) -- 容器 vector<int>
    for (vector<int>::iterator vit = it->begin(); vit != it->end(); vit++) {
      cout << *vit << (vit == it->end() - 1 ? "\n" : "\t");
    }
  }
}

int main() {
  test01();

  system("pause");

  return 0;
}

3 STL 常用容器

3.1 string 容器

3.1.1 string 基本概念

本质：

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

string和char *区别:：

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

特点：
string类内部封装了很多成员方法

例如：查找find，拷贝copy，删除delete，替换replace，插入insert

string管理char所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责

3.1.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>
#include <string>

using namespace std;

void test01() {
  //默认构造
  string s1;
  //使用字符串初始化
  const char *str = "Hello world!";
  string s2(str);
  cout << s2 << endl;
  //使用一个string对象初始化另一个string对象
  string s3(s2);
  cout << s3 << endl;
  //使用n个字符c初始化
  string s4(10, 'a');
  cout << s4 << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：string的多种构造方法没有可比性，灵活使用过即可

3.1.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>
#include <string>

using namespace std;

void test01() {
  //char*类型字符串赋值给当前的字符串
  string s1;
  s1 = "Hello world 1";
  cout << "s1 = " << s1 << endl;
  //把字符串s赋给当前的字符串
  string s2;
  s2 = s1;
  cout << "s2 = " << s2 << endl;
  //字符赋值给当前的字符串
  string s3;
  s3 = 'a';
  cout << "s3 = " << s3 << endl;

  //把字符串s赋给当前的字符串
  string s4;
  s4.assign("Hello world 2");
  cout << "s4 = " << s4 << endl;
  //把符串s的前n个字符赋给当前的字符串
  string s5;
  s5.assign("Hello world", 5);
  cout << "s5 = " << s5 << endl;
  //把字符串s赋给当前字符串
  string s6;
  s6.assign(s5);
  cout << "s6 = " << s6 << endl;
  //用n个字符c赋给当前字符串
  string s7;
  s7.assign(10, 'a');
  cout << "st = " << s7;
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：string的赋值方式有很多，operator=这种方式是比较实用的

3.1.4 string 字符串拼接

功能描述：

实现在字符串末尾拼接字符串

函数原型：

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

示例：

#include <iostream>
#include <string>

using namespace std;

void test01() {
  string str1 = "I";
  cout << str1 << endl;
  //string &operator+=(const char *str);                   //重载+=操作符
  str1 += (" like coding");
  cout << str1 << endl;
  //string &operator+=(const char c);                      //重载+=操作符
  str1 += ',';
  cout << str1 << endl;
  //string &operator+=(const string &str);                 //重载+=操作符
  string str2 = " C, C++, Java and Python. ";
  str1 += str2;
  cout << str1 << endl;
  //string &append(const char *s);                         /把字符串s连接到当前字符串结尾
  str1.append("Coding is ");
  cout << str1 << endl;
  //string &append(const char *s, int n);                  //把字符串s的前n个字符连接到当前字符串结尾
  str1.append("veryabcdefg ", 4);
  cout << str1 << endl;
  //string &append(const string &s);                       //同operator+=(const string &str);
  string str4 = " fun";
  str1.append(str4);
  cout << str1 << endl;
  //string &append(const string &s, int pos, int n);       //字符串s从pos开始的n个字符连接到字符串结尾
  string str5 = ".,/?!\'\"\\[]{}()";
  str1.append(str5, 4, 1);
  cout << str1 << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.1.5 string 查找和替换

功能描述：

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

函数原型

int find(const string &str, int pos = 0) const; //从pos开始查找str第一次出现的位置
int find(const char *s, int pos = 0) const; //从pos开始查找s第一次出现的位置
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; //从pos开始查找str最后一次出现的位置
int rfind(const char *s, int pos = npos) const; //从pos开始查找str最后一次出现的位置
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 chat *s); //将从pos开始的n个字符替换为字符串s

示例：

#include <iostream>
#include <string>

using namespace std;

void test01() {
  string str1 = "abcdefghij";
  string str2 = "de";
  //int find(const string &str, int pos = 0) const;           //从pos开始查找str第一次出现位置
  int pos = str1.find(str2);
  cout << "int pos = str1.find(str2);\t\t\t\t";
  pos == -1 ? cout << "未找到字符串" << endl : cout << "pos = " << pos << endl;
  //int find(const char *s, int pos = 0) const;               //从pos开始查找s第一次出现位置
  pos = str1.find("fh");
  cout << "int pos = str1.find(\"fh\");\t\t\t\t";
  pos == -1 ? cout << "未找到字符串" << endl : cout << "pos = " << pos << endl;
  //int find(const char *s, int pos, int n) const;            //从pos位置查找s的前n个字符第一次出现的位置
  pos = str1.find("fghijk", 0, 3);
  cout << "int pos = str1.find(\"fghijk\", 0, 3);\t";
  pos == -1 ? cout << "未找到字符串" << endl : cout << "pos = " << pos << endl;
  //int find(const char c, int pos = 0) const;                //查找字符c第一次出现位置
  pos = str1.find('h');
  cout << "int pos = str1.find(\'h\');\t\t\t\t";
  pos == -1 ? cout << "未找到字符" << endl : cout << "pos = " << pos << endl;
  //int rfind(const string &str, int pos = npos) const;       //从pos开始查找str最后一次出现的位置
  pos = str1.rfind(str2);
  cout << "int pos = str1.rfind(str2);\t\t\t\t";
  pos == -1 ? cout << "未找到字符串" << endl : cout << "pos = " << pos << endl;
  //int rfind(const char *s, int pos = npos) const;           //从pos开始查找str最后一次出现的位置
  pos = str1.rfind("fg");
  cout << "pos = str1.rfind(\"fg\");\t\t\t\t\t";
  pos == -1 ? cout << "未找到字符串" << endl : cout << "pos = " << pos << endl;
  //int rfind(const char *s, int pos, int n) const;           //从pos开始查找s的前n个字符最后一次出现的位置
  pos = str1.rfind("fhgijk", 0, 3);
  cout << "pos = str1.rfind(\"fhgijk\", 0, 3);\t\t";
  pos == -1 ? cout << "未找到字符串" << endl : cout << "pos = " << pos << endl;
  //int rfind(const char c, int pos = 0) const;               //查找字符c最后一次出现的位置
  pos = str1.rfind('h');
  cout << "pos = str1.rfind(\'h\');\t\t\t\t\t";
  pos == -1 ? cout << "未找到字符串" << endl : cout << "pos = " << pos << endl;
}

void test02() {
  string str1 = "abcdefg";
  //string &replace(int pos, int n, const string &str);       //将从pos开始的n个字符替换为字符串str
  string str2 = "1234";
  str1.replace(1, 3, str2);
  cout << "str1.replace(1, 3, str2);\t" << str1 << endl;
  //string &replace(int pos, int n, const chat *s);           //将从pos开始的n个字符替换为字符串s
  str1.replace(1, 3, "4321");
  cout << "str1.replace(1, 3, \"4321\");\t" << str1 << endl;
}

int main() {
  test01();
  cout << "-=-=-=-=-=-=-=-=-=-=-=替  换-=-=-=-=-=-=-=-=-=-=-=" << endl;
  test02();

  system("pause");

  return 0;
}

总结：

find查找是从左往后， rfind从右往左

find找到字符串后返回查找的第一个字符位置，找不到返回-1

replace在替换时，要指定从哪个位置起，多少个字符，替换成什么样的字符串

3.1.6 string 字符串比较

比较方式：

字符串的比较是按字符的ASCII码进行对比
= 返回 0
> 返回 1
< 返回 -1

函数原型：

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

#include <iostream>
#include <string>

using namespace std;

void compareStrings(string &str1, string &str2) {
  //int compare(const string &s) const;   //与字符串s比较
  if (str1.compare(str2) == 0) { cout << str1 << " 等于 " << str2 << endl; }
  else if (str1.compare(str2) > 0) { cout << str1 << " 大于 " << str2 << endl; }
  else if (str1.compare(str2) < 0) { cout << str1 << " 小于 " << str2 << endl; }
}

void test01() {
  string str1 = "hello";
  string str2 = "hello";
  string str3 = "hellO";
  string str4 = "xello";
  compareStrings(str1, str2);
  compareStrings(str1, str3);
  compareStrings(str1, str4);
  //int compare(const char *s) const;     //与字符串s比较
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：字符串对比主要是用于比较两个字符串是否相等，判断谁大谁小的意义并不是很大

3.1.7 string 字符存取

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

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

示例：

#include <iostream>
#include <string>

using namespace std;

void test01() {
  string str = "Hello!";
  cout << "str = " << str << endl;
  //char &operator[](int n);      //通过[]方式获取字符
  for (int i = 0; i < str.size(); ++i) {
    cout << str[i] << " ";
  }
  cout << endl;
  //char &at(int a);                //通过at方式获取字符
  for (int i = 0; i < str.size(); ++i) {
    cout << str.at(i) << " ";
  }
  cout << endl;

  //修改单个字符
  str[0] = 'x';
  cout << "str = " << str << endl;
  str.at(1) = 'E';
  cout << "str = " << str << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：string字符串中单个字符存取方式有两种：利用[]或at

3.1.8 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>
#include <string>

using namespace std;

void test01() {
  string str1 = "H, ";
  cout << "str1 = " << str1 << endl;
  //string &insert(int pos, const char *s);       //插入字符串
  str1.insert(1, "eo");
  cout << "str1 = " << str1 << endl;
  //string &insert(int pos, const string &str);   //插入字符串
  string str2 = "world aha!";
  str1.insert(5, str2);
  cout << "str1 = " << str1 << endl;
  //string &insert(int pos, int n, char c);       //在指定位置插入n个字符c
  str1.insert(2, 2, 'l');
  cout << "str1 = " << str1 << endl;
  //string &erase(int pos, int n = npos);         //删除从pos开始的n个字符
  str1.erase(str1.find(" aha"), 4);
  cout << "str1 = " << str1 << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：插入和删除的起始下标都是从0开始

3.1.9 string 子串

功能描述：

从string中获取想要的子串

函数原型：

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

示例：

#include <iostream>
#include <string>

using namespace std;

void test01() {
  string str1 = "abcdefg";
  cout << "str1 = " << str1 << endl;
  //string substr(int pos = 0, int n = npose) const;  //返回由`pos`开始的`n`个字符组成的字符串
  string substr = str1.substr(1, 4);
  cout << "substr = " << substr << endl;
}

//实用操作
void test02() {
  string email1 = "zhangsan@qq.com";
  string email2 = "lisi@google.com";
  //从邮件地址中获取用户名信息
  string usrName1 = email1.substr(0, email1.find('@'));
  cout << usrName1 << endl;
  string usrName2 = email2.substr(0, email2.find('@'));
  cout << usrName2 << endl;
  //从邮件地址中获取邮箱供应商
  string provider1 = email1.substr(email1.find('@') + 1, email1.find('.') - email1.find('@') - 1);
  cout << provider1 << endl;
  string provider2 = email2.substr(email2.find('@') + 1, email2.find('.') - email2.find('@') - 1);
  cout << provider2 << endl;
}

int main() {
  test01();
  test02();

  system("pause");

  return 0;
}

总结：灵活运用求子串功能，可以在实际开发中获取有效的信息

3.2 vector 容器

3.2.1 vector基本概念

功能：

vector数据结构和数组非常相似，也称为单端数组

vector与普通数组区别：

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

动态扩展：

并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间

vector容器

vector容器的迭代器支持随机访问

3.2.2 vector构造函数

函数原型：

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

示例：

#include <iostream>
#include <vector>

using namespace std;

void printVector(vector<int> &v) {
  for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  //vector<T> v;                  //采用模板实现，默认构造函数
  vector<int> v1;
  for (int i = 0; i < 10; ++i) {
    v1.push_back(i);
  }
  printVector(v1);
  //vector(v.begin(), v.end());   //将[v.begin, v.end())中区间中的元素拷贝给本身
  vector<int> v2(v1.begin(), v1.end());
  printVector(v2);
  //vector(n, elem);                //将n个elem拷贝给本身
  vector<int> v3(10, 100);
  printVector(v3);
  //vector(const vector &vec);    //拷贝构造函数
  vector<int> v4(v3);
  printVector(v4);
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：vector的多种构造方式没有可比性，灵活使用即可

3.2.3 vector 赋值操作

函数原型：

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

示例：

#include <iostream>
#include <vector>

using namespace std;

void printVector(vector<int> &v) {
  for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  vector<int> v1;
  for (int i = 0; i < 10; ++i) {
    v1.push_back(i + 1);
  }
  printVector(v1);

  //vector &operator=(const vector &vec);     //重载operator=（等号操作符）
  vector<int> v2 = v1;
  printVector(v2);
  //assign(beg, end);                         //将[beg, end)区间中的数据拷贝赋值给本身
  vector<int> v3;
  v3.assign(v1.begin(), v1.end());
  printVector(v3);
  //assign(n, elem);                          //将n个elem拷贝赋值给本身
  vector<int> v4;
  v4.assign(10, 100);
  printVector(v4);
}

int main() {
  test01();

  system("pause");

  return 0;
}

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

3.2.4 vector 容量和大小

函数原型：

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

示例：

#include <iostream>
#include <vector>

using namespace std;

void printVector(vector<int> &v) {
  for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  vector<int> v1;
  for (int i = 0; i < 10; ++i) {
    v1.push_back(i + 1);
  }
  printVector(v1);

  //empty();                  //判断容器是否为空
  v1.empty() ? cout << "v1 is empty!" << endl : cout << "v1 is not empty!" << endl;
  vector<int> v2;
  v2.empty() ? cout << "v2 is empty!" << endl : cout << "v2 is not empty!" << endl;
  //capacity();               //容器的容量
  cout << "v1.capacity() = " << v1.capacity() << endl;
  cout << "v2.capacity() = " << v2.capacity() << endl;
  //size();                   //返回容器中元素的个数
  cout << "v1.size() = " << v1.size() << endl;
  //resize(int num);          //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。
  v1.resize(15);
  printVector(v1);
  //resize(int num, elem);    //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。
  v1.resize(20, 100);
  printVector(v1);
  //如果容器变短，则未尾超出容器长度的元素被删除。
  v1.resize(5);
  printVector(v1);
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.2.5 vector 插入和删除

函数原型：

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); //删除迭代器从start到end之间的元素
clear(); //删除容器中所有元素

示例：

#include <iostream>
#include <vector>

using namespace std;

void printVector(vector<int> &v) {
  if (v.begin() == v.end()) {
    cout << "The vector is empty!" << endl;
    return;
  }
  for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  vector<int> v1;
  for (int i = 0; i < 10; ++i) {
    //push_back(ele);                               //尾部插入元素ele
    v1.push_back(i + 1);
  }
  printVector(v1);
  //pop_back();                                       //删除最后一个元素
  v1.pop_back();
  printVector(v1);
  //insert(const_iterator pos, ele);                  //迭代器指向位置`pos`插入元素`ele`
  v1.insert(v1.begin(), 0);
  printVector(v1);
  //insert(const_iterator pos, int count, ele);       //迭代器指向位置`pos`插入`count`个元素`ele`
  v1.insert(v1.begin(), 2, -1);
  printVector(v1);
  //erase(const_iterator pos);                        //删除迭代器指向的元素
  v1.erase(v1.begin());
  printVector(v1);
  //erase(const_iterator start, const_iterator end);  //删除迭代器从`start`到`end`之间的元素
  v1.erase(v1.begin(), v1.begin() + 2);
  printVector(v1);
  //clear();                                          //删除容器中所有元素
  v1.clear();
  printVector(v1);
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.2.6 vector 数据存取

函数原型：

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

示例：

#include <iostream>
#include <vector>

using namespace std;

void test01() {
  vector<int> v;
  for (int i = 0; i < 10; ++i) {
    v.push_back(i + 1);
  }
  //at(int idx)   //返回索引idx所指向的数据
  for (int i = 0; i < v.size(); ++i) {
    cout << v.at(i) << (i == v.size() - 1 ? "\n" : ", ");
  }
  //operator[]    //返回索引idx所指向的数据
  for (int i = 0; i < v.size(); ++i) {
    cout << v[i] << (i == v.size() - 1 ? "\n" : ", ");
  }
  //front()       //返回容器中第一个数据元素
  cout << "The first element is " << v.front() << endl;
  //back()        //返回容器中最后一个数据元素
  cout << "The last element is " << v.back() << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.2.7 vector 互换容器

函数原型：

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

示例：

#include <iostream>
#include <vector>

using namespace std;

void printVector(vector<int> &v) {
  if (v.begin() == v.end()) {
    cout << "The vector is empty!" << endl;
    return;
  }
  for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  cout << "交换前：" << endl;
  vector<int> v1;
  cout << "\tv1 = ";
  for (int i = 0; i < 10; ++i) {
    v1.push_back(i + 1);
  }
  printVector(v1);
  vector<int> v2;
  cout << "\tv2 = ";
  for (int i = 10; i > 0; --i) {
    v2.push_back(i);
  }
  printVector(v2);

  cout << "交换后：" << endl;
  v1.swap(v2);
  cout << "\tv1 = ";
  printVector(v1);
  cout << "\tv2 = ";
  printVector(v2);
}

//实际运用
//巧用swap可以收缩内存空间
void test02() {
  vector<int> v;
  for (int i = 0; i < 100000; ++i) {
    v.push_back(i);
  }
  cout << "The capacity of v is " << v.capacity() << endl;
  cout << "The size of v is " << v.size() << endl;
  cout << "-=-=-=-=-=RESIZE-=-=-=-=-=" << endl;
  v.resize(3);
  cout << "The capacity of v is " << v.capacity() << endl;
  cout << "The size of v is " << v.size() << endl;
  //巧用swap收缩内存
  vector<int>(v).swap(v);
  //vector<int>(v)    //匿名对象
  //(v).swap(v)       //交换对象
  //原来的v变为匿名对象，执行结束后立即销毁
  cout << "-=-=vector<int>(v).swap(v);-=-=" << endl;
  cout << "The capacity of v is " << v.capacity() << endl;
  cout << "The size of v is " << v.size() << endl;
}

int main() {
  test01();
  cout << "\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n" << endl;
  test02();

  system("pause");

  return 0;
}

3.2.8 vector 预留空间

功能描述：

减少vector在动态扩展容量时的扩展次数

函数原型：

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

#include <iostream>
#include <vector>

using namespace std;

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

void test01() {
  vector<int> v1;
  int num = 0;        //统计开辟次数
  int *p = nullptr;
  for (int i = 0; i < 100000; ++i) {
    v1.push_back(i + 1);
    //统计开辟新空间次数
    if (p != &v1[0]) {
      p = &v1[0];
      num++;
    }
  }
  cout << "v1.size() = " << v1.size() << endl;
  cout << "v1.capacity = " << v1.capacity() << endl;
  cout << "num = " << num << endl;

  vector<int> v2;
  //reserve(int len);     //容器预留len个元素长度，预留位置不初始化，元素不可访问
  v2.reserve(100000);
  num = 0;        //统计开辟次数
  p = nullptr;
  for (int i = 0; i < 100000; ++i) {
    v2.push_back(i + 1);
    //统计开辟新空间次数
    if (p != &v1[0]) {
      p = &v1[0];
      num++;
    }
  }
  cout << "v2.size() = " << v2.size() << endl;
  cout << "v2.capacity = " << v2.capacity() << endl;
  cout << "num = " << num << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

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

3.3 deque 容器

3.3.1 deque 容器基本概念

功能：

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

deque与vector区别

vector对于头部的插入效率低，数据量越大，效率越低
deque相对而言，对头部的插入删除速度会比vector快
vector访问元素时的速度会比deque快，这和两者内部实现有关

deque容器

deque内部工作原理：

deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据
中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间

deque容器 - 中控器

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

3.3.2 deque 构造函数

函数原型：

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

示例：

#include <iostream>
#include <deque>

using namespace std;

void printDeque(const deque<int> &d) {
  for (deque<int>::const_iterator it = d.begin(); it < d.end(); it++) {
    //*it = 100;    //只读迭代器中的容器不可修改
    cout << *it << (it == d.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  //deque<T> deqT;            //默认构造形式
  deque<int> d1;
  for (int i = 0; i < 10; ++i) {
    d1.push_back(i + 1);
  }
  printDeque(d1);
  //deque(beg, end);          //构造函数将[beg, end)区间中的元素拷贝给本身
  deque<int> d2(d1.begin(), d1.end());
  printDeque(d2);
  //deque(n, elem);           //构造函数将n个elem拷贝给本身
  deque<int> d3(10, 1);
  printDeque(d3);
  //deque(const deque &deq);  //拷贝构造函数
  deque<int> d4(d1);
  printDeque(d4);
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.3.3 duque 赋值操作

函数原型：

deque &operator=(const deque &deq); //operator=重载
assign(beg, end); //将 $[$ beg $,$ end $)$ 区间中的数据拷贝赋值给本身
assign(n, elem); //将n个elem拷贝赋值给本身

示例：

#include <iostream>
#include <deque>

using namespace std;

void printDeque(const deque<int> &d) {
  for (auto it = d.begin(); it < d.end(); it++) {
    cout << *it << (it == d.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  deque<int> d1;
  for (int i = 0; i < 10; ++i) {
    d1.push_back(i + 1);
  }
  printDeque(d1);
  //deque &operator=(const deque &deq);   //operator=重载
  deque<int> d2 = d1;
  printDeque(d2);
  //assign(beg, end);                     //将[beg, end)区间中的数据拷贝赋值给本身
  deque<int> d3(d1.begin(), d1.end());
  printDeque(d3);
  //assign(n, elem);                      //将n个elem拷贝赋值给本身
  deque<int> d4(10, 1);
  printDeque(d4);
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.3.4 deque 容器大小操作

函数原型：

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

示例：

#include <iostream>
#include <deque>

using namespace std;

void printDeque(const deque<int> &d) {
  for (auto it = d.begin(); it < d.end(); it++) {
    cout << *it << (it == d.end() - 1 ? "\n" : ", ");
  }
}

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

  //deque.empty();            //判断容器是否为空
  d1.empty() ? cout << "d1 is empty!" << endl : cout << "d1 is not empty!" << endl;
  deque<int> d2;
  d2.empty() ? cout << "d2 is empty!" << endl : cout << "d2 is not empty!" << endl;
  //deque.size();             //返回容器中元s素的个数
  cout << "d1.size() = " << d1.size() << endl;
  //resize(int num);          //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。
  d1.resize(15);
  printDeque(d1);
  //resize(int num, elem);    //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。
  d1.resize(20, 100);
  printDeque(d1);
  //如果容器变短，则未尾超出容器长度的元素被删除。
  d1.resize(5);
  printDeque(d1);
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：deque没有容量的概念

3.3.5 deque 插入和删除

两端插入操作：

deque.push_back(elem); //在容器尾部添加一个数据
deque.push_front(elem); //在容器头部添加一个数据
deque.pop_back(elem); //删除容器最后一个数据
deque.pop_front(elem); //删除容器第一个数据

指定位置操作：

deque.insert(pos, elem); //在pos位置插入一个elem元素的拷贝，返回新数据的位置
deque.insert(os, n, elem); //在pos位置插入n个elem元素，无返回值
deque.insert(pos, begin, end); //在pos位置插入 $[$ beg $,$ end $)$ 区间的数据，无返回值
deque.clear(); //清空容器的所有数据
deque.erase(beg, end); //删除 $[$ beg $,$ end $)$ 区间的数据，返回下一个数据的位置
deque.erase(pos); //删除pos位置的数据，返回下一个数据的位置

示例：

#include <iostream>
#include <deque>

using namespace std;

void printDeque(const deque<int> &d) {
  for (auto it = d.begin(); it < d.end(); it++) {
    cout << *it << (it == d.end() - 1 ? "\n" : ", ");
  }
}

//两端插入操作
void test01() {
  deque<int> d;
  for (int i = 0; i < 5; ++i) {
    //deque.push_back(elem);    //在容器尾部添加一个数据
    d.push_back(i + 1);
  }
  printDeque(d);
  for (int i = 0; i > -6; --i) {
    //deque.push_front(elem);   //在容器头部添加一个数据
    d.push_front(i);
  }
  printDeque(d);
  //deque.pop_back(elem);         //删除容器最后一个数据
  d.pop_back();
  printDeque(d);
  //deque.pop_front(elem);        //删除容器第一个数据
  d.pop_front();
  printDeque(d);
}

//指定位置操作
void test02() {
  deque<int> d1;
  for (int i = 0; i < 5; ++i) {
    d1.push_back((i + 1) * 2);
  }
  printDeque(d1);
  //deque.insert(pos, elem);          //在pos位置插入一个elem元素的拷贝，返回新数据的位置
  d1.insert(d1.begin(), 1);
  printDeque(d1);
  //deque.insert(os, n, elem);        //在pos位置插入n个elem元素，无返回值
  d1.insert(d1.end(), 5, 100);
  printDeque(d1);
  //deque.insert(pos, begin, end);    //在pos位置插入[beg, end)区间的数据，无返回值
  deque<int> d2;
  d2.push_back(1);
  d2.push_back(2);
  d2.push_back(3);
  d1.insert(d1.end() - 3, d2.begin(), d2.end());
  printDeque(d1);
  //deque.erase(beg, end);            //删除[beg, end)区间的数据，返回下一个数据的位置
  d1.erase(d1.begin() + 10, d1.end());
  printDeque(d1);
  //deque.erase(pos);                 //删除pos位置的数据，返回下一个数据的位置
  //deque<int>::iterator it2 = d1.end() - 5;
  auto it2 = d1.end() - 5;
  d1.erase(it2);
  printDeque(d1);
  //deque.clear();                    //清空容器的所有数据
  d1.clear();
  if (d1.empty()) { cout << "d1 is empty!" << endl; } else {printDeque(d1);}
}

int main() {
  test01();
  test02();

  system("pause");

  return 0;
}

总结：插入和删除提供的位置是迭代器

3.3.6 deque 数据存取

功能描述：

对deque中数据的存取操作

函数原型：

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

示例：

#include <iostream>
#include <deque>

using namespace std;

void printDeque(const deque<int> &d) {
  for (auto it = d.begin(); it < d.end(); it++) {
    cout << *it << (it == d.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  deque<int> d;
  for (int i = 0; i < 10; ++i) {
    d.push_back(i + 1);
  }
  printDeque(d);
  //at(int idx);  //返回索引idx所指的数据
  cout << "d.at(2) = " << d.at(2) << endl;
  //operator [];  //返回索引idx所指的数据
  cout << "d[5] = " << d[5] << endl;
  //front();      //返回容器中第一个数据元素
  cout << "d.front() = " << d.front() << endl;
  //back();       //返回容器中最后一个数据元素
  cout << "d.back() = " << d.back() << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.3.7 duque 排序

功能描述：

利用算法实现对deque容器进行排序

算法：

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

示例：

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

using namespace std;

void printDeque(const deque<int> &d) {
  for (auto it = d.begin(); it < d.end(); it++) {
    cout << *it << (it == d.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  deque<int> d;

  cout << "排序前：";
  d.push_back(20);
  d.push_back(406);
  d.push_back(152);
  d.push_back(-123);
  d.push_front(73);
  d.push_front(-42);
  d.push_front(321);
  d.push_front(81);
  printDeque(d);
  //排序前：81, 321, -42, 73, 20, 406, 152, -123

  cout << "排序后：";
  sort(d.begin(), d.end());
  printDeque(d);
  //排序后：-123, -42, 20, 73, 81, 152, 321, 406

  //对于支持随机访问的迭代器的容器，都可以利用sort()算法直接对其进行排序
  cout << "-=-=-=-=-=-=-=-=- vector -=-=-=-=-=-=-=-=-" << endl;
  cout << "排序前：";
  vector<int> v;
  v.push_back(2);
  v.push_back(40);
  v.push_back(-14);
  v.push_back(192);
  v.push_back(37);
  v.push_back(32);
  v.push_back(-185);
  v.push_back(18);
  for (auto it = v.begin(); it < v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
  sort(v.begin(), v.end());
  cout << "排序胡：";
  for (auto it = v.begin(); it < v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
}

int main() {
  test01();

  system("pause");

  return 0;
}

总结：sort()默认升序排列

3.4 案例 - 评委打分

3.4.1 案例描述

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

3.4.2 实现步骤

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

示例：

#include <algorithm>
#include <deque>
#include <iostream>
#include <random>
#include <string>
#include <ctime>
#include <utility>
#include <vector>

using namespace std;

//c++11 random library
uniform_int_distribution<unsigned> u(60, 100);
default_random_engine e(time(nullptr));

class Competitor {
  public:
  Competitor(string name, int score) {
    this->m_Name = std::move(name);
    this->m_Score = score;
  }

  string m_Name; //姓名
  int m_Score;   //平均分
};

void createCompetitor(vector<Competitor> &v) {
  string nameSeed[] = {"刘一", "陈二", "张三", "李四", "王五", "赵六"};
  for (int i = 0; i < nameSeed->size(); ++i) {
    string name = "选手：";
    name += nameSeed[I];
    int score = 0;
    Competitor p(name, score);
    v.push_back(p);
  }
}

void setScore(vector<Competitor> &v) {
  for (auto &vectorItem : v) {
    //将评委的分数放入deque
    deque<int> d;
    for (int i = 0; i < 10; ++i) {
      //随机数
      //int score = rand() % 41 + 60;
      int score = u(e);
      d.push_back(score);
    }
    /*
        //输出
        cout << vectorItem.m_Name << " 的得分是：";
        for (auto &dequeItem :d) {
            cout << dequeItem << (dequeItem == *(d.end() - 1) ? "" : ", ");
        }
        cout << endl;
         */
    //排序
    sort(d.begin(), d.end());
    //去除最高和最低分
    d.pop_front();
    d.pop_back();
    //取平均分
    int sum = 0;
    for (auto &dequeItem : d) { sum += dequeItem; }
    int avg = sum / d.size();
    //将平均分赋值给选手
    vectorItem.m_Score = avg;
  }
}

void showScore(vector<Competitor> &v) {
  for (auto &item:v) {
    cout << item.m_Name << " 的平均分是 " << item.m_Score << " 分" << endl;
  }
}

int main() {
  //创建选手
  vector<Competitor> v;   //存放选手容器
  createCompetitor(v);
  //给选手打分
  setScore(v);
  //显示分数
  showScore(v);

  system("pause");

  return 0;
}

3.5 stack 容器

3.5.1 stack 基本概念

概念：stack是一种先进后出 (First In Last Out, FILO) 的数据结构，它只有一个出口

stack容器

栈中只有顶端的元素才可以被外界使用，因此栈不允许有遍历行为

栈中进入数据称为 - 入栈 push
栈中弹出数据称为 - 出栈 pop

3.5.2 stack 常用接口

构造函数：

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

赋值操作：

stack &operator=(const stack &stk); //重载等号操作符

数据存取：

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

大小操作：

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

示例：

#include <iostream>
#include <stack>

using namespace std;

void test01() {
  stack<int> stk;
  for (int i = 0; i < 5; ++i) {
    stk.push(i + 1);
  }
  cout << "栈的大小：" << stk.size() << endl;

  while (!stk.empty()) {
    cout << "栈顶元素为：" << stk.top() << endl;
    //出栈
    stk.pop();
  }

  cout << "栈的大小：" << stk.size() << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.6 queue 容器

3.6.1 queue 容器概念

概念：queue容器是一种先进先出 (First In First Out, FIFO) 的数据结构，它有两个出口

queue容器

队列容器允许从一端新增元素，从另一端移除元素

队列中只有队头和队尾才可以被外界使用，因此队列不允许有遍历行为

队列中进入数据称为 - 入队 push
队列中弹出数据称为 - 出队 pop

3.6.2 queue 常用接口

构造函数：

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

赋值操作：

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

数据存取：

push(elem); //向队尾添加元素
pop()； //从队头移除第一个元素
back()； //返回最后一个元素
front()‘ //返回第一个元素

大小操作：

empty()； //判断堆队列是否为空
size()； //返回队列的大小

示例：

#include <iostream>
#include <queue>

using namespace std;

class Person {
  public:
  Person(string name = "name", short age = 0) {
    this->m_Name = move(name);
    this->m_Age = age;
  }

  string m_Name;
  short m_Age;
};

void test01() {
  Person p1("唐僧", 30);
  Person p2("孙悟空", 1000);
  Person p3("猪悟能", 999);
  Person p4("沙悟净", 998);
  //创建队列
  queue<Person> q;
  //入队
  q.push(p1);
  q.push(p2);
  q.push(p3);
  q.push(p4);
  cout << "队列大小为：" << q.size() << endl;
  //如果队列不为空，查看队头，查看队尾，出队
  while (!q.empty()) {
    //查看队头元素
    cout << "队头元素：" << q.front().m_Name << ", " << q.front().m_Age << ", ";
    //查看队尾元素
    cout << "队尾元素：" << q.back().m_Name << ", " << q.back().m_Age << endl;
    //出队
    q.pop();
  }
  cout << "队列大小为：" << q.size() << endl;
}

int main() {
  test01();
  system("pause");

  return 0;
}

3.7 list 容器

3.7.1 list 基本概念

功能：将数据进行链式储存

链表 (list)：是一种物理储存单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的

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

结点的组成：一个是储存数据单元的数据域，另一个数储存下一个结点地址的指针域

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

list容器

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

list的优点：

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

list的缺点：

链表灵活，但是空间（指针域）和时间（遍历）额外耗费较大

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

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

3.7.2 list 构造函数

函数原型：

list<T> lst; //list采用模板类实现，对象的默认构造函数
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 test01() {
  //list<T> lst;              //list采用模板类实现，对象的默认构造函数
  list<int> l1;
  for (int i = 0; i < 10; ++i) {
    l1.push_back(i + 1);
  }
  printList(l1);
  // list(beg, end);           //构造函数将[beg, end)区间中的元素拷贝给本身
  list<int>l2(l1.begin(), l1.end());
  printList(l2);
  // list(n, elem);            //构造函数将n个elem拷贝给本身
  list<int>l3(10, 1);
  printList(l3);
  // list(const list &lst);    //拷贝构造函数
  list<int>l4(l1);
  printList(l4);
}

int main() {
  test01();
  system("pause");
  return 0;
}

3.7.3 list 赋值和交换

功能描述：

给list容器进行赋值，以及交换list容器

函数原型：

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

示例：

#include <iostream>
#include <list>

using namespace std;

void printList(const list<int> &l) {
  for (auto it = l.cbegin(); it != l.cend(); ++it) {
    cout << *it << " ";
  }
  cout << endl;
}

void test01() {
  list<int> l1;
  for (int i = 0; i < 10; ++i) {
    l1.push_back(i + 1);
  }
  printList(l1);
  //assign(beg, end);                     //将[beg, end)区间中的数据拷贝赋值给本身
  list<int> l2;
  l2.assign(l1.begin(), l1.end());
  printList(l2);
  //Assign(n, elem);                      //将n个elem拷贝赋值给本身
  list<int> l3;
  l3.assign(10, 1);
  printList(l3);
  //list &operator=(const list &lst);     //重载等号操作符
  list<int> l4 = l1;
  printList(l4);
}

void test02() {
  list<int> l1;
  for (int i = 0; i < 5; ++i) {
    l1.push_back(i + 1);
  }
  list<int> l2;
  l2.assign(10, 5);
  cout << "-=-=-=-=-=-交换前-=-=-=-=-=-" << endl;
  cout << "l1: ";
  printList(l1);
  cout << "l2: ";
  printList(l2);

  //swap(lst);                            //将lst与本身的元素互换
  l1.swap(l2);
  cout << "-=-=-=-=-=-交换后-=-=-=-=-=-" << endl;
  cout << "l1: ";
  printList(l1);
  cout << "l2: ";
  printList(l2);
}

int main() {
  test01();
  test02();
  system("pause");
  return 0;
}

3.7.4 list 大小操作

函数原型：

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

示例：

#include <iostream>
#include <list>

using namespace std;

void printList(const list<int> &l) {
  for (auto it : l) { cout << it << " "; }
  cout << endl;
}

void test01() {
  list<int> l1;
  for (int i = 0; i < 10; ++i) {
    l1.push_back(i + 1);
  }
  cout << "l1: ";
  printList(l1);
  list<int> l2;
  cout << "l2: ";
  printList(l2);
  //size();               //返回容器中元素的个数
  cout << "l1.size() = " << l1.size() << endl;
  cout << "l2.size() = " << l2.size() << endl;
  //empty();              //判断容器是否为空
  cout << "l1.empty() = " << l1.empty() << " (" << (l1.empty() ? "True" : "False") << ")" << endl;
  cout << "l2.empty() = " << l2.empty() << " (" << (l2.empty() ? "True" : "False") << ")" << endl;
  //resize(num);          //重新指定容器的长度为num，若容器变长，则以默认值填充新位置
  //                      //如果容器变短，则末尾超出容器长度的元素被删除
  cout << "l1.resize(5);\t";
  l1.resize(5);
  cout << "l1: ";
  printList(l1);
  cout << "l2.resize(5);\t";
  l2.resize(5);
  cout << "l2: ";
  printList(l2);
  //resize(num, elem);    //重新指定容器的长度为num，若容器变长，则以elem值填充新位置
  //                      //如果容器变短，则末尾超出容器长度的元素被删除
  cout << "l1.resize(10, 5);\t";
  l1.resize(10, 5);
  cout << "l1: ";
  printList(l1);
}

int main() {
  test01();
  system("pause");
  return 0;
}

3.7.5 list 插入和删除

函数原型：

push_back(elem); //在容器尾部加入一个元素
pop_back(); //删除容器中最后一个元素
push_front(elem); //在容器开头插入一个元素
pop_front(elem); //从容器开头移除第一个元素
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值匹配的元素

示例：

#include <iostream>
#include <list>

using namespace std;

void printList(const list<int> &l) {
  for (auto it : l) { cout << it << " "; }
  cout << endl;
}

void test01() {
  list<int> l;
  for (int i = 0; i < 11; ++i) {
    //push_back(elem);        //在容器尾部加入一个元素
    l.push_back(i + 1);
  }
  printList(l);
  //pop_back();               //删除容器中最后一个元素
  l.pop_back();
  printList(l);
  for (int i = 0; i > -11; --i) {
    //push_front(elem);       //在容器开头插入一个元素
    l.push_front(i - 1);
  }
  printList(l);
  //pop_front(elem);          //从容器开头移除第一个元素
  l.pop_front();
  printList(l);
  //insert(pos, elem);        //在pos位置插入elem元素的拷贝，返回新数据的位置
  auto it = l.begin();
  for (int i = 0; i < 10; ++i) { ++it; }
  l.insert(it, 0);
  printList(l);
  //insert(pos, n, elem);     //在pos位置插入n个elem数据，无返回值
  l.insert(l.begin(), 3, -1000);
  printList(l);
  //insert(pos, beg, end);    //在pos位置插入[beg, end)区间的数据，无返回值
  list<int> l2;
  for (int i = 0; i < 3; ++i) { l2.push_back(1000); }
  l.insert(l.end(), l2.begin(), l2.end());
  printList(l);
  //clear();                  //移除容器的所有数据
  cout << "l2:";
  printList(l2);
  l2.clear();
  cout << "l2:";
  printList(l2);
  //erase(beg, end);          //删除[beg, end)区间的数据，返回下一个数据的位置
  it = l.begin();
  for (int i = 0; i < 3; ++i) { ++it; }
  l.erase(l.begin(), it);
  printList(l);
  //erase(pos);               //删除pos位置的数据，返回下一个数据的位置
  it = l.begin();
  for (int i = 0; i < 10; ++i) { ++it; }
  l.erase(it);
  printList(l);
  //remove(elem);             //删除容器中所有与elem值匹配的元素
  l.remove(1000);
  printList(l);
}

int main() {
  test01();
  system("pause");
  return 0;
}

3.7.6 list 数据存取

函数原型：

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

#include <iostream>
#include <list>

using namespace std;

void printList(const list<int> &l) {
  for (auto it : l) { cout << it << " "; }
  cout << endl;
}

void test01() {
  list<int> l;
  for (int i = 0; i < 10; ++i) {
    l.push_back(i + 1);
  }
  printList(l);
  //front();    //返回第一个元素
  cout << "l.front() = " << l.front() << endl;
  //back();     //返回最后一个元素
  cout << "l.back() = "<< l.back() << endl;
  
  //list迭代器是不支持随机访问的
  list<int>::iterator it = l.begin();
  it++;
  it--; //支持双向
  //it = it + 1;
}

int main() {
  test01();
  system("pause");
  return 0;
}

总结：list容器不可以通过[]或者at()方式访问数据

3.7.7 list 反转和排序

函数原型：

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

#include <iostream>
#include <list>
#include <random>
#include <ctime>

using namespace std;

default_random_engine e(time(nullptr));
uniform_int_distribution<int> d(-500, 500);

void printList(const list<int> &l) {
  for (auto it : l) { cout << it << " "; }
  cout << endl;
}

list<int> &randList() {
  auto *l = new list<int>;
  auto it = l->begin();
  int randNum;
  for (int i = 0; i < 20; ++i) {
    randNum = d(e);
    l->push_back(randNum);
    ++it;
  }
  return *l;
}

bool myCompare(int v1, int v2) {
  //降序：v1>v2
  return v1 > v2;
}

void test01() {
  list<int> l = randList();
  cout << "反转前：";
  printList(l);
  //reverse();    //反转链表
  l.reverse();
  cout << "反转后：";
  printList(l);
  //sort()        //链表排序
  cout << "排序后：";
  //不支持随机访问迭代器的容器，内部会提供一些对应算法
  l.sort();           //默认升序排列
  printList(l);
  l.sort(myCompare);  //降序排列
  cout << "降序排：";
  printList(l);
}

int main() {
  test01();
  system("pause");
  return 0;
}

3.7.8 排序案例

案例描述：将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高

排序规则：按照年龄进行升序，如果年龄相同按照身高进行降序排序

示例：

#include <iostream>
#include <string>
#include <list>

using namespace std;

class Person {
  public:
  Person(string name, int age, int height) {
    this->m_Name = move(name);
    this->m_Age = age;
    this->m_Height = height;
  }

  string m_Name;  //姓名
  int m_Age;      //年龄
  int m_Height;   //身高
};

void printList(const list<Person> &l) {
  for (const auto &it:l) {
    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_Age < p2.m_Age;
  //年龄相同，身高降序
  else
    return p1.m_Height > p2.m_Height;
}

int main() {
  list<Person> l;
  //准备数据
  Person p1("刘备", 35, 175);
  Person p2("曹操", 45, 180);
  Person p3("孙权", 40, 170);
  Person p4("赵云", 25, 190);
  Person p5("张飞", 35, 160);
  Person p6("关羽", 35, 195);
  //插入数据
  l.push_back(p1);
  l.push_back(p2);
  l.push_back(p3);
  l.push_back(p4);
  l.push_back(p5);
  l.push_back(p6);
  cout << " -=-=-排序前-=-=-" << endl;
  printList(l);
  //排序
  l.sort(comparePerson);
  cout << endl;
  cout << " -=-=-排序后-=-=-" << endl;
  printList(l);
  
  system("pause");
  return 0;
}

总结：

对于自定义数据类型，必须要指定排序规则，否则编译器不知道如何进行排序

高级排序只是在排序规则上再进行一次逻辑规则制定，并不复杂

3.8 set / multiset 容器

3.8.1 set 基本概念

简介：

所有元素都会在插入时自动被排序

本质：

set / multiset属于关联式容器，底层结构使用二叉树实现

set和multiset区别

set不允许容器中有重复的元素
multiset允许容器中有重复的元素

3.8.2 set 构造和赋值

构造：

set<T> st; //默认构造函数
set(const set &st); //拷贝构造函数

赋值：

set &operator=(const set &st); //重载等号操作符

示例：

#include <iostream>
#include <set>

using namespace std;

void printSet(set<int> &s) {
  for (set<int>::iterator it = s.begin(); it != s.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;
}

void test01() {
  //set<T> st;            //默认构造函数
  set<int> s1;
  for (int i = 0; i < 10; ++i) {
    //插入数值，只有insert()方式
    s1.insert(i + 1);
  }
  //遍历容器
  printSet(s1);
  //所有元素插入的时候自动排序
  //set不允许插入重复值
  s1.insert(10);
  printSet(s1);

  //set(const set &st);   //拷贝构造函数
  set<int> s2(s1);
  printSet(s2);

  //set &operator=(const set &st);    //重载等号操作符
  set<int> s3;
  s3 = s2;
  printSet(s2);
}

int main() {
  test01();
  system("pause");
  return 0;
}

3.8.3 set 大小和交换

函数原型：

size(); //返回容器中元素的数目
empty() //判断容器是否为空
swap(st) //交换两个集合容器

示例：

#include <iostream>
#include <set>

using namespace std;

ostream &operator<<(ostream &cout, set<int> &s) {
    for (auto &it:s) {
        cout << it << " ";
    }
    return cout;
}

void test01() {
    set<int> s1;
    for (int i = 0; i < 10; ++i) {
        s1.insert(i + 1);
    }
    cout << "s1: " << s1 << endl;
    set<int> s2;
    cout << "s2: " << s2 << endl;
    //size();   //返回容器中元素的数目
    cout << "s1.size() = " << s1.size() << endl;
    cout << "s2.size() = " << s2.size() << endl;
    //empty()   //判断容器是否为空
    cout << "s1.empty() = " << s1.empty() << (s1.empty() ? " (True)" : " (False)") << endl;
    cout << "s2.empty() = " << s2.empty() << (s2.empty() ? " (True)" : " (False)") << endl;
    //swap(st)  //交换两个集合容器
    s1.swap(s2);
    cout << "-=-=-=-=-交换后-=-=-=-=-" << endl;
    cout << "s1: " << s1 << endl;
    cout << "s2: " << s2 << endl;
}

int main() {
    test01();
    system("pause");
    return 0;
}

3.8.4 set 插入和删除

函数原型：

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

示例：

#include <iostream>
#include <set>

using namespace std;

ostream &operator<<(ostream &cout, set<int> &s) {
  for (auto &it:s) {
    cout << it << " ";
  }
  return cout;
}

void test01() {
  set<int> s;
  for (int i = 0; i < 10; ++i) {
    //insert(elem);        //在容器中插入元素
    s.insert(i + 1);
  }
  cout << "s: " << s << endl;
  //erase(pos);       //删除pos迭代器所指的元素，返回下一个元素的迭代器
  s.erase(s.begin());
  cout << "s: " << s << endl;
  //erase(pos, end);  //删除区间[beg, end)的所有元素，返回下一个元素的迭代器
  s.erase(++(++s.begin()), --(--s.end()));
  cout << "s: " << s << endl;
  //erase(elem);      //删除容器中值为elem的元素
  s.erase(10);
  cout << "s: " << s << endl;
  //clear();          //清除所有元素
  s.clear();
  cout << "s: " << s << endl;
}

int main() {
  test01();
  system("pause");
  return 0;
}

3.8.5 set 查找和统计

功能描述：

对set容器进行查找数据以及统计数据

函数原型：

find(key); //查找key是否存在，若存在，返回该键的元素迭代器；若不存在，返回set.end()
count(key); //统计key的元素个数

示例：

#include <iostream>
#include <set>
#include <random>
#include <ctime>

using namespace std;

default_random_engine e(time(nullptr));
uniform_int_distribution<int> d(0, 10);

ostream &operator<<(ostream &cout, set<int> &s) {
  for (auto &it:s) { cout << it << " "; }
  return cout;
}

ostream &operator<<(ostream &cout, multiset<int> &s) {
  for (auto &it:s) { cout << it << " "; }
  return cout;
}

void test01() {
  set<int> s;
  for (int i = 0; i < 10; ++i) { s.insert(i + 1); }
  cout << s << endl;

  set<int>::iterator pos = s.find(10);

  if (pos != s.end()) {
    cout << "找到元素 " << *pos << "!" << endl;
  } else {
    cout << "未找到元素." << endl;
  }
}

void test02() {
  set<int> set;
  for (int i = 0; i < 100; ++i) { set.insert(d(e)); }
  multiset<int> multiset;
  for (int i = 0; i < 100; ++i) { multiset.insert(d(e)); }

  cout << "set: " << set << endl;
  cout << "set中有" << set.count(5) << "个5." << endl;   //对于set而言，统计结果要么是0，要么是1
  cout << "multiset: " << multiset << endl;
  cout << "multiset中有" << multiset.count(5) << "个5." << endl;
}

int main() {
  test01();
  test02();
  system("pause");
  return 0;
}

3.8.6 set 和 multiset 区别

区别：

set不可以插入重复数值，而multiset可以
set插入数据的同时会返回插入结果，表示插入是否成功
multiset不会检测数据，因此可以插入重复数据

示例：

#include <iostream>
#include <set>

using namespace std;

ostream &operator<<(ostream &cout, multiset<int> &s) {
  for (auto &it:s) { cout << it << " "; }
  return cout;
}

void test01() {
  set<int> s;
  pair<set<int>::iterator, bool> ret = s.insert(10);
  cout << "第一次插入" << (ret.second ? "成功！" : "\u001b[31m失败\u001b[0m！") << endl;
  ret = s.insert(10);
  cout << "第二次插入" << (ret.second ? "成功！" : "\u001b[31m失败\u001b[0m！") << endl;

  multiset<int> ms;
  ms.insert(10);
  ms.insert(10);
  cout << "ms: " << ms << endl;
}

int main() {
  test01();
  system("pause");
  return 0;
}

总结：

如果不允许插入重复数据可以使用set

如果需要插入重复数据，利用multiset

3.8.7 pair对组创建

功能描述：

成对出现的数据，利用对组可以返回两个数据

两种创建方式：

pair<type, type> p(value1, value2);
pair<type, type> p = make_pair(value1, value2);

示例：

#include <iostream>
#include <string>

using namespace std;

template<typename First, typename Second>
ostream &operator<<(ostream &cout, pair<First, Second> &p) {
  cout << p.first << ", " << p.second;
  return cout;
}

void test01() {
  //pair<type, type> p(value1, value2);
  pair<string, int> p1("张三", 18);
  cout << "p1: " << p1 << endl;
  //pair<type, type> p = make_pair(value1, value2);
  pair<string, int> p2 = make_pair("李四", 19);
  cout << "p2: " << p2 << endl;
}

int main() {
  test01();
  system("pause");
  return 0;
}

3.8.8 set 容器排序

主要技术点：

利用仿函数，可以改变排序规则

示例一：set存放内置数据类型

#include <iostream>
#include <set>

using namespace std;

//改变排序规则
class MyCompare {
  public:
  bool operator()(int v1, int v2) { return v1 > v2; }
};

template<typename Type>
ostream &operator<<(ostream &cout, set<Type> &s) {
  for (auto &it : s) { cout << it << " "; }
  return cout;
}

template<typename Type, typename Rule>
ostream &operator<<(ostream &cout, set<Type, Rule> &s) {
  for (auto &it : s) { cout << it << " "; }
  return cout;
}

void test01() {
  set<int> s1;
  for (int i = 0; i < 10; ++i) {
    s1.insert(i + 1);
  }
  cout << s1 << endl;
  //指定排序规则为从大到小
  set<int, MyCompare> s2;
  for (int i = 0; i < 10; ++i) {
    s2.insert(i + 1);
  }
  cout << s2 << endl;
}

int main() {
  test01();
  system("pause");
  return 0;
}

示例二：set存放自定义数据类型

#include <iostream>
#include <set>

using namespace std;

class Person {
  public:
  Person(string name, int age) {
    this->m_Name = name;
    this->m_Age = age;
  }

  string m_Name;
  int m_Age;
};

class ComparePerson {
  public:
  //按照年龄降序排列
  bool operator()(const Person &p1, const Person &p2) { return p1.m_Age > p2.m_Age; }
};

ostream &operator<<(ostream &cout, set<Person, ComparePerson> &s) {
  for (auto &it : s) { cout << "姓名：" << it.m_Name << "，年龄：" << it.m_Age << endl; }
  return cout;
}

void test01() {
  //自定义数据类型，都会指定排序规则
  set<Person, ComparePerson> s;
  //准备数据
  Person p1("刘备", 25);
  Person p2("曹操", 45);
  Person p3("孙权", 40);
  Person p4("赵云", 20);
  Person p5("张飞", 35);
  Person p6("关羽", 30);
  //插入数据
  s.insert(p1);
  s.insert(p2);
  s.insert(p3);
  s.insert(p4);
  s.insert(p5);
  s.insert(p6);
  cout << s;
}

int main() {
  test01();
  system("pause");
  return 0;
}