C++学习 虚函数，容器

一、虚函数

1. 虚函数是C++中的一种函数，允许子类重写父类中的函数，以便在运行时通过基类指针或引用调用子类的函数实现。
2. 虚函数的主要作用是实现多态性，这使得基类指针或引用可以根据实际指向的对象类型调用不同的函数实现。
3. 具体用法

• 虚函数的声明：在基类中使用关键字 virtual 声明函数，告诉编译器这个函数是虚函数。

class Base {
public:virtual void display() {std::cout << "Base display" << std::endl;}
};

• 子类重写虚函数：子类可以通过定义与基类相同签名的函数来重写虚函数。重写的函数不需要再次使用 virtual 关键字，但通常会标记为 override 来确保它确实是对基类虚函数的重写。

class BaseChild1 : public Base {public:void display() override{std::cout << "BaseChild1 display" << std::endl;}
};class BaseChild2 : public Base {public:void display() override{std::cout << "BaseChild2 display" << std::endl;}
};

4. 多态性

• 如果通过基类指针或引用调用一个虚函数，实际调用的函数取决于对象的实际类型，而不是指针或引用的类型。
• 虚函数实现的是动态多态性，即在运行时决定调用哪个函数。
• 相比之下，模板和函数重载则是静态多态性的实现形式，它们在编译时决定调用哪个函数。两者各有优缺点，应该根据具体需求选择使用哪种多态性。

 Base *ptr = new BaseChild1;ptr->display();std::cout << "------------------------------------" << std::endl;Base *ptr1 = new BaseChild2;std::cout << "------------------------------------" << std::endl;Base *ptr2 = new Base;ptr2->display();

5. 虚函数表V-Table

• 编译器会为包含虚函数的类生成一个虚函数表（V-Table），其中包含指向虚函数实现的指针。
• 每个包含虚函数的对象都会有一个指向其所属类的V-Table的指针。
• 在调用虚函数时，程序会通过这个表查找函数的实际实现。

6. 析构函数的虚拟化：
   如果一个类有虚函数，通常也需要将析构函数声明为虚函数，以确保在删除对象时，调用正确的析构函数（特别是通过基类指针删除子类对象时）。
7. 纯虚函数

• 如果一个虚函数在基类中没有定义实现（即为0），那么这个函数就是纯虚函数。

class Base {
public:virtual void show() = 0; // 纯虚函数
};

• 定义了纯虚函数的类称为抽象类，它不能实例化，只能用作派生类的基类。
• 派生类必须实现所有继承的纯虚函数，否则派生类本身也将成为抽象类。

8. 虚函数在构造函数和析构函数中的行为

• 在构造函数和析构函数中，虚函数的调用行为有所不同。在构造函数中，虚函数的调用是静态绑定的，即调用的是当前类的函数版本，而不是派生类的版本。
• 这意味着在基类构造函数中调用虚函数时，即使对象类型是派生类，调用的也是基类中的函数版本。

