wu-sketch
C/C++笔记¶
class¶
class keywords¶
一些关于class的关键字：
override是一种安全校验，是可选的，你意图是覆盖父类的父方法，那么就会校验父类有没有，函数签名匹配不匹配，编译器拦截低级错误。final是一种安全校验，是可选的，你的类或者类成员函数不想让人继承就用final修饰。virtual是必须的，类的成员函数如果想被子类重写，必须是virtual, 如果一个基类打算被继承，那么它的析构函数必须是虚函数。子类中覆盖父类的virtual函数时，virtual关键字可选，一般无需再加，建议加上override来明确语义方便编辑器检查。default这个关键字指定默认特殊成员函数，包括：构造、析构、拷贝构造、拷贝赋值、移动构造、移动赋值。某些特定成员函数的用户自定义声明会抑制（阻止）编译器自动生成其他特定的成员函数，但是你还需要，并且编译器默认实现的也满足需求，此时可以使用default。delete同样针对上面的特殊类成员函数：构造、析构、移动构造、拷贝构造、赋值运算符等，这个关键字可以做到显示的删除，让其不能够被移动，被赋值等，方便后续实现unique_ptr等特性。explicit关键字，防止单参数构造函数被隐式转换，避免一些低级错误。mutable关键字，指定类的成员变量可以在 const 成员函数中被修改。static关键字，指定类的成员变量或成员函数属于类本身，而不是类的某个实例。静态成员变量在所有实例间共享，静态成员函数只能访问静态成员变量和其他静态成员函数。
备注
对于 =default 关键字，注意以下几点:
用户声明了自定义的拷贝操作（拷贝构造或拷贝赋值），会抑制移动操作（移动构造和移动赋值）的自动生成。
用户声明了自定义的移动操作、析构函数或构造函数，会抑制拷贝操作和移动操作的自动生成。
用户声明了任何构造函数（包括拷贝构造、移动构造），会抑制默认构造函数的自动生成。
对于 explicit 关键字，除非你有一个非常好的理由允许隐式转换，否则应该尽量为所有的单参构造函数（以及除拷贝构造外的多参构造函数）都加上 explicit关键字。这是一种防御编程，不是必须，是为了让编程的意图更加的清晰，还有就是可以一定程度的省去临时对象开销。防止的就是这种情况：你本以传递1个参数，你并不想传递那个类的对象，但是编译器帮你隐式转换了，导致了低级错误，而编译期无法检测出来。
三/五/零之法则¶
https://c-cpp.com/cpp/language/rule_of_three
C++中有一个重要的设计原则，三/五/零之法则：
零法则（Rule of Zero）： 现代 C++ 的首选。如果你的类不拥有任何需要手动管理的资源（如裸指针），那么你不需要自定义任何特殊成员函数,让编译器自动生成即可。当有意将某个基类用于多态用途时，可能必须将其析构函数声明为公开的虚函数。由于这会阻拦隐式移动（并弃用隐式复制）的生成，因而必须将各特殊成员函数声明为预置的。然而这使得类有可能被切片，这是多态类经常把复制定义为弃置的原因。
三法则（Rule of Three）： C++98 时代的法则。如果你的类拥有需要手动管理的资源，且你自定义了以下三者中的任何一个，就应该自定义所有三个：析构函数、拷贝构造函数和拷贝赋值运算符。
五法则（Rule of Five）： C++11 引入移动语义后的扩展。在三法则的基础上，为了支持移动语义，还应该提供 移动构造函数 和 移动赋值运算 符。
备注
黄金准则： 在现代 C++ 中，尽量使用“零法则”。你的类成员应仅由基本类型、智能指针和标准库容器组成。
一个典型的多态基类定义：
class Animal {
public:
// 必须有虚析构函数，以支持多态
virtual ~Animal() = default;
// 显式禁用复制，以防止对象切片
Animal(const Animal&) = delete;
Animal& operator=(const Animal&) = delete;
// 显式预置移动，如果需要
// Animal(Animal&&) = default;
// Animal& operator=(Animal&&) = default;
// 其他虚函数
virtual void eat() = 0;
};
移动语义¶
移动语义： 内部资源的转移（比如raw_data指针、文件描述符fd等等)，核心实是实现了移动构造、移动赋值这两个特殊的成员函数和运算符的重载。
右值：右值通常是字面量、临时对象或即将被销毁的对象，如字面量、临时对象、没有被赋值给任何左值的临时对象。这种类型如果内部实现了移动语义的方法，编译器遇到的时候优先进行移动赋值和和构造，从而减少不必要的资源拷贝，提高效率。
在实现的时候，判断是否是自身对象指针(对象的自赋值移动），转移后raw_data指针置空等。编译器如何识别呢？对于 右值类型 ，可以被 T&& 引用，编译器在遇到构造或者赋值的时候，触发移动语义，即调用对应的移动构造和移动赋值运算符。 std::move 的本质是一个类型的转换，告诉编译器，这个是右值类型，可以调用后续移动语义的方法了。
智能指针¶
有了上面的 C++11 引入的语言特性后，我们就可以用库的方式来实现智能指针了。实现智能指针的语言特性基础（编译器级别的语法）有：
RAII机制，对象生命周期结束自动析构（调用析构函数），典型就是超出作用域自动析构，编译器会帮你调用析构函数；default/delete, 方便显示的对赋值构造等特殊成员函数的实现进行控制；移动语义，对于可被
T&&引用的类型，编译器编译是会去调用对应的移动构造或者赋值的实现；class的模板机制，任意类型都可以传给class来进行对应实例的管理；运算符重载，方便智能指针像普通指针一样使用，重载了
* ->等指针操作符, 还有operator bool()方便做非空判断；显式构造函数 (
explicit) 主要用于单参构造函数，避免不必要的隐式转换；
unique_ptr¶
它是1个泛型class，传入类型 T 的实例，可以被自动管理，这个unique_ptr只会被1个左值所拥有，确保了在程序的任何一个时间点都是被唯一的左值拥有所有权。同样，作为指针，它重载了 * -> 这些指针操作，可以像普通指针一样使用。
实现原理：
用 delete 关键字去掉赋值和拷贝构造函数的实现，从而禁止普通的赋值与拷贝；
实现移动赋值和移动构造函数，被赋值给其他的时候，要用
std::move来显示转移；
注意点：
get方法慎用，这个是获取内部的raw_ptr，我们不要把unique_ptr和裸指针混用；reset后，重置了uniptre，会显示释放掉原来的数据；release后，会返回 raw_ptr，后续要自己来管理了，注意避免泄漏，这种方法用的很少；
weak_ptr¶
也是个泛型class，常配合 shared_ptr 使用，不会导致 shared_ptr 内部data的引用计数增加，更多的是一个 观察 的模式。因为 weak_ptr 不参与资源管理，访问前先 lock, 然后会判断是否 lock 成功非空指针，然后才能访问其指向的实例。
实现原理：
weak_ptr的赋值和拷贝构造: 操作的是弱引用计数。它不会增加强引用计数，因此不会阻止所指向的对象被释放。弱引用计数为0时，释放用于管理引用计数的*控制块*本身。shared_ptr的赋值和拷贝构造: 操作的是强引用计数。强引用计数为0时，释放管理的对象资源。
备注
使用 shared_ptr 出现循环引用会发生什么，假设有两个类 A 和 B，A 持有一个指向 B 的 shared_ptr，B 持有一个指向 A 的 shared_ptr 。再假设我们创建了 A 和 B 的实例，并让它们互相引用：
struct B; // 前向声明
struct A {
std::shared_ptr<B> b_ptr; // A 持有 B 的 shared_ptr
~A() { std::cout << "A destroyed" << std::endl; }
};
struct B {
std::shared_ptr<A> a_ptr; // B 持有 A 的 shared_ptr
~B() { std::cout << "B destroyed" << std::endl; }
};
// 那么在我们给 A 和 B 赋值后：
{
auto a = std::make_shared<A>(); // a 刚创建，内部成员都是空，a 的引用计数是 1
auto b = std::make_shared<B>(); // b 刚创建，内部成员都是空，b 的引用计数是 1
a->b_ptr = b; // 注意： a 持有 b 的 shared_ptr， b 的引用计数 + 1
b->a_ptr = a; // 注意： b 持有 a 的 shared_ptr， a 的引用计数 + 1
// 现在 a 和 b 的引用计数都是 2
// 现在 a 和 b 互相引用，形成循环引用
// 当 a 和 b 超出作用域时，它们的引用计数都不会变成 0
// 因为 a 和 b 互相引用，导致它们的引用计数都至少是 1
// 所以它们的析构函数都不会被调用，资源不会被释放
// 这就导致了内存泄漏
// 这种，任何一方如果可以正常销毁，其内部引用别人的关联对象也会销毁，最终另1个对象也会销毁了
// 如果 A 强引用了 B, 那么 B 就应该弱引用 A 了
}
lambda¶
C++中的 lambda 是一种匿名函数，大大的增加了语言的表达能力。在函数内有时候需要增加1个小的辅助函数，就可以直接内部实现，不用在外部专门进行声明和定义了，而且更加方便的是其可以捕获其所在的作用域内的变量，有值、引用、移动等多种捕获方式。
常见的使用场景有：比如对一个对象数组或者vector进行排序，可以很方便的传递一个比较函数，因为比较函数通常都是比较简短的，这种使用lambda就是最方便的。因为其可以捕获其所在作用域的其他对象，这个特点就会让其比普通的函数更加的强大和方便。
备注
lambda 捕获变量的原理，是编译器在后台为你生成一个匿名类，并把捕获的变量作为这个类的成员，通过构造函数进行初始化，从而实现了将外部状态“打包”到函数对象中的闭包特性。
STL¶
迭代器¶
C++ 迭代器是基于运算符重载的类，它提供了一种统一的接口，让你能够像操作指针一样遍历不同容器中的元素。库与编译器特性共同协作实现。核心思想是将指针的行为泛化。重载了 * -> ++ -- == != 等运算符，从而实现类似指针的行为。
容器类(vector/list/map)都提供内置嵌套的迭代器，方便遍历集合。
备注
特别注意可能会导致迭代期失效的操作。比如：C++ 语言标准明确规定了 std::vector::erase 会导致迭代器失效，因为其本质是删除元素后，可能会移动其他元素来填补空缺，从而使得原有的迭代器指向无效的位置。此时，正确的做法是，erase 操作后，使用erase 返回的新迭代器继续遍历。其他不同容器进行删除操作后，失效的规则也不一样。
vector¶
vector 底层是连续内存，维护了一个 array，然后就是大小，自动扩容等；emplace_back 方法在 C++11 中引入的特性来提高性能。相比 push_back, 会减少不必要的拷贝和移动操作，直接在容器的内存位置上构造对象。
备注
vector 的 emplace_back 和 push_back 的区别：
push_back 是将一个已经存在的对象拷贝或者移动到容器中，可能会涉及额外的拷贝或移动开销。
emplace_back 则是在容器的内存位置上直接构造对象，避免了不必要的拷贝和移动，提高了性能。
emplace_back 可构造函数的参数，直接在容器内构造对象，而 push_back 只能接受一个完整的对象。
people.emplace_back(Person("Alice", 30)); // 错误，多构造了对象导致了多余的拷贝或者移动people.emplace_back("Bob", 25); // 正确，直接传递构造函数参数
list, forward_list¶
list 是双向链表，forward_list 是单向链表，底层是节点指针的链式存储结构，适合频繁插入和删除操作的场景。这种由于对缓存不友好，遍历性能不如 vector/deque，用的比较少。
deque, stack, queue¶
deque 是双端队列，底层是分段连续内存，支持在两端高效插入和删除操作。stack 和 queue 是基于 deque 实现的适配器容器。deque 和 vector 的区别：
deque 底层是分段连续内存，而 vector 是单一连续内存。
deque 适合需要频繁在两端插入和删除元素的场景，而 vector 更适合随机访问和按索引访问的场景。
deque 也支持随机访问，重载了
[]和at()方法，性能略逊于 vector。
map, multimap¶
map 是基于红黑树实现的有序关联容器，适合需要按键排序和范围查询的场景。multimap 也是，只不过允许多个元素拥有相同的键。
备注
对于multimap，即使有重复的key，红黑树特性依然满足：左子树小于根节点，右子树大于根节点。
插入元素时，当键等价时，它们被视为不严格小于也不严格大于，所以可以被放在任何一边，这里保持新插入的元素放在右子树。
查找元素时，equal_range() 方法返回一个 std::pair，表示具有指定键的所有元素的范围
[first, second)。
std::map 的 insert 方法返回一个 std::pair，其中包含一个迭代器和一个布尔值(表示是否成功)。
std::multimap 的 insert 方法返回一个迭代器，指向新插入的元素。
std::map 使用 [] 操作符访问 map 时，如果键不存在，会自动插入一个默认值；而 multimap 不支持 [] 操作符。
multimap 的插入和查找代码举例：
void foo() {
std::multimap<int, std::string> myMultimap;
// 插入元素，用{}来统一初始化
myMultimap.insert({1, "Alice"});
myMultimap.insert({2, "Bob"});
myMultimap.insert({1, "Charlie"}); // 允许重复的键
myMultimap.insert({3, "David"});
// 查找键为 1 的所有元素
auto range = myMultimap.equal_range(1);
std::cout << "Elements with key 1:" << std::endl;
for (auto it = range.first; it != range.second; ++it) {
// 这个 it 是迭代期，it->first 是 key, it->second 是 value
std::cout << it->first << ": " << it->second << std::endl;
}
}
priority_queue¶
priority_queue 底层默认 vector 做容器，用 max-heap 最大对组织元素。最大堆父节点总是大于子节点，是一个完全二叉树，满足：每个父节点的值都大于或等于其子节点的值。这意味着最大的元素总是在树的根部。通常用数组实现利用数组索引间的数学关系（如 父节点索引 = (子节点索引-1)/2）来模拟树形结构，从而避免使用指针，节省内存并提高缓存效率。
访问最大元素： 使用 top() 方法，时间复杂度为 O(1)。
插入新元素： 使用 push() 方法，时间复杂度为 O(log n)，因为可能需要调整堆以维护堆属性。
删除最大元素： 使用 pop() 方法，时间复杂度为 O(log n)，同样需要调整堆。
备注
对于 priority_queue 的一些注意点，比较函数和优先级正好相反，less 是最大堆，greater 是最小堆。
默认是最大堆, 比较器是
std::less<T>，top() 方法返回堆顶最大元素。如果要最小堆，可以使用
std::greater<T>作为比较器。
也可以自定义比较器，使用 lambda 表达式或者函数对象来定义元素的优先级。
因为会涉及到大量的交换操作，priority_queue 适合存储小型对象，大型对象会影响性能。对于大对象，建议存储指针或者智能指针。这个对于 C++ 标准库的其他容器也是类似的，大对象对性能影响较大，都用指针或者智能指针。不要用引用，因为引用不能重新绑定，不适合被容器管理。
// 最小堆
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
// 自定义比较器，lambda函数，按字符串长度排序
auto cmp = [](const std::string &a, const std::string &b) {
return a.length() > b.length(); // 长度短的优先级高
};
std::priority_queue<std::string, std::vector<std::string>, decltype(cmp)> customHeap(cmp);
copy, remove¶
算法库里有变动型 (Mutating) 算法和非变动型 (Non-mutating) 算法。
变动型算法会修改输入范围的元素，比如
std::remove会重新排列元素，将不需要的元素移到末尾，并返回新的逻辑结尾迭代器。非变动型算法不会修改输入范围的元素，比如
std::copy会将元素从一个范围复制到另一个范围。
C++社区鼓励使用这种算法，而不是手写循环。这种方式更简洁、易读，并且经过高度优化。一些例子如下：
// 使用 std::copy 复制元素
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(5);
std::copy(source.begin(), source.end(), destination.begin());
// 使用 std::remove 移除元素
std::vector<int> vec = {1, 2, 3, 4, 5, 3};
auto newEnd = std::remove(vec.begin(), vec.end(), 3); // 移除值为3的元素
// vec 现在是 {1, 2, 4, 5, ?, ?}，?表示未定义的值
// newEnd 指向新的逻辑结尾
// 下面的 erase 实际删除元素
vec.erase(newEnd, vec.end()); // 实际删除元素