| [学习笔记] 3. C++ / CPP提高 | 您所在的位置：网站首页 › nametype › [学习笔记] 3. C++ / CPP提高 |
[学习笔记] 3. C++ / CPP提高
|
本阶段主要针对C++泛型编程和STL技术做详细讲解，探讨C++更深层的使用。 [学习笔记] 3. C++ / CPP提高 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（Standard Template Library，标准模板库）初识2.1 STL的诞生2.2 STL基本概念2.3 STL六大组件2.4 STL中容器、算法、迭代器1. 容器(Container)：置物之所也2. 算法：问题之解法也3. 迭代器：容器和算法之间的粘合剂 2.5 容器、算法、迭代器初识2.5.1 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插入和删除1. 两端插入操作2. 指定位置操作 3.3.6 deque数据存取3.3.7 deque排序 3.4案例：评委打分3.4.1 案例描述3.4.2 实现步骤 3.5 stack容器3.5.1 stack基本概念3.5.2 stack常用接口 3.6 queue容器3.6.1 queue基本概念3.6.2 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 排序案例 3.8 set / multiset容器3.8.1 set基本概念3.8.2 set构造和赋值3.8.3 set大小和交换3.8.4 set插入和删除3.8.5 set查找和统计3.8.6 set和multiset区别3.8.7 pair对组创建3.8.8 set容器排序示例一：set存放内置数据类型示例二：set存放自定义数据类型 3.9 map / multimap容器3.9.1 map基本概念3.9.2 map构造和赋值3.9.3 map大小和交换3.9.4 map插入和删除3.9.5 map查找和统计3.9.6 map容器排序拓展：自定义数据类型 3.10案例：员工分组3.10.1 案例描述3.10.2 实现步骤 4. STL：函数对象4.1 函数对象4.1.1 函数对象概念4.1.2 函数对象使用 4.2谓词4.2.1 谓词概念 4.3 内建国数对象4.3.1 算术仿函数4.3.2 关系仿函数4.3.3 逻辑仿函数 5. STL的常用算法5.1 常用遍历算法5.1.1 for_each5.1.2 transform 5.2 常用查找算法5.2.1 find5.2.2 find_if5.2.3 adjacent_find5.2.4 binary_search5.2.5 count5.2.6 count_if 5.3常用排序算法5.3.1 sort5.3.2 random_shuffle5.3.3 merge5.3.4 reverse 5.4 常用拷贝和替换算法5.4.1 copy5.4.2 replace5.4.3 replace_if5.4.4 swap 5.5 常用算术生成算法5.5.1 accumulate5.5.2 fill 5.6 常用集合算法5.6.1 set_intersection5.6.2 set_union5.6.3 set_differenceSTL（Standard Template Library，标准模板库）是 C++ 标准库的一部分，也是 C++ 中非常重要的一个技术。它是由 Alexander Stepanov 和 Meng Lee 于 1994 年开发的，旨在提供一组通用的、高效的数据结构和算法，能够满足大多数程序的需求。 STL 技术的核心是模板（template）和泛型编程（generic programming）。模板是一种 C++ 语言特性，可以让程序员编写通用的代码，而不用为不同的类型分别编写不同的代码。泛型编程则是一种编程理念，强调代码的通用性和复用性，通过使用模板来实现。 STL 中提供了多种容器（container）和算法（algorithm），容器是一种用于存储数据的对象，包括 vector、list、set、map 等；算法则是一些用于对容器中的数据进行操作的函数，包括排序、查找、遍历等。 此外，STL 还提供了迭代器（iterator）、函数对象（function object）和适配器（adapter）等辅助组件，帮助程序员更方便地使用容器和算法。 STL 技术的优点包括： 代码通用且重用性高，可以大大提高开发效率；STL 中的容器和算法都经过了充分测试和优化，具有高效性和可靠性；STL 技术为 C++ 中的面向对象编程和泛型编程提供了支持，使得程序设计更加灵活和可扩展。因此，STL 技术已经成为了 C++ 程序员必备的技能之一，广泛应用于各种领域的软件开发中。 1. 模板 1.1 模板的概念在 C++ 中，模板（template）是一种通用的代码结构，可以用于生成特定类型或值的代码。通过模板，程序员可以编写一次代码，然后使用不同的数据类型或值来实例化该模板，生成不同的代码实例。这种方式被称为泛型编程（generic programming），它可以提高代码的可重用性和通用性。 generic: 英[dʒəˈnerɪk] 美[dʒəˈnerɪk] adj. 通用的; 一般的; 普通的; 无厂家商标的; 无商标的; 模板就是建立通用的模具，大大提高复用性。 例如生活中的模板：一寸照片模板、PPT模板。 模板的特点： 模板不可以直接使用，它只是一个框架模板的通用并不是万能的 1.2 函数模板 C++另一种编程思想称为泛型编程（generic programming），主要利用的技术就是模板。C++提供两种模板机制：①函数模板和②类模板 1.2.1 函数模板语法函数模板作用：建立一个通用函数，其函数返回值类型和形参类型可以不具体制定，用一个虚拟的类型来代表。 语法： template 函数的声明或定义解释： template —— 声明创建模板typename —— 表面其后面的符号是一种数据类型，可以用class代替T —— 通用的数据类型，名称可以替换，通常为大写字母T(Template)。可以换别的名称，但一般用T比较清晰明了 总结： 函数模板利用关键字template使用函数模板有两种方式： 自动类型推导：函数名() —— swap_fn(a, b);显示指定类型：函数名() —— swap_fn(a, b); 模板的目的是为了提高复用性，将类型参数化 #include using namespace std; // 函数模板 // [传统方法]交互两个整型函数 void swap_int(int& a, int& b) { int tmp = a; a = b; b = tmp; } // [传统方法]交换两个浮点型函数 void swap_double(double& a, double& b) { double tmp = a; a = b; b = tmp; } void test01_01() { int a = 10; int b = 20; swap_int(a, b); cout /* 利用函数模板实现交换，有两种使用方式： 1. 自动类型推导：函数名() 2. 显示指定类型：函数名() */ int a = 10; int b = 20; // 1. 自动类型推导 swap_fn(a, b); cout T tmp = a; a = b; b = tmp; } void test02_01() { int a = 10; int b = 20; float c = 1.1f; // 1. 自动类型推导，必须推导出一致的数据类型T才可以使用 swap_02(a, b); // a和b的数据类型一致，没问题 // swap_02(a, c); // Error: 没有与参数列表匹配的函数模板"swap_02"实例 // 推导不出一致的数据类型 } // 2. 模板必须要确定出T的数据类型，才可以使用 template void func() { cout test02_01(); test02_02(); system("pause"); return 0; }总结：使用模板时必须确定出通用数据类型T，并且能够推导出一致的类型。 1.2. 3函数模板案例案例描述： 利用函数模板封装一个排序的函数，可以对不同数据类型数组进行排序。排序规则从大到小，排序算法为选择排序。 分别利用char数组和int数组进行测试。 示例： #include using namespace std; /* 实现通用 对数组进行排序的函数 规则：从大到小 算法：选择排序 测试：char数组、int数组 */ // 交换函数模板 template void swap_two_element(T& a, T& b) { T tmp = a; a = b; b = tmp; } // 利用模板写排序算法 template void select_sort(T arr[], int len) { /* * arr: 数组 * len: 数组的长度 */ for (int i = 0; i if (arr[max_idx] // 交换元素 swap_two_element(arr[max_idx], arr[i]); } } } // 打印数组的模板 template void print_array(T arr[], int len) { for (int i = 0; i // 测试：char数组 char char_arr[] = "badcfe"; int len = sizeof(char_arr) / sizeof(char); select_sort(char_arr, len); print_array(char_arr, len); // f e d c b a } void test03_02() { // 测试：int数组 int int_arr[] = { 7, 5, 1, 3, 9, 2, 4, 6, 8 }; int len = sizeof(int_arr) / sizeof(int); select_sort(int_arr, len); print_array(int_arr, len); // 9 8 7 6 5 4 3 2 1 } int main() { test03_01(); test03_02(); system("pause"); return 0; } 1.2.4 普通函数与函数模板的区别普通函数与函数模板区别： 普通函数调用时可以发生自动类型转换(隐式类型转换)函数模板调用时，如果利用自动类型推导，不会发生隐式类型转换如果利用显示指定类型的方式，可以发生隐式类型转换隐式类型转换是指在表达式中自动地将一种类型转换为另一种类型，而无需显式地使用类型转换运算符。例如，将整数类型转换为浮点数类型，或将字符类型转换为整数类型。隐式类型转换可以简化代码编写，但有时也可能导致意外的错误。因此，在进行隐式类型转换时需要格外小心。 下面是一个隐式类型转换的例子： int a = 10; double b = a; // 将整数类型a隐式转换为浮点数类型b在上面的代码中，a是整数类型，b是浮点数类型。当将a赋值给b时，C++会自动将a转换为浮点数类型，这个过程就是隐式类型转换。 示例： #include using namespace std; /* 普通函数与函数模板区别： 1. 普通函数调用时可以发生自动类型转换(隐式类型转换) 2. 函数模板调用时，如果利用自动类型推导，不会发生隐式类型转换 3. 如果利用显示指定类型的方式，可以发生隐式类型转换 */ // 普通函数 int add_fn_01(int a, int b) { return a + b; } void test04_01() { int a = 10; int b = 20; cout int a = 10; int b = 20; // 自动类型推导 cout cout cout test05_01(); // 调用普通函数 system("pause"); return 0; } 1.2.6 模板的局限性局限性： 模板的通用性并不是万能的例如： template void f(T a, T b) { a = b; }在上述代码中提供的赋值操作，如果传入的a和b是一个数组，就无法实现了。 再例如: template void f(T a, T b) { if (a > b) {...} }在上述代码中，如果T的数据类型传入的是像Person这样的自定义数据类型，也无法正常运行。 因此C++为了解决这种问题，提供模板的重载，可以为这些特定的类型提供具体化的模板。 语法：template 返回值类型 同名模板(具体参数类型 参数名称, ...) {} // 对比两个数据是否相等的函数模板 template bool my_compare(T& a, T& b) { if (a == b) { cout if (p1.name == p2.name && p1.age == p2.age) { cout if (a == b) { cout int a = 10; int b = 20; bool res = my_compare(a, b); } class Person { public: Person(string name, int age) { this->name = name; this->age = age; } public: string name; int age; }; // 利用具体化的Person的版本实现代码，具体化会优先调用 template bool my_compare(Person& p1, Person& p2) { if (p1.name == p2.name && p1.age == p2.age) { cout Person p1("Tom", 10); Person p2("Jerry", 10); // bool res = my_compare(p1, p2); // 二进制”==":"T"不定义该运算符或到预定义运算符可接收的类型的转换 /* 解决思路： 1. 运算符重载 2. 模板重载 */ bool res = my_compare(p1, p2); // 两者不相等 } int main() { test06_01(); test06_02(); system("pause"); return 0; } 1.3 类模板 1.3.1 类模板语法类模板作用：建立一个通用类，类中的成员数据类型可以不具体制定，用一个虚拟的类型来代表。 语法: template 类的声明或定义解释： template —— 声明创建模板typename —— 表面其后面的符号是一种数据类型，可以用class代替T —— 通用的数据类型，名称可以替换，通常为大写字母总结：类模板和函数模板语法相似，在声明模板template后面加类class，此类称为类模板。 示例： #include using namespace std; #include // 类模板 template class Person { public: Person(string name, int age) { this->name = name; this->age = age; } public: void show_info() { cout test01_01(); system("pause"); return 0; } 1.3.2 类模板与函数模板的区别类模板与函数模板区别主要有两点： 类模板没有自动类型推导的使用方式（必须要提前指定数据类型）类模板在模板参数列表中可以有默认参数（在实例化时，也必须要写）语法示例： // 1. 类模板没有自动类型推导的使用方式（必须要提前指定数据类型） template class Person01 { private: NameType name; AgeType age; }; Person01 p1("张三", 23); // 报错！类模板没有自动类型推导的使用方式 Person01 p1("张三", 23); // 不报错！（必须要提前指定数据类型） // 2. 类模板在模板参数列表中可以有默认参数 template class Person02 { private: NameType name; AgeType age; }; Person02 p2("李四", 20); // 报错！基本有默认参数，也必须要写 Person02 p2("李四", 20); // 不报错！总结： 类模板使用只能用显式指定类型方式类模板中的模板参数列表可以有默认参数类模板在实例化时必须有示例： #include using namespace std; #include /* 类模板与函数模板的区别： 1. 类模板没有自动类型推导的使用方式 2. 类模板在模板参数列表中可以有默认参数 */ template class Person02_1 { public: Person02_1(string name, int age) { this->name = name; this->age = age; } public: void show_info() { cout this->name = name; this->age = age; } public: void show_info() { cout // Person02_2 p = { "李四", 20 }; // 在实例化类模板的时候，必须有 Person02_2 p = { "李四", 20 }; p.show_info(); // name: 李四 age: 20 } int main() { test02_01(); test02_02(); system("pause"); return 0; } 1.3.3 类模板中成员函数创建时机类模板中成员函数和普通类中成员函数创建时机是有区别的： 普通类中的成员函数一开始就可以创建类模板中的成员函数在调用时才创建这是因为类模板的数据类型T不能确定，所以类模板中的成员函数一开始是不会创建的，只有在调用时，数据类型T才确定，此时类模板的成员函数才可以创建。 因此在使用类模板时，编译器代码生成可能不会报错，但会在运行时出错，此时问题一般发生在类模板的成员函数这里。 示例： #include using namespace std; #include /* 类模板中成员函数和普通类中成员函数创建时机是有区别的： + 普通类中的成员函数一开始就可以创建 + 类模板中的成员函数在调用时才创建 */ class Person03_01 { public: void show_info_1() { cout cout obj.show_info_1(); } void func_2() { obj.show_info_2(); } }; void test_03_01() { MyClass m; m.func_1(); m.func_2(); // Error: "show_info_2":不是"Person03_01"的成员 } int main() { test_03_01(); system("pause"); return 0; } 1.3.4 类模板对象做函数参数学习目标： 类模板实例化出的对象，向函数传参的方式。一共有三种传入方式： 指定传入的类型：直接显式对象的数据类型 —— 普通函数调用类模板参数模板化：将对象中的参数变为模板进行传递 —— 函数模板调用类模板整个类模板化：将这个对象类型模板化进行传递 —— 函数模板调用类模板语法示例： // 1. 指定传入的类型：直接显式对象的数据类型 void print_person_1(Person04& p) { p.show_info(); } // 2. 参数模板化：将对象中的参数变为模板进行传递 template void print_person_2(Person04& p) { p.show_info(); // 姓名: 李四 年龄: 20 cout public: Person04(T1 name, T2 age) { this->name = name; this->age = age; } public: void show_info() { cout Person04 p("张三", 23); print_person_1(p); // 姓名: 张三 年龄: 23 } // 2. 参数模板化：将对象中的参数变为模板进行传递 template void print_person_2(Person04& p) { p.show_info(); // 姓名: 李四 年龄: 20 cout p.show_info(); } void test04_03() { Person04 p("王五", 30); print_person_3(p); // 姓名: 王五 年龄: 30 cout private: T m; }; // 1. 当子类继承的父类是一个类模板时，子类在声明的时候，要指定出父类中`T`的类型。如果不指定，编译器无法给子类分配内存 —— 类继承类模板 /* class Son : public Base { // 必须要知道父类中T的类型，才能继承给子类 如果没有指定父类T的数据类型，那么子类就没法创建， 因为不知道到底该开拓多大的内存空间 }; */ class Son : public Base { // 显式说明父类模板数据类型 }; void test05_01() { Son s1; } // 2. 如果想灵活指定出父类中`T`的类型，子类也需变为类模板 —— 类模板继承类模板 template class Son2 : public Base { public: Son2() { cout test05_01(); test05_02(); system("pause"); return 0; } 1.3.6 类模板成员函数的类外实现学习目标：能够掌握类模板中的成员函数类外实现。 语法示例： // 类外实现 // 构造函数的类外实现 template Person06::Person06(T1 name, T2 age) { this->name = name; this->age = age; } // 成员函数的类外实现 template void Person06::show_info() { cout this->name = name; this->age = age; } // 成员函数的类外实现 template void Person06::show_info() { cout test06_01(); system("pause"); return 0; } 1.3.7 类模板分文件编写学习目标：掌握类模板成员函数分文件编写产生的问题以及解决方式。 问题： 类模板中成员函数创建时机是在调用阶段，导致分文件编写时链接不到。解决： 解决方式1：直接包含.cpp源文件解决方式2：将声明和实现写到同一个文件中，并更改后缀名为.hpp，hpp是约定的名称，并不是强制。总结：主流的解决方式是第二种，即类模板和其成员函数的实现写到一起，并将后缀名改为.hpp 示例： person.hpp中代码： #pragma once #include using namespace std; template class Person { public: Person(T1 name, T2 age); public: void show_info(); private: T1 name; T2 age; }; template Person::Person(T1 name, T2 age) { this->name = name; this->age = age; } template void Person::show_info() { cout test07_01(); system("pause"); return 0; } 1.3.8 类模板与友元学习目标：掌握类模板配合友元函数的类内和类外实现， 全局函数类内实现：直接在类内声明友元即可全局函数类外实现：需要提前让编译器知道全局函数的存在虽然友元函数的实现在类的内部，但它仍然是一个全局函数，因为它没有被声明为类的成员函数。它只是被声明为类的友元函数，因此它可以访问类的私有成员变量。 将它声明为全局函数的好处是，它可以在类的外部被访问和调用，而不需要创建类的实例。 Q：友元函数都是全局函数吗？ A：是的，友元函数通常是全局函数，因为它们在类外定义，但在类内声明。它们不是类的成员函数，因此可以在类的外部访问和调用。友元函数可以访问类的私有和保护成员，这使得它们非常有用，可以实现一些特殊的功能， 但应该谨慎使用友元函数，因为它们破坏了类的封装性。 对于类模板，全局函数的类内和类外实现的语法与普通类有所不同。以下是语法示例： 类内实现全局函数： // 1. 先写类模板 template class MyClass { public: // 2. 声明并实现友元函数 friend T myFunction(MyClass obj) { return obj.myValue + 1; // 具体实现 } private: T myValue = 0; };在这个示例中，myFunction函数被声明为MyClass的友元函数，并在类内定义为一个全局函数。由于MyClass是一个类模板，因此要在函数名后面加上模板参数T。 类外实现全局函数： // 1. 先写类模板的声明 template class MyClass; // 2. 全局函数的类外实现 template T myFunction(MyClass obj) { return obj.myValue + 1; // 具体实现 } // 3. 最后写类模板 template class MyClass { public: friend T myFunction(MyClass obj); // 声明友元函数且加上参数列表 private: T myValue = 0; };在这个示例中，myFunction函数被声明为MyClass的友元函数，并在类外定义为一个全局函数。由于MyClass是一个类模板，因此要在函数名后面加上模板参数T，并在函数定义前面加上template。 需要注意的是，类模板的友元函数的语法有些特殊，但它们的作用与普通类的友元函数相同。 总结：建议全局函数做类内实现，用法简单，而且编译器可以直接识别。类外实现太麻烦了！ 示例: #include using namespace std; #include // 类模板与友元 /* 通过全局函数打印Person08的信息： 1. 类内实现 2. 类外实现 */ template class Person08_01 { public: Person08_01(T1 name, T2 age) { this->name = name; this->age = age; } public: // 1. 全局函数：类内实现 /* 虽然print_person_01函数的实现在类的内部，但它仍然是一个全局 函数，因为它没有被声明为类的成员函数。它只是被声明为类的友元 函数，因此它可以访问类的私有成员变量。 将它声明为全局函数的好处是，它可以在类的外部被访问和调用，而 不需要创建类的实例。 Q：友元函数都是全局函数吗？ A：是的，友元函数通常是全局函数，因为它们在类外定义，但在类内 声明。它们不是类的成员函数，因此可以在类的外部访问和调用。友元 函数可以访问类的私有和保护成员，这使得它们非常有用，可以实现一 些特殊的功能，但应该谨慎使用，因为它们破坏了类的封装性。 */ friend void print_person_01(Person08_01& p) { cout cout this->name = name; this->age = age; } public: // 2. 全局函数：类外实现（类内只做声明，不做实现） // 需要加一个空模板的参数列表 // 如果全局函数是类外实现的话，需要让编译器提前知道这个函数的存在， // 即先写实现，再写声明（实现的代码在声明代码的上面） // 但这样会导致一个问题，实现的时候会用到Person08_02这个类，所以 // 我们还需要声明一下这个类模板 // 类外实现全局函数太过于麻烦了！ friend void print_person_02(Person08_02& p); private: T1 name; T2 age; }; // 2. 全局函数：类外实现 void test08_02() { Person08_02 p("Tom", 20); print_person_02(p); // [2. 全局函数的类外实现]name: Tom age: 20 } // 1. 先写类模板的声明 template class MyClass; // 2. 全局函数的类外实现 template T myFunction(MyClass obj) { return obj.myValue + 1; } // 3. 最后写类模板 template class MyClass { public: friend T myFunction(MyClass obj); // 声明友元函数且加上参数列表 private: T myValue = 0; }; void test08_03() { MyClass obj; int res = myFunction(obj); cout public: MyArray(int capacity) { // 有参构造 this->capacity = capacity; this->size = 0; this->ptr_address = new T[this->capacity]; } MyArray(const MyArray& arr) { // 拷贝构造（深拷贝） this->capacity = arr.capacity; this->size = arr.size; // this->ptr_address = arr.ptr_address; // 指针不能直接复制，否则会导致内存重复释放，应该使用深拷贝 this->ptr_address = new T[arr.capacity]; // 深拷贝 // 将arr中的数据都拷贝过来 for (int i = 0; i size; i++) { /* 使用已有对象的capacity属性来动态分配内存，以避免缓冲区溢出的问题。 同时，在写入数据之前，可以先判断写入的位置是否超出了缓冲区的范围，以避免缓冲区溢出的问题。 */ if (i capacity) { this->ptr_address[i] = arr.ptr_address[i]; } } } ~MyArray() { // 析构函数 if (this->ptr_address != NULL) { delete[] this->ptr_address; ptr_address = NULL; } } public: // 重载=操作符，防止浅拷贝问题 MyArray& operator=(const MyArray& arr) { // 先判断原来堆区是否有数据，如果有：先释放 if (this != &arr) // 在重载=操作符时，应该先判断是否自我赋值，否则可能会导致内存泄漏问题。 { if (this->ptr_address != NULL) { delete[] this->ptr_address; this->ptr_address = NULL; this->capacity = 0; this->size = 0; } // 再深拷贝 this->capacity = arr.capacity; this->size = arr.size; this->ptr_address = new T[arr.capacity]; for (int i = 0; i size; i++) { this->ptr_address[i] = arr.ptr_address[i]; } } return *this; // 返回自身 } // 尾插法 void push_back(const T& value) { // 判断容量是否等于大小 if (this->capacity == this->size) { cout this->size -= 1; } else { cout return this->capacity; } // 返回数组的大小（当前有几个元素） int get_size() { return this->size; } // 打印输出 void print() { cout cout cout cout public: Person09(); Person09(string name, int age); public: string get_name(); int get_age(); private: string name; int age; };person09.cpp中代码： #include "person09.h" // 类实现 Person09::Person09() {} Person09::Person09(string name, int age) { this->name = name; this->age = age; } string Person09::get_name() { return this->name; } int Person09::get_age() { return this->age; }主函数.cpp中代码： #include using namespace std; #include #include "MyArray.hpp" #include "person09.h" void test09_01() { MyArray arr1(5); // 有参构造 MyArray arr2(arr1); // 拷贝构造 MyArray arr3(100); arr3 = arr1; // =运算符 // arr1[0]; // 没有与这些操作数匹配的“"运算符 for (int i = 0; i MyArray arr(10); // 利用尾插法插入元素 arr.push_back(Person09("张三", 20)); arr.push_back(Person09("李四", 23)); arr.push_back(Person09("王五", 26)); arr.push_back(Person09("周六", 21)); arr.push_back(Person09("田七", 18)); // 打印数组 arr.print(true); // 这里对打印的成员函数进行重载，打印Person类型需要填入bool类型 // 姓名: 张三 年龄: 20, 姓名: 李四 年龄: 23, 姓名: 王五 年龄: 26, 姓名: 周六 年龄: 21, 姓名: 田七 年龄: 18 ] cout v.push_back(i * 10); } vector::iterator iter_begin = v.begin();; vector::iterator iter_end = v.end(); // 第一种遍历方式：while循环 while (iter_begin != iter_end) { cout vector v; // 向容器中插入数据 for (int i = 0; i cout v.push_back(i * 10); } vector::iterator iter_begin = v.begin();; vector::iterator iter_end = v.end(); // 第二种遍历方式：for循环 for (vector::iterator it = v.begin(); it != v.end(); it++) { cout vector v; for (int i = 0; i test01_01(); test01_02(); test01_03(); system("pause"); return 0; } 2.5.2 Vector存放自定义数据类型学习目标: vector中存放自定义数据类型，并打印输出。 对于vector：中是什么数据类型，那么解引用后就是什么数据类型。 举个例子： vector::iterator iter = v.begin(); // 那么*iter的数据类型就是Person*示例： #include using namespace std; #include // STL中每个容器使用前都需要包含其头文件 #include // 标准算法的头文件 #include // vector容器存放自定义数据类型 class Person { public: Person(string name, int age) { this->name = name; this->age = age; } public: string get_name() { return this->name; } int get_age() { return this->age; } private: string name; int age; }; // 存放自定义数据类型 void test02_01() { cout // cout cout // cout test02_01(); test02_02(); system("pause"); return 0; } 2.5.3 Vector容器嵌套容器学习目标：容器中嵌套容器，我们将所有数据进行遍历输出。 示例： #include using namespace std; #include // STL中每个容器使用前都需要包含其头文件 #include // 标准算法的头文件 #include // 容器嵌套容器 void test03_01() { vector v; // 创建小容器 vector v1; vector v2; vector v3; vector v4; // 向小容器中添加数据 for (int i = 0; i // *iter的数据类型是vector，所以还要遍历 for (vector::iterator iter2 = (*iter).begin(); iter2 != (*iter).end(); iter2++) { cout cout string s1; // 默认构造 // string s1(); // 两种写法都可以，因为都是默认构造 const char* str = "Hello World"; // C语言风格的字符串 string s2(str); // 有参构造 cout cout test_02_01(); system("pause"); return 0; } 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& append(const string& str, size_t pos, size_t n);而言，其中，str 是要追加的字符串，pos 是指定要追加的 str 中的起始位置，n 是指定要追加的字符数： 如果 pos 大于等于 str 的长度，则 append() 函数不会追加任何字符。如果如果 n 大于 str 中从 pos 位置开始的字符数，则只会追加 str 中从 pos 位置开始的所有字符。当 n 的值为 -1 时，append() 函数会将 str 中从 pos 位置开始的所有字符都追加到当前字符串的末尾，直到 str 的末尾为止。这相当于将 str 中从 pos 位置开始的所有字符全部追加到当前字符串的末尾。 需要注意的是，虽然在 C++11 标准中，string::append() 函数的 n 参数允许取负数，但是在 C++03 标准中，n 参数只能取非负数。因此，如果你使用的是 C++03 标准，你需要将 n 参数的值限制为非负数。 总结：空符串拼接的重载版本很多，初学阶段记住几种即可。 示例： #include using namespace std; #include // string字符串的拼接 /* 函数原型： 1. string& operator+=(const char* str); //重载+=操作符 2. string& operator+=(const char c); //重载+=操作符 3. string& operator+-(const string& str); //重载+=操作符 4. string& append(const char *s); //把字符串s连接到当前字符串结尾 5. string& append(const char *s, int n); //把字符串s的前n个字符连接到当前字符串结尾 6. string& append(const string &s); //同operator+=(const string& str) 7. string& append(const string &s, int pos, int n); //字符串s中从pos开始的n个字符连接到字符串结尾 */ void print_string(string str) { cout test03_01(); system("pause"); return 0; } 3.1.5 string查找和替换功能描述： 查找：查找指定字符串是否存在替换：在指定的位置替换字符串、函数原型： 函数重载含义int find(const string& str, int pos = e) const;查找str第一次出现位置，从pos开始查找int find(const char* s, int pos = 0) const;查找s第一次出现位置，从pos开始查找int find(const char* s, int pos, int n) const;从pos位置查找s的前n个字符第一次位置int find(const char c, int pos = 0) const;查找字符c第一次出现位置int rfind(const string& str, int pos = npos) const;查找str最后一次位置（从右往左查，只不过返回的位置还是从左往右计算的），从pos开始查找int rfind(const char* s, int pos = npos) const;查找s最后一次出现位置（从右往左查，只不过返回的位置还是从左往右计算的），从pos开始查找int rfind( const char* s, int pos, int n) const;从pos查找s的前n个字符最后一次位置（从右往左查，只不过返回的位置还是从左往右计算的）int rfind( const char c, int pos = 0) const;查找字符c最后一次出现位置（从右往左查，只不过返回的位置还是从左往右计算的）string& replace(int pos，int n,const string& str);替换从pos开始n个字符为字符串strstring& replace(int pos, int n,const char* s );替换从pos开始的n个字符为字符串s find：从左往右找rfind：从右往左找（但是返回的位置信息还是从左往右计算的）总结： find查找是从左往后，rfind从右往左find找到字符串后返回查找的第一个字符位置，找不到返回-1replace在替换时，要指定从哪个位置起，多少个字符，替换成什么样的字符串示例: #include using namespace std; #include // string字符串的查找与替换 /* 函数原型： 1. int find(const string& str, int pos = 0) const; //查找str第一次出现位置，从pos开始查找 2. int find(const char* s, int pos = 0) const; //查找s第一次出现位置，从pos开始查找 3. int find(const char* s, int pos, int n) const; //从pos位置查找s的前n个字符第一次位置 4. int find(const char c, int pos = 0) const; //查找字符c第一次出现位置 5. int rfind(const string& str, int pos = npos) const; //查找str最后一次位置，从pos开始查找 6. int rfind(const char* s, int pos = npos) const; //查找s最后一次出现位置，从pos开始查找 7. int rfind( const char* s, int pos, int n) const; //从pos查找s的前n个字符最后一次位置 8. int rfind( const char c, int pos = 0) const; //查找字符c最后一次出现位置 9. string& replace(int pos，int n,const string& str); //替换从pos开始n个字符为字符串str 10. string& replace(int pos, int n,const char* s ); //替换从pos开始的n个字符为字符串s */ template void my_print(T elem) { cout test04_01(); system("pause"); return 0; } 3.1.6 string字符串比较功能描述：字符串之间的比较。 比较方式：字符串比较是按字符的ASCII码进行对比。 情况返回值=0>1B，返回1。只有两个字符串的字符相等时，才会对比第二个字符。函数原型： 函数重载含义int compare(const string &s) const;与字符串s比较int compare(const char *s) const;与字符串s比较注意：字符串比较其实应用的场景比较受限，因为对于英文字符串而言，还可以通过ASCII码进行比较，对于中文而言，得到哪个字符串大或哪个字符串小是没有什么意义的。所以在应用中，我们对比两个字符长的目的，主要是想知道这两个字符串是否相等，仅此而已！ 中文字符串的比较不是ASCII码，因为就没有，而是将其转换为Unicode编码，再做比较。 示例： #include using namespace std; #include // string字符串的比较 void test05_01() { string str1 = "haaaa"; string str2 = "Haaaa"; if (str1.compare(str2) == 0) { cout cout cout string str = "Hello"; // 1. 通过[]访问单个字符 for (int i = 0; i cout // 1. string& insert(int pos, const char* s); //插入字符串 string str = "Hello"; str.insert(1, "11111"); cout string str = "abcdefg"; string sub_str = str.substr(0, 3); cout string user_name = email.substr(0, idx); cout string cooperation_name = email.substr(idx + 1, pos); cout test08_01(); test08_02(); system("pause"); return 0; } 3.2 vector容器向量容器。 3.2.1 vector基本概念功能：vector数据结构和数组非常相似，也称为单端数组。 vector与普通数组区别：不同之处在于数组是静态空间，而vector可以动态扩展。 动态扩展：并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间。 因为很有可能后面的内存空间已经被别人用到了，申请不到了。
注意：vector容器的迭代器是支持随机访问的迭代器（最强悍的迭代器）。 3.2.2 vector构造函数功能描述：创建vector容器。 函数原型： 函数重载含义vector v;采用模板实现类实现，默认构造函数vector(v.begin(), v.end());将v[ begin(), end() )区间（左闭右开）中的元素拷贝给本身vector(n, elem);构造函数将n个elem拷贝给本身vector(const vector &vec);拷贝构造函数总结: vector的多种构造方式没有可比性，灵活使用即可。 示例： #include using namespace std; #include #include // vector容器构造 /* 1. vector v; //采用模板实现类实现，默认构造函数 2. vector(v.begin(), v.end()); //将v[ begin(), end() )区间（左闭右开）中的元素拷贝给本身 3. vector(n, elem); //构造函数将n个elem拷贝给本身 4. vector(const vector &vec); //拷贝构造函数 */ template void print_vector(vector& v) { for (typename vector::iterator iter = v.begin(); iter != v.end(); iter++) { cout v1.push_back(i); } print_vector(v1); // 0 1 2 3 4 5 6 7 8 9 // 2. vector(v.begin(), v.end()); //将v[ begin(), end() )区间（左闭右开）中的元素拷贝给本身 vector v2(v1.begin(), v1.end()); print_vector(v2); // 0 1 2 3 4 5 6 7 8 9 // 3. vector(n, elem); //构造函数将n个elem拷贝给本身 vector v3(5, 100); print_vector(v3); // 100 100 100 100 100 // 4. vector(const vector &vec); //拷贝构造函数 vector v4(v3); print_vector(v4); // 100 100 100 100 100 } int main() { test01_01(); system("pause"); return 0; } 3.2.3 vector赋值操作功能描述：给vector容器进行赋值。 函数原型： 函数重载含义vector& operator=(const vector &vec);重载等号操作符assign(beg, end);将[beg, end)区间中的数据拷贝赋值给本身assign(n, elem);将n个elem拷贝赋值给本身总结: vector赋值方式比较简单，使用operator=，或者assign都可以 示例： #include using namespace std; #include #include // vector容器的赋值操作 /* 1. vector& operator=(const vector &vec); //重载等号操作符 2. assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身 3. assign(n, elem); //将n个elem拷贝赋值给本身 */ template void print_vector(vector& vec) { for (class vector::iterator iter = vec.begin(); iter != vec.end(); iter++) { cout v1.push_back(i); } print_vector(v1); // 0 1 2 3 4 5 6 7 8 9 // 1. vector& operator=(const vector &vec); //重载等号操作符 vector v2; v2 = v1; print_vector(v2); // 0 1 2 3 4 5 6 7 8 9 // 2. assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身 vector v3; v3.assign(v1.begin(), v1.end()); print_vector(v3); // 3. assign(n, elem); //将n个elem拷贝赋值给本身 vector v4; v4.assign(10, 'A'); print_vector(v4); // A A A A A A A A A A } int main() { test_02(); system("pause"); return 0; } 3.2.4 vector容量和大小功能描述：对vector容器的容量和大小操作。 函数原型： 函数重载含义empty();判断容器是否为空capacity();容器的容量size();返回容器中元素的个数resize(int num);重新指定容器的长度为num，用默认构造填充resize(int num, elem);重新指定容器的长度为num，用elem填充在调用 C++ 中的 vector 容器的 resize() 方法时，如果不提供任何值，则会使用默认构造函数来初始化新元素。也就是说，默认值取决于元素类型的默认构造函数。例如，如果元素类型是 int，则新元素将被初始化为 0。如果元素类型是自定义类，则必须提供该类的默认构造函数。如果提供了值，则使用提供的值来初始化新元素。 对于resize(int num);而言： 如果容器变长，则以默认值填充新位置如果容器变短，则末尾超出容器长度的元素被删除对于resize(int num, elem);而言： 如果器变长，则以elem值填充新位置如果容器变短，则末尾超出容器长度的元素被删除示例： #include using namespace std; #include #include // vector容器的容量和大小 /* 1. empty(); //判断容器是否为空 2. capacity(); //容器的容量 3. size(); //返回容器中元素的个数 4. resize(int num); //重新指定容器的长度为num 5. resize(int num, elem); //重新指定容器的长度为num，用elem填充 */ template void print_vec(vector& vec) { for (typename vector::iterator iter = vec.begin(); iter != vec.end(); iter++) { cout v1.push_back(i); } print_vec(v1); // 0 1 2 3 4 5 6 7 8 9 // 1. empty(); //判断容器是否为空 if (v1.empty()) { cout test03(); system("pause"); return 0; } 3.2.5 vector插入和删除功能描述：对vector容器进行插入、删除操作。 函数原型： 函数重载含义push_back(elem);尾部插入元素elempop_back();删除最后一个元素insert(const_iterator pos, elem);迭代器指向位置pos插入元素eleminsert(const_iterator pos, int count, elem);迭代器指向位置pos插入count个elem元素erase(const_iterator pos);删除迭代器指向的元素erase(const_iterator start, const_iterator end);删除迭代器从start到end之间的元素clear();删除容器中所有元素注意：const_iterator pos这是一个迭代器对象，即vector::iterator，一般我们可以传入.begin(), .end()，+ int也是可以的。 总结： 尾插 — push_back尾删 — pop_back插入 — insert(位置迭代器)删除 — erase(位置迭代器)清空 — clear示例: #include using namespace std; #include #include // vector容器的插入和删除 /* 1. push_back(elem); // 尾部插入元素elem 2. pop_back(); // 删除最后一个元素 3. insert(const_iterator pos, elem); // 迭代器指向位置pos插入元素elem 4. insert(const_iterator pos, int count, elem); // 迭代器指向位置pos插入count个elem元素 5. erase(const_iterator pos); // 删除迭代器指向的元素 6. erase(const_iterator start, const_iterator end); // 删除迭代器从start到end之间的元素 7. clear(); // 删除容器中所有元素 */ template void print_vec(vector& vec) { for (typename vector::iterator iter = vec.begin(); iter != vec.end(); iter++) { cout // 1. push_back(elem); // 尾部插入元素elem v1.push_back(i * 10); } print_vec(v1); // 10 20 30 40 50 // 2. pop_back(); // 删除最后一个元素 v1.pop_back(); print_vec(v1); // 10 20 30 40 // 3. insert(const_iterator pos, elem); // 迭代器指向位置pos插入元素elem v1.insert(v1.begin(), 100); print_vec(v1); // 100 10 20 30 40 v1.insert(v1.begin() + 3, 200); print_vec(v1); // 100 10 20 200 30 40 // 4. insert(const_iterator pos, int count, elem); // 迭代器指向位置pos插入count个elem元素 v1.insert(v1.begin(), 2, 1000); print_vec(v1); // 1000 1000 100 10 20 200 30 40 // 5. erase(const_iterator pos); // 删除迭代器指向的元素 v1.erase(v1.begin()); print_vec(v1); // 1000 100 10 20 200 30 40 // 6. erase(const_iterator start, const_iterator end); // 删除迭代器从start到end之间的元素 v1.erase(v1.begin(), v1.end() - 3); print_vec(v1); // 200 30 40 // 7. clear(); // 删除容器中所有元素 v1.clear(); print_vec(v1); // } int main() { test04(); system("pause"); return 0; } 3.2.6 vector数据存取功能描述：对vector中的数据的存取操作。 函数原型： 函数重载含义at(int idx);返回索引idx所指的数据operator[];返回索引idx所指的数据front();返回容器中第一个数据元素back();返回容器中最后一个数据元素总结： 除了用迭代器获取vector容器中元素，[]和at也可以front返回容器第一个元素back返回容器最后一个元素示例： #include using namespace std; #include #include // vector容器的数据存取 /* 1. at(int idx); // 返回索引idx所指的数据 2. operator[]; // 返回索引idx所指的数据 3. front(); // 返回容器中第一个数据元素 4. back(); // 返回容器中最后一个数据元素 */ void test05() { vector vec; for (int i = 0; i cout cout for (int i = 0; i vector vec1; for (int i = 0; i vec2.push_back(i); } cout vec.push_back(i); } cout vector vec; /* 因为vector容器是动态扩展的，因此在插入这10万个数的过程中， 会不断的扩展自己的内存占用，那么究竟分配了多少次内存？ */ int count = 0; // 统计开辟次数 int* ptr = NULL; for (int i = 0; i ptr = &vec[0]; count += 1; } } cout vec.push_back(i); if (ptr != &vec[0]) { ptr = &vec[0]; count += 1; } } cout // 添加const防止修改 // 因为形参是const，所以迭代器应该是只读的迭代器，即const_iterator，而不是iterator for (typename deque::const_iterator iter = deq.begin(); iter !=deq.end(); iter++) { cout cout d1.push_back(i); } print_deque(d1); // 0 1 2 3 4 5 6 7 8 9 // 2. deque(beg, end); // 构造函数将[beg, end)（左闭右开）区间中的元素拷贝给本身 deque d2(d1.begin(), d1.end() - 3); print_deque(d2); // 0 1 2 3 4 5 6 // 3. deque(n, elem); // 构造函数将n个elem拷贝给本身 deque d3(5, "Hello"); print_deque(d3); // Hello Hello Hello Hello Hello // 4. deque(const deque & deq); // 拷贝构造函数 deque d4(d3); print_deque(d4); // Hello Hello Hello Hello Hello } int main() { test01(); system("pause"); return 0; } 3.3.3 deque赋值操作功能描述：给deque容器进行赋值。 函数原型： 函数重载含义deque& operator=(const deque &deq);重载等号操作符assign(beg, end);将[beg, end)（左闭右开）区间中的数据拷贝赋值给本身assign(n, elem);将n个elem拷贝赋值给本身总结：deque赋值操作也与vector相同，需熟练掌握。 示例： #include using namespace std; #include #include // deque容器的赋值操作 /* 1. deque& operator=(const deque &deq); // 重载等号操作符 2. assign(beg, end); // 将[beg, end)（左闭右开）区间中的数据拷贝赋值给本身 3. assign(n, elem); // 将n个elem拷贝赋值给本身 */ template void print_deque(const deque& deq) { for (typename deque::const_iterator iter = deq.begin(); iter != deq.end(); iter++) { cout d1.push_back(i); } print_deque(d1); // 0 1 2 3 4 5 6 7 8 9 // 1. deque& operator=(const deque &deq); // 重载等号操作符 deque d2; d2 = d1; print_deque(d2); // 0 1 2 3 4 5 6 7 8 9 // 2. assign(beg, end); // 将[beg, end)（左闭右开）区间中的数据拷贝赋值给本身 deque d3; d3.assign(d1.begin() + 2, d1.end() - 1); print_deque(d3); // 2 3 4 5 6 7 8 // 3. assign(n, elem); // 将n个elem拷贝赋值给本身 deque d4; d4.assign(5, 'A'); print_deque(d4); // A A A A A } int main() { test(); // 0 1 2 3 4 5 6 7 8 9 system("pause"); return 0; } 3.3.4 deque大小操作功能描述：对deque容器的大小进行操作。 函数原型： 函数重载含义deque.empty();判断容器是否为空deque.size();返回容器中元素的个数deque.resize(num);重新指定容器的长度为numdeque.resize(num, elem);重新指定容器的长度为num总结：deque大小操作也与vector相同，需熟练掌握。 deque容器和vector容器的区别： vector容器有capacity()方法，而deque容器是没有这个方法的，因为二者的本质结构不同示例： #include using namespace std; #include #include // deque容器的赋值操作 /* 1. deque.empty(); // 判断容器是否为空 2. deque.size(); // 返回容器中元素的个数 3. deque.resize(num); // 重新指定容器的长度为num 4. deque.resize(num, elem); // 重新指定容器的长度为num */ template void print_deque(const deque& deq) { for (typename deque::const_iterator iter = deq.begin(); iter != deq.end(); iter++) { cout deq.push_back(i); } print_deque(deq); // 0 1 2 3 4 5 6 7 8 9 // 1. deque.empty(); // 判断容器是否为空 if (deq.empty()) { cout test(); system("pause"); return 0; } 3.3.5 deque插入和删除功能描述：向deque容器中插入和删除数据。 1. 两端插入操作函数原型： 函数重载含义push_back(elem);在容器尾部添加一个数据push_front(elem);在容器头部插入一个数据pop_back();删除容器最后一个数据pop_front();删除容器第一个数据 2. 指定位置操作函数原型： 函数重载含义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位置的数据，返回下一个数据的位置（返回值类型是迭代器）总结： 插入和删除提供的位置是迭代器!（传入固定数字是不行的，因为指针的位置不是从0开始的😂）尾插 — push_back尾删 — pop_back头插 — push_front头删 — pop_front示例： #include using namespace std; #include #include // deque容器的删除与插入操作 /* 两端插入操作： 1. push_back(elem); // 在容器尾部添加一个数据 2. push_front(elem); // 在容器头部插入一个数据 3. pop_back(); // 删除容器最后一个数据 4. pop_front(); // 删除容器第一个数据 指定位置操作： 1. insert(pos, elem); // 在pos位置插入一个elem元素的拷贝，返回新数据的位置（返回值类型是迭代器） 2. insert(pos, n, elem); // 在pos位置插入n个elem教据，无返回值 3. insert(pos, beg, end); // 在pos位置插入[beg, end)区间（左闭右开）的数据，无返回值 4. clear(); // 清空容器的所有数据 5. erase(beg, end); // 删除[beg, end)区间（左闭右开）的数据，返回下一个数据的位置（返回值类型是迭代器） 6. erase(pos); // 删除pos位置的数据，返回下一个数据的位置 */ template void print_deque(const deque& deq) { for (typename deque::const_iterator iter = deq.begin(); iter != deq.end(); iter++) { cout deque deq; for (int i = 1; i test01(); test02(); system("pause"); return 0; } 3.3.6 deque数据存取功能描述：对deque中的数据的存取操作。 函数原型： 函数重载含义at(int idx);返回索引idx所指的数据operator[];返回索引idx所指的数据front();返回容器中第一个数据元素back();返回容器中最后一个数据元素总结：deque取存操作也与vector相同，需熟练掌握。 示例： #include using namespace std; #include #include // deque容器的数据存取 /* 1. at(int idx); // 返回索引idx所指的数据 2. operator[]; // 返回索引idx所指的数据 3. front(); // 返回容器中第一个数据元素 4. back(); // 返回容器中最后一个数据元素 */ void test() { deque deq; deq.push_back(10); deq.push_back(20); deq.push_back(30); deq.push_front(100); deq.push_front(200); deq.push_front(300); // 1. at(int idx); // 返回索引idx所指的数据 for (int i = 0; i cout for (typename deque::const_iterator iter = deq.begin(); iter != deq.end(); iter++) { cout test(); system("pause"); return 0; } 3.4案例：评委打分 3.4.1 案例描述有5名选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委中最低分，取平均分。 3.4.2 实现步骤 创建五名选手，放到vector容器中遍历vector容器，取出每一个选手，执行for循环，可以把10个评分打分存到deque容器中sort()算法对deque容器中分数排序，去除最高和最低分deque容器遍历一遍，累加总分获取平均分使用deque容器是因为它对头和尾的操作支持比较好 示例代码： #include using namespace std; #include #include #include #include /* 有5名选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委中最低分，取平均分。 */ class Person { public: Person() {} Person(string name, int score) { this->name = name; this->score = score; } ~Person() {} public: string get_name() { return this->name; } int get_score() { return this->score; } void set_name(string name) { this->name = name; } void set_score(int score) { this->score = score; } private: string name; int score; }; void create_player(vector& vec) { string name_seed = "ABCDE"; for (int i = 0; i for (vector::iterator iter = vec.begin(); iter != vec.end(); iter++) { // 将评委的分数放入deque容器中 deque deq; for (int i = 0; i sum += *de_iter; } int avg = sum / deq.size(); // 将平均分赋值给Player iter->set_score(avg); } } int main() { // 设置随机种子 srand(time(NULL)); // 1. 创建5名选手 vector vec; // 存放选手的容器 create_player(vec); // 2. 给5名选手打分 set_score(vec); // 3. 显示最后得分 for (vector::iterator iter = vec.begin(); iter != vec.end(); iter++) { cout stk.push(i * 10); } cout test(); system("pause"); return 0; } 3.6 queue容器 3.6.1 queue基本概念概念：Queue是一种先进先出(First In First Out，FIFO)的数据结构，它有两个出口。
功能描述：栈容器常用的对外接口。 函数原型： 性质函数重载含义构造函数queue que;queue采用模板类实现，queue对象的默认构造形式构造函数queue(const queue& que);拷贝构造函数赋值操作queue& operator=(const queue& que);重载等号操作符数据存取push(elem);往队尾添加元素数据存取pop();从队头移除第一个元素数据存取back();返回最后一个元素数据存取front();返回第一个元素大小操作empty();判断堆栈是否为空大小操作size();返回栈的大小总结：常用接口如下 入队 — push()出队 — pop()返回队头元素 — front()返回队尾元素 — back()判断队是否为空 — empty()返回队列大小 — size()示例： #include using namespace std; #include #include // 队列queue容器 /* 1. 构造函数：queue que; // queue采用模板类实现，queue对象的默认构造形式 2. 构造函数：queue(const queue& que); // 拷贝构造函数 3. 赋值操作：queue& operator=(const queue& que); // 重载等号操作符 4. 数据存取：push(elem); // 往队尾添加元素 5. 数据存取：pop(); // 从队头移除第一个元素 6. 数据存取：back(); // 返回最后一个元素 7. 数据存取：front(); // 返回第一个元素 8. 大小操作：empty(); // 判断堆栈是否为空 9. 大小操作：size(); // 返回栈的大小 */ class Person { public: Person(string name, int age) { this->name = name; this->age = age; } public: string get_name() { return this->name; } int get_age() { return this->age; } void set_name(string name) { this->name = name; } void set_age(int age) { this->age = age; } private: string name; int age; }; void test() { queue que; Person p1("张三", 20); Person p2("李四", 30); Person p3("王五", 35); Person p4("赵六", 40); que.push(p1); que.push(p2); que.push(p3); que.push(p4); cout test(); system("pause"); return 0; } 3.7 list容器问：C++中的list和Python中的list是一回事吗？ 答：虽然它们都叫做list，但是C++中的list和Python中的list是不同的数据结构。 在Python中，list是一种动态数组（dynamic array），它可以存储任意类型的数据，而且大小可以动态地调整。Python的list支持随机访问，也就是说可以通过下标访问任意位置的元素，并且支持切片操作、迭代等常见操作。而在C++中，list是一种双向链表（doubly linked list），它也可以存储任意类型的数据，但是不支持随机访问，只能通过迭代器（iterator）访问元素。C++的list支持高效的插入和删除操作，但是在访问元素时效率较低，因为需要从头或尾开始遍历链表。因此，虽然它们都叫做list，但是它们的实现方式和使用方法有很大的不同。 Python中list是列表；而C++中list是双向链表！ 3.7.1 list基本概念功能：将数据进行链式存储。 链表（list）是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。 链表的组成：链表由一系列结点组成。 结点的组成：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表的优点： 可以对任意位置进行快速插入或删除元素。链表的缺点： list的遍历速度没有数组array快（array是连续的内存空间）list占用空间比array大（除了数据外要一个指针）STL中的链表是一个双向循环链表，如下图所示：
由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器。 list的优点： 采用动态存储分配，不会造成内存浪费和溢出链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素 list的缺点： 链表灵活，但是空间(指针域)和时间(遍历)额外耗费较大list有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。 在C++中，list容器的插入和删除操作不会造成原有list迭代器的失效，这是因为list容器的元素在内存中是通过双向链表连接起来的，每个元素都有指向前一个元素和后一个元素的指针。当进行插入或删除操作时，只需要修改相应元素的指针，不会涉及到其他元素的内存位置，因此不会造成迭代器的失效。而在vector容器中，由于元素在内存中是连续存储的，当进行插入或删除操作时，可能会导致其他元素的内存位置发生改变，从而使得迭代器失效。因此，在vector容器中进行插入或删除操作时需要格外小心，以避免迭代器失效的问题。 总结：STL中list和vector是两个最常被使用的容器，各有优缺点。 在C++中，动态分配内存的容器包括： vector：动态分配连续的内存空间，支持快速的随机访问和尾部插入/删除操作。list：动态分配非连续的内存空间，支持快速的插入/删除操作。deque：动态分配多个连续的内存块，支持快速的随机访问和头尾插入/删除操作。map：动态分配内存空间，按照键值对的方式存储数据，支持快速的查找操作。set：动态分配内存空间，按照键值存储数据，支持快速的查找操作。而静态分配内存的容器包括： array：静态分配连续的内存空间，其大小在编译时就已经确定，无法动态改变。forward_list：静态分配非连续的内存空间，其大小在编译时就已经确定，无法动态改变。需要注意的是，虽然array和forward_list都是静态分配内存的容器，但它们的实现方式不同。array是连续的内存空间，而forward_list是非连续的内存空间。 3.7.2 list构造函数功能描述：创建list容器。 函数重载含义list lst;list采用采用模板类实现对象的默认构造形式list(beg, end);构造函数将[beg, end)区间（左闭右开）中的元素拷贝给本身list(n, elem);构造函数将n个elem拷贝给本身list(const list &lst);拷贝构造函数总结：list构造方式同其他几个STL常用容器，熟练掌握即可。 主要注意的是，区间构造的方式不能加减内存地址了，因为list的存储方式和array、vector、deque不同！ 示例： #include using namespace std; #include #include // 链表list容器 /* 1. list lst; // list采用采用模板类实现对象的默认构造形式 2. list(beg, end); // 构造函数将[beg, end)区间（左闭右开）中的元素拷贝给本身 3. list(n, elem); // 构造函数将n个elem拷贝给本身 4. list(const list &lst); // 拷贝构造函数 */ template void print_list(const list& lst) { for (typename list::const_iterator iter = lst.begin(); iter != lst.end(); iter++) { cout lst.push_back((i + 1) * 10); } print_list(lst); // 10 20 30 40 50 // 2. list(beg, end); // 构造函数将[beg, end)区间（左闭右开）中的元素拷贝给本身 list lst2(lst.begin(), lst.end()); // list lst2(lst.begin() + 1, lst.end() - 2); // 因为list链表的内存地址不是连续的，所以不能加减了 print_list(lst2); // 10 20 30 40 50 // 3. list(n, elem); // 构造函数将n个elem拷贝给本身 list lst3(lst2); print_list(lst3); // 10 20 30 40 50 // 4. list(const list & lst); // 拷贝构造函数 list lst4(10, 'A'); print_list(lst4); // A A A A A A A A A A } int main() { test(); 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与本身的元素互换总结：list赋值和交换操作能够灵活运用即可。 示例： #include using namespace std; #include #include // 链表list容器的赋值和交换 /* 1. assign(beg, end); // 将[beg, end)区间（左开右闭）中的数据拷贝赋值给本身 2. assign(n, elem); // 将n个elem拷贝赋值给本身 3. list& operator=(const list& lst); // 重载等号操作符 4. swap(lst); // 将lst与本身的元素互换 */ template void print_list(const list& lst) { for (typename list::const_iterator iter = lst.begin(); iter != lst.end(); iter++) { cout lst1.push_back(i); } print_list(lst1); // 0 1 2 3 4 // 1. assign(beg, end); // 将[beg, end)区间（左开右闭）中的数据拷贝赋值给本身 list lst2; lst2.assign(lst1.begin(), lst1.end()); print_list(lst2); // 0 1 2 3 4 // 2. assign(n, elem); // 将n个elem拷贝赋值给本身 list lst3; lst3.assign(10, 'A'); print_list(lst3); // A A A A A A A A A A // 3. list & operator=(const list & lst); // 重载等号操作符 list lst4; lst4 = lst3; print_list(lst4); // A A A A A A A A A A // 4. swap(lst); // 将lst与本身的元素互换 list lst5; lst5.assign(5, 'B'); print_list(lst4); // A A A A A A A A A A print_list(lst5); // B B B B B lst5.swap(lst4); // 交互两个链表 print_list(lst4); // B B B B B print_list(lst5); // A A A A A A A A A A } int main() { test(); system("pause"); return 0; } 3.7.4 list大小操作功能描述：对list容器的大小进行操作。 函数重载含义size();返回容器中元素的个数empty();判断容器是否为空resize(num);重新指定容器的长度为num，默认值为数据类型的默认构造resize(num, elem);重新指定容器的长度为num，以elem值填充新位置总结： 判断是否为空 — empty()返回元素个数 — size()重新指定个数 — resize()示例： #include using namespace std; #include #include // 链表list容器的大小操作 /* 1. size(); // 返回容器中元素的个数 2. empty(); // 判断容器是否为空 3. resize(num); // 重新指定容器的长度为num，默认值为数据类型的默认构造 4. resize(num, elem); // 重新指定容器的长度为num，以elem值填充新位置 */ template void print_list(const list& lst) { for (typename list::const_iterator iter = lst.begin(); iter != lst.end(); iter++) { cout lst.push_back(i); } print_list(lst); // 0 1 2 3 4 // 1. size(); // 返回容器中元素的个数 cout for (typename list::const_iterator iter = lst.begin(); iter != lst.end(); iter++) { cout test(); system("pause"); return 0; } 3.7.6 list数据存取功能描述：对list容器中数据进行存取。 函数重载含义front();返回第一个元素back();返回最后一个元素注意：list链表容器不可以用[]和.at()的方式来访问list容器中的元素，因为list不是用连续线性空间存储数据，迭代器也是不支持随机访问的。 list因为地址空间不是连续的，所以只能看到头和尾，因此不能按索引进行存取数据（不能跳跃式访问）。故，list容器对于数据存取只有front和back两个接口。 示例： #include using namespace std; #include #include // 链表list容器的数据存取 /* 1. front(); // 返回第一个元素 2. back(); // 返回最后一个元素 */ template void print_list(const list& lst) { for (typename list::const_iterator iter = lst.begin(); iter != lst.end(); iter++) { cout lst.push_back(i * 10); } print_list(lst); // 0 10 20 30 40 /* list链表容器不可以用[]和at的方式来访问list容器中的元素， 因为list不是用连续线性空间存储数据，迭代器也是不支持随机访问的。 */ // lst[0]; // 没有与这些操作数匹配的“["运算符 // lst.at(0); // 类"std:list"没有成员"at" // 1. front(); // 返回第一个元素 cout for (typename list::const_iterator iter = lst.begin(); iter != lst.end(); iter++) { cout lst.push_back(rand() % 41 + 60); } print_list(lst); // 100 74 90 93 84 // 1. reverse(); // 反转链表 lst.reverse(); print_list(lst); // 84 93 90 74 100 // 2. sort(); // 链表排序 lst.sort(); // 默认是升序 print_list(lst); // 74 84 90 93 100 // 降序 auto fn = [](int v1, int v2) {return v1 > v2; }; lst.sort(fn); // 传入一个函数即可实现降序排序 print_list(lst); // 100 93 90 84 74 /* 使用algorithm的sort()没有办法对链表list进行排序！ 1. 所有不支持随机访问迭代器的容器，不可以用标准算法 2. 不支持随机访问迭代器的容器，内部会提供对应的一些算法 */ // sort(lst.begin(), lst.end()); // algorithm报错 } int main() { // 设置随机种子 srand(time(NULL)); test(); system("pause"); return 0; } 3.7.8 排序案例案例描述：将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高。 排序规则：按照年龄进行升序，如果年龄相同按照身高进行降序。 总结： 对于自定义数据类型，必须要指定排序规则，否则编译器不知道如何进行排序高级排序只是在排序规则上再进行一次逻辑规则制定，并不复杂list.sort()方法的规则最终要的数据类型是bool示例： #include using namespace std; #include #include // 链表list容器的排序案例 /* 案例描述：将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高。 排序规则：按照年龄进行升序，如果年龄相同按照身高进行降序。 */ template void print_lst(list& lst) { for (typename list::iterator it = lst.begin(); it != lst.end(); it++) { cout this->name = name; this->age = age; this->height = height; } public: string get_name() { return this->name; } int get_age() { return this->age; } int get_height() { return this->height; } void set_name(string name) { this->name = name; } void set_age(int age) { this->age = age; } void set_height(int height) { this->height = height; } private: string name; int age; int height; }; void test() { list lst; lst.push_back(Person("张三", 35, 175)); lst.push_back(Person("李四", 45, 180)); lst.push_back(Person("王五", 40, 170)); lst.push_back(Person("赵六", 25, 190)); lst.push_back(Person("孙七", 35, 160)); lst.push_back(Person("周八", 35, 200)); // 打印数据 print_lst(lst); /* 姓名: 张三 年龄: 35 身高: 175 姓名: 李四 年龄: 45 身高: 180 姓名: 王五 年龄: 40 身高: 170 姓名: 赵六 年龄: 25 身高: 190 姓名: 孙七 年龄: 35 身高: 160 姓名: 周八 年龄: 35 身高: 200 */ // 直接排序 /* 直接排序的话，因为list存放的是自定义数据类型，所以sort方法不知道该怎么排序， 所以我们要自己写一个函数，来指定排序的规则！ */ // lst.sort(); // 对类类型"std:less void>"的对象的调用:未找到匹配的调用运算符 // print_lst(lst); // 使用匿名函数指定排序规则 auto compare_fn = [](Person& p1, Person& p2) { return p1.get_age() // 按照身高降序排序 return p1.get_height() > p2.get_height(); } // 按照年龄升序排序 return p1.get_age() for (typename list::iterator it = lst.begin(); it != lst.end(); it++) { cout this->name = name; this->age = age; this->height = height; this->weight = weight; } public: string get_name() { return this->name; } int get_age() { return this->age; } int get_height() { return this->height; } int get_weight() { return this->weight; } void set_name(string name) { this->name = name; } void set_age(int age) { this->age = age; } void set_height(int height) { this->height = height; } void set_weight(int weight) { this->weight = weight; } private: string name; int age; int height; int weight; }; void test() { list lst; lst.push_back(Person("张三", 35, 160, 100)); lst.push_back(Person("李四", 45, 170, 160)); lst.push_back(Person("王五", 40, 170, 172)); lst.push_back(Person("赵六", 25, 190, 150)); lst.push_back(Person("孙七", 35, 160, 120)); lst.push_back(Person("周八", 35, 200, 157)); // 打印数据 print_lst(lst); /* 姓名: 张三 年龄: 35 身高: 160 体重: 100 姓名: 李四 年龄: 45 身高: 170 体重: 160 姓名: 王五 年龄: 40 身高: 170 体重: 172 姓名: 赵六 年龄: 25 身高: 190 体重: 150 姓名: 孙七 年龄: 35 身高: 160 体重: 120 姓名: 周八 年龄: 35 身高: 200 体重: 157 */ // 直接排序 /* 直接排序的话，因为list存放的是自定义数据类型，所以sort方法不知道该怎么排序， 所以我们要自己写一个函数，来指定排序的规则！ */ // lst.sort(); // 对类类型"std:less void>"的对象的调用:未找到匹配的调用运算符 // print_lst(lst); // 使用匿名函数指定排序规则 auto compare_fn = [](Person& p1, Person& p2) { return p1.get_age() // 按照身高降序排序 return p1.get_height() > p2.get_height(); } // 按照年龄升序排序 return p1.get_age() return true; } else if (p1.get_age() == p2.get_age()) { if (p1.get_height() > p2.get_height()) { return true; } else if (p1.get_height() == p2.get_height()) { return p1.get_weight() > p2.get_weight(); } } return false; }; lst.sort(final_compare_fn); print_lst(lst); /* 姓名: 赵六 年龄: 25 身高: 190 体重: 150 姓名: 周八 年龄: 35 身高: 200 体重: 157 姓名: 孙七 年龄: 35 身高: 160 体重: 120 姓名: 张三 年龄: 35 身高: 160 体重: 100 姓名: 王五 年龄: 40 身高: 170 体重: 172 姓名: 李四 年龄: 45 身高: 170 体重: 160 */ } int main() { test(); system("pause"); return 0; } 3.8 set / multiset容器在名称上，C++ 中的 set 和 Python 中的 set 都被称为集合（set），但它们在实现和用法上有一些不同。 C++ 中的 set 是一个关联容器，它使用红黑树来存储元素，并且保持元素的顺序。set 中的元素是唯一的，即不允许重复元素，而且元素是有序的。set 提供了插入、删除、查找等操作，并且这些操作的平均时间复杂度都是 O ( log n ) O(\log^n) O(logn)。set 还提供了迭代器和反向迭代器，可以用来遍历集合中的元素。 Python 中的 set 是一个内置类型，它是一个无序的、唯一的元素集合。与 C++ 中的 set 不同，Python 中的 set 不使用红黑树来存储元素，而是使用哈希表来实现。因此，Python 中的 set 中的元素是无序的，但是它们是唯一的。set 提供了添加、删除、查找等操作，并且这些操作的平均时间复杂度都是 O ( 1 ) O(1) O(1)。set 还提供了迭代器和集合运算（如并集、交集、差集等），可以用来操作集合中的元素。 因此，虽然 C++ 中的 set 和 Python 中的 set 都被称为集合，但它们在实现和用法上有一些不同。 multiset 的全拼是 multiple set，即“多重集合”的意思。 3.8.1 set基本概念简介：所有元素都会在插入时自动被排序。 本质：set/multiset属于关联式容器，底层结构是用二叉树实现。 set和multiset区别： set不允许容器中有重复的元素 multiset允许容器中有重复的元素 set：集合 multiset：多重集合 3.8.2 set构造和赋值功能描述：创建set容器以及赋值。 性质函数重载含义构造set st;默认构造函数构造set(const set& st);拷贝构造函数赋值set& operator=(const set& st);重载等号操作符set集合的特点： 没有push和pop方法所有元素在插入后会自动排序不允许插入重复的值（不会报错，但不会插入成功）总结： set容器插入数据时用insertset容器插入数据的数据会自动排序示例： #include using namespace std; #include #include // 集合set容器的构造函数 /* 1. 构造set st; // 默认构造函数 2. 构造set(const set& st); // 拷贝构造函数 3. 赋值set& operator=(const set& st); // 重载等号操作符 */ template void print_set(set& st) { for (typename set::iterator it = st.begin(); it != st.end() ; it++) { cout st_1.insert(rand() % 100); } print_set(st_1); // 37 46 72 79 87 /* set容器的特点： 1. 没有push和pop方法 2. 所有元素在插入后会自动排序 3. 不允许插入重复的值（不会报错，但不会插入成功） */ // 2. 构造set(const set & st); // 拷贝构造函数 set st_2(st_1); print_set(st_2); // 37 46 72 79 87 // 3. 赋值set & operator=(const set & st); // 重载等号操作符 set st_3; st_3 = st_1; print_set(st_3); // 37 46 72 79 87 } int main() { srand(time(NULL)); test(); system("pause"); return 0; } 3.8.3 set大小和交换功能描述：统计set容器大小以及交换set容器。 函数重载含义size();返回容器中元素的数目empty();判断容器是否为空swap(st);交换两个集合容器set容器没有.resize()方法，因为之前讲的几种容器在resize时有默认值填充，而set容器是不允许有重复值的，所以就没有.resize()方法。 总结： 统计大小 — .size()判断是否为空 — .empty()交换容器 — .swap()示例： #include using namespace std; #include #include // 集合set容器的大小和交换 /* 1. size(); // 返回容器中元素的数目 2. empty(); // 判断容器是否为空 3. swap(st); // 交换两个集合容器 */ template void print_set(set& st) { for (typename set::iterator it = st.begin(); it != st.end(); it++) { cout st.insert(rand() % 100); } print_set(st); // 5 18 57 60 70 // 1. size(); // 返回容器中元素的数目 cout for (typename set::iterator it = st.begin(); it != st.end(); it++) { cout st.insert(rand() % 100); } print_set(st); // 0 34 41 67 69 // 2. clear(); // 清除所有元素 set st2(st); st2.clear(); print_set(st2); // // 3. erase(pos); // 删除pos迭代器所指的元素，返回下一个元素的迭代器 set st3(st); st3.erase(st3.begin()); print_set(st3); // 34 41 67 69 st3.erase(++st3.begin()); print_set(st3); // 34 67 69 st3.erase(--st3.end()); // .end()返回的迭代器指向容器中最后一个元素之后的位置（因此需要前置--） print_set(st3); // 34 67 // 4. erase(beg, end); // 删除区间[beg, end)的所有元素，返回下一个元素的迭代器 set st4; st4 = st; st4.erase(++st4.begin(), --st4.end()); print_set(st3); // 23 71 // 5. erase(elem); // 删除容器中值为elem的元素 set st5; st5.insert(10); st5.insert(10); st5.insert(10); st5.insert(20); st5.insert(30); print_set(st5); // 10 20 30 st5.erase(10); print_set(st5); // 20 30 st5.erase(0); print_set(st5); // 20 30 } int main() { test(); system("pause"); return 0; } 3.8.5 set查找和统计功能描述：对set容器进行查找数据以及统计数据。 函数重载含义find(key);查找key是否存在。若存在，返回该键的元素的迭代器；若不存在，返回set.end();count( key );统计key的元素个数注意： set.end()返回的迭代器指向的是最后一个元素的下一个位置，不能直接调用哦。set.count()返回的只可能是0或1，因为set容器它是不允许有重复元素的！总结： 查找 — .find() —— (返回的是迭代器)统计 — .count() —— (对于set，结果只能是0或1)示例： #include using namespace std; #include #include // 集合set容器的查找和统计 /* 1. find(key); // 查找key是否存在。若存在，返回该键的元素的迭代器；若不存在，返回set.end(); 2. count( key ); // 统计key的元素个数 */ template void print_set(set& st) { for (typename set::iterator it = st.begin(); it != st.end(); it++) { cout st.insert(i * 10); } print_set(st); // 0 10 20 30 40 50 60 70 80 90 // 1. find(key); // 查找key是否存在。若存在，返回该键的元素的迭代器；若不存在，返回set.end(); set::iterator pos = st.find(10); if (pos != st.end()) { cout test(); system("pause"); return 0; } 3.8.6 set和multiset区别学习目标：掌握set和multiset的区别。 区别： set不可以插入重复数据，而multiset可以set插入数据的同时会返回插入结果，表示插入是否成功multiset不会检测数据，因此可以插入重复数据总结： 如果不允许插入重复数据可以利用set如果需要插入重复数据利用multiset注意：multiset是std下的，即std::multiset，不需要引入额外的头文件 示例： #include using namespace std; #include #include // set容器和multiset容器的区别 /* 区别： + set不可以插入重复数据，而multiset可以 + set插入数据的同时会返回插入结果，表示插入是否成功 + multiset不会检测数据，因此可以插入重复数据 */ template void print_set(set& st) { for (typename set::iterator it = st.begin(); it != st.end(); it++) { cout cout cout cout mst.insert(i); mst.insert(i); } // 遍历看一下这个多重集合 for (multiset::iterator it = mst.begin(); it != mst.end(); it++) { cout // 1. pair p (value1, value2); pair pr("Tom", 20); cout // struct默认权限为public int operator()(int a, int b) const { return a + b; } }; int main() { Add add; int sum = add(1, 2); // 调用仿函数计算两个数的和 // int sum = Add()()(1, 2); // 这样也是可以的 std::cout // 重载()运算符 return v1 > v2; // 降序 } }; void test() { // 将set容器的排序规则修改为降序（更改排序规则一定要在创建set容器之前进行！） /* 因为中要求传入的是数据类型，因此我们不能像之前那样传入一个 函数，因为函数不是一个数据类型。所以我们需要用仿函数， 因为仿函数是重载()运算符的的类或结构体。类和结构体都是我们 自定义数据类型用的，它本身就是一个数据类型，所以符合我们的条件！ */ set st; for (int i = 1; i cout public: Person(string name, int age) { this->name = name; this->age = age; } public: string get_name() const { return this->name; } int get_age() const { return this->age; } private: string name; int age; }; class PersonCompare { public: bool operator()(const Person& p1, const Person& p2) const { // 按照年龄进行降序排序 return p1.get_age() > p2.get_age(); } }; void test() { set st; /* 因为set容器是有序的，所以直接插入后，因为不知道怎么排序，插入后会直接报错的！ */ st.insert(Person("张三", 20)); st.insert(Person("李四", 25)); st.insert(Person("王五", 22)); st.insert(Person("赵六", 30)); for (set::iterator it = st.begin(); it != st.end(); it++) { cout for (typename map::iterator it = mp.begin(); it != mp.end(); it++) { cout test(); system("pause"); return 0; } 3.9.3 map大小和交换功能描述：统计map容器大小以及交换map容器。 函数重载含义size();返回容器中元素的数目empty();判断容器是否为空swap(mp);交换两个集合容器总结： 统计大小 — .size()判断是否为空 — .empty()交换容器 — .swap()示例： #include using namespace std; #include #include // map容器：大小和交换 /* 1. size(); // 返回容器中元素的数目 2. empty(); // 判断容器是否为空 3. swap(st); // 交换两个集合容器 */ template void print_mp(map& mp) { for (typename map::iterator it = mp.begin(); it != mp.end(); it++) { cout mp.insert(make_pair(i, i * 10)); } print_mp(mp); /* key: 0 value: 0 key: 1 value: 10 key: 2 value: 20 key: 3 value: 30 key: 4 value: 40 key: 5 value: 50 */ // 1. size(); // 返回容器中元素的数目 cout for (typename map::iterator it = mp.begin(); it != mp.end(); it++) { cout test(); system("pause"); return 0; } 3.9.5 map查找和统计功能描述：对map容器进行查找数据以及统计数据。 函数重载含义find(key);查找key是否存在。若存在，返回该键的元素的迭代器；若不存在，返回mp.end();count(key);统计key的元素个数（对于map容器而言，结果要么是0要么是1）一定要注意，mp.end()返回的是一个迭代器，指向最后一个元素的下一个位置。 总结： 查找 — .find() —— (返回的是迭代器)统计 — .count() —— (对于map，结果为0或者1)示例： #include using namespace std; #include #include // map容器：查找和统计 /* 1. find(key); // 查找key是否存在。若存在，返回该键的元素的迭代器；若不存在，返回mp.end(); 2. count(key); // 统计key的元素个数 */ template void print_mp(map& mp) { for (typename map::iterator it = mp.begin(); it != mp.end(); it++) { cout mp.insert(make_pair(i, i * 10)); } print_mp(mp); /* key: 0 value: 0 key: 1 value: 10 key: 2 value: 20 key: 3 value: 30 key: 4 value: 40 key: 5 value: 50 */ // 1. find(key); // 查找key是否存在。若存在，返回该键的元素的迭代器；若不存在，返回mp.end(); auto pos_it = mp.find(3); if (pos_it != mp.end()) { cout test(); system("pause"); return 0; }可以使用auto来接收，但一定要让编译器推导出对应的数据类型，只是编译阶段会影响一些速度，运行过程中不会有影响！ 3.9.6 map容器排序学习目标：map容器默认排序规则为按照key值进行从小到大排序，掌握如何改变排序规则。 主要技术点：利用仿函数，可以改变排序规则。 总结： 利用仿函数可以指定map容器的排序规则对于自定义数据类型，map必须要指定排序规则，同set容器注意： 自定义的仿函数中的 operator() 运算符必须声明为 const，否则编译器会报错自定义数据类型在get数据时需要加上const示例： #include using namespace std; #include #include // map容器：查找和统计 /* 学习目标：map容器默认排序规则为按照key值进行从小到大排序，掌握如何改变排序规则。 主要技术点：利用仿函数，可以改变排序规则。 */ template void print_mp(map& mp) { for (typename map::iterator it = mp.begin(); it != mp.end(); it++) { cout // 自定义的仿函数中的 () 运算符必须声明为 const，否则编译器会报错 // 降序 return v1 > v2; } }; void test() { map mp1; for (int i = 0; i mp2.insert(make_pair(rand() % 10, rand() % 100)); } // 查看 for (map::iterator it = mp2.begin(); it != mp2.end(); it++) { cout public: Person(string name, int age) { this->name = name; this->age = age; } public: string get_name() const { return this->name; } int get_age() const { return this->age; } private: string name; int age; }; class PersonCompare { public: // 自定义的仿函数中的 () 运算符必须声明为 const，否则编译器会报错 bool operator()(const Person& p1, const Person& p2) const { return p1.get_age() > p2.get_age(); } }; void test() { map mp; mp.insert(make_pair(Person("张三", 20), 160)); mp.insert(make_pair(Person("李四", 25), 140)); mp.insert(make_pair(Person("王五", 23), 150)); mp.insert(make_pair(Person("赵六", 24), 170)); for (map::iterator it = mp.begin(); it != mp.end(); it++) { cout public: void set_name(string name) { this->name = name; } void set_salary(int salary) { this->salary = salary; } string get_name() { return this->name; } int get_salary() { return this->salary; } private: string name; int salary; }; void create_worker(vector& vec) { string name_lst = "ABCDEFGHIJ"; for (int i = 0; i for (vector::iterator it = vec.begin(); it != vec.end(); it++) { // 产生随机部门编号 int dept_id = rand() % 3 + 1; // 1~3 // 将员工插到分组中 mmp.insert(make_pair(dept_id, *it)); // key为部门编号，value为具体员工 } } void show_worker_by_group(multimap& mmp) { cout cout // 1. 创建员工 vector vec_worker; create_worker(vec_worker); // 2. 员工分组 multimap mmp_worker; // int: 部门编号; Worker: 员工 set_group(vec_worker, mmp_worker); // 3. 分组显示员工 show_worker_by_group(mmp_worker); /* 部门1---------------------- 姓名: 员工D 工资: 16500 姓名: 员工I 工资: 16962 姓名: 员工J 工资: 14464 部门2---------------------- 姓名: 员工C 工资: 16334 姓名: 员工E 工资: 19169 姓名: 员工G 工资: 11478 部门3---------------------- 姓名: 员工A 工资: 10041 姓名: 员工B 工资: 18467 姓名: 员工F 工资: 15724 姓名: 员工H 工资: 19358 */ system("pause"); return 0; } 4. STL：函数对象 4.1 函数对象 4.1.1 函数对象概念概念： 重载函数调用操作符的类，其对象常称为函数对象。函数对象使用重载的()时，行为类似函数调用，也叫仿函数本质：函数对象(仿函数)是一个类，不是一个函数。 仿函数除了可以用类class实现外，还可以用结构体struct实现。二者只要重载了operator()都可以称为仿函数。 4.1.2 函数对象使用特点： 函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值函数对象超出普通函数的概念，函数对象可以有自己的状态（因为本质上是一个类/结构体，可以有自定义内容）函数对象可以作为参数传递示例： #include using namespace std; #include // 仿函数 /* 特点： 1. 函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值 2. 函数对象超出普通函数的概念，函数对象可以有自己的状态（因为本质上是一个类/结构体，可以有自定义内容） 3. 函数对象可以作为参数传递 */ // 1. 函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值 class MyAdd { public: int operator()(int v1, int v2) { return v1 + v2; } }; void test01() { MyAdd my_add; int res = my_add(10, 10); cout this->obj_count = 0; this->class_count += 1; } public: void operator()(string str) { cout return this->class_count; } private: int obj_count; // 内部自己的状态：统计类对象调用了多少次 static int class_count; // 内部自己的状态：统计类被创建了多少次 }; int MyPrint::class_count = 0; // static属性需要在类外初始化 void test02() { MyPrint mp; mp("Hello World!"); // Hello World! mp("Hello World!"); // Hello World! mp("Hello World!"); // Hello World! mp("Hello World!"); // Hello World! mp("Hello World!"); // Hello World! cout MyPrint mp; do_print(mp, "Hello C++"); // Hello C++ } int main() { test01(); test02(); test03(); system("pause"); return 0; } 4.2谓词在 C++ 中，谓词（Predicate）是一个可调用对象，它接受一个或多个参数并返回一个布尔值，用于对序列中的元素进行测试或筛选。谓词通常用于标准库算法中，例如 std::find_if()、std::remove_if() 等。 predicate：美 [ˈpredɪkeɪt] 英 ['predɪkət] v.断言；使基于；使以…为依据；表明 adj.述语的；谓项的 n.谓语 网络谓词；述词；断定 4.2.1 谓词概念概念：返回bool类型的仿函数称为谓词。谓词分为两种： 如果operator(参数1)接受一个参数，那么叫做一元谓词如果operator(参数1, 参数2)接受两个参数，那么叫做二元谓词示例： #include using namespace std; #include #include #include #include // 谓词：仿函数的返回值类型是bool，则称这个仿函数为谓词 /* 1. 如果operator()接受一个参数，那么叫做一元谓词 2. 如果operator()接受两个参数，那么叫做二元谓词 */ class GreaterFive { public: // 1. 如果operator()接受一个参数，那么叫做一元谓词 bool operator()(int val) { if (val > 5) { return true; } else { return false; } } }; void test01() { vector vec; for (int i = 0; i cout public: // 2. 如果operator()接受两个参数，那么叫做二元谓词 bool operator()(int v1, int v2) const { return v1 > v2; } }; void test02() { vector vec; for (int i = 0; i cout st.insert(rand() % 100); } for (set::iterator it = st.begin(); it != st.end(); it++) { cout // 1. template T plus; // 加法仿函数 plus pls; auto res = pls(10, 20); cout // 3. template T multiplies; // 乘法仿函数 auto res = multiplies()(100, 10); cout // 5. template T modulus; // 取模仿函数 auto res = modulus()(10, 3); cout test01(); test02(); test03(); test04(); test05(); test06(); system("pause"); return 0; } 4.3.2 关系仿函数功能描述：实现关系对比。 仿函数原型含义template bool equal_to等于template bool not_equal_to不等于template bool greater大于template bool greater_equal大于等于template bool less小于template bool less_equal小于等于注意： 这些关系仿函数可以直接当作sort的谓词使用，不用我们自己写了greater、less、greater_equal、less_equal是我们常用的会自动排序的容器（set、multiset、map、multiset）默认使用的是less谓词在C++中会自动排序的容器只有四个：set、multiset、map、multiset 示例： #include using namespace std; #include #include #include #include // 内建函数对象的头文件 // 内建函数对象（内建仿函数）：关系仿函数 /* 1. template bool equal_to; // 等于 2. template bool not_equal_to; // 不等于 3. template bool greater; // 大于 4. template bool greater_equal; // 大于等于 5. template bool less; // 小于 6. template bool less_equal; // 小于等于 */ // 以greater举例 class VectorCompare { public: bool operator () (int v1, int v2) const { return v1 > v2; } }; void test01() { vector vec; for (int i = 0; i cout vector vec; for (int i = 0; i cout test01(); test02(); system("pause"); return 0; } 4.3.3 逻辑仿函数功能描述：实现逻辑运算。 仿函数原型含义template bool logical_and逻辑与template bool logical_or逻辑或template bool logical_not逻辑非示例： #include using namespace std; #include #include #include // transform的头文件 #include // 内建函数对象的头文件 // 内建函数对象（内建仿函数）：逻辑仿函数 /* 1. template bool logical_and; // 逻辑与 2. template bool logical_or; // 逻辑或 3. template bool logical_not; // 逻辑非 */ // 以逻辑非logical_not举例 void test() { vector vec; vec.push_back(true); vec.push_back(true); vec.push_back(false); vec.push_back(true); vec.push_back(false); vec.push_back(false); for (vector::iterator it = vec.begin(); it != vec.end(); it++) { cout test(); system("pause"); return 0; } 5. STL的常用算法概述：算法主要是由头文件、、组成。 是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历操作、复制、修改等等体积很小，只包括几个在序列上面进行简单数学运算的模板函数定义了一些模板类，用以声明函数对象（仿函数）。C++中的函数对象就是仿函数（Functor）。仿函数是一种重载了函数调用运算符()的对象，可以像函数一样被调用。仿函数可以像函数指针一样传递，也可以像普通对象一样拥有状态，因此在某些情况下可以比函数指针更加灵活和高效。 5.1 常用遍历算法学习目标：掌握常用的遍历算法。 算法简介： for_each：遍历容器transform：搬运容器到另一个容器中 5.1.1 for_each功能描述：实现遍历容器。 函数原型含义for_each(iterator beg, iterator end, _func);遍历算法遍历容器元素其中： beg：开始迭代器end：结束迭代器_func：函数或者函数对象总结: for_each在实际开发中是最常用遍历算法，需要熟练掌握。 示例： #include using namespace std; #include #include #include #include // 内建函数对象的头文件 // 常用的遍历算法：for_each /* for_each(iterator beg, iterator end, _func); // 遍历算法遍历容器元素 其中： + beg：开始迭代器 + end：结束迭代器 + _func：函数或者函数对象 */ class Print02 { public: void operator()(int val) const { cout vec.push_back(i); } // 传统的for循环遍历 for (vector::iterator it = vec.begin(); it != vec.end(); it++) { cout test(); system("pause"); return 0; } 5.1.2 transform功能描述：搬运容器到另一个容器中。 函数原型含义transform(iterator beg1, iterator end1, iterator beg2, _func);搬运容器到另一个容器中其中： beg1：源容器开始迭代器 —— vec1.begin()end1：源容器结束迭代器 —— vec1.end()beg2：目标容器开始迭代器 —— vec2.begin()_func：函数或者函数对象 —— fn()注意： 目标容器需要提前开辟空间，否则搬不进去（会报错）。在写搬运规则的时候我们可以对原数据进行操作示例： #include using namespace std; #include #include #include #include // 内建函数对象的头文件 // 常用的遍历算法：transform /* transform(iterator beg1, iterator end1, iterator beg2, _func); // 搬运容器到另一个容器中 其中： + beg1：源容器开始迭代器 —— vec1.begin() + end1：源容器结束迭代器 —— vec1.end() + beg2：目标容器开始迭代器 —— vec2.begin() + _func：函数或者函数对象 —— fn() */ class TransformFn { public: int operator()(int v) const { // 在这里可以一些额外的操作 return v * 100; } }; class MyPrint { public: void operator()(int val) const { cout vec.push_back(i); } vector vec_target; // 这样定义的容器是没有空间的 vec_target.resize(vec.size()); // 需要我们提前开辟空间 transform(vec.begin(), vec.end(), vec_target.begin(), TransformFn()); for_each(vec_target.begin(), vec_target.end(), MyPrint()); cout for (class vector::iterator it = vec.begin(); it != vec.end(); it++) { cout vec.push_back(i); } print_vec(vec); // 0 1 2 3 4 5 6 7 8 9 // 查找容器中是否有5这个元素 vector::iterator pos = find(vec.begin(), vec.end(), 5); if (pos == vec.end()) { cout public: Person(string name, int age) { this->name = name; this->age = age; } public: bool operator==(const Person& p) const { if (this->name == p.name && this->age == p.age) { return true; } else { return false; } } public: string name; int age; }; void test02() { vector vec; Person p1 = Person("张三", 20); Person p2 = Person("李四", 30); Person p3 = Person("王五", 40); vec.push_back(p1); vec.push_back(p2); vec.push_back(p3); Person pp = Person("李四", 30); // find()函数判断是否找到用的是==运算符，而自定义数据类型需要重载==运算符 vector::iterator it = find(vec.begin(), vec.end(), pp); if (it == vec.end()) { cout test01(); test02(); system("pause"); return 0; } 5.2.2 find_if功能描述：按条件查找元素。 函数原型含义find_if(iterator beg, iterator end, _pred);按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置其中： beg：开始迭代器end：结束迭代器_Pred：函数或者谓词(返回bool类型的仿函数)示例： #include using namespace std; #include #include #include // 常用的查找算法：find_if /* find_if(iterator beg, iterator end, _pred); // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 其中： + beg：开始迭代器 + end：结束迭代器 + _Pred：函数或者谓词(返回bool类型的仿函数) */ template void print_vec(vector& vec) { for (class vector::iterator it = vec.begin(); it != vec.end(); it++) { cout return value > 5; // 这样比写if...else要简洁很多 } }; // 查找内置数据类型 void test01() { vector vec; for (int i = 0; i cout public: Person(string name, int age) { this->name = name; this->age = age; } public: string name; int age; }; void print_Person_vec(const vector& vec) { int idx = 0; for (vector::const_iterator it = vec.begin(); it != vec.end(); it++) { cout return p.age > 20; } }; void test02() { vector vec; Person p1 = Person("aaa", 10); Person p2 = Person("bbb", 20); Person p3 = Person("ccc", 30); Person p4 = Person("ddd", 40); vec.push_back(p1); vec.push_back(p2); vec.push_back(p3); vec.push_back(p4); print_Person_vec(vec); /* 第[0]个元素-> 姓名: aaa 年龄: 10 第[1]个元素-> 姓名: bbb 年龄: 20 第[2]个元素-> 姓名: ccc 年龄: 30 第[3]个元素-> 姓名: ddd 年龄: 40 */ // 找年龄大于20的人 vector::iterator it = find_if(vec.begin(), vec.end(), PersonFindCondition()); if (it == vec.end()) { cout test01(); test02(); system("pause"); return 0; } 5.2.3 adjacent_find功能描述：查找相邻重复元素。 总结：面试题中如果出现查找相邻重复元素，记得用STL中的adjacent_find()算法。 函数原型含义adjacent_find(iterator beg, iterator end);查找相邻重复元素，返回相邻元素的第一个位置的迭代器其中： beg：开始迭代器end：结束迭代器示例： #include using namespace std; #include #include #include // 常用的查找算法：adjacent_find /* adjacent_find(iterator beg, iterator end); // 查找相邻重复元素，返回相邻元素的第一个位置的迭代器 其中： + beg：开始迭代器 + end：结束迭代器 */ void test() { vector vec; vec.push_back(0); vec.push_back(2); vec.push_back(0); vec.push_back(3); vec.push_back(1); vec.push_back(4); vec.push_back(3); // 应该返回指向这个元素的迭代器 vec.push_back(3); vec.push_back(2); vec.push_back(1); vec.push_back(2); vector::iterator pos = adjacent_find(vec.begin(), vec.end()); if (pos == vec.end()) { cout test(); system("pause"); return 0; } 5.2.4 binary_search功能描述：查找指定元素是否存在。 函数原型含义bool binary_search(iterator beg, iterator end, value);查找指定的元素，查到返回true否则false注意： 在无序序列中不可用（二分查找本身就只适用于有序序列）二分查找返回的是bool，不是一个iteratorbeg：开始迭代器end：结束迭代器value：查找的元素如果容器本身是无序的，二分查找不会报错，但结果将不可靠！有序的容器只有：set, multiset, map, multimap总结：二分查找法查找效率很高，值得注意的是查找的容器中元素必须的有序序列，否则结果不可靠！ 二分查找是一种在有序数组中查找目标值的算法，其时间复杂度为 O ( log n ) O(\log^n) O(logn)。 这是因为在每一次比较中，我们都将搜索范围缩小一半，因此在最坏情况下，我们需要进行 log n 次比较才能找到目标值。因此，二分查找的时间复杂度为 O ( log n ) O(\log^n) O(logn)。 需要注意的是： 二分查找只适用于有序数组。如果数组是无序的，我们需要先对其进行排序，这将增加算法的时间复杂度。在算法分析中，通常使用对数的底数不重要，因为不同底数的对数之间只相差一个常数因子。因此，我们通常使用 log \log log 来表示对数，而不指定底数。在计算机科学中，通常默认对数的底数为 2。但是，在某些特定的情况下，我们可能需要使用其他底数的对数，这时我们需要明确指定底数。示例： #include using namespace std; #include #include #include // 常用的查找算法：binary_search /* bool binary_search(iterator beg, iterator end, value); // 查找指定的元素，查到返回true否则false 其中： + beg：开始迭代器 + end：结束迭代器 + value：查找的元素 注意： + 在无序序列中不可用（二分查找本身就只适用于有序序列） + 二分查找返回的是bool，不是一个iterator */ void test() { vector vec; for (int i = 0; i cout test(); system("pause"); return 0; } 5.2.5 count功能描述：统计元素个数。 函数原型含义int count(iterator beg, iterator end, value);统计元素出现次数其中： beg：开始迭代器end：结束迭代器value：查找的元素示例： #include using namespace std; #include #include #include // 常用的查找算法：count /* int count(iterator beg, iterator end, value); // 统计元素出现次数 其中： + beg：开始迭代器 + end：结束迭代器 + value：查找的元素 */ // 统计内置数据类型 void test01() { vector vec; vec.push_back(10); vec.push_back(20); vec.push_back(40); vec.push_back(30); vec.push_back(30); vec.push_back(40); vec.push_back(30); vec.push_back(50); vec.push_back(50); // 统计元素 int count_elem = 30; int res = count(vec.begin(), vec.end(), count_elem); cout this->name = nm; this->age = ag; } public: bool operator==(const Person& p)const { if (this->age == p.age) { return true; } else { return false; } } public: string get_name() { return this->name; } int get_age() { return this->age; } private: string name; int age; }; void test02() { vector vec; vec.push_back(Person("aaa", 10)); vec.push_back(Person("bbb", 20)); vec.push_back(Person("ccc", 30)); vec.push_back(Person("ddd", 40)); vec.push_back(Person("eee", 30)); vec.push_back(Person("fff", 30)); vec.push_back(Person("ggg", 30)); // 统计元素：count()函数进行对比使用的是==，我们自定义数据类型时需要重载== Person count_p = { "张三", 30 }; int res = count(vec.begin(), vec.end(), count_p); cout public: bool operator()(int val) const { return val > 20; } }; void test01() { vector vec; vec.push_back(10); vec.push_back(20); vec.push_back(40); vec.push_back(30); vec.push_back(30); vec.push_back(40); vec.push_back(30); vec.push_back(50); vec.push_back(50); // 统计大于20的元素个数 // count_if(beg, end, _pred) int res = count_if(vec.begin(), vec.end(), Greater20()); cout this->name = nm; this->age = ag; } public: string get_name() const { return this->name; } int get_age() const { return this->age; } private: string name; int age; }; class AgeGreater20 { public: bool operator()(const Person& p) const { return p.get_age() > 20; } }; void test02() { vector vec; vec.push_back(Person("aaa", 35)); vec.push_back(Person("bbb", 35)); vec.push_back(Person("ccc", 35)); vec.push_back(Person("ddd", 40)); vec.push_back(Person("eee", 20)); vec.push_back(Person("fff", 18)); // 统计大于20岁的人员个数 int res = count_if(vec.begin(), vec.end(), AgeGreater20()); cout for (vector::iterator it = vec.begin(); it != vec.end(); it++) { cout return v1 > v2; } }; void test() { vector vec; for (int i = 0; i test(); system("pause"); return 0; } 5.3.2 random_shuffle功能描述：洗牌指定范围内的元素随机调整次序。 函数原型含义void random_shuffle(iterator beg, iterator end);指定范围内的元素随机调整次序其中： beg：开始迭代器end：开始迭代器注意： random_shuffle()没有返回值随机也是由随机种子控制，可以更改种子以达到真实随机的效果总结：random_shuffle()洗牌算法比较实用，使用时记得加随机数种子。 示例： #include using namespace std; #include #include #include // 常用的排序算法：random_shuffle /* void random_shuffle(iterator beg, iterator end); // 指定范围内的元素随机调整次序 其中： + beg：开始迭代器 + end：结束迭代器 */ void print_vec(vector vec) { for (vector::iterator it = vec.begin(); it != vec.end(); it++) { cout vec.push_back(i); } print_vec(vec); // 0 1 2 3 4 5 6 7 8 9 // 利用洗牌算法，打乱容器中元素的顺序（也是由随机种子控制的） random_shuffle(vec.begin(), vec.end()); print_vec(vec); // 8 1 9 2 0 5 7 3 4 6 } int main() { test(); system("pause"); return 0; } 5.3.3 merge功能描述：两个容器元素合并，并存储到另一容器中。 函数原型含义merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);容器元素合并，并存储到另一容器中其中： beg1：容器1开始迭代器end1：容器1结束迭代器beg2：容器2开始迭代器end2：容器2结束迭代器dest：目标容器开始迭代器注意： 两个容器必须是有序的（两个容器的顺序必须是一致的，要么都是升序，要么都是降序）merge()函数返回的是目标容器的开始迭代器（可以接收也可以不接收！）目标容器记得提前开辟足够的空间，否则会报错！示例： #include using namespace std; #include #include #include // 常用的排序算法：merge /* iterator merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // 容器元素合并，并存储到另一容器中 其中： + beg1：容器1开始迭代器 + end1：容器1结束迭代器 + beg2：容器2开始迭代器 + end2：容器2结束迭代器 + dest：目标容器开始迭代器 */ void print_vec(vector vec) { for (vector::iterator it = vec.begin(); it != vec.end(); it++) { cout if (i % 2 == 0) { vec1.push_back(i); // Odd } else { vec2.push_back(i); // Even } } print_vec(vec1); // 0 2 4 6 8 print_vec(vec2); // 1 3 5 7 9 // 目标容器 vector target_vec; // 提前给目标容器分配空间 target_vec.resize(vec1.size() + vec2.size()); vector::iterator it = merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), target_vec.begin()); print_vec(target_vec); // 0 1 2 3 4 5 6 7 8 9 } int main() { test(); system("pause"); return 0; } 5.3.4 reverse功能描述：将容器内元素进行反转。 函数原型含义reverse(iterator beg, iterator end);反转指定范围的元素其中： beg：开始迭代器end：开始迭代器注意： reverse()函数没有返回值示例： #include using namespace std; #include #include #include // 常用的排序算法：reverse /* void reverse(iterator beg, iterator end); // 反转指定范围的元素 其中： + beg：开始迭代器 + end：开始迭代器 */ void print_vec(vector vec) { for (vector::iterator it = vec.begin(); it != vec.end(); it++) { cout vec.push_back(i); } print_vec(vec); // 0 1 2 3 4 5 6 7 8 9 // 翻转容器 reverse(vec.begin(), vec.end()); print_vec(vec); // 9 8 7 6 5 4 3 2 1 0 } int main() { test(); system("pause"); return 0; } 5.4 常用拷贝和替换算法学习目标：掌握常用的拷贝和替换算法。 算法简介: copy()：容器内指定范围的元素拷贝到另一容器中replace()：将容器内指定范围的旧元素修改为新元素replace_if()：容器内指定范围满足条件的元素替换为新元素swap()：互换两个容器的元素 5.4.1 copy功能描述：容器内指定范围的元素拷贝到另一容器中。 函数原型含义iterator copy(iterator beg, iterator end, iterator dest;按值查找元素，找到返回指定位置迭代器；找不到返回结束迭代器位置其中： beg：开始迭代器end：结束迭代器dest：目标起始迭代器注意： copy()算法对于我们来说没有太大的必要，因为很多容器提供了拷贝构造，而且还可以用=运算符目标容器记得提前开辟空间示例： #include using namespace std; #include #include #include // 常用的拷贝和替换算法：copy /* iterator copy(iterator beg, iterator end, iterator dest; // 按值查找元素，找到返回指定位置迭代器；找不到返回结束迭代器位置 其中： + beg：开始迭代器 + end：开始迭代器 + dest：目标起始迭代器 */ void print_vec(vector vec) { for (vector::iterator it = vec.begin(); it != vec.end(); it++) { cout vec.push_back(i); } print_vec(vec); // 0 1 2 3 4 5 6 7 8 9 // 创建目标容器并分配空间 vector target_vec; target_vec.resize(vec.size()); // 拷贝 copy(vec.begin(), vec.end(), target_vec.begin()); print_vec(target_vec); // 0 1 2 3 4 5 6 7 8 9 } int main() { test(); system("pause"); return 0; } 5.4.2 replace功能描述：将容器内指定范围的旧元素修改为新元素。 函数原型含义void replace(iterator beg, iterator end, oldvalue, newvalue);将区间内旧元素替换成新元素其中： beg：开始迭代器end：结束迭代器oldvalue：旧元素newvalue：新元素总结：replace()会替换区间内满足条件的所有元素（不是一个，而是所有）。 示例： #include using namespace std; #include #include #include // 常用的拷贝和替换算法：replace /* void replace(iterator beg, iterator end, oldvalue, newvalue); // 将区间内旧元素替换成新元素 其中： + beg：开始迭代器 + end：结束迭代器 + oldvalue：旧元素 + newvalue：新元素 */ class PrintVector { public: void operator()(int val) { cout test(); system("pause"); return 0; } 5.4.3 replace_if功能描述：将区间内满足条件的元素，替换成指定元素。 函数原型含义void replace_if(iterator beg, iterator end, _pred, newvalue);按条件替换元素，满足条件的替换成指定元素其中： beg：开始迭代器end：结束迭代器_pred：谓词newvalue：替换的新元素总结：replace_if()按条件查找，可以利用仿函数灵活筛选满足的条件。 示例： #include using namespace std; #include #include #include // 常用的拷贝和替换算法：replace_if /* void replace_if(iterator beg, iterator end, _pred, newvalue); // 按条件替换元素，满足条件的替换成指定元素 其中： + beg：开始迭代器 + end：结束迭代器 + _pred：谓词 + newvalue：替换的新元素 */ class PrintVector { public: void operator()(int val) { cout return val >= 30; } }; void test() { vector vec; vec.push_back(20); vec.push_back(30); vec.push_back(50); vec.push_back(40); vec.push_back(20); vec.push_back(10); vec.push_back(20); vec.push_back(20); // 将>=30的元素替换为3000 cout for (vector::const_iterator it = vec.begin(); it != vec.end(); it++) { cout vec1.push_back(i); vec2.push_back(i + 100); } cout vector vec; for (int i = 0; i test(); system("pause"); return 0; } 5.5.2 fill功能描述:向容器中填充指定的元素。 函数原型含义void fill(iterator beg, iterator end, value);向容器中填充元素其中： beg：开始迭代器end：结束迭代器value：起始值总结：利用fill()可以将容器区间内元素慎充为指定的值。 示例： #include #include #include using namespace std; // 常用的算术生成算法：fill /* fill(iterator beg, iterator end, value); // 向容器中填充元素 其中： + beg：开始迭代器 + end：结束迭代器 + value：起始值 */ template void print_vec(vector& vec) { for (vector::iterator it=vec.begin(); it!=vec.end() ; it++) { cout test(); return 0; } 5.6 常用集合算法学习目标：掌握常用的集合算法。 算法简介： set_intersection()：求两个容器的交集set_union()：求两个容器的并集set_difference()：求两个容器的差集 5.6.1 set_intersection功能描述：求两个容器的交集。 函数原型含义set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);求两个集合的交集其中： beg1：容器1开始迭代器end1：容器1结束迭代器beg2：容器2开始迭代器end2：容器2结束迭代器dest：目标容器开始迭代器注意： 两个集合必须是有序序列，不然结果不能保证！目标容器开辟空间需要从两个容器中取小值：min(vec1.size(), vec2.size())，使用min时需要引入头文件遍历的时候要用set_intersection()函数提供的迭代器遍历容器的特殊写法：for (element_type & element : container) {循环体} void print_vec(vector& vec) { /* 这是C++11中引入的一种 "for-each" 循环语法，也叫 "范围 for 循环"。它可以遍历一个容器的所有元素，语法形式为： for (element_type & element : container) {循环体} 其中 "element_type" 是容器中元素的类型，"element" 是对当前元素的引用，"container" 是被遍历的容器。 */ for (int& it : vec) { cout cout vec1.push_back(i); // 0~9 vec2.push_back(i + 5); // 5~14 } print_vec(vec1); // 0 1 2 3 4 5 6 7 8 9 print_vec(vec2); // 5 6 7 8 9 10 11 12 13 14 // 创建目标容器 vector vec_target; // 目标容器需要提前开辟空间：最特殊的情况就是完全包含一个小容器，取min即可 vec_target.resize(min(vec1.size(), vec2.size())); // set_intersection会返回交集的迭代器，指向交集的第最后一个元素的后一个位置 auto it_end = set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec_target.begin()); // 遍历的时候要用set_intersection()函数提供的迭代器 for_each(vec_target.begin(), vec_target.end(), [](int val) {cout test(); return 0; } 5.6.2 set_union功能描述：求两个集合的并集。 函数原型含义iterator set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);求两个集合的并集其中： beg1：容器1开始迭代器end1：容器1结束迭代器beg2：容器2开始迭代器end2：容器2结束迭代器dest：目标容器开始迭代器注意： 两个集合必须是有序序列目标容器开辟空间需要两个容器大小的相加：target_vec.resize(vec1.size() + vec2.size());set_union()返回值是并集中最后一个元素的下一个位置示例： #include #include #include // min的头文件 using namespace std; // 常用的集合算法：set_union() /* iterator set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // 求两个集合的并集 其中： + beg1：容器1开始迭代器 + end1：容器1结束迭代器 + beg2：容器2开始迭代器 + end2：容器2结束迭代器 + dest：目标容器开始迭代器 */ void print_vec(vector& vec) { for (int val : vec) { cout vec1.push_back(i); // 0~9 vec2.push_back(i + 5); // 5~14 } print_vec(vec1); // 0 1 2 3 4 5 6 7 8 9 print_vec(vec2); // 5 6 7 8 9 10 11 12 13 14 vector target_vec; // 目标容器需要提前开辟空间，最特殊的情况就是两个容器没有交集 target_vec.resize(vec1.size() + vec2.size()); // 求并集 auto it_end = set_union(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), target_vec.begin()); // 遍历（错误写法） for_each(target_vec.begin(), target_vec.end(), [](int val) {cout test(); system("pause"); return 0; } 5.6.3 set_difference功能描述：求两个集合的差集。 在数学中，给定两个集合A和B，它们的差集指的是只属于集合A而不属于集合B的元素组成的集合。差集可以用符号 “-” 表示，即 A - B。 例如，如果集合A包含 {1, 2, 3, 4}，集合B包含 {3, 4, 5, 6}，则 A - B 等于 {1, 2}，因为只有元素 1 和 2 属于集合A，而不属于集合B。 差集的结果是根据谁-谁，A-B和B-A的结果是不一样的。 函数原型含义iterator set_difference(iterator beg1，iterator end1，iterator beg2，iterator end2，iterator dest);求两个集合的差集其中： beg1：容器1开始迭代器end1：容器1结束迭代器beg2：容器2开始迭代器end2：容器2结束迭代器dest：目标容器开始迭代器注意： 两个集合必须是有序序列目标容器开辟空间需要从两个容器中取最大值：target_vec.resize(max(vec1.size(), vec2.size()));set_difference()返回值是差集中最后一个元素的下一个位置示例： #include #include #include // min的头文件 using namespace std; // 常用的集合算法：set_difference() /* iterator set_difference(iterator beg1，iterator end1，iterator beg2，iterator end2，iterator dest); // 求两个集合的差集 其中： + beg1：容器1开始迭代器 + end1：容器1结束迭代器 + beg2：容器2开始迭代器 + end2：容器2结束迭代器 + dest：目标容器开始迭代器 */ template void print_vec(vector& vec) { for (T val : vec) { cout vec1.push_back(i); // 0~9 vec2.push_back(i + 5); // 5~14 } print_vec(vec1); // 0 1 2 3 4 5 6 7 8 9 print_vec(vec2); // 5 6 7 8 9 10 11 12 13 14 // 创建目标容器 vector target_vec; // 目标容器需要提前开辟空间，最特殊的情况就是两个容器没有交集 -> 取两个容器中大的size作为目标容器的开辟空间 target_vec.resize(max(vec1.size(), vec2.size())); // 求并集 auto it_end = set_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), target_vec.begin()); auto fn = [](int val) {cout |
【本文地址】
公司简介
联系我们