class Base {
public:Base() {show(); // 调用 Base::show()}virtual void show() {std::cout << "Base show" << std::endl;}
};class Derived : public Base {
public:void show() override {std::cout << "Derived show" << std::endl;}
};int main() {Derived obj; // 调用 Base::show() 而不是 Derived::show()return 0;
}

9. 多重继承与虚函数

• 多重继承：在多重继承中，如果基类包含虚函数，虚函数表的管理会变得更加复杂。
  在这种情况下，每个继承的路径可能会生成一个单独的虚函数表。

class Base1 {
public:virtual void show() { std::cout << "Base1 show" << std::endl; }
};class Base2 {
public:virtual void display() { std::cout << "Base2 display" << std::endl; }
};class Derived : public Base1, public Base2 {
public://Derived 类会拥有两个虚函数表，一个用于 Base1，另一个用于 Base2，以正确处理多重继承中虚函数的调用。void show() override { std::cout << "Derived show" << std::endl; }void display() override { std::cout << "Derived display" << std::endl; }
};

二、auto关键字

• 在 C++ 中，auto 关键字用于自动推导变量的类型，编译器会根据变量的初始值推断出其类型。这样可以让代码更加简洁，减少显式类型声明的冗余。
• 常量类型：auto 会忽略 const 和 volatile 修饰符，除非显式声明。

std::vector<int>::iterator it = vec.begin(); // 传统写法
auto it = vec.begin();                      // 使用 auto
auto result = func();  // 由函数返回值推断类型
//避免显式类型错误：有时显式类型声明可能会出错，特别是使用模板时，auto 可以确保类型推导正确。const int a = 5;
auto b = a;       // b 的类型是 int 而不是 const int
const auto c = a; // c 的类型是 const intint x = 10;
auto y = x;   // y 是 x 的副本，y 和 x 没有关系
y = 20;       // 修改 y，不影响 x
std::cout << "x = " << x << ", y = " << y << std::endl;  // 输出 x = 10, y = 20auto& z = x;  // z 是 x 的引用
z = 30;       // 修改 z，相当于修改 x
std::cout << "x = " << x << ", z = " << z << std::endl;  // 输出 x = 30, z = 30int* ptr = &a;  // 指针 ptr 指向 a
int& ref = a;   // 引用 ref 绑定到 a

• 推导规则
  左值引用：如果初始值是左值引用，auto 推导的结果是值类型，而不是引用类型。如果希望推导为引用，可以显式加上 &。

int x = 10;
auto y = x;   // y 是 int 类型的副本
auto& z = x;  // z 是对 x 的引用

三、顺序容器(头文件就是容器本身)

• 顺序容器是C++标准模板库（STL）中一种重要的容器类型，专门用于存储和管理元素的有序集合。
• 顺序容器以线性方式组织数据，元素按插入顺序排列，用户可以通过迭代器或索引来访问它们。

主要的顺序容器

• 在C++中，顺序容器（Sequence Containers）是一类存储元素的容器，其元素按插入顺序存储。这类容器的主要特点是元素的存储顺序与插入顺序一致，提供了随机访问或线性遍历的能力。

1. std::vector
   • 特点：
     - 动态数组，支持随机访问。
     - 支持高效的尾部插入和删除
     - 动态扩展容量
   • 适用场景：
     - 需要频繁的随机访问。
     - 需要在末尾频繁插入和删除元素。
2. std::deque
   • 特点：
     - 双端队列，支持从两端快速插入和删除，元素不一定存储在连续的内存中。
   • 适用场景
     - 适合需要频繁在两端插入或删除元素的场景。
3. std::list
   • 双向链表。只支持双向顺序访问。在list中任何位置进行插入/删除操作速度都很快。
4. std::forward_list
   • 特点：
     • 单向链表，每个元素只包含指向下一个元素的指针，内存使用更小。
   • 适用场景
     • 适合内存非常有限并且只需要单向遍历的场景。
5. std::array
   • 特点
     • std::array 是 C++11 引入的一个定长数组容器，存储在栈上，大小在编译时就确定。
     • 元素存储在连续的内存中，类似于 std::vector，但其大小是固定的，不能动态调整。
     • 由于大小在编译时就确定，因此更适合存储在栈上，而不是堆上。
     • 不提供内存的动态分配，因此比 std::vector 更加轻量。
   • 适用场景
     • 适合大小固定且不需要动态增长的数组，如对性能和内存开销有严格要求时。
6. std::string
   • 特点：std::string 是一个用于存储字符序列的容器，实质上是动态的字符数组，内部实现类似于 std::vector<char>，但提供了更多处理字符串的功能。
   • 适用场景：适合处理文本数据和字符序列，广泛用于字符串处理、文本解析等场景。

顺序容器公有操作(私有操作繁多，用时再查)

1.定义

std::vector<int> vec;//int也可以换成其他数据类型
std::deque<int> dq;
std::list<int> lst;
std::array<int,5> arr;
std::string str;

2. 初始化操作类比

// 1. 默认构造
std::vector<int> vec1;  // 创建一个空的 vector// 2. 指定大小构造（所有元素初始化为默认值）
std::vector<int> vec2(5);  // 创建一个大小为 5 的 vector，元素初始化为 0// 3. 指定大小和初始值的构造
std::vector<int> vec3(5, 10);  // 创建一个大小为 5 的 vector，所有元素初始化为 10// 4. 使用初始值列表构造
std::vector<int> vec4 = {1, 2, 3, 4, 5};  // 使用列表初始化 vector

3. 元素访问

vec[2] = 10;  // 访问 vector 的第 3 个元素
int val = vec.at(2);  // 安全访问 vector 的第 3 个元素，越界时抛出异常
int first = vec.front();//返回容器中第一个元素。
int last = vec.back();//返回容器中最后一个元素（std::array 除外，其他容器支持）。

4. 容量相关操作

size_t n = vec.size();  // 返回元素数量
bool is_empty = vec.empty();  // 如果容器为空则返回 true
size_t max_n = vec.max_size();//返回容器可能存储的最大元素数量。

5. 修改容器内容

vec.clear();  // 删除所有元素
vec.insert(vec.begin() + 1, 20);  // 在第二个位置插入 20
vec.erase(vec.begin()+0);  // 删除第一个元素
vec.push_back(10);  // 在末尾插入 10（std::array 不支持）
vec.pop_back();  // 移除末尾元素（std::array 不支持）
vec1.swap(vec2);  // 交换 vec1 和 vec2 的内容

迭代器

• 在 C++ 中，迭代器（iterator）是一种用于遍历容器中元素的对象，类似于指针。
• 所有标准容器（如 std::vector、std::deque、std::list、std::array、std::string 等）都提供了迭代器，用来顺序访问容器中的元素。
• 迭代器的操作方式比较统一，但不同的容器支持的迭代器类型和特性可能有所不同。

1. 常见的迭代器类型

迭代器	用途
iterator	用于指向容器中的元素，支持读写操作。
const_iterator	用于指向容器中的元素，支持只读操作。
reverse_iterator	反向迭代器，用于倒序遍历容器。
const_reverse_iterator	只读的反向迭代器。
begin() 和 end()	返回迭代器，分别指向容器的第一个元素和尾后元素（即最后一个元素的下一个位置）。
rbegin() 和 rend()	返回反向迭代器，分别指向容器的最后一个元素和第一个元素之前的位置。

2. 迭代器的使用示例

#include <iostream>
#include <vector>int main() {std::vector<int> vec = {1, 2, 3, 4, 5};// 使用 iterator 遍历 vector//std::vector<int>::iterator 表明迭代器的类型和谁的迭代器。for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {std::cout << *it << " ";  // 输出元素}// 使用 const_iterator 进行只读访问for (std::vector<int>::const_iterator it = vec.cbegin(); it != vec.cend(); ++it) {std::cout << *it << " ";  // 只能读取元素}// 使用 reverse_iterator 反向遍历for (std::vector<int>::reverse_iterator it = vec.rbegin(); it != vec.rend(); ++it) {std::cout << *it << " ";  // 输出元素}
}

