再系统地过一次，夯实基础

学习目标：

过一遍黑马程序员C/C++学习视频

---

文章目录

学习目标：学习内容：一、C++基础入门二、通讯录管理系统三、C++核心编程三、 C++核心编程(面向对象) 继承四、基于多态的企业职工系统五、C++提高编程1. 模板1.1 模板的概念1.2 函数模板1.2.1 函数模板语法1.2.2 函数模板注意事项1.2.3 函数模板案例1.2.4 普通函数与函数模板的区别1.2.5 普通函数与函数模板的调用规则1.2.6 模型的局限性 1.3 类模板1.3.1 类模板语法1.3.2 类模板与函数模板区别1.3.3 类模板中成员函数创建时机1.3.4 类模板对象做函数参数1.3.5 类模板与继承1.3.6 类模板成员函数类外实现1.3.7 类模板份文件编写1.3.8 类模板与友元1.3.9 类模板案例 2. STL初识2.1 STL基本概念2. 2 STL基本概念2.3 STL六大组件2.4 STL中容器、算法、迭代器2.5 容器算法迭代器初识2.5.2 vector存放内置数据类型2.5.2 vector存放自定义数据类型2.5.3 vector容器嵌套容器 3. STL常用容器3.1 string容器3.1.1 string基本概念3.1.2 string构造函数3.1.3 string赋值操作3.1.4 string字符串拼接3.1.5 string查找和替换3.1.6 string字符串比较3.1.7 string字符存取3.1.8 string 插入和删除3.1.9 string子串 3.2 vector容器3.2.1 vector基本概念3.2.2 vector构造函数3.2.3 vector赋值操作3.2.4 vector容量和大小3.2.5 vector插入和删除3.2.6 vector数据存取3.2.7 vector互换容器3.2.8 vector预留空间 3.3 deque容器3.3.1 deque容器基本概念3.3.2 deque构造函数3.3.3 deque赋值操作3.3.4 deque大小操作3.3.5 deque插入和删除3.3.6 deque数据存取3.3.7 deque排序 3.4 案例-评委打分3.4.1 案例描述3.4.2 实现步骤 3.5 stack容器3.5.1 stack基本概念 3.6 queue容器3.6.1 queue 基本概念 3.7 list容器3.7.1 list基本概念3.7.2 list构造函数3.7.3 list赋值和交换3.7.4 list大小操作3.7.5 list插入和删除3.7.6 list数据存取3.7.7 list反转和排序3.7.8 排序案例 五、C++提高编程(2)六、基于STL泛化编程的演讲比赛七、C++实战项目机房预约管理系统 学习产出：

学习内容：

一、C++基础入门

---

二、通讯录管理系统

---

三、C++核心编程

三、 C++核心编程(面向对象) 继承

---

四、基于多态的企业职工系统

---

五、C++提高编程

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

1. 模板

1.1 模板的概念

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

例如生活中的模板

一寸照片模板： PPT模板：

1.2 函数模板

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

1.2.1 函数模板语法

函数模板作用：

建立一个通用函数，其函数返回值类型和形参类型可以不具体指定，用一个虚拟的类型来代替

语法：

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

解释： template – 声明创建模板 typename – 表明其后面的符号是一种数据类型，可以用class代替 T — 通用的数据类型，名称可以替换，通常为大写字母

//函数模板 template<typename T>//声明一个模板，告诉编译器后面代码中紧跟着的T不要报错，T是一个通用数据类型 void mySwap(T& a, T& b) { T temp = a; a = b; b = temp; } void test01() { int a = 10; int b = 20; //利用函数模板交换 //两种方式使用函数模板 //1、自动类型推导 mySwap(a, b); //2、显示指定类型 mySwap<int>(a, b); cout << "a = " << a << endl; cout << "b = " << b << endl; }

1.2.2 函数模板注意事项

注意事项：

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

自动类型推导，必须推导出一致的数据类型T才可以使用：

//函数模板注意事项 template<class T> //typename可以替换成class void mySwap(T& a, T& b) { T temp = a; a = b; b = temp; } //1、自动类型推导，必须推导出一致的数据类型T才可以使用 void test01() { int a = 10; int b = 20; char c = 'c'; mySwap(a, b); mySwap(a, c);//错误！推导不出一致的T类型 cout << "a = " << a << endl; cout << "b = " << b << endl; }

模板必须要确定出T的类型，才可以使用

//函数模板注意事项 //2、模板必须要确定出T的数据类型，才可以使用 template<class T> //typename可以替换成class void func() { cout << "func 调用" << endl; } void test01() { func<int>();//如果不确定这个类型，就不能这么使用 //正是2的原因。 }

总结：

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

1.2.3 函数模板案例

案例描述：

利用函数模板封装一个排序的函数，可以对不同数据类型数组进行排序排序规则从大到小，排序算法为选择排序分别利用char数组和int数组进行测试 #include<iostream> using namespace std; template<class T> void func(T& arr[]) { for (int i = 0; i < (sizeof(arr) / sizeof(arr[0]) - 1); i++) { int max = i; for (int j = i + 1; j < (sizeof(arr) / sizeof(arr[0])); j++) { if (arr[max] < arr[j]) { max = j; } } if (max!= i) { T temp; temp = arr[max]; arr[max] = arr[i]; arr[i] = temp; } } for (int i = 0; i < (sizeof(arr) / sizeof(arr[0])); i++) { cout << arr[i] << " "; } } int main() { int arr[10] = { 2, 1, 3, 4, 9, 6, 7, 8, 5, 0 }; func(arr); system("pause"); return 0; }

教程源码

