C++笔记
编程语言
C++
封装、继承、多态
封装：将具体实现过程和数据封装成一个类，对外部提供接口，从而隐藏内部实现细节，降低了耦合性。通过封装，类可以保护数据，防止外部的直接访问，确保对象的内部状态只能通过特定方法进行修改，从而保护数据的完整性和安全性。
继承：子类继承父类的特征和行为，提高了代码的复用性，减少冗余，子类不仅能够继承父类的成员，还可以扩展父类的功能或重写父类的方法。
多态：相同函数调用在不同对象上具有不同的行为，基类的指针指向或绑定到派生类的对象，使得基类指针呈现不同的表现形式。加强了代码的可扩展性，以及增强了程序的灵活性，提高了使用效率，简化了代码的编写和修改。
多态分为静态多态（编译时多态）和动态多态（运行时多态），静态多态在系统编译时期就可以确定程序将要执行哪个函数，其主要通过函数重载和运算符重载实现；动态多态通过利用虚函数实现，其条件为：1、前提：继承，2、有虚函数，3、子类重写父类的虚函数，4、调用此函数的类型是基类的指针或引用。
原理：只要类中有虚函数，类对象就有一个虚函数表，该表是一个虚函数指针数组，没有存放在对象中，一半存放在代码段（因为虚表对于一个类的所有对象来说是共享的）。虚表指针存储在对象内存的起始处，用于指向该对象所属类的虚函数表，子类会继承父类的虚表，如果子类的虚表中有重写的虚函数，则对应的虚函数指针也会被子类的虚函数指针覆盖。
构造函数不能是虚函数，因为构造函数的作用是初始化一个对象的状态，对象在构造时虚表指针尚未正确设置，虚函数机制无法正常工作。
析构函数可以是虚函数，因为析构函数的作用是销毁对象的状态，析构函数的调用顺序与构造函数相反，首先调用派生类的析构函数，然后调用基类的析构函数。确保正确的析构顺序，防止派生类的资源没有正确释放，造成内存泄漏等问题。
引用
- 引用必须初始化
- 变量可以有多个引用
- 引用只能引用一个变量
普通类型引用只能引用左值，不能引用右值，const引用既可以引用左值，也可引用右值。
右值引用：
定义：右值引用是为一个临时变量取别名，它通常绑定到一个临时变量、字面值或返回值上。实际开发中我们可能需要对右值进行修改（实现移动语义时就需要）而右值引用可以对右值进行修改。
目的：1、为了支持移动语义，右值引用可以绑定到临时对象、表达式等右值上，这些右值在生命周期结束后就会被销毁，因此可以在右值引用中窃取其资源，从而避免昂贵的复制操作，实现资源的重复利用。利用std::move可以将参数转换为右值引用，从而触发移动语义。
2、完美转发：完美转发是指在函数模板中，完全依照模板的参数的类型，将参数传递给函数模板中调用的另外一个函数。通过std::forward实现保持原有类型不变。
函数模板在向其他函数传递自身形参时，如果相应实参是左值，它就应该被转发为左值；如果相应实参是右值，它就应该被转发为右值。这样做是为了保留在其他函数针对转发而来的参数的左右值属性进行不同处理（比如参数为左值时实施拷贝语义；参数为右值时实施移动语义）。
C++内存管理
- 栈：在函数内部定义的局部变量/函数参数/返回值等，存放在函数栈内。
- 堆：通过动态开辟出来的空间，都放在堆上，比如定义了一个指针指向一块动态开辟的空间，指针本身可能存放在别的地方，但是该指针存放的内容是堆上的地址，该指针的解引用获取的内容也是堆上的东西。
- 数据段：包含全局数据和静态数据。全局定义的变量，或者任何位置（全局或者函数内部）定义的静态变量都存放在数据段中。
- 代码段：可执行代码/只读常量。文本数据等都属于常量，存放在代码段中。
智能指针
之前定义指针申请内存空间使用后要进行delete进行资源释放，但是如果在资源释放之前就抛出异常，则不会进行正常的资源释放，造成资源泄露的问题。因此通过定义智能指针，利用对象的生命周期来控制程序资源，在生命周期结束时自动释放资源。
std::auto_ptr：使用管理权转移的思想，拷贝时直接将新指针指向被拷贝对象资源，被拷贝对象指针悬空。
std::unique_ptr：主要为了防拷贝。保证资源独有
std::shared_ptr：支持拷贝，通过引用计数的方式来实现多个shared_ptr对象之间共享资源。给每个资源都维护了一份计数，用来记录该份资源被几个对象共享。，在对象被销毁时计数-1，如果计数为0则释放该资源。
但是有一个循环引用的问题，谁也不会进行释放。
使用weak_ptr可以在拷贝时不进行计数+1操作，因此可以正常调用析构，进行资源释放。
数据结构
排序算法
1、插入排序
直接插入排序：时间复杂度O(n^2)，空间复杂度O(1)，稳定
给已经有序的序列插入新的数据，从有序序列的最后一个位置向前遍历，找到第一个小于待插入数据的位置，然后插入该位置的下一个位置。
希尔排序：时间复杂度O(n^1.3)，空间复杂度O(1)，不稳定
让数据越来越接近有序，减少数据移动的次数，调高插入排序的性能。通过设置gap值，按照间隔插入排序，最后一趟排序间隔为1。
2、选择排序
选择排序：时间复杂度O(n^2)，空间复杂度O(1)，不稳定
每次从未排序的数据中找一个最小的，把最小的放到未排序的数据头部，继续重复执行。
堆排序：时间复杂度O(nlogn)，空间复杂度O(1)，不稳定
通过建大堆，从最后一个非叶子节点（(n-2)/2）开始执行向下调整，然后交换根节点和最后一个叶子节点的位置，执行向下调整（最后一个叶子节点不进行操作）。
3、交换排序：
冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)，稳定
相邻元素进行比较，大的元素向后移动。
快速排序：时间复杂度O(nlogn)，空间复杂度O(logn)，不稳定
选取一个基准值
从剩余元素开始遍历
从后往前找第一个小于基准值的数据，从前往后找第一个大于基准值的数据。
交换找到的两个数据
从交换位置继续开始查找，直到两个数据相遇
用相遇位置的数据和基准值交换。
4、归并排序: 时间复杂度O(nlogn)，空间复杂度O(n)，稳定
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
分解：把数据按照位置，均衡的分成两个子序列，一直到子序列中只有一个数据
合并：相邻有序的子序列进行合并
STL容器
序列式容器
vector、list、deque统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。
vector:
优点：随机访问，尾部的操作O(1)，空间利用率高，不容易造成内存碎片
缺点：中间头部操作O(n)，增容代价比较大（深拷贝）每次都要重新开辟一个更大空间进行数据搬移。
list:
优点：任意位置操作性能高，插入删除O(1)
缺点：不支持随机访问，空间利用率比较低（频繁的申请释放），容易造成内容碎片。
deque：
优点：支持随机访问（性能略低于vector），头部尾部的操作O(1)，增容的代价小
缺点：中间位置的操作性能比较低：O(n)
stack：默认实现：deque
堆的实现可以用vector,list,deque
因为stack的实现不需要随机访问，因此vector的优势体现不出来，并且list空间利用率较低。
queue：默认实现：deque
队列的实现可以用list,deque
队列只在头部和尾部操作，因此deque中间操作性能低不受影响。list空间利用率低需要频繁申请释放。
priority_queue：默认实现：vector
优先队列的实现可以用vector,deque
需要容器支持随机访问（因为要实现元素的交换），vector的元素都在连续位置（物理连续），随机访问是O(1)的操作，遍历是O(n)的操作。deque虽然支持随机访问，但是它的性能略低于vector。元素不是完全连续。
deque（双端队列）：增容代价小
1.数据缓冲区已满，新开一个缓冲区，缓冲区首地址存入指针数组
2.指针数组已满，新开一个指针数组，只需要拷贝原有缓冲区的指针，不需要拷贝元素内容
树型结构关联式容器
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。
根据应用场景不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。
树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。
set介绍：
set是按照一定次序存储元素的容器
在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
set在底层是用二叉搜索树(红黑树)实现的。
与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
set中插入元素时，只需要插入value即可，不需要构造键值对。
set中的元素不可以重复(因此可以使用set进行去重)。
使用set的迭代器遍历set中的元素，可以得到有序序列
set中的元素默认按照小于来比较
set中查找某个元素，时间复杂度为：log n
set中的元素不允许修改
set中的底层使用二叉搜索树(红黑树)来实现。
map介绍
map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型，value_type绑定在一起，为其取别名称为pair:typedef pair<const key, T> value_type;
在内部，map中的元素总是按照键值key进行比较排序的。
map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
map支持下标访问符，即在[ ]中放入key，就可以找到与key对应的value。
map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。
哈希结构关联式容器
前讲解在C++98中STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到logn，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同使用哈希结构。unordered_map、unordered_set、unordered_multimap和unordered_multiset
unordered_map
unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
它的迭代器只有前向迭代器。
哈希函数
直接定址法：
kx+b ：适用于小范围数据的位置计算。如果数据范围过大会造成空间浪费。
除留余数法：
x%空间大小：通用
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
解决哈希冲突
闭散列：
线性探测：从计算的哈希位置开始，找第一个空闲的位置，存放数据。
二次探测：与线性探测的不同在于找一个空位置的不同，线性探测一个一个找，二次探测每次找的位置是上次的二次，比如第一次找第一个位置，第二次找二个位置，第三次找第四个位置。
开散列：
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
位图概念
位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。
正常存放一个整数，需要4个字节，32位；用位图在存放一个整数的信息，只需要用一个bit位的大小，相当于正常存放的1/32。
布隆过滤器概念
概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
操作系统
网络基础
原文地址：https://blog.csdn.net/m0_49619206/article/details/142787240
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！