3. 迭代器常见操作

• 解引用 (*it)：访问迭代器指向的元素。
• 前进 (++it)：将迭代器移动到下一个元素。
• 后退 (–it)：将迭代器移动到前一个元素（双向迭代器才支持）。
• 比较 (it == end())：检查迭代器是否到达容器的末尾。

泛型算法

• 泛型算法是指可以应用于多种数据结构或容器类型的算法，通常通过模板实现，允许编写与具体类型无关的通用代码。
• 在 C++ 中，泛型算法是通过标准模板库（STL）中的算法库实现的，这些算法可以与各种容器（如 vector、list、deque 等）结合使用。
• 特点：独立于容器，基于迭代器，模板实现。
• STL 中提供了许多常用的泛型算法，包括排序、查找、变换、合并等操作。通过迭代器和模板，STL 中的算法能够处理任意类型的容器或范围。
• 头文件： #include 或者 #include (算数相关)
• 迭代器是 STL 容器和算法之间的桥梁。所有的泛型算法都使用迭代器来访问容器的数据，而不是直接操作容器。这种设计使得算法可以独立于容器，变得非常灵活。

常用的泛型算法

1. 非修改序列算法：不修改容器内容，只读取和比较元素。
   示例：std::find、std::count、std::accumulate。
2. 修改序列算法：修改容器的内容或结构。
   示例：std::copy、std::fill、std::replace。
3. 排序和相关算法：对元素进行排序或重新排列。
   示例：std::sort、std::stable_sort、std::partial_sort。
4. 排序操作算法：基于排序的查找和集合操作。
   示例：std::binary_search、std::merge、std::includes。
5. 数值算法：对数值序列进行计算。
   示例：std::accumulate、std::inner_product、std::adjacent_difference。

泛型算法的使用示例

// 使用 std::find 查找值为 3 的元素auto it = std::find(vec.begin(), vec.end(), 3);
// 使用 std::sort 对元素进行排序std::sort(vec.begin(), vec.end());
// 使用 std::copy 将元素从 src 复制到 deststd::copy(src.begin(), src.end(), dest.begin());
// 使用 std::replace 将值为 2 的元素替换为 5std::replace(vec.begin(), vec.end(), 2, 5);

based for 循环