template<class T> void mySwap(T& a, T& b) { T temp = a; a = b; b = temp; } template<class T> void mySort(T arr[], int len) { 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<class T> void printArray(T arr[], int len) { for (int i = 0; i < len; i++) { cout << arr[i] << ' '; } cout << endl; } void test01() { //int arr[10] = { 2, 1, 3, 4, 9, 6, 7, 8, 5, 0 }; char charArr[] = "badcfe"; int num = sizeof(charArr) / sizeof(char); mySort(charArr, num); printArray(charArr, num); }

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

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

普通函数调用时可以发生自动类型转换(隐式类型转换)函数模板调用时，如果利用自动类型推导，不会发生隐式类型转换如果利用显示指定类型的方式，可以发生隐式类型转换 //普通函数调用时可以发生自动类型转换(隐式类型转换) //函数模板调用时，如果利用自动类型推导，不会发生隐式类型转换 //如果利用显示指定类型的方式，可以发生隐式类型转换 template<class T> T myAdd(T a, T b) { return a + b; } void test01() { int a = 0; char c = 'c'; cout << myAdd<int>(a, c) << endl;//109 cout << myAdd(a, c) << endl;//报错 }

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

调用规则如下：

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

优先调用普通函数

void myPrint(int a, int b) { cout << "调用普通函数" << endl; } template<class T> void myPrint(T a, T b) { cout << "调用函数模板" << endl; } void test01() { int a = 10; int b = 20; myPrint(a, b);//调用普通函数 }

通过空模板参数列表，强制调用函数模板

void test01() { int a = 10; int b = 20; //通过空模板参数列表，强制调用函数模板 myPrint<>(a, b); }

函数模板也可以发生函数重载

template<class T> void myPrint(T a, T b) { cout << "调用函数模板" << endl; } template<class T> void myPrint(T a, T b, T c) { cout << "调用函数重载模板" << endl; } void test01() { int a = 10; int b = 20; int c = 30; myPrint(a, b, c); }

如果函数模板可以产生更好的匹配，优先调用函数模板

void myPrint(int a, int b) { cout << "调用普通函数" << endl; } template<class T> void myPrint(T a, T b) { cout << "调用函数模板" << endl; } void test01() { char c1 = 'a'; char c2 = 'b'; myPrint(c1, c2);//调用函数模板 }

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

1.2.6 模型的局限性

局限性：

模板的通用性并不是万能的

例如：

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

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

再例如：

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

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

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

//对比两个数据是否相等函数 class Person { public: //姓名 string name; //年龄 int age; Person(string name, int age) { this->name = name; this->age = age; } }; template<class T> bool myCompare(T& a, T& b) { if (a == b) return true; else return false; } //利用具体化Person的版本代码，具体化优先调用 template<> //模板特化 bool myCompare(Person& a, Person& b) { if (a.name == b.name && a.age == b.age) return true; else return false; } void test01() { Person p1("Tom", 10); Person p2("Tom", 10); bool ret = myCompare(p1, p2); if (ret) cout << "p1 == p2" << endl; else cout << "p1 != p2" << endl; }

总结：

利用具体化的模板，可以解决自定义类型的通用化学习模板并不是为了写模板，而是在STL能够运用系统提供的模板。

1.3 类模板

1.3.1 类模板语法

类模板作用：

简历一个通用类，类种的成员 数据类型可以不具体制定， 用一个虚构的类型来代表

语法：

template<typename T> 类 //类模板 template<class NameType, class AgeType> class Person { public: NameType m_Name; AgeType m_Age; Person(NameType name, AgeType age) { this->m_Name = name; this->m_Age = age; } void showPerson() { cout << "name: " << m_Name << "age: " << this->m_Age << endl; } }; void test01() { Person<string, int> p1("孙悟空", 999); p1.showPerson(); }

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

1.3.2 类模板与函数模板区别

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

类模板没有自动类型推导的使用方式类模板在模板参数列表中可以有默认参数 //类模板与函数模板的区别 template<class NameType, class AgeType = int> class Person { public: NameType m_name; AgeType m_age; Person(NameType name, AgeType age) { this->m_name = name; this->m_age = age; } void showPerson() { cout << "Name: " << this->m_name << "Age: " << this->m_age << endl; } }; //1、类模板没有自动类型推导使用方式 //2、类模板在模板参数列表中可以有默认参数 void test01() { Person<string> p("猪八戒", 999); p.showPerson(); }

总结：

类模板使用只能显示制定类型方式类模板中的模板参数列表可以有默认参数

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

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

普通类中的成员函数一开始就可以创建类模板中的成员函数在调用时才创建 //类模板中成员函数的创建时机 //类模板中成员函数在调用时才去创建 class Person1 { public: void showPerson1() { cout << "Person1 show" << endl; } }; class Person1 { public: void showPerson2() { cout << "Person2 show" << endl; } }; template<class T> class MyClass { public: T obj; //类模板中的成员函数 //只有调用的时候才会创建，所以可以直接编译成功，不报错 void func1() { obj.showPerson1(); } void func2() { obj.showPerson2(); } }; void test01() { MyClass<Person1> m; m.func1();//可以运行 m.func2();//报错，此时判断出showPerson2()不是Person1的成员函数 }

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

1.3.4 类模板对象做函数参数

学习目标：

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

一共有三种传入方式：

指定传入的类型 — 直接显示对象的数据类型参数模板化 — 将对象中的参数变为模板进行传递整个类模板化 — 将这个对象类型 模板化进行传递 //类模板对象做函数参数 template<class T1, class T2> class Person { public: Person(T1 name, T2 age) { this->m_Name = name; this->m_Age = age; } void showPerson() { cout << "姓名： " << this->m_Name << "年龄： " << this->m_Age << endl; } T1 m_Name; T2 m_Age; }; //1、指定传入类型 void printPerson1(Person<string, int>& p) { p.showPerson(); } void test01() { Person<string, int> p1("孙悟空", 100); printPerson1(p1); } //2、参数模板化 template<class T1, class T2> void printPerson2(Person<T1, T2>& p) { p.showPerson(); cout << "T1 的类型为： " << typeid(T1).name() << endl; cout << "T2 的类型为： " << typeid(T2).name() << endl; } void test02() { Person<string, int> p2("猪八戒", 90); printPerson2(p2); } //3、整个类模板化 template<class T> void printPerson3(T &p) { p.showPerson(); cout << "T的数据类型是： " << typeid(p).name() << endl; } void test03() { Person<string, int> p3("唐僧", 30); printPerson3(p3); }

总结：

通过类模板创建对象，可以有三种方式向函数中进行传参使用比较广泛的是第一种：指定传入的类型

1.3.5 类模板与继承

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

当子类继承的父类是一个类模板时，子类在声明的时候，需要指出父类中T的类型如果不指定，编译器无法给子类分配内存如果想灵活指定出父类中T的类型，子类也需要变为类模板 //类模板与继承 template<class T> class Base { public: T m; }; //class Son :public Base {//错误，必须知道父类中T类型，才能继承给子类 class Son:public Base<int>{ }; //2、如果想灵活指定父类中T类型，子类也需要变类模板 template<class T1, class T2> class Son2 :public Base<T2> { public: Son2() { cout << "T1的类型为：" << typeid(T1).name() << endl; cout << "T2的类型为：" << typeid(T2).name() << endl; } T1 obj; }; void test01() { //int 传给了T1 //char 传给了T2，又传给了父类Base Son2<int, char> s2; }

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

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

学习目标：能够掌握类模板中的成员函数类外实现

//类模板成员函数类外实现 template<class T1, class T2> class Person { public: Person(T1 name, T2 age); void showPerson(); T1 m_Name; T2 m_Age; }; //构造函数的类外实现 template<class T1, class T2> Person<T1, T2>::Person(T1 name, T2 age) { this->m_Name = name; this->m_Age = age; } template<class T1, class T2> void Person<T1, T2>::showPerson() { cout << "姓名： " << this->m_Name << endl; cout << "年龄： " << this->m_Age << endl; } void test01() { Person<string, int> p("张三", 18); p.showPerson(); }

1.3.7 类模板份文件编写

学习目标：

掌握类模板成员函数份文件编写产生的问题以及解决方式

问题：

类模板中成员函数创建时机实在调用阶段，导致份文件编写时链接不到解决方式1：直接包含.cpp源文件结局方式2：将声明和实现写道统一文件中，并更改后缀名为.hpp，.hpp是约定的名称，并不是强制

解决方式1：main文件直接包含.cpp源文件

不常用

结局方式2：将声明和实现写道统一文件中，并更改后缀名为.hpp，.hpp是约定的名称，并不是强制

#include <iostream> using namespace std; #include <string> #include "person.hpp" //第二种解决方式，将 .h和.cpp中的内容写到一起，将后缀名改为.hpp文件 void test01() { Person<string, int> p("张三", 99); p.showPerson(); } int main() { test01(); system("pause"); return 0; }

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

1.3.8 类模板与友元

学习目标：

掌握类模板配合友元函数的类内和类外实现

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

//通过全局函数 打印Person信息 template<class T1, class T2> class Person { //全局函数 类内实现 friend void printPerson(Person<T1, T2> p) { cout << "姓名： " << p.m_Name << "年龄： " << p.m_Age << endl; } public: Person(T1 name, T2 age) { this->m_Name = name; this->m_Age = age; } private: T1 m_Name; T2 m_Age; }; //1、全局函数在类内实现 void test01() { Person<string, int> p("Tom", 20); printPerson(p); }

全局函数类外实现 - 需要提前让编译器知道全局函数的存在 注意，不能直接按之前实现的来写，因为对于类中的定义，属于普通函数 在类外实现时变成了函数模板 所以需要加一个空模板参数列表 friend void printPerson<> (Person<T1, T2> p) 如果全局函数 是类外实现，需要让编译器提前知道这个函数的存在

#include <iostream> using namespace std; #include <string> //通过全局函数 打印Person信息 //提前让编译器知道Person类的存在 template<class T1, class T2> class Person; template<class T1, class T2> void printPerson(Person<T1, T2> p) { cout << "姓名： " << p.m_Name << "年龄： " << p.m_Age << endl; } template<class T1, class T2> class Person { //全局函数 类外实现 friend void printPerson<>(Person<T1, T2> p); public: Person(T1 name, T2 age) { this->m_Name = name; this->m_Age = age; } private: T1 m_Name; T2 m_Age; }; //1、全局函数在类外实现 //注意，不能直接按之前实现的来写，因为对于类中的定义，属于普通函数 //在类外实现时变成了函数模板 //所以需要加一个空模板参数列表 //如果全局函数 是类外实现，需要让编译器提前知道这个函数的存在 void test01() { Person<string, int> p("Tom", 20); printPerson(p); }

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

1.3.9 类模板案例

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

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

在头文件中创建Myarray.hpp文件 在main源文件中引用

#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 << "Myarray的有参构造" << endl; } //析构函数 ~MyArray() { cout << "Myarray的析构" << endl; if (this->pAddress != nullptr) { delete[] this->pAddress; this->pAddress = nullptr; } } //深拷贝构造 MyArray(const MyArray& arr) { this->m_Capacity = m_Capacity; this->m_Size = m_Size; //深拷贝 this->pAddress = new T[arr.m_Capacity]; //将arr中的数据都拷贝过来 for (int i = 0; i < this->m_Size; i++) { this->pAddress[i] = arr.pAddress[i]; } cout << "Myarray的拷贝构造" << endl; } //operator= 防止浅拷贝 MyArray& operator=(const MyArray& arr) { //先判断原来堆区是否有数据，如果有，先释放 if (this->pAddress != nullptr) { delete[] this->pAddress; this->pAddress = nullptr; this->m_Capacity = 0; this->m_Size = 0; } //深拷贝 this->m_Capacity = arr.m_Capacity; this->m_Size = arr.m_Size; this->pAddress = new T[arr.m_Capacity]; for (int i = 0; i < this->m_Size; i++) { this->pAddress[i] = arr.pAddress[i]; } cout << "Myarray的operator=" << endl; return *this; } private: //指向堆区开辟的真实数组 T* pAddress; int m_Capacity;//数组容量 int m_Size;//数组大小 };

main文件中：

#include <iostream> using namespace std; #include <string> #include "MyArray.hpp" void test01() { MyArray<int> arr1(5); MyArray<int> arr2(arr1); MyArray<int> arr3(100); arr3 = arr1; } int main() { test01(); system("pause"); return 0; }

后三点实现： MyArray.hpp定义和实现

//尾插法 void Push_Back(const T& val) { //判断容量是否等于大小 if (this->m_Capacity == this->m_Size) { cout << "容量已满" << endl; return; } this->pAddress[m_Size] = val;//在数组末尾插入数据 this->m_Size++;//更新数组大小 } //尾删法 void Pop_Back() { //让用户访问不到最后一个元素 if (this->m_Size == 0){ cout << "没有数据" << endl; return; } this->m_Size--; } //通过下标的方式访问数组中的元素 arr[0] = 100; T& operator[](int index) { return this->pAddress[index]; } //返回数组容量 int getCapacity() { return this->m_Capacity; } //返回数组大小 int getSize() { return this->m_Size; } this->m_Size--; } //通过下标的方式访问数组中的元素 arr[0] = 100; T& operator[](int index) { return this->pAddress[index]; } //返回数组容量 int getCapacity() { return this->m_Capacity; } //返回数组大小 int getSize() { return this->m_Size; }

class.cpp文件更新：

#include <iostream> using namespace std; #include <string> #include "MyArray.hpp" void printIntArray(MyArray<int>& arr) { for (int i = 0; i < arr.getSize(); i++) { cout << arr[i] << endl; } } void test01() { MyArray<int> arr1(5); for (int i = 0; i < 5; i++) { //利用尾插法向数组中插入数据 arr1.Push_Back(i); } cout << "arr1的打印输出为：" << endl; printIntArray(arr1); cout << "arr1的容量为： " << arr1.getCapacity() << endl; cout << "arr1的大小为： " << arr1.getSize() << endl; MyArray<int> arr2(arr1); printIntArray(arr2); cout << "arr2的容量为： " << arr2.getCapacity() << endl; cout << "arr2的大小为： " << arr2.getSize() << endl; //尾删 arr2.Pop_Back(); printIntArray(arr2); cout << "arr2的容量为： " << arr2.getCapacity() << endl; cout << "arr2的大小为： " << arr2.getSize() << endl; } //测试自定义数据类型 class Person { public: Person() {}; Person(string name, int age) { this->m_Age = age; this->m_Name = name; } string m_Name; int m_Age; }; void printPersonArray(MyArray<Person>& arr) { for (int i = 0; i < arr.getSize(); i++) { cout << "姓名： " << arr[i].m_Name << "年龄：" << arr[i].m_Age << endl; } } void test02() { MyArray<Person> arr(10); Person p1("孙悟空", 999); Person p2("韩信", 20); Person p3("妲己", 30); Person p4("赵云", 40); Person p5("安琪拉", 25); //将数据插入到数组中 arr.Push_Back(p1); arr.Push_Back(p2); arr.Push_Back(p3); arr.Push_Back(p4); arr.Push_Back(p5); //打印数组 printPersonArray(arr); //输出容量 cout << "arr的容量为： " << arr.getCapacity() << endl; cout << "arr的大小为： " << arr.getSize() << endl; } int main() { test02(); system("pause"); return 0; }

2. STL初识

2.1 STL基本概念

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

2. 2 STL基本概念

STL(Standard Template Library,标准模板库)STL从广义上分为：容器(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中最常用的容器时vecor，可以理解为数组。

2.5.2 vector存放内置数据类型

容器：vector 算法：for_each 迭代器：vector<int>::iterator

#include <iostream> using namespace std; #include <string> #include <algorithm> #include <vector> //vector容器存放内置数据类型 void myPrint(int val) { cout << val << endl; } void test01() { vector<int> v; v.push_back(10); v.push_back(20); v.push_back(30); v.push_back(40); //通过迭代器访问容器中的数据 vector<int>::iterator itBegin = v.begin();//起始迭代器 指向容器中第一个元素 vector<int>::iterator itEnd = v.end();//结束迭代器，指向容器中最后一个元素的下一个位置 //第一种遍历方式 while (itBegin != itEnd) { cout << *itBegin << endl; itBegin++; } //第二种遍历方式 for (vector<int>::iterator it = v.begin(); it != v.end(); it++) { cout << *it << endl; } //第三种遍历方式 利用STL遍历算法 for_each(v.begin(), v.end(), myPrint); }

2.5.2 vector存放自定义数据类型

学习目标：vector中存放自定义数据类型，并打印输出

//vector容器中存放自定义数据类型 class Person { public: Person(string name, int age) { this->m_Name = name; this->m_Age = age; } string m_Name; int m_Age; }; void test01() { vector<Person> v; Person p1("aaa", 10); Person p2("bbb", 10); Person p3("ccc", 10); Person p4("ddd", 10); Person p5("eee", 10); //向容器中添加数据 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 << endl; cout << "年龄： " << it->m_Age << endl; } } //存放自定义数据指针 void test02() { vector<Person*> v; Person p1("aaa", 10); Person p2("bbb", 10); Person p3("ccc", 10); Person p4("ddd", 10); Person p5("eee", 10); //向容器中添加数据 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 << endl; cout << "年龄： " << (*it)->m_Age << endl; } }

2.5.3 vector容器嵌套容器

学习目标：容器中嵌套容器，将所有数据进行遍历输出

//容器嵌套容器 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 + 2); v3.push_back(i + 3); v4.push_back(i + 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++) { for (vector<int>::iterator vit = (*it).begin(); vit != (*it).end(); vit++) { cout << *vit << ' '; } cout << endl; } }

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初始化 //string的构造函数 void test01() { string s1;//默认构造 const char* str = "hello world"; string s2(str); cout << "s2 = " << s2 << endl; string s3(s2); cout << "s3 = " << s3 << endl; string s4(10, 'a'); cout << "s4 = " << s4 << endl; }

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赋给当前字符串 //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赋给当前字符串 void test01() { string str1; str1 = "hello world"; cout << "str1 = " << str1 << endl; string str2; str2 = str1; cout << "str2 = " << str2 << endl; string str3; str3 = 'a'; cout << "str3 = " << str3 << endl; string str4; str4.assign("hello C++"); cout << "str4 = " << str4 << endl; string str5; str5.assign("hello C++", 5); cout << "str5 = " << str5 << endl; string str6; str6.assign(5, 'a'); cout << "str6 = " << str6 << endl; string str7; str7.assign(str5); cout << "str7 = " << str7 << endl; }

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个字符连接到字符串结尾 //string字符串拼接操作 void test01() { string str1 = "我"; str1 += "爱玩儿游戏"; cout << "str1 = " << str1 << endl; str1 += ':'; cout << "str1 = " << str1 << endl; string str2 = "Lol DNF"; str1 += str2; cout << "str1 = " << str1 << endl; string str3 = "I"; str3.append(" Love"); cout << "str3 = " << str3 << endl; str3.append(" game abcde", 5); cout << "str3 = " << str3 << endl; str3.append(str2); cout << "str3 = " << str3 << endl; str3.append(str2, 4, 6); cout << "str3 = " << str3 << endl; }

3.1.5 string查找和替换

功能描述：

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

函数原型：

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* 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个字符为字符串strstring& replace(int pos, int n, const char* s);//替换从pos开始的n个字符串为字符串s

rfind和find的区别： rfind：从右往左查找 find：从左往右查找 查找

//1、查找 void test01() { string str1 = "abcdefgde"; int pos = str1.find("de"); cout << "find pos = " << pos << endl;//pos = 3 //rfind() pos = str1.rfind("de"); cout << "rfind pos = " << pos << endl;//pos = 7 }

替换

//2、替换 void test01() { string str1 = "abcdefgde"; //从一号位置起的三个字符替换为 “1111” str1.replace(1, 3, "1111"); cout << "str1 = " << str1 << endl; }

总结：

find查找是从左往右，rfind从右往左find找到字符串后返回查找的第一个字符位置，找不到返回-1replace在替换时，要制定从哪个位置起，多少个字符，替换成什么样的字符串

3.1.6 string字符串比较

功能描述：

字符串之间的比较

比较方式：

字符串比较是按字符串的ADCII码进行对比

= 返回 0 > 返回 1 < 返回 -1

函数原型

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

3.1.7 string字符存取

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

char& operator[](int n);//通过[]方式取字符char& at(int n);//通过at方法获取字符 //string字符存取 void test01() { string str = "hello"; cout << "str = " << str << endl; cout << str[1] << endl; cout << str.at(1) << endl; //修改单个字符 str[0] = 'X'; str.at(1) = 'X'; cout << str << endl; }

3.1.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个字符cstring& erase(int pos, int n = npos);//删除从pos开始的n个字符 //string字符存取 void test01() { string str = "hello"; cout << "str = " << str << endl; cout << str[1] << endl; cout << str.at(1) << endl; //修改单个字符 str[0] = 'X'; str.at(1) = 'X'; cout << str << endl; }

3.1.9 string子串

功能描述：

从字符串中获取想要的子串

函数原型：

string substr(int pos = 0; int n = npos) const;//返回由pos开始的n个字符组成的字符串 void test01() { string str = "abcdef"; string subStr = str.substr(1, 3); cout << "subStr = " << subStr;//bcd } //使用操作 void test02() { string email = "hello@sina.com"; //从邮箱地址中获取用户名信息 int pos = email.find('@'); string name = email.substr(0, pos); cout << name << endl; }

3.2 vector容器

3.2.1 vector基本概念

功能：

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

vector与普通数组的区别：

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

动态扩展：

并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原有数据拷贝到新空间，释放原空间 vector容器的迭代器是支持随机访问的迭代器

3.2.2 vector构造函数

功能描述：

创建vector容器

函数原型：

vector<T> v;//采用模板实现类实现，默认构造函数vector(v.begin(), v.end())//将v[begin(), end())区间中的元素拷贝给本身vector(n, elem);//构造函数将n个elem拷贝给本身vector(const vector &vec);//拷贝构造函数 void printVector(vector<int>& v) { for (vector<int>::iterator it = v.begin(); it != v.end(); it++) { cout << *it << ' '; } cout << endl; } void test01() { vector<int> v1;//默认构造 无参构造 for (int i = 0; i < 10; i++) { v1.push_back(i); } printVector(v1); //通过区间的方式进行构造 vector<int> v2(v1.begin(), v1.end()); printVector(v2); //n个elem方式构造 vector<int> v3(10, 100); printVector(v3); //拷贝构造 vector<int> v4(v3); printVector(v4); }

3.2.3 vector赋值操作

功能描述：

给vector容器进行赋值

函数原型：

vector& operator=(const vector& vec);//重载等号操作符assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身assign(n, elem);//将n个elem拷贝赋值给本身 void printVector(vector<int>& v) { for (vector<int>::iterator it = v.begin(); it != v.end(); it++) { cout << *it << ' '; } cout << endl; } //vector的赋值 void test01() { vector<int> v1; for (int i = 0; i < 10; i++) { v1.push_back(i); } printVector(v1); //赋值 operator= vector<int> v2; v2 = v1; printVector(v2); //assign vector<int> v3; v3.assign(v1.begin(), v1.end()); printVector(v3); vector<int> v4; v4.assign(10, 100); printVector(v4); }

3.2.4 vector容量和大小

功能描述：

对vector容器的容量和大小操作

函数原型：

empty();//判断容器是否为空capacity();//容器的容量size();//返回容器中元素的个数resize(int num);//重新指定容器的长度为num, 若容器变长，则以默认值填充新的位置；如果容器变短，则末尾超出容器长度的元素被删除resize(int num, else);//重新指定容器的长度为num,若容器边长，则以elem值填充新的位置；如果容器变短，则末尾超出长度的元素被删除 void printVector(vector<int>& v) { for (vector<int>::iterator it = v.begin(); it != v.end(); it++) { cout << *it << ' '; } cout << endl; } //vector容器的容量和大小操作 void test01() { vector<int> v1; for (int i = 0; i < 10; i++) { v1.push_back(i); } printVector(v1); if (v1.empty()) { cout << "v1为空" << endl; } else { cout << "v1不为空" << endl; cout << "v1的容量为： " << v1.capacity() << endl; cout << "v1的大小为： " << v1.size() << endl; } //重新指定大小 v1.resize(15);//v1.resize(15, 100)指定用100填充 printVector(v1);//如果重新指定的长度过长，默认用0填充新的位置 v1.resize(5); printVector(v1);//如果重新指定的长度短了，超出部分会被删掉 } 判断是否为空 — empty返回元素个数 — size返回容器容量 — capacity重新指定大小 — resize

3.2.5 vector插入和删除

功能描述：

对vector容器进行插入、删除操作

函数原型：

push_back(ele); //尾部插入元素elepop_back();//删除最后一个元素insert(const_iterator pos, ele);//迭代器指向位置pos插入元素eleinsert(const_iterator pos, int count, ele);//迭代器指向位置pos插入count个元素eleerase(const_iterator pos);//删除迭代器指向的元素erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素clear();//删除容器中所有元素 void printVector(vector<int>& v) { for (vector<int>::iterator it = v.begin(); it != v.end(); it++) { cout << *it << ' '; } cout << endl; } //插入和删除 void test01() { vector<int> v1; //尾插 v1.push_back(10); v1.push_back(20); v1.push_back(30); v1.push_back(40); v1.push_back(50); //遍历 printVector(v1); //尾删 v1.pop_back(); printVector(v1);//删除了50 //插入 第一个参数为迭代器 v1.insert(v1.begin(), 100); printVector(v1); v1.insert(v1.begin(), 2, 1000); printVector(v1); //删除 参数也是迭代器 v1.erase(v1.begin()); printVector(v1); //清空 //v1.erase(v1.begin(), v1.end()); v1.clear(); printVector(v1); }

3.2.6 vector数据存取

功能描述：

对vector中的数据的存取操作

函数原型：

at(int idx);//返回索引idx所指的数据operator[];//返回索引所指的数据front();//返回容器中第一个数据元素back();//返回容器中最后一个数据元素 //vector容器 数据存取 void test01() { vector<int> v1; for (int i = 0; i < 10; i++) { v1.push_back(i); } //利用[]访问 for (int i = 0; i < 10; i++) { cout << v1[i] << " "; } cout << endl; //利用at()方式访问 for (int i = 0; i < 10; i++) { cout << v1.at(i) << ' '; } cout << endl; //获取第一个元素 cout << "第一个元素为： " << v1.front() << endl; //获取最后一个元素 cout << "最后一个元素为： " << v1.back() << endl; }

3.2.7 vector互换容器

功能描述：

实现两个容器内元素进行互换

函数原型：

swap(vec);//将vec与本身的元素互换 void printVector(vector<int>& v) { for (vector<int>::iterator it = v.begin(); it != v.end(); it++) { cout << *it << ' '; } cout << endl; } //vector互换容器 //1、基本使用 void test01() { vector<int> v1; for (int i = 0; i < 10; i++) { v1.push_back(i); } cout << "交换前" << endl; printVector(v1); vector<int> v2; for(int i = 10; i > 0; i--){ v2.push_back(i); } v1.swap(v2); cout << "交换后: " << endl; printVector(v1); } //2、实际用途 //巧用swap可以收缩内存空间 void test02() { vector<int> v; for (int i = 0; i < 100000; i++) { v.push_back(i); } cout << "v的容量为：" << v.capacity() << endl; cout << "v的大小为：" << v.size() << endl; v.resize(3);//重新制定大小 cout << "v的容量为：" << v.capacity() << endl;//容量没变，依然很大，空间浪费 cout << "v的大小为：" << v.size() << endl; //巧用swap()收缩内存 vector<int>(v).swap(v); cout << "v的容量为：" << v.capacity() << endl; cout << "v的大小为：" << v.size() << endl; }

代码解释： vector<int>(v).swap(v); vector<int>(v):匿名对象，利用v创建一个新的对象，但是没有名称，按v所用的元素个数来初始化匿名对象的大小，所以为 3。 .swap(v):做了容器的交换，指向容器的指针做了互换。然后因为匿名对象，匿名对象的内存被自动释放，达到了收缩内存的效果

3.2.8 vector预留空间

功能描述：

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

函数原型：

reserve(int len); //容器预留len个元素长度，预留位置不初始化，元素不可访问 //vector容器 预留空间 void test01() { vector<int> v; //不使用reserve时num = 30; //使用reserve后，num = 1; v.reserve(100001); int num = 0;//同积开辟次数 int* p = nullptr; for (int i = 0; i < 100000; i++) { v.push_back(i); if (p != &v[0]) { p = &v[0]; num++; } } cout << "num = " << num << endl; }

3.3 deque容器

3.3.1 deque容器基本概念

功能：

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

deque与vector区别：

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

deque内部工作原理：

deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据

中控器维护的时每个缓冲区的地址，使得使用deque时像一片连续的内存空间

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

3.3.2 deque构造函数

功能描述：

deque容器构造

函数原型：

deque<T> deqT;//默认构造形式deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身deque(n, elem);//构造函数将n个elem拷贝给本身deque(const deque& deq);//拷贝构造函数 #include <deque> void printDeque(const deque<int>& d) {//限定只读状态 for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) { //通过const，使得容器中的数据不可以修改 //*it = 100;报错 cout << *it << ' '; } cout << endl; } //deque构造函数 void test01() { deque<int> d1; for (int i = 0; i < 10; i++) { d1.push_back(i); } printDeque(d1); deque<int> d2(d1.begin(), d1.end()); printDeque(d2); deque<int> d3(10, 100); printDeque(d3); deque<int> d4(d3); printDeque(d4); }

3.3.3 deque赋值操作

功能描述：

给deque容器进行赋值

函数原型：

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

3.3.4 deque大小操作

功能描述：

对deque容器的大小进行操作

函数原型：

deque.empty();//判断容器是否为空deque.size();//返回容器中元素的个数deque.resize(num);//重新指定容器的长度为num, 若容器变长，则以默认值填充新的位置；如果容器变短，则末尾超出容器长度的元素被删除deque.resize(int num, else);//重新指定容器的长度为num,若容器边长，则以elem值填充新的位置；如果容器变短，则末尾超出长度的元素被删除 //deque容器大小操作 void test01() { deque<int> d1; for (int i = 0; i < 10; i++) { d1.push_back(i); } printDeque(d1); if (d1.empty()) { cout << "d1为空" << endl; } else { cout << "d1不为空" << endl; cout << "d1的大小： " << d1.size() << endl; //deque容器没有容量概念 } //重新指定大小 //d1.resize(15, 1),指定用1填充 d1.resize(15); printDeque(d1); d1.resize(5); printDeque(d1); }

3.3.5 deque插入和删除

功能描述：

向dequer容器中插入和删除数据

函数原型：

两端插入操作：

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);//删除[ebg, end)区间的数据，返回下一个数据的位置erase(pos);//删除pos位置的数据，返回下一个数据的位置 //deque容器插入和删除 //两端操作 void test01() { deque<int> d1; //尾插 d1.push_back(10); d1.push_back(20); //头插 d1.push_front(100); d1.push_front(200); printDeque(d1); //尾删 d1.pop_back(); printDeque(d1); //头删 d1.pop_front(); printDeque(d1); } void test02() { deque<int> d1; d1.push_back(10); d1.push_back(20); d1.push_front(100); d1.push_front(200); printDeque(d1); //insert()插入 d1.insert(d1.begin(), 1000); printDeque(d1); d1.insert(d1.begin(), 2, 10000); printDeque(d1); //按照区间进行插入 deque<int> d2; d2.push_back(1); d2.push_back(2); d2.push_back(3); d1.insert(d1.begin(), d2.begin(), d2.end()); printDeque(d1); } //删除 void test03() { deque<int> d1; d1.push_back(10); d1.push_back(20); d1.push_front(100); d1.push_front(200); deque<int>::iterator it = d1.begin(); it++; //删除 //d1.erase(d1.begin()); d1.erase(it); printDeque(d1); //按照区间方式删除 d1.erase(d1.begin(), d1.end()); printDeque(d1); d1.clear(); printDeque(d1); }

3.3.6 deque数据存取

功能描述：

对deque中的数据的存取操作

函数原型：

at(int idx); //返回索引idx所指的数据operator[];//返回索引所指的数据front();//返回容器中第一个数据元素back();//返回容器中最后一个数据元素 //deque容器的存取操作 void test01() { deque<int> d; d.push_back(10); d.push_back(20); d.push_back(30); d.push_front(100); d.push_front(200); d.push_front(300); //通过[]方式访问元素 for (int i = 0; i < d.size(); i++) { cout << d[i] << " "; } cout << endl; //通过at方式访问元素 for (int i = 0; i < d.size(); i++) { cout << d.at(i) << ' '; } cout << endl; cout << "第一个元素为： " << d.front() << endl; cout << "最后一个元素为： " << d.back() << endl; }

3.3.7 deque排序

功能描述：

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

算法：

sort(iterator beg, iterator end);//对beg和end区间内元素进行排序 //deque容器排序 void test01() { deque<int> d; d.push_back(10); d.push_back(20); d.push_back(30); d.push_front(100); d.push_front(200); d.push_front(300); printDeque(d); //排序 //对于支持随机访问的迭代器的容器，都可以利用sort算法直接对其进行排序 //vector容器也可以利用sort进行排序 sort(d.begin(), d.end()); printDeque(d); }

3.4 案例-评委打分

3.4.1 案例描述

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

3.4.2 实现步骤

创建五名选手，放到vector中遍历vector容器中，取出每一个选手，执行for循环，可以把10个评分打分存到deque容器中sort算法对deque容器中分数排序，去除最高分和最低分deque容器遍历一遍，累加总分获取平均分 #include <iostream> using namespace std; #include <algorithm> #include <string> #include <deque> #include <vector> #include <ctime> class Person { public: Person(string name, int score) { this->m_Name = name; this->m_score = score; } string m_Name; int m_score; }; void creatPerson(vector<Person>& v) { string nameSeed = "ABCDE"; for (int i = 0; i < 5; i++) { string name = "选手"; name += nameSeed[i]; name += '\t'; int score = 0; Person p(name, score); //将创建的Person对象，放入到容器中 v.push_back(p); } } //打分 void setScore(vector<Person>& v) { for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) { //将评委的分数放入deque容器中 deque<int> d; for (int i = 0; i < 10; i++) { int score = rand() % 40 + 60 + 1; // 60~100 d.push_back(score); } //测试 //cout << "选手：" << it->m_Name << "打分：" << endl; //for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++) { // cout << *dit << ' '; //} //cout << endl; //排序，去除最高最低分 sort(d.begin(), d.end()); d.pop_back(); d.pop_front(); //取平均分 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>& v) { for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) { cout << "姓名：" << it->m_Name << "平均分：" << it->m_score << endl; } } int main() { //随机数种子 srand((unsigned int)time(nullptr)); //1、创建5名选手 //存放选手的容器 vector<Person> v; creatPerson(v); //测试 //for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) { // cout << "姓名： " << (*it).m_Name << "分数： " << (*it).m_score << endl; //} //2、给5名选手打分 setScore(v); //3、显示最后得分 showScore(v); system("pause"); return 0; }

3.5 stack容器

3.5.1 stack基本概念

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

3.6 queue容器

3.6.1 queue 基本概念

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

3.7 list容器

3.7.1 list基本概念

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

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

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

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

优点

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

缺点

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

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

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

3.7.2 list构造函数

功能描述：

创建list容器

函数原型：

list<T> lst;//list采用模板类实现，对象的默认构造形式list(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身list(n, elem);//构造函数将n个elem拷贝给本身list(const list& lst);//拷贝构造函数 #include <list> void printList(const list<int>& L) { for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) { cout << *it << " "; } cout << endl; } //list容器的狗塑造函数 void test01() { list<int> L1; //添加数据 L1.push_back(10); L1.push_back(20); L1.push_back(30); L1.push_back(40); //遍历容器 printList(L1); //添加数据 list<int> L2(L1.begin(), L1.end()); printList(L2); //拷贝构造 list<int> L3(L2); printList(L3); //n个elem list<int> L4(10, 1000); printList(L4); }

3.7.3 list赋值和交换

功能描述：

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

函数原型：

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给自身assign(n, elem);//将n个elem拷贝赋值给本身list& operator=(const list &lst);//重载等号操作符swap(lst);//将lst与本身的元素互换 //list容器的赋值和交换 void test01() { list<int>l1; l1.push_back(10); l1.push_back(20); l1.push_back(30); l1.push_back(40); printList(l1); list<int> l2; l2 = l1;//operator= printList(l2); list<int> l3; l3.assign(l2.begin(), l2.end()); printList(l3); list<int> l4; l4.assign(10, 100); printList(l4); } void test02() { list<int>l1; l1.push_back(10); l1.push_back(20); l1.push_back(30); l1.push_back(40); printList(l1); list<int> l2; l2.assign(10, 100); cout << "交换前：" << endl; printList(l1); printList(l2); cout << "交换后：" << endl; l2.swap(l1); printList(l1); printList(l2); }

3.7.4 list大小操作

功能描述：

对list容器的大小进行操作

3.7.5 list插入和删除

功能描述：

对list容器进行数据的插入和删除

函数原型：

push_back(elem);//在容器尾部加入一个元素pop_back();//删除容器中最后一个元素push_front(elem);//在容器开头插入一个元素pop_front();//从从容器开头移除第一个元素insert(pos, elem);//在pos位置插elem元素的拷贝，返回新数据的位置insert(pos, n, elem);//在pos位置插入n个elem数据，无返回值insert(pos, beg, end);//在pos位置插入[beg, end)区间的数据，无返回值clear();//移除容器的所有数据erase(beg, end);//删除(beg, end]区间的数据，返回下一个数据的位置erase(pos);//删除pos位置的数据，返回下一个数据的位置remove(elem);//删除容器中所有与elem值匹配的元素 void printList(const list<int>& L) { for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) { cout << *it << " "; } cout << endl; } //list插入和删除 void test01() { list<int> l; //尾插 l.push_back(10); l.push_back(20); l.push_back(30); //头插 l.push_front(100); l.push_front(200); l.push_front(300); printList(l); //尾删 l.pop_back(); printList(l); //头删 l.pop_front(); printList(l); //insert插入 l.insert(l.begin(), 1000); printList(l); //删除 l.erase(l.begin()); printList(l); //移除 //remove删除List中所有匹配的值 l.push_back(10000); printList(l); l.remove(10000); printList(l); //清空 l.clear(); printList(l); }

3.7.6 list数据存取

功能描述：

对list容器中数据进行存取

函数原型：

front();//返回第一个元素back();//返回最后一个元素 void test01() { list<int> l; l.push_back(10); l.push_back(20); l.push_back(30); l.push_back(40); //l[0] 不可以用[]访问list容器中的元素 //l.at(0) 不可以用at方式访问list容器中的元素 //原因是list本质是链表，不是用连续线性空间存储数据，迭代器也不支持随机访问 cout << "第一个元素为：" << l.front() << endl; cout << "第二个元素为：" << l.back() << endl; //验证迭代器不支持随机访问 list<int>::iterator it = l.begin(); it++;//支持双向 it--; it = it + 1;//报错 不支持随机 }

3.7.7 list反转和排序

功能描述：

将容器中的元素反转，以及将容器中的数据进行排序

函数原型：

reverse();//反转链表sort();//链表排序 bool myCompare(int v1, int v2) { //降序 就让第一个数大于第二个数 return v1 > v2; } //反转和排序 void test01() { list<int> l; l.push_back(10); l.push_back(30); l.push_back(2); l.push_back(15); printList(l); //反转 l.reverse(); printList(l); //排序 l.sort();//默认升序 //所有不支持随机访问迭代器的容器，不可以用标准算法 //sort(l.begin(), l.end());//报错 printList(l); //降序 l.sort(myCompare); printList(l); }

总结：

反转 — reverse排序 — sort(成员函数)

3.7.8 排序案例

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

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

class Person { public: Person(string name, int age, int height) { this->m_Name = name; this->m_Age = age; this->m_Height = height; } string m_Name; int m_Age; int m_Height; }; //指定排序规则 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; } void test01() { 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, 200); //插入数据 l.push_back(p1); l.push_back(p2); l.push_back(p3); l.push_back(p4); l.push_back(p5); l.push_back(p6); for (list<Person>::const_iterator it = l.begin(); it != l.end(); it++) { cout << "姓名: " << (*it).m_Name << " " << "年龄: " << it->m_Age << " " << "身高: " << it->m_Height << endl; } //排序 cout << "---------------------------------" << endl; cout << "排序后：" << endl; l.sort(comparePerson); for (list<Person>::const_iterator it = l.begin(); it != l.end(); it++) { cout << "姓名: " << (*it).m_Name << " " << "年龄: " << it->m_Age << " " << "身高: " << it->m_Height << endl; } }

总结：

对于自定义数据类型，必须指定排序规则，否则编译器不知道如何进行排序高级排序只是在排序规则上再进行一次逻辑规则制定

五、C++提高编程(2)

---

六、基于STL泛化编程的演讲比赛

---

七、C++实战项目机房预约管理系统

---

学习产出：

1、github 啃STL简化项目，能够自己实现STL相关项目 2、做一个微信小程序，具体功能暂定