• 基于范围的 for 循环
• 基于范围的 for 循环（Range-based for loop）是 C++11 引入的一种简洁的语法，用于遍历容器或序列中的元素。
• 相比于传统的 for 循环，基于范围的 for 循环更简单、可读性更高，并且减少了迭代器或索引的使用。
• 语法

for (declaration : range_expression) {// loop body
}
参数:declaration：循环体中每次迭代时用来接收当前元素的变量声明。可以是变量的值、引用或常量引用。range_expression：一个可遍历的范围或容器，比如数组、std::vector、std::array、std::list 等。还可以是具有 begin() 和 end() 方法的自定义类。

• 使用例子范例

#include <iostream>
#include <vector>
int main() {int arr[] = {1, 2, 3, 4, 5};std::vector<int> vec = {10, 20, 30, 40, 50};// 基于范围的 for 循环遍历数组for (int x : arr) {std::cout << x << " ";}// 基于范围的 for 循环遍历 vectorfor (int x : vec) {std::cout << x << " ";}// 使用引用遍历，修改 vector 中的值for (int& x : vec) {x += 10;  // 修改元素值}for (int x : vec) {std::cout << x << " ";}return 0;
}

• 使用 const 来防止修改元素

#include <iostream>
#include <vector>int main() {std::vector<int> vec = {10, 20, 30, 40, 50};// 使用 const 引用遍历，防止修改元素for (const int& x : vec) {std::cout << x << " ";}return 0;
}

总结

• 泛型算法允许我们编写通用代码，能够适用于不同的容器和数据类型。
• C++ STL 中提供了丰富的泛型算法，如查找、排序、变换、复制等操作。
• 泛型算法通过迭代器来与容器交互，使得它们与具体容器解耦，能够处理不同类型的容器。
• 通过使用模板、迭代器和 Lambda 表达式，我们可以轻松地自定义和扩展泛型算法。

关联容器

• 关联容器（Associative Containers）是C++标准模板库（STL）中用于高效存储和检索键-值对的数据结构。
• 与顺序容器（如vector、deque等）不同，关联容器主要依赖键（也就是关键字）来访问元素，而不是通过索引。

主要的关联容器类型

容器类型	解释
std::set	用于存储唯一元素的有序集合，基于平衡二叉树实现。插入、删除、查找的时间复杂度为O(log n)。
std::map	键值对的有序集合，其中每个键唯一，且按键有序排列。插入、删除、查找操作的时间复杂度同样为O(log n)。
std::multiset	与set类似，但允许存储重复元素。
std::multimap	类似于map，但允许一个键对应多个值。
无序关联容器
std::unordered_set	存储唯一元素的无序集合，底层基于哈希表实现。插入、删除、查找的时间复杂度为O(1)（最优情况下）。
std::unordered_map	键值对的无序集合，基于哈希表。键值对无序排列，插入、删除、查找的时间复杂度为O(1)（最优情况下）。
std::unordered_multiset	与unordered_set类似，但允许存储重复元素。
std::unordered_multimap	类似于unordered_map，但允许一个键对应多个值。

关联容器用法

1. std::set
   std::set 用于存储唯一元素，元素默认按升序排列。
   构造

std::set<int> mySet;  // 默认构造一个空集合
std::set<int> mySet = {10, 20, 30};  // 用初始化列表构造

插入

mySet.insert(40);  // 插入元素40，返回一个pair，第一个值是迭代器，第二个值是是否插入成功

删除

mySet.erase(10);  // 删除值为10的元素
mySet.clear();    // 清空集合

查找

auto it = mySet.find(20);  // 返回指向值为20的迭代器，如果未找到则返回end()
bool contains = mySet.count(20) > 0;  // 判断是否存在20

2. std::map

• std::map存储键值对，每个键都是唯一的，键默认按升序排列。
• .first是第一个键，.second是第二个值
  构造

std::map<int, std::string> myMap;  // 空的map
std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}};  // 用初始化列表构造

插入

myMap[3] = "three";  // 插入键值对{3, "three"}
myMap.insert({4, "four"});  // 插入键值对{4, "four"}

删除

myMap.erase(1);  // 删除键为1的元素
myMap.clear();   // 清空所有键值对

查找

auto it = myMap.find(2);  // 查找键为2的元素，返回迭代器
if (it != myMap.end()) {std::cout << "Key 2 maps to " << it->second << std::endl;
}

遍历

for (const auto &pair : myMap) {std::cout << pair.first << ": " << pair.second << std::endl;  // 输出所有键值对
}

3. 其余的都是在这两个基础上推展出来的，无非就是无序，重复