八股

面试准备

cpp基础部分

STL

标准模版的组成

• 1.容器(Container)

数据结构，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器。

• list、deque、vector

• 2.算法(Algorithm)

是用来操作容器中数据的模版函数，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象， 函数本身与他们操作的数据的结构和类型无关，因此他们可以用于从简单数组到高度复杂容器的任何数据结构上。

• 3.迭代器(Iterator)

提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。 迭代器就如同一个指针。事实上，C++ 的指针也是一种迭代器。 但是，迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符方法的类对象;

• 4.仿函数(Function object)

• 仿函数又称之为函数对象， 其实就是**重载了操作符的struct,**没有什么特别的地方。

• 5.适配器（Adaptor）

简单的说就是一种接口类，专门用来修改现有类的接口，提供一中新的接口；或调用现有的函数来实现所需要的功能。主要包括3中适配器Container Adaptor、Iterator Adaptor、Function Adaptor

• 6.空间配制器（Allocator）

为STL提供空间配置的系统。其中主要工作包括两部分：

• 对象的创建与销毁
• 内存的获取与释放

STL中常见容器

• 顺序容器

  • vector

  底层使用动态数组，元素在内存中连续存放。

  支持随机存取元素，在尾端增删元素具有较佳的性能

  • deque

  底层使用双向队列，元素在内存中连续存放。

  支持随机存取元素，效率比vector略低，但也是常数时间。在两端增删元素具有较佳的性能（大部分情况下是常数时间）。

  • list

  底层使用双向链表。元素在内存中不连续存放。

  不支持随机存取

• 关联式容器

  • set/multiset

  set 即集合。set中不允许相同元素，multiset中允许存在相同元素。

  • map/multimap

  map与set的不同在于map中存放的元素有且仅有两个成员变，一个名为first,另一个名为second, map根据first值对元素从小到大排序，并可快速地根据first来检索元素

  注意：map同multimap的不同在于是否允许相同first值的元素。

• 适配性容器

  • 封装了一些基本的容器，使之具备了新的函数功能。比如把deque封装一下变为一个具有stack功能的数据结构。这新得到的数据结构就叫适配器。包含stack,queue,priority_queue
  • stack FILO

  栈是项的有限序列，并满足序列中被删除、检索和修改的项只能是最进插入序列的项（栈顶的项）。后进先出。

  • queueFIFO

  队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。先进先出。

  • priority_queue

  优先级队列。内部维持某种有序，然后确保优先级最高的元素总是位于头部。优先级最高的元素总是第一个出列

---

map hashtable deque list 的实现原理

• map实现原理

  底层是红黑树(红黑树是非严格平衡的二叉搜索树，而AVL是严格平衡的二叉搜索树)。红黑树有自动排序的功能。因此map内所有元素都是有序的。红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找、删除、添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉树（又名二叉查找树、二叉排序树）存储的，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值。使用中序遍历可将键值按照从小到大遍历出来。

• hashtable(散列表、哈希表)实现原理

  hashtable采用了函数映射的思想记录的存储位置与记录的关键字，从而能够快速地进行查找。它同数组、链表以及二叉排序树等相比较有很明显的区别，它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。

• deque实现原理

  底层是双向队列，元素在内存中连续存放。支持随机存储？，所有适用于vector的操作都适用于deque。支持两端增删元素

• list实现原理

  底层是双向链表，元素在内存中随机存放，不支持随机存取。无成员函数，给定一个下表i，访问第i个元素的内容，只能从头部挨个遍历到第i个元素

---

介绍一下 STL 的空间配置器（allocator）

• allocator是用来实现内存空间分配的工具，每一种容器的空间分配都是通过分配器allocator实现的

• 两种对象实例化方式

  • 1.利用构造函数，直接构造类对象tg Test test()
  • 2.通过new来实例化一个类对象。Test *pTest = new Test

• 两种实例化方式的异同

  • 内存分配的三种方式
    • 静态存储区分配：内存在程序编译的时候已经分配好了。这块内存在程序的整个运行空间内都存在。如全局变量、静态变量等
    • 栈空间分配：程序在运行期间，函数内的局部变量通过栈空间来分配存储(函数调用栈)，当函数执行完毕返回时，相对应的栈空间立即回收。主要是局部变量
    • 堆空间分配：程序在运行期间，通过在堆空间上为数据分配存储空间，通过malloc和new创建的对象都是从堆空间分配内存，这类空间需要程序员自己来管理，必须通过free()或者是delete()函数对堆空间进行释放，否则会造成内存溢出。
  • 现在从分配的角度来区分两者的异同
    • 对于第一种方式来说，是直接通过调用Test类的构造函数来实例化Test类对象的,如果该实例化对象是一个局部变量，则其是在栈空间分配相应的存储空间。
    • 对于第二种方式来说,就显得比较复杂。这里主要以new类对象来说明一下。new一个类对象,其实是执行了两步操作：首先**,调用new在堆空间分配内存,然后调用类的构造函数构造对象的内容；同样，使用delete释放时，也是经历了两个步骤：首先调用类的析构函数释放类对象，然后调用delete释放堆空间。**

• allocator空间适配器的实现

  • 为了实现空间配置器，完全可以利用new和delete函数并对其进行封装实现STL的空间配置器，的确可以这样。但是这样效率低
  • STL中，将对象的构造切分开来，分成空间配置和对象构造两部分
    • 内存配置操作：通过alloc：allocate()实现
    • 内存释放操作：通过alloc::deallocate()实现
    • 对象构造操作：通过::construct()实现
    • 对象释放操作： 通过::destroy()实现
  • 关于内存空间的配置与释放，SGI STL采用了两级配置器：一级配置器主要是考虑大块内存空间，利用malloc和free实现；二级配置器主要是考虑小块内存空间而设计的（为了最大化解决内存碎片问题，进而提升效率），采用链表free_list来维护内存池（memory pool），free_list通过union结构实现，空闲的内存块互相挂接在一块，内存块一旦被使用，则被从链表中剔除，易于维护。

---

STL 容器用过哪些，查找的时间复杂度是多少

• STL中常用的容器有vector、deque、list、map、set、multimap、multiset、unordered_map、unordered_set等

• vector：采用一维数组

  • 插入：O(N)
  • 查找：O(1)
  • 删除：O(N)

• deque：采用双向队列

  • 插入：O(N)
  • 查找：O(1)
  • 删除：O(N)

• list：采用双向链表

  • 插入：O(1)
  • 查找：O(N)
  • 删除：O(1)

• map、set、multiset、multimap

  • 上述四种容器采用红黑树实现，红黑树是平衡二叉树的一种

  • 插入：O(logN)

  • 查找：O(logN)

  • 删除：O(logN)

• unordered_map、unordered_set、unordered_multimap、 unordered_multiset

  • 上述四种容器采用哈希表实现

  • 插入：最好O(1)，最坏O(N)

  • 查找：最好O(1)，最坏O(N)

  • 删除：最好O(1)，最坏O(N)

• 注意：容器的时间复杂度取决于其底层实现方式。

---

迭代器什么时候会失效？

• 1.对于序列容器vector，deque来说，使用rease后，后面的每个元素的迭代器都会失效，后面每个元素都往前移动一位，erase返回下一个有效的迭代器
• 2.对于关联容器map，set来说，使用erase后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素，不会影响下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可
• 对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的迭代器，因此上面两种方法都可以使用。

---

迭代器和指针的区别

• 迭代器的作用：

  • 用于指向顺序容器和关联容器中的元素
  • 通过迭代器可以读取它指向的元素
  • 通过非const迭代器还可以修改其指向的元素

• 两者区别

  迭代器是类模版，不是指针！，迭代器的行为很像指针，重载了指针的一些操作符：->,++,–等。

  迭代器封装了指针，是一个”可遍历STL（ Standard Template Library）容器内全部或部分元素”的对象，本质是封装了原生指针，是指针概念的一种提升，提供了比指针更高级的行为，相当于一种智能指针，他可以根据不同类型的数据结构来实现不同的++，–等操作。

  迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用取值后的值而不能直接输出其自身。

• 迭代器产生的原因

  • iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。

• 容器已经容器的迭代器类别

  容器	容器上的迭代器类别
  vector	随机访问
  deque	随机访问
  list	双向
  set/multiset	双向
  map/multimap	双向
  stack	不支持迭代器
  queue	不支持迭代器
  priority_queue	不支持迭代器

STL 中 resize 和 reserve 的区别

• 两个概念

  • capacity：该值在容器初始化时赋值，指的是容器能够容纳的最大的元素个数，还不能通过下标等访问，因为此时容器中还没有创建任何对象。

  • size：是此时容器中元素的个数，可以通过下标访问0-(size-1)访问

  • resize既修改capacity大小，也修改size大小，reserve只修改capacity大小，不修改size大小

  • 两者的形参个数不一样。 resize带两个参数，一个表示容器大小，一个表示初始值（默认为0）；reserve只带一个参数，表示容器预留的大小。

  • resize 和 reserve 既有差别，也有共同点。两个接口的共同点是它们都保证了vector的空间大小(capacity)最少达到它的参数所指定的大小。下面就他们的细节进行分析

  • 为实现resize的语义，resize接口做了两个保证：

  ​ （1）保证区间[0, new_size)范围内数据有效，如果下标index在此区间内，vector[indext]是合法的；

  ​ （2）保证区间[0, new_size)范围以外数据无效，如果下标index在区间外，vector[indext]是非法的

              reserve只是保证vector的空间大小(capacity)最少达到它的参数所指定的大小n。在区间[0, n)范围内，如果下标是index，vector[index]这种访问有可能是合法的，也有可能是非法的，视具体情况而定
  

• reserve只是保证vector的空间大小(capacity)最少达到它的参数所指定的大小n。在区间[0, n)范围内，如果下标是index，vector[index]这种访问有可能是合法的，也有可能是非法的，视具体情况而定

map和unordered_map的区别

• map实现原理

map底层是红黑树，红黑树有自动排序的功能，因此map内部所有元素是有序的。map进行的查找、删除、添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉树（又名二叉查找树、二叉排序树）存储的，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值。使用中序遍历可将键值按照从小到大遍历出来。

• unordered_map实现原理

unordered_map底层是哈希表，通过关键码值映射到Hash表中一个位置来访问记录。查找时间复杂度可以为O(1)，元素是无序的

vector 和 list 的区别

• vector

底层是一维数组，支持随机访问，容器空间不足时需要扩容

• list

底层是双向链表，只能通过指针来访问，没有重载[]

• 应用场景
  • vector：拥有一段连续的内存空间，需要高效的随机访问，不在乎插入和删除的效率使用vector
  • list：拥有一段不连续的内存空间，需要高效的插入和删除，不关系随机访问使用list

vector插入删除迭代器

底层一维数组

• 新增元素

若集合已满，则在新增数据的时候，需要另外找一块更大的内存，将原来的数据拷贝，释放之前的内存。插入可以分为push_back插在最后和迭代器插入任意位置。通过迭代器与第一个位置的距离相比得出要插入的位置，该元素后面的所有元素都要向后移动一个位置，在空出来的位置上存入新的元素

//新增元素  
void insert(const_iterator iter,const T& t ) {
    int index=iter-begin();  
    if (index<size_) {   
        if (size_==capacity_)   {    
            int capa=calculateCapacity();   
            newCapacity(capa);   
        }   
        memmove(buf+index+1,buf+index,(size_-index)*sizeof(T));    
        buf[index]=t; 
        size_++;  
    } 
}

• 插入元素

通过删除最后一个元素pop_back()和迭代器删除任意一个元素erase(iter);

通过迭代器删除还是先找到要删除元素的位置，即int index=iter-begin();这个位置后面的每个元素都想前移动一个元素的位置。同时我们知道erase不释放内存只初始化成默认值。

删除全部元素使用clear，只是循环调用了erase，不释放内存，内存是在析构函数中释放的

//删除元素  
iterator erase(const_iterator iter) {
	int index=iter-begin();      
	if (index<size_ && size_>0)     {
		memmove(buf+index ,buf+index+1,(size_-index)*sizeof(T));          
		buf[--size_]=T();    
	}      
	return iterator(iter); 
} 

STL新特性

主要包括含语法改进和标准库扩充两个方面，主要有11点

• 

• 1.语法的新特性

  1.统一的初始化方法

  2.成员变量默认初始化

  3**.auto关键字**

  4**.decltype 求表达式的类型**

  5.智能指针 shared_ptr

  6.空指针nullptr

  7.基于返回的for循环

  8**.右值引用和move语义**，让程序员有意识的减少深拷贝

• 2.标准库扩充

  1.无需容器(哈希表)：用法和功能跟map，区别在于哈希表的效率更高

  2.正则表达式：正则表达式实质上是一个字符串，该字符串描述了一种特定模式的字符串

  3,。lambda表达式

• auto和decltype区别

  auto varname = value; decltype(exp) varname = value;

  • 其中，varname 表示变量名，value 表示赋给变量的值，exp 表示一个表达式。

    auto 根据”=”右边的初始值 value 推导出变量的类型，而 decltype 根据 exp 表达式推导出变量的类型，跟”=”右边的 value 没有关系。

  • 另外，auto 要求变量必须初始化，而 decltype 不要求。这很容易理解，auto 是根据变量的初始值来推导出变量类型的，如果不初始化，变量的类型也就无法推导了。decltype 可以写成下面的形式：

    decltype(exp) varname;
    // decltype 用法举例 
    int a = 0; decltype(a) b = 1;  //b 被推导成了 int 
    decltype(10.8) x = 5.5;  //x 被推导成了 double 
    decltype(x + 100) y;  //y 被推导成了 double

• 智能指针 shared ptr

  • 智能指针可以共同使用同一块堆内存，并且智能指针采用引用计数机制，，即便有一个 shared_ptr 指针放弃了堆内存的“使用权”（引用计数减 1），也不会影响其他指向同一堆内存的 shared_ptr 指针。(只有引用计数为0，堆内存才会被自动释放)

  #include <iostream> #include <memory> 
  using namespace std; 
  int main() {     
      //构建 2 个智能指针     
      std::shared_ptr<int> p1(new int(10));     
      std::shared_ptr<int> p2(p1);     
      //输出 p2 指向的数据     
      cout << *p2 << endl;     
      p1.reset();
      //引用计数减 1,p1为空指针     
      if (p1) {         
          cout << "p1 不为空" << endl;     
      }else {        
          cout << "p1 为空" << endl;     
      }     
      //以上操作，并不会影响 p2     
      cout << *p2 << endl;     
      //判断当前和 p2 同指向的智能指针有多少个    
      cout << p2.use_count() << endl;    
      return 0; 
  }  /*      程序运行结果：          10  p1 为空  10  1  */          

• 空指针 nullptr（原来NULL）

  • nullptr是nullptr_t的右值常量，专门用于初始化控类型指针。
  • nullptr可以被隐式的转换成任意的指针类型

  int * a1 = nullptr;
  char * a2 = nullptr;
  double * a3 = nullptr;

• move

  将一个左值强制转换为右值而不进行实际的拷贝操作

  move(arg); // 返回arg对象的右值形式

  对于容器、智能指针、字符串等具有资源管理的对象非常有用

  #include <iostream>
  #include <vector>
  
  int main() {
      std::vector<int> source = {1, 2, 3};
  
      // 使用 std::move 将 source 的内容移动到 target
      std::vector<int> target = std::move(source);
  
      std::cout << "Target size: " << target.size() << std::endl; // 输出：Target size: 3
      std::cout << "Source size: " << source.size() << std::endl; // 输出：Source size: 0
  
      return 0;
  }

• 无序容器(哈希表)

  • 用法和功能跟map一样，但是哈希表效率更高
  • 特点

  1.无序容器内部存储的键值对都是无序的，各键值对的存储位置取决于该键值对中的键

  2.与关联式容器相比，无序容器擅长通过指定键查找对应的值，但对于使用迭代器遍历容器中存储的元素，无序容器执行效率比关联式容器效率低

  

• 正则表达式

  实质是一个字符串，该字符串描述了一种特定模式的字符串，常用的符号如下：

• lambda匿名函数

  格式：

  ​ [外部变量访问方式说明符] (参数) mutable noexcept/throw() -> 返回值类型 { 函数体; };

  • 各部分解释：
    • []:用于向编译器表明当前是一个lambda表达式，其不能被省略。在方括号内部，可以注明当前 lambda 函数的函数体中可以使用哪些“外部变量”。
      • 外部变量：指的是和当前 lambda 表达式位于同一作用域内的所有局部变量
    • ()：参数。和普通函数的定义一样，lambda 匿名函数也可以接收外部传递的多个参数。和普通函数不同的是，如果不需要传递参数，可以连同 () 小括号一起省略
    • mutable：此关键词可省略。如果使用则之前的 () 小括号将不能省略（参数个数可以为 0）。默认情况下，对于以值传递方式引入的外部变量，不允许在 lambda 表达式内部修改它们的值（可以理解为这部分变量都是 const 常量）。而如果想修改它们，就必须使用 mutable 关键字
      • 注意，值传递不会修改变量本身
    • noexcept/throw()： 可以省略，如果使用，在之前的 () 小括号将不能省略（参数个数可以为 0）。默认情况下，lambda 函数的函数体中可以抛出任何类型的异常。而标注 noexcept 关键字，则表示函数体内不会抛出任何异常；使用 throw() 可以指定 lambda 函数内部可以抛出的异常类型。
    • -> :返回值类型。指明 lambda 匿名函数的返回值类型。，如果 lambda 函数体内只有一个 return 语句，或者该函数返回 void，则编译器可以自行推断出返回值类型，此情况下可以直接省略”-> 返回值类型”
    • {}：函数体 和普通函数一样，lambda 匿名函数包含的内部代码都放置在函数体中。该函数体内除了可以使用指定传递进来的参数之外，还可以使用指定的外部变量以及全局范围内的所有全局变量。

• 智能指针的内存泄漏

  • 当两个对象使用一个shared_ptr指向地方时，会造成循环引用，使引用计数失效，从而导致内存泄漏
  • 使用weak_ptr解决

---

• c++11的四种类型转换

const_cast、static_cast、dynamic_cast、reinterpret_cast

• const_cast
  • 将const变量转换为非const
• static_cast
  • 最常用，可用于各种隐式转换。比如非const转const，static_cast可以用于类向上转换，但向下转换能成功但是不安全。
• dynamic_cast
  • 只能用于含有虚函数的类转换，用于类向上和向下转换
  • 向上转换：指子类向基类转换。
  • 向下转换：指基类向子类转换
  • 当父类转换成子类时可能出现非法内存访问的问题。当父类转换成子类时可能出现非法内存访问的问题。
• reinterpret_cast
  • reinterpret_cast可以做任何类型的转换，不过不对转换结果保证，容易出问题。
• 注意：强制转换虽然功能强大，但是转换不够明确，不能检查错误。

老白课上

继承

• 有虚函数的类为多态类

  • 每个多态类有一个虚表
  • 多态类的每个对象都有一个指针指向虚表
    • 指针在内存中的偏移量一般是0

• 多继承

  • 二义性问题：

    • 分别继承的两个父类继承同一个父类。这样有两份相同的代码

    • 解决：确保公共子对象只有一个，具体保留哪一个无关紧要

    • 方式：在直接基类上添上virtual，虚继承，确保公共子对象在子类只保留一个对象

      • 忽略直接基类的构造函数，意味着父类子对象来自于远祖

      

• 接口

全部都是纯虚函数的类就是接口。意味着这个类没有数据成员。接口不是class而是struct

可以用 using 来定义类型

模版

• 变量模版
  • 推荐关键字typename。eg：template < typename T>
    • 模版参数可以有多个
    • 非类型参数必须是常量整数类型
  • 模版不是变量实体，除非模版被实例化

• 立即函数

// var-tpl.cpp

#include <iostream>

// 在编译期间计算出一个值来, 立即函数
consteval size_t fibo_r(size_t n) {
    return n < 3 ? 1 : (fibo_r(n - 1) + fibo_r(n - 2));
}

int main() {
    constexpr size_t n = 10;                                   // 编译期常量
    std::cout << fibo_r(n) << ' ' << fibo_r(40) << std::endl;  // 使用之后，在编译期就完成计算

    return 0;
}

• 模版特化

  

  • < 这里必须是简单名字>不能是const char*等复杂名字

只用了模版参数一部分叫做模版的偏特化

• 模版元编程

// var-tpl.cpp

#include <iostream>

size_t fibo_r(size_t n) {
    return n < 3 ? 1 : (fibo_r(n - 1) + fibo_r(n - 2));
}

template <size_t N>  // 模版变量带有一个非类型参数,必须是常量
// 普通模版
constexpr size_t fibo_v = fibo_v<N - 1> + fibo_v<N - 2>;  // 这是模版递归,递归定义,需要有递归终点。

// 特化的模版,可以不止一个。必须要有普通的模版
template <>
constexpr size_t fibo_v<1> = 1;
template <>
constexpr size_t fibo_v<2> = 1;
// constexpr最好，是c++新的关键字，表明这是一个编译期常量。另外还有 const修饰变量, consteval修饰函数，这两者修饰不同的类型
// 三者通过牺牲编译时间换取运行效率

int main() {
    size_t n = 10;
    std::cout << fibo_r(n) << ' ' << fibo_v<40uz> << std::endl;

    return 0;
}

函数模版

• 基础、模版特化

#include <iostream>

// 函数模版如果没有实例化不是实体,不被编译
// 函数模版的实例化与模版变量的实例化不一样。模版变量的实例化是显示的，而函数模版的实例化是隐式的
template <typename T, T zero = T(0)>
auto abs(T v) {  // 类型自动规约
    return v < 0 ? -v : v;
}

// 为指针类型特化, 不被允许的
// template <typename T>
// auto abs<T*>(T* v) {
//     return v;
// }

int main(int argc, char const* argv[]) {
    // std::cout << abs(-2) << std::endl;  // abs(-2)就是在隐式实例化函数模版
    // 编译器将函数模版实例化,完成模版参数的替换,然后编译器自动生成一个T类型的函数。生成的这个函数叫做模版函数,编译器不会生成函数实现
    // std::cout << abs<int, 0>(-2) << std::endl;  // 函数模版的显示实例化,非类型参数依赖于类型参数

    // 指针
    int a, *p = &a;
    std::cout << abs(p) << std::endl;
    return 0;
}

• 模版缩写、decltype：强制类型相同

// fun-tpl-abbr.cpp

#include <iostream>

template <typename T>
auto add(T a, T b) {
    return a + b;
}

// 模板特化, 报错，模版参数只有一个
// template <>
// auto add<int>(int a, double b) {
//     return a + b;
// }

// 重载,编译器先匹配实函数在匹配模版
// auto add(int a, double b) {
//     return a + b;
// }

// 模版缩写
// auto add2(auto a, auto b) {
//     return a + b;
// }

// b和a的类型强制相同
auto add2(auto a, decltype(a) b) {
    return a + b;
}

int main() {
    std::cout << add(1, 2) << std::endl;
    std::cout << add2(3.3, 4.4) << std::endl;

    return 0;
}

• 完美转发

// perfect-forward.cpp

#include <iostream>

void f(int&) { std::cout << "f(int&)" << std::endl; }
void f(int&&) { std::cout << "f(int&&)" << std::endl; }

template <typename T>
void forward_v(T a) { f(a); }  // 会造成类型折叠

template <typename T>
void forward_r(T& a) { f(a); }

// 完美转发:参数必须是右值引用
template <typename T>
void forward_p(T&& a) { f(std::forward<T>(a)); }

int main() {
    int x = 0;  // 持久变量
    int&& rrx = std::move(x);

    std::cout << "forward by value:\n";
    forward_v(x);    // lvalue左值
    forward_v(1);    // prvalue纯右值
    forward_v(rrx);  // lvalue!!!右值引用，注意右值引用不是右值。凡事有名字的对象都是左值

    std::cout << "forward by ref:\n";
    forward_r(x);
    // forward_r(1); //纯右值不能绑定在左值引用上
    forward_r(rrx);

    std::cout << "forward by perfectly:\n";
    forward_p(x);    // lvalue左值
    forward_p(1);    // prvalue纯右值
    forward_p(rrx);  // lvalue!!!右值引用，注意右值引用不是右值。凡事有名字的对象都是左值

    return 0;
}

• 变长模版，变长数组 + 折叠表达式、sizeof…()表达式

// sum.cpp

#include <cstdarg>
#include <iostream>

template <typename T>
// auto sum(int count, T v0, ...) { // C style
auto sum(int count, T v0...) {  // C++ style
    va_list args;

    va_start(args, v0);

    auto s = v0;
    while (count-- > 0) s += va_arg(args, T);

    va_end(args);

    return s;
}

// 变长参数 + 折叠表达式
template <typename... types>
auto sum2(types... args) {
    std::cout << sizeof...(args) << std::endl;
    return (0 + ... + args);
}

int main() {
    std::cout << sum(4, 1, 2, 3, 4) << std::endl;
    std::cout << sum2(1, 2, 3, 4) << std::endl;

    return 0;
}

外部模版 extern

阻止编译器重复的实例化变量

• 只会生成一个实例，添加特例模版后不会重复实例化

// add-wrapper.cpp

#include "add.h"

// 声明外部模版 针对int进行特化
extern template auto add<int>(int, int);

int add_wrapper(int a, int b) {
    return add(a, b);  // 添加模版后此处就不需要实例化了,直接调用实例化好的模版
}

• 当有不同的类型时，函数会重新实例化

变量模版

#pragma once
// #include <iostream>

// 变量模版
template <typename T>
inline constexpr bool is_boolean = false;

// 特化
template <>
inline constexpr bool is_boolean<bool> = true;

// 添加一个概念concept.是一个编译期机制
template <typename T>
concept Addable = requires(T x) { x + x; };  // 表明T类型定义了加法操作

and not is_boolean<T>;

// template <typename T>
template <Addable T>
auto add(T a, T b) {
    // static int c = 0;
    // std::cout << c++ << std::endl;
    return a + b;
}

类模版

• 类模版中的成员变量都是便变量，函数都是函数模版

• 类模版的实例化必须是显示的

• 引用一个中间类，解决很多问题

// typetraits.cpp

#include <format>
#include <iostream>
#include <typeinfo>

// 类模板：带有内部类型的模板
template <typename T>
struct X {
    using value_type = long;
};

template <typename T>
struct type_traits {
    // 作为任意的内建类型
    using value_type = T;
};

// 做偏特化处理
template <typename T>
struct type_traits<X<T>> {
    // 作为任意的内建类型
    using value_type = X<T>::value_type;
};

// 函数模板：生成一个类型T内部类型的临时对象
template <typename T>
auto f() {
    return typename type_traits<T>::value_type{};
};

// 打印f()返回值的类型名
template <typename T>
void type_name() {
    std::cout << typeid(f<T>()).name() << std::endl;
}

int main() {
    type_name<X<int>>();
    type_name<int>();
    return 0;
}

• trait
  • 将相同的东西抽象出来

容器、迭代器和泛型计算

迭代器模拟了原生指针，是一个类中类

• foreach循环默认使用正向迭代器

• 迭代器设计

// dlist.h

#pragma once

#include <exception>
#include <format>
#include <initializer_list>
#include <iostream>

// 外部类型
// using value_type = int;  // 用value_type代替int

// 类型隔离
template <typename value_t>
class dlist {
public:
    // 类型的作用域在dlist中,在public中，在类外也可以使用
    // using value_type = ::value_type;     // :: 是作用于选择运算符,左边是作用域,现在是空的，等同于是全局作用域,右边是member
    using value_type = value_t;
    using pointer = value_type*;         // 指针
    using reference = value_type&;       // 引用
    using constref = value_type const&;  // 常量引用

private:
    // 节点类型，应该仅为类服务，定义在私有域中
    struct node {              // node是一个类型名
        value_type data;       // 定义一个data
        node* next = nullptr;  // 自动初始化为nullptr
        node* prior = nullptr;

        node() = default;
        template <typename... types>
        node(types&&... args) : data(args...) {
        }
    };

    using nodeptr_t = node*;  // 指向节点的指针类型

    nodeptr_t head = nullptr;
    nodeptr_t tail = nullptr;
    size_t length = 0;  // 链表长度

    // 私有的方法加一个下划线开头
    void _init() {
        head = new node;
        tail = new node;
        head->next = tail;
        tail->prior = head;
    }

    void _clear() {
        // 释放所有节点
        auto p = head;
        auto q = p;
        while (p != nullptr) {
            q = p;
            p = p->next;
            delete q;
        }
        length = 0;
    }

    void _linkbefore(nodeptr_t post, nodeptr_t p) {
        p->next = post;
        p->prior = post->prior;
        post->prior->next = p;
        post->prior = p;
        length++;
    }

protected:
public:
    // 链表的初始化函数，默认构造函数，构造函数没有返回值类型 noexcept不抛出异常,没有异常.
    dlist() noexcept {
        // std::cout << "dlist()\n";
        _init();  // 调用函数构造类
    }

    // initializer_list初始化列表,遇到<>,说明这是个模版,noexcept表明这里的参数是一个常量引用
    // 该构造函数之前先执行委托构造函数。构造函数初始化列表?
    dlist(std::initializer_list<value_type> const& l) noexcept : dlist() {  // : dlist() 希望在这里调用默认的构造函数。称之为构造函数委托
        // std::cout << "dlist({})\n";
        for (auto& v : l) {
            // push_back(v);
            emplace_back(v);
        }
    }

    // 复制构造函数
    /*
        为什么必须是引用:
            若没有,则是值传递,默认调用构造函数，会形成循环
    */
    dlist(dlist const& l) : dlist() {
        std::cout << "dlist(copy)\n";
        for (auto p = l.head->next; p != l.tail; p = p->next) {
            push_back(p->data);
        }
    }

    // 析构函数,析构函数没有参数,因此不能被重载
    ~dlist() noexcept {
        _clear();
    }

    // 赋值号 = 重载
    dlist& operator=(dlist const& l) {
        std::cout << "dlist(=)\n";
        _clear();
        _init();
        for (auto p = l.head->next; p != l.tail; p = p->next) {
            push_back(p->data);
        }
        return *this;  // 指向对象本身.隐式传递的第一个参数
    }

    // move 转移构造函数(用于将亡对象)
    dlist(dlist&& l) : dlist() {  // 将亡对象用右值引用定义
        // 把l的资源直接转移个this
        std::swap(head, l.head);
        std::swap(tail, l.tail);
        std::swap(length, l.length);
    }

    // 右值作用等号重载
    dlist& operator=(dlist&& l) {
        std::cout << "dlist(=)\n";
        std::swap(head, l.head);
        std::swap(tail, l.tail);
        std::swap(length, l.length);

        return *this;  // 指向对象本身.隐式传递的第一个参数
    }

    // 禁止复制,但是可转移
    // dlist(dlist const&) = delete;

    // void push_back(constref v) {  // 形参是实参的别名,避免了内存的复制,定义为常量，保护形参
    //     auto p = new node{v};

    //     _linkbefore(tail, p);
    // }

    template <typename... types>
    void emplace_back(types&&... args) {  // 形参是实参的别名,避免了内存的复制,定义为常量，保护形参
        auto p = new node{args...};
        _linkbefore(tail, p);
    }

    void insert(size_t pos, constref v) try {
        auto p = head->next;
        for (auto i = 0uz; i < pos && p != nullptr; i++) {
            p = p->next;
        }
        if (p == nullptr) {
            throw std::out_of_range("insert postion was out of range");
        }
        auto q = new node{v};
        _linkbefore(p, q);
    } catch (std::out_of_range& e) {
        std::cout << e.what() << std::endl;
        exit(1);
    }

    // 行为参数化是一种典型的函数式编程思维,称之为回调函数
    // callback_t 是个函数类型，参数是一个引用，没有返回值
    // using callback_t = void(reference);

    // 变成模版
    template <typename callback_t>
    void traverse(callback_t visit) {  // visit是个函数的名字
        for (auto p = head->next; p != tail; p = p->next) {
            visit(p->data);
        }
    }

    using container_type = dlist;
    using dataptr_type = nodeptr_t;
    using difference_type = ptrdiff_t;

    // 声明iterator是dlist的友元
    // 迭代器是一个内部类
    friend class iterator;
    class iterator {
    public:
        // 迭代器的类型定义
        using value_type = container_type::value_type;
        using pointer = container_type::pointer;
        using reference = container_type::reference;
        using difference_type = container_type::difference_type;

    private:
        using dataptr_type = container_type::dataptr_type;
        // 定义迭代器成员
        dataptr_type p;

    public:
        // 迭代器的构造函数
        iterator(dataptr_type p = nullptr) : p(p) {}
        // 迭代器重载运算符 constexpr:若评估为常量,设置伪inline
        constexpr bool operator!=(iterator const& itr) const {
            // 实质上是内部指针的比较
            return p != itr.p;
        }

        iterator& operator++() {
            // 实质上是内部指针的比较, 返回左值引用
            // p = p->next;
            // return *this;
            return advance();
        }

        iterator& operator--() {
            // 实质上是内部指针的比较, 返回左值引用
            // p = p->next;
            // return *this;
            return advance(-1);
        }
        // 后缀自加
        iterator&& operator++(int) {
            auto t = p;
            // p = p->next;
            advance();
            return iterator(t);
        }

        // *运算符
        reference operator*() {
            return p->data;
        }

        iterator& advance(difference_type n = 1) {
            if (n >= 0) {
                for (auto i = 0; i < n; i++) {
                    p = p->next;
                }
            } else {
                for (auto i = 0; i < -n; i++) {
                    p = p->prior;
                }
            }
            return *this;
        }

        iterator operator+(difference_type n) {
            // 生成临时迭代器
            // iterator itr(p);
            // return itr.advance(n);
            return iterator(p).advance(n);
        }

        iterator operator-(difference_type n) {
            // 生成临时迭代器
            // iterator itr(p);
            // return itr.advance(n);
            return iterator(p).advance(-n);
        }
    };
    constexpr iterator begin() const {
        return iterator(head->next);
    }

    constexpr iterator end() const {
        return iterator(tail);
    }

    friend class reverse_iterator;
    class reverse_iterator {
    public:
        // 迭代器的类型定义
        using value_type = container_type::value_type;
        using pointer = container_type::pointer;
        using reference = container_type::reference;
        using difference_type = container_type::difference_type;

    private:
        using dataptr_type = container_type::dataptr_type;
        // 定义迭代器成员
        dataptr_type p;

    public:
        // 迭代器的构造函数
        reverse_iterator(dataptr_type p = nullptr) : p(p) {}
        // 迭代器重载运算符 constexpr:若评估为常量,设置伪inline
        constexpr bool operator!=(reverse_iterator const& itr) const {
            // 实质上是内部指针的比较
            return p != itr.p;
        }

        reverse_iterator& operator++() {
            // 实质上是内部指针的比较, 返回左值引用
            // p = p->next;
            // return *this;
            return advance();
        }

        reverse_iterator& operator--() {
            // 实质上是内部指针的比较, 返回左值引用
            // p = p->next;
            // return *this;
            return advance(-1);
        }
        // 后缀自加
        reverse_iterator&& operator++(int) {
            auto t = p;
            // p = p->next;
            advance();
            return reverse_iterator(t);
        }

        // *运算符
        reference operator*() {
            return p->data;
        }

        reverse_iterator& advance(difference_type n = 1) {
            if (n >= 0) {
                for (auto i = 0; i < n; i++) {
                    p = p->prior;
                }
            } else {
                for (auto i = 0; i < -n; i++) {
                    p = p->next;
                }
            }
            return *this;
        }

        reverse_iterator operator+(difference_type n) {
            // 生成临时迭代器
            // reverse_iterator itr(p);
            // return itr.advance(n);
            return reverse_iterator(p).advance(n);
        }

        reverse_iterator operator-(difference_type n) {
            // 生成临时迭代器
            // reverse_iterator itr(p);
            // return itr.advance(n);
            return reverse_iterator(p).advance(-n);
        }
    };
    constexpr reverse_iterator rbegin() const {
        return reverse_iterator(tail->prior);
    }

    constexpr reverse_iterator rend() const {
        return reverse_iterator(head);
    }
};

• 测试代码

// testdlist.cpp

#include <format>
#include <iostream>

#include "dlist.h"

struct foo {
    int i;
    double d;
    foo(int _i = 0, double _d = 0) : i(_i), d(_d) {
    }
    foo(foo const& f) : i(f.i), d(f.d) {
        std::cout << "foo: copy ctor" << std::endl;
    }
};

std::ostream& operator<<(std::ostream& os, foo const& f) {
    return os << std::format("({},{})", f.i, f.d);
}

// template <typename value_t>
// void print_l(dlist<value_t>& l) {
//     l.traverse([](auto& v) {
//         std::cout << v << ' ';
//     });  // 调用dlist中的方法进行遍历
//     std::cout << std::endl;
// }

template <typename iterator>
void print_l(iterator first, iterator last) {
    for (auto itr = first; itr != last; ++itr) {
        std::cout << *itr << ' ';
    }
    std::cout << std::endl;
}

int main() {
    // 花括号初始化列表,是一种可迭代的类型
    // 类模版的实例化必须是显示的
    // dlist<int> l{1, 2, 3, 4, 5, 6};  // 编译器在这里强制调用对象的构造函数

    // print_l(l);

    dlist<foo> l2;
    for (int i = 1; i <= 10; i++) {
        // l2.push_back(foo{i, i * 1.23});
        l2.emplace_back(i, i * 1.23);
    }
    // print_l(l2);

    // 当容器有了迭代器之后就可以使用foreach循环
    // for (auto& e : l2) {
    //     std::cout << e;
    // }
    std::cout << std::endl;

    print_l(l2.begin(), l2.end());
    print_l(l2.begin() + 3, l2.end() - 2);
     print_l(l2.rbegin(), l2.rend());
    print_l(l2.rbegin() + 3, l2.rend() - 2);

    // dlist<char> l2{'A', 'B', 'C'};
    // print_l(l2);

    // // lambda匿名函数,[]表示捕获参数
    // l.traverse([](auto& v) {
    //     v++;
    // });
    // l.insert(9, 7);

    // print_l(l);

    // 这样执行会出错。发生了一次复制，内存的对拷 ---> 浅拷贝
    // 内部指针指向相同的内存,当打印完l2之后,两个对象的析构函数会被强制调用,c++是基于栈的语言，l2先析构，内存被释放，
    // 此时内部指针指向的地址已经被释放,所以会报错
    // dlist l2;  // = l;  // 编译器合成了一个构造函数, 功能是两个对象的内存拷贝,导致资源共享, 默认调用此构造函数,我们称之为复制构造函数
    // l2 = l;
    // print_l(l2);

    return 0;
}

操作系统

软连接和硬链接

• 定义不同

• 软连接又叫符号链接，这个文件包含了另一个文件的路径名。可以是任意文件或目录，可以链接不同文件系统的文件

• 硬链接就是一个文件的一个或多个文件名。把文件名和计算机文件系统使用的节点号链接起来。因此我们可以用多个文件名与同一个文件进行链接，这些文件名可以在同一目录或不同目录。

• 限制不同
  • 硬链接只能对已存在的文件进行创建，不能交叉文件系统进行硬链接的创建
  • 软链接可对不存在的文件或目录创建软链接；可交叉文件系统
• 创建方式不同
  • 硬链接不能对目录进行创建，只可对文件创建
  • 软链接可对文件或目录创建
• 影响不同
  • 删除一个硬链接并不影响其他有相同inode号的文件
  • 删除软链接并不影响被指向的文件，但若被指向的源文件被删除，则相关软连接被称为死链接（即 dangling link，若被指向路径文件被重新创建，死链接可恢复为正常的软链接）。

动态库和静态库的制作及区别

• 静态库的制作

gcc hello.c  -c //这样就生成hello.o目标文件 
ar rcs libhello.a  hello.o //生成libhello.a静态库

• 静态库使用

gcc main.c -lhello -o staticLibrary //main.c和hello静态库链接，生成staticLibrary执行文件
/*     
	 main.c：是指main主函数     
	-lhello：是我们生成的.a 文件砍头去尾（lib不要 .a也不要）前面加-l    
    -L：是指告诉gcc编译器先从-L指定的路径去找静态库，默认是从/usr/lib/ 或者  /usr/local/lib/ 去找。    
    ./：是指当前路径的意思     
    staticLibrary：是最后想生成的文件名（这里可随意起名字） 
*/

• 动态库制作

gcc -shared -fpic hello.c -o libhello.so
	-shared 指定生成动态库 
	-fpic ：fPIC选项作用于编译阶段，在生成目标文件时就得使用该选项，以生成位置无关的代码。

• 动态库使用

gcc main.c -lhello -L ./ -o dynamicDepot 
/*     
	main.c：是指main主函数     
	-lhello：是我们生成的.so 文件砍头去尾（lib不要 .so也不要）前面加-l     
	-L：是指告诉gcc编译器先从-L指定的路径去找静态库，默认是从/usr/lib/ 或者 /usr/local/lib/ 去找。     
	./：是指当前路径的意思     
	dynamicDepot：是最后想生成的文件名（这里可随意起名字） 
*/

• 两者区别
  • 静态库代码装载的速度快，执行速度略比动态库快
  • 动态库更节省内存，可执行文件体积比静态库小很多
  • 静态库是在编译时加载，动态库是在运行时加载
  • 生成的静态链接库，windows下以**.lib为后缀，Linux下以.a**为后缀
  • 生成的动态链接库，windows下以**.dll为后缀，Linux下以.so**为后缀

GDB调试命令

• GDB调试

fdb调试的是可执行文件，在gcc编译时加入 -g，告诉gcc在编译时加入调试信息，这样gdb才能调试这个被编译的文件gcc -g test.c -o test

• GDB命令格式
  • quit：退出gdb
  • list：查看程序源代码
  • reverse-search：字符串用来从当前行向前查找第一个匹配的字符窜
• run：程序开始执行
• help list/all：
  • 查看帮助信息
• break： 设置断点
  • break 7：在第七行设置断点
  • break get_num：以函数名设置断点
  • break 行号或者函数名 if 条件：以条件表达式设置断点
• watch条件表达式：条件表达式发生改变时程序就会停下来
• next：继续执行下一条语句，会把函数当做一条语句执行
• step：继续执行下一条语句，会跟踪进入函数，一次执行函数内的代码

网络字节序

• 小端

低的有效字节存储在低的存储器地址。小端一般为主机字节序；常用的X86结构是小端模式。很多的ARM，DSP都为小端模式

• 大端

低的有效字节存储在低的存储器地址。小端一般为主机字节序；常用的X86结构是小端模式。很多的ARM，DSP都为小端模式

• 网络字节序

网络上传输的数据都是字节流

• UDP/TCP/IP协议规定:把接收到的第一个字节当作高位字节看待,这就要求发送端发送的第一个字节是高位字节;
  • 即TCP等协议是大端协议

虚拟内存

• 存储系统为每一个进程分配一个独立的地址空间，虚拟内存与物理内存存在映射关系，通过页表寻址完成虚拟地址和物理地址的转换

内核态和用户态

内核态和用户态是操作系统的两种运行级别

• 系统态、内核态：

  • 拥有最高权限，可以访问所有系统指令，用户态则只能访问一部分指令
  • 进入内核态的三种方式

  1.系统调用：主动的

  2.异常：被动的

  3.设备中断：被动的

进程、线程、协程

• 进程
  • 进程是由程序段、数据段和PCB组成的，是程序运行的实例。
    • 程序段：
      • 运行着哪段程序
    • 数据段：
      • 进程运行过程中需要用到的数据
    • PCB
      • 进程描述信息
      • 进程控制和管理信息
      • 资源分配清淡
      • CPU相关信息
• 线程
  • 一个进程里的执行单元。一个进程里包含多个线程并发执行任务
• 协程
  • 一个线程包含多个协程，在子程序内部执行，可在子程序内部中断，转而执行别的子程序，在适当的时候再返回来接着执行

fork()函数

• 创建一个子进程

创建成功会在父进程中返回对应子进程的pid

在子进程中返回0

失败返回-1

fork函数创建一个新进程后，会为这个新进程分配进程空间，将父进程的进程空间中的内容复制到子进程的空间中，包括父进程的数据段和堆栈段，并且和父进程共享代码段。这时候，子进程和父进程一模一样，都接受系统的调度。因为两个进程都停留在fork()函数中，最后fork()函数会返回两次，一次在父进程中返回，一次在子进程中返回，两次返回的值不一样，如上面的三种情况。

---

守护进程

守护进程是运行在后台的一种生存期长的特殊进程

• 实现：
  • 1.创建子进程，终止父进程。
    • fork()之后推出父进程
  • 2.调用setid()创建一个新会话
  • 3.将当前目录更改为根目录。子进程也进程了父进程的当前工作目录
  • 4.重设文件权限掩码
  • 5.关闭不再需要的文件描述符。子进程从父进程继承打开的文件描述符

进程通信

---

信号量

本质是一个计数器，用于多进程对共享数据的读取。主要用来保护共享资源，使得资源在一个时刻只有一个进程独享

• 原理
  • pv操作
  • P(sv)操作：如果sv的值大于零，就给它减1；如果它的值为零，就挂起该进程的执行（信号量的值为正，进程获得该资源的使用权，进程将信号量减1，表示它使用了一个资源单位）。
  • V(sv)操作：如果有其他进程因等待sv而被挂起，就让它恢复运行，如果没有进程因等待sv而挂起，就给它加1（若此时信号量的值为0，则进程进入挂起状态，直到信号量的值大于0，若进程被唤醒则返回至第一步）。

进程和线程的区别

• 最大的区别在于资源共享的层级不同，均使用do_fork()实现
• 父进程与子进程之间仅共享程序文本段，而同一个进程下的所有线程却共享数据段，堆段和文件描述符
• 线程更容易通信，因为拥有相同数据段，全局变量共享
  • 线程的创建速度更高，数据重合度高，只需要创建自己的堆栈即可
  • 线程之间的切换比进程间切换开销小
• 进程是资源分配的最小单位，线程是系统调度的最小单位

计网

DNS域名解析过程

• 当我们在浏览器地址栏中输入www.baidu.com时，DNS解析将会有将近10个步骤

  

1.检查浏览器缓存是否有对应域名解析过的IP地址，有就停止解析(注意该缓存时间不能太长也不能太短，大小也有限制)

2.在操作系统缓存查找(Linux在/etc/hosts文件)

3.前两者都没法解析，操作系统把这个域名发送给本地DBS服务器，在该域名服务器的缓存中查找。80%到这结束

4.若还是没有找到，直接到根域名服务器请求解析

5.通过递归查询或者迭代查询

三次握手和四次挥手

• 三次握手

1.第一次握手：建立连接时：客户端向服务器发送SYN=1，seq =x。请求建立连接，等待确认

2.第二次握手：服务器接收到客户端SYN包，回一个ACK包(ACK = 1),确认收到，ack = x + 1，同时发送一个seq = y给客户端

3.第三次握手：客户端收到确认报文，再返回一个ACK确认报文，告诉服务器已经收到

• 四次挥手

1.客户端发送FIN包(FIN = 1)给服务器。告诉服务器自己数据发送完毕，请求终止连接。此时客户端不能发送数据，但是可以接收数据。客户端进入FIN-WAIT-1状态

2.服务器接收到断开连接FIN包，回一个ACK确认报文。告诉客户端它已经收到包了。此时并未断开socket连接，而是等待剩下的数据传输完毕。服务器进入CLOSE-WAIT状态。客户端收到该报文后进入FIN-WAIT-2

3.服务器等待数据传输完毕后，向客户端发送FIN断开连接报文，表明可以断开连接。服务器进入LAST-ACK

4.客户端接收到FIN报文后，返回ACK确认报文，进入TIME-WAIT状态，等待2MSL，确认服务器不再有数据发送过来，然后CLOSED

TCP可靠性保证

TCP主要提供了检验和、序列号/确认应答、超时重传、最大消息长度MSS、滑动窗口控制等方法实现可靠性传输

• 最大消息长度
  • 在建立TCP的时候，通信双方约定的数据的最大长度。理想情况是该长度的数刚好不被网络层分块
• 滑动窗口机制
  • 窗口的大小就是在无需等待确认包的情况下，发送端还能发送的最大数据量。这个机制的实现就是使用了大量的缓冲区，通过对多个段进行确认应答的功能。通过下一次的确认包可以判断接收端是否已经接收到了数据，如果已经接收了就从缓冲区里面删除数据。
  • 
• 拥塞控制
  • 滑动窗口解决了两台主机之间因为传送速率不同而引起的丢包问题
  • 如果网络非常拥堵，此时发送的数据可能超过了最大生存时间TTL也没有到达，也会引起丢包。此时使用拥塞控制
  • 发送开始时定义拥塞窗口大小为1；每次收到一个ACK应答，拥塞窗口加1；而在每次发送数据时，发送窗口取拥塞窗口与接送段接收窗口最小者

cookie和session

cookie和session都是会话中的一种方式。

• 它们的典型使用场景比如“购物车”，当你点击下单按钮时，服务端并不清楚具体用户的具体操作，为了标识并跟踪该用户，了解购物车中有几样物品，服务端通过为该用户创建Cookie/Session来获取这些信息。
• cookie数据放在客户的浏览器上，session数据放在服务器上
• cookie并不安全，可以分析本地cookie并利用
• session会在一定时间内保存在服务器上，当访问增多，会占用服务器性能
• 单个cookie保存的数据不能超过4K，很多浏览器都限制一个站点最多保存20个cookie

DNS负载均衡

• 当有一个网站有足够多的用户时，假如每次请求的资源都位于同一台机器上，那么这台机器随时可能崩掉。处理办法就是用DNS负载均衡技术
• 在DNS服务器中为同一个域名配置多个IP地址，在应答DNS查询时，DNS服务器对每个查询将以DNS文件中主机记录的IP地址按顺序返回不同的解析结果，将客户端的访问引导到不同的机器上去，使得不同的客户端访问到不同的服务器。

应用层

域名系统DNS

DNS是一个分布式数据库，提供域名和IP之间的转化服务。

• DNS可以使用TCP或者UDP进行传输，使用的端口号都是53
  • 大多数都使用UDP传输。这就要求域名服务器和域名解析器都必须自己处理超时和重传从而保证可靠性

文件传输协议FTP

FTP使用TCP进行连接

它有两个连接传输文件

• 控制连接：服务器打开21号端口等待客户端连接
  • 客户端主动建立连接后，使用这个连接将客户端的命令传送给服务器，并传回服务器的应答。

根据数据连接是否是服务器主动建立，FTP有主动和被动两种模式

• 主动模式：服务器主动建立连接
  • 服务器端口号为20，客户端端口随意(＞1024)
• 被动模式：客户端主动建立连接
  • 其中客户端的端口号由客户端自己指定，服务器端的端口号随机。

动态主机配置协议DHCP

DHCP提供了即插即用的连网方式，用户不需要手动配置IP地址等信息

• DHCP不仅配置IP地址，还有子网掩码，网关IP等
• 客户端端口号68，服务器进程读端口号67
• 一般通过UDP通信

• 过程(简易版)：
  • 1.客户端发送 Discover 报文，该报文的目的地址为 255.255.255.255:67，源地址为 0.0.0.0:68，被放入 UDP 中，该报文被广播到同一个子网的所有主机上。如果客户端和 DHCP 服务器不在同一个子网，就需要使用中继代理。
  • 2.DHCP 服务器收到 Discover 报文之后，发送 Offer 报文给客户端，该报文包含了客户端所需要的信息。因为客户端可能收到多个 DHCP 服务器提供的信息，因此客户端需要进行选择
  • 3.如果客户端选择了某个 DHCP 服务器提供的信息，那么就发送 Request 报文给该 DHCP 服务器。
  • 4.DHCP 服务器发送 Ack 报文，表示客户端此时可以使用提供给它的信息。

常用端口

页面请求过程

• 1.DHCP配置主机信息

若主机最开始没有IP及其他信息，就需要使用DHCP协议来获取

• 主机生成一个DHCP请求报文，发送端口为68，服务器接受端口为67。原地址为0.0.0.0，目的地址的255.255.255.255
• 该数据报被放置在MAC帧中。该帧具有目的地址，将广播到与交换机连接的所有设备
• 连接在交换机的DHCP服务器收到广播帧之后，不断地向上分解得到IP数据报，UDP报文段和DHCP请求报文。之后生成DHCPACK报文，该报文包含：
  • IP地址、DNS服务器的IP地址、默认网关路由器的IP地址和子网掩码。
  • DHCP报文被放入UDP报文段中，UDP报文段被放入IP数据报中，最后封装成MAC帧
  • 该MAC帧的目的地址是请求主机的MAC地址，因为交换机具有自学习能力，之前主机发送了广播帧之后就记录了MAC地址到其转发接口的交换表项，因此交换机现在知道向哪个接口发送该帧
• 主机收到该帧后，不断分解得到 DHCP 报文。之后就配置它的 IP 地址、子网掩码和 DNS 服务器的 IP 地址，并在其 IP 转发表中安装默认网关。

• 2.ARP协议解析MAC地址

• 主机通过浏览器生成一个 TCP 套接字，套接字向 HTTP 服务器发送 HTTP 请求。为了生成该套接字，主机需要知道网站的域名对应的 IP 地址。

• 主机生成一个DNS查询报文，对应53号端口
• 该 DNS 查询报文被放入目的地址为 DNS 服务器 IP 地址的 IP 数据报中。
• 该 IP 数据报被放入一个以太网帧中，该帧将发送到网关路由器。
• DHCP协议只知道网关路由器的IP地址，为了获取网关路由器的MAC地址，需要使用ARP协议
• 主机生成一个包含目的地址为网关路由器 IP 地址的 ARP 查询报文，将该 ARP 查询报文放入一个具有广播目的地址的以太网帧中，并向交换机发送该以太网帧，交换机将该帧转发给所有的连接设备，包括网关路由器。
• 网关路由器接收到该帧后，不断向上分解得到 ARP 报文，发现其中的 IP 地址与其接口的 IP 地址匹配，因此就发送一个 ARP 回答报文，包含了它的 MAC 地址，发回给主机。

• 3.DNS域名解析

知道了网关路由器的 MAC 地址之后，就可以继续 DNS 的解析过程了。

• 网关路由器接收到包含 DNS 查询报文的以太网帧后，抽取出 IP 数据报，并根据转发表决定该 IP 数据报应该转发的路由器
• 因为路由器具有内部网关协议（RIP、OSPF）和外部网关协议（BGP）这两种路由选择协议，因此路由表中已经配置了网关路由器到达 DNS 服务器的路由表项
• 到达 DNS 服务器之后，DNS 服务器抽取出 DNS 查询报文，并在 DNS 数据库中查找待解析的域名
• 找到 DNS 记录之后，发送 DNS 回答报文，将该回答报文放入 UDP 报文段中，然后放入 IP 数据报中，通过路由器反向转发回网关路由器，并经过以太网交换机到达主机。

• 4.HTTP请求页面

有了 HTTP 服务器的 IP 地址之后，主机就能够生成 TCP 套接字，该套接字将用于向 Web 服务器发送 HTTP GET 报文

• 在生成 TCP 套接字之前，必须先与 HTTP 服务器进行三次握手来建立连接。生成一个具有目的端口 80 的 TCP SYN 报文段，并向 HTTP 服务器发送该报文段。
• HTTP 服务器收到该报文段之后，生成 TCP SYN ACK 报文段，发回给主机。
• 连接建立之后，浏览器生成 HTTP GET 报文，并交付给 HTTP 服务器。
• HTTP 服务器从 TCP 套接字读取 HTTP GET 报文，生成一个 HTTP 响应报文，将 Web 页面内容放入报文主体中，发回给主机。
• 浏览器收到 HTTP 响应报文后，抽取出 Web 页面内容，之后进行渲染，显示 Web 页面。

---

传输层

UDP和TCP特点

• UDP

  • 用户数据报是无连接的，尽最大可能交付。没有拥塞控制、流量控制等，面相报文，对应用程序传下俩的报文不合并也不拆分，只是添加UDP头部。支持1对1,1对多，多对1，多对多
  • 首部8个字节。包括源IP，目的IP，长度，检验和。
  • 伪首部12字节，为了计算检验和临时添加的

• TCP

  • 传输控制协议是面向连接的，提供可靠交付。有流量控制，拥塞控制，超时重传。提供全双工通信，面相字节流，即把应用层传下来的报文看成字节流，把字节流组织成大小不等的数据块。TCP连接是一对一的
  • 首部20字节，包括：
    • 序列号：用于对字节流进行编号，例如序号为 301，表示第一个字节的编号为 301，如果携带的数据长度为 100 字节，那么下一个报文段的序号应为 401。
    • 确认号：期望收到的下一个报文段的序号。例如 B 正确收到 A 发送来的一个报文段，序号为 501，携带的数据长度为 200 字节，因此 B 期望下一个报文段的序号为 701，B 发送给 A 的确认报文段中确认号就为 701。
    • 数据偏移：指的是数据部分距离报文段起始处的偏移量。实际上是首部的长度
    • 确认ACK：当ACK = 1时确认号字段有效，否则无效。TCP 规定，在连接建立后所有传送的报文段都必须把 ACK 置 1。
    • 同步SYN：在连接建立时用来同步序号。当 SYN=1，ACK=0 时表示这是一个连接请求报文段。若对方同意建立连接，则响应报文中 SYN=1，ACK=1。
    • 终止FIN：用来释放一个连接。当FIN = 1时，表示此报文段的发送方的数据已经发送完毕，并要求释放连接
    • 窗口：窗口值作为接收方让发送方设置其发送窗口的依据。之所以要有这个限制，是因为接收方的数据缓存空间是有限的。

  

TCP滑动窗口

• 窗口是缓存的一部分，用来暂时存放字节流。发送方和接收方各有一个窗口，接收方通过 TCP 报文段中的窗口字段告诉发送方自己的窗口大小，发送方根据这个值和其它信息设置自己的窗口大小。
• 发送窗口内的字节都允许被发送，接收窗口内的字节都允许被接收。如果发送窗口左部的字节已经发送并且收到了确认，那么就将发送窗口向右滑动一定距离，直到左部第一个字节不是已发送并且已确认的状态；接收窗口的滑动类似，接收窗口左部字节已经发送确认并交付主机，就向右滑动接收窗口。
• 接收窗口只会对窗口内最后一个按序到达的字节进行确认。
  • 例如接收窗口已经收到的字节为 {31, 34, 35}，其中 {31} 按序到达，而 {34, 35} 就不是，因此只对字节 31 进行确认。发送方得到一个字节的确认之后，就知道这个字节之前的所有字节都已经被接收。

TCP流量控制

流量控制是为了控制发送方发送速率，保证接收方来得及接收。

• 接收方发送的确认报文中的窗口字段可以用来控制发送方窗口大小，从而影响发送方的发送速率
  • 将窗口字段设置为0则发送方不能发送数据

TCP拥塞控制

流量控制是为了让接收方能来得及接收，而拥塞控制是为了降低整个网络的拥塞程度。

• 四大算法：

  • 慢开始
  • 拥塞避免
  • 快重传
  • 快恢复

• 发送方需要维护一个叫做拥塞窗口（cwnd）的状态变量，注意拥塞窗口与发送方窗口的区别：拥塞窗口只是一个状态变量，实际决定发送方能发送多少数据的是发送方窗口。

  

• 慢开始与拥塞避免

  • 慢开始：发送的最初执行慢开始，令 cwnd = 1，发送方只能发送 1 个报文段；当收到确认后，将 cwnd 加倍，因此之后发送方能够发送的报文段数量为：2、4、8 …
  • 拥塞避免：设置一个慢开始门限 ssthresh，当 cwnd >= ssthresh 时，进入拥塞避免，每个轮次只将 cwnd 加 1。
  • 如果出现了超时，则令 ssthresh = cwnd / 2，然后重新执行慢开始，cwnd = 1

• 快重传与快恢复

  • 在接收方，要求每次接收到报文段都应该对最后一个已收到的有序报文段进行确认。例如已经接收到 M1 和 M2，此时收到 M4，应当发送对 M2 的确认。
  • 在发送方，如果收到三个重复确认，那么可以知道下一个报文段丢失，此时执行快重传，立即重传下一个报文段。例如收到三个 M2，则 M3 丢失，立即重传 M3。
  • 在这种情况下，只是丢失个别报文段，而不是网络拥塞。因此执行快恢复，令 ssthresh = cwnd / 2 ，cwnd = ssthresh，注意到此时直接进入拥塞避免
  • 慢开始和快恢复的快慢指的是 cwnd 的设定值，而不是 cwnd 的增长速率。慢开始 cwnd 设定为 1，而快恢复 cwnd 设定为 ssthresh。

网络层

网络层是整个互联网的核心。因此要求网络层尽可能的简单。

网络层向上只提供简单灵活的、无连接的、尽最大努力交互的数据报服务。

使用 IP 协议，可以把异构的物理网络连接起来，使得在网络层看起来好像是一个统一的网络。

IP数据报

• 长度为20字节
• 版本：有IPv4和IPv6
• 首部长度：展4位，0-15。值为 1 表示的是 1 个 32 位字的长度，也就是 4 字节。因为固定部分长度为 20 字节，因此该值最小为 5。如果可选字段的长度不是 4 字节的整数倍，就用尾部的填充部分来填充
• 总长度：包括首部长度和数据部分长度
• 生存时间TTL：是为了防止无法交付的数据报在互联网中一直兜圈子。以路由器跳数为单位，当TTL为0时就放弃数据报
• 协议 ：指出携带的数据应该上交给哪个协议进行处理，例如 ICMP、TCP、UDP 等。
• 首部校验和：因为数据报每经过一个路由器，都要重新计算检验和，因此检验和不包含数据部分可以减少计算的工作量
• 标识：在数据报长度过长从而发生分片的情况，相同数据报的不同分片具有相同的标识符
• 偏移量：和标识符一起，用于发生分片的情况。片偏移的单位为 8 字节。

IP编址方式

• 三个发展阶段

  • 分类
  • 子网划分
  • 无分类

• 分类：

  • 由两部分组成，网络号和主机号，其中不同分类具有不同的网络号长度，并且是固定的

  

• 子网划分：

  • 通过在主机号字段中拿一部分作为子网号，把两级 IP 地址划分为三级 IP 地址。
  • 要使用子网，必须配置子网掩码。一个 B 类地址的默认子网掩码为 255.255.0.0，如果 B 类地址的子网占两个比特，那么子网掩码为 11111111 11111111 11000000 00000000，也就是 255.255.192.0。
  • 注意：外部网络看不到子网的存在

• 无分类情况

  • 消除传统ABC类地址及子网划分的概念。使用网络前缀和主机号来对IP地址进行编码，网络前缀的长度可以根据需要变化
  • CIDR 的记法上采用在 IP 地址后面加上网络前缀长度的方法，例如 128.14.35.7/20 表示前 20 位为网络前缀。
  • 一个 CIDR 地址块中有很多地址，一个 CIDR 表示的网络就可以表示原来的很多个网络，并且在路由表中只需要一个路由就可以代替原来的多个路由，减少了路由表项的数量。把这种通过使用网络前缀来减少路由表项的方式称为路由聚合，也称为 构成超网 。
  • 在路由表中的项目由“网络前缀”和“下一跳地址”组成，在查找时可能会得到不止一个匹配结果，应当采用最长前缀匹配来确定应该匹配哪一个

地址解析协议ARP

网络层实现主机之间的通信，而链路层实现具体每段链路之间的通信。因此在通信过程中，IP 数据报的源地址和目的地址始终不变，而 MAC 地址随着链路的改变而改变。

• 每个主机都有一个 ARP 高速缓存，里面有本局域网上的各主机和路由器的 IP 地址到 MAC 地址的映射表。

• 如果主机 A 知道主机 B 的 IP 地址，但是 ARP 高速缓存中没有该 IP 地址到 MAC 地址的映射，此时主机 A 通过广播的方式发送 ARP 请求分组，主机 B 收到该请求后会发送 ARP 响应分组给主机 A 告知其 MAC 地址，随后主机 A 向其高速缓存中写入主机 B 的 IP 地址到 MAC 地址的映射。

  

网际控制报文协议ICMP

• ICMP 是为了更有效地转发 IP 数据报和提高交付成功的机会。它封装在 IP数据报中，但是不属于高层协议。

  

  • ICMP 报文分为差错报告报文和询问报文

  

ping

• ping是ICMP的一个重要应用，主要用来测试两台主机之间的连通性
• Ping 的原理是通过向目的主机发送 ICMP Echo 请求报文，目的主机收到之后会发送 Echo 回答报文。Ping 会根据时间和成功响应的次数估算出数据包往返时间以及丢包率。

traceroute

• Traceroute 是 ICMP 的另一个应用，用来跟踪一个分组从源点到终点的路径。

• Traceroute 发送的 IP 数据报封装的是无法交付的 UDP 用户数据报，并由目的主机发送终点不可达差错报告报文。

  

网络地址转换NAT

使用后本地IP地址的主机想和互联网上的主机进行通信时，使用NAT来将本地IP转换为全球IP

• 在以前，NAT 将本地 IP 和全球 IP 一一对应，这种方式下拥有 n 个全球 IP 地址的专用网内最多只可以同时有 n 台主机接入互联网。为了更有效地利用全球 IP 地址，现在常用的 NAT 转换表把传输层的端口号也用上了，使得多个专用网内部的主机共用一个全球 IP 地址。使用端口号的 NAT 也叫做网络地址与端口转换 NAPT。

路由器

• 结构

从功能上分为：路由选择和存储转发

• 分组转发的结构：

  • 交换结构、一组输入端口和一组输出端口

  

• 路由器分组转发流程

  • 从数据报的首部提取目的主机的 IP 地址 D，得到目的网络地址 N。
  • 若 N 就是与此路由器直接相连的某个网络地址，则进行直接交付；
  • 若路由表中有目的地址为 D 的特定主机路由，则把数据报传送给表中所指明的下一跳路由器；
  • 若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器
  • 若上述都不满足，报告转发分组出错

  

路由选择协议

路由选择协议都是自适应的，能随着网络通信量和拓扑结构的变化而自适应地进行调整。

• 互联网可以划分为许多较小的自治系统 AS，一个 AS 可以使用一种和别的 AS 不同的路由选择协议
• 路由选择协议分为两大类：
  • 自治系统内部的路由选择：RIP和OSPF
  • 自治系统间的路由选择：BGP

RIP-基于距离向量

• RIP 是一种基于距离向量的路由选择协议。距离是指跳数，直接相连的路由器跳数为 1。跳数最多为 15，超过 15 表示不可达。
• RIP 按固定的时间间隔仅和相邻路由器交换自己的路由表，经过若干次交换之后，所有路由器最终会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器地址。
• 距离向量算法
  • 对地址为 X 的相邻路由器发来的 RIP 报文，先修改报文中的所有项目，把下一跳字段中的地址改为 X，并把所有的距离字段加 1；
  • 对修改后的 RIP 报文中的每一个项目，进行以下步骤：
  • 若原来的路由表中没有目的网络 N，则把该项目添加到路由表中；
  • 否则：若下一跳路由器地址是 X，则把收到的项目替换原来路由表中的项目；否则：若收到的项目中的距离 d 小于路由表中的距离，则进行更新（例如原始路由表项为 Net2, 5, P，新表项为 Net2, 4, X，则更新）；否则什么也不做。
  • 若 3 分钟还没有收到相邻路由器的更新路由表，则把该相邻路由器标为不可达，即把距离置为 1

内部网关协议ospf-Dijkstra 算法

开放最短路径优先 OSPF，是为了克服 RIP 的缺点而开发出来的。

• 最短路径优先表示使用了 Dijkstra 提出的最短路径算法 SPF。
• ospf的特点:
  • 向本自治系统中的所有路由器发送信息，这种方法是洪泛法
  • 发送的信息就是与相邻路由器的链路状态，链路状态包括与哪些路由器相连以及链路的度量，度量用费用、距离、时延、带宽等来表示
  • 只有当链路状态发生变化时，路由器才会发送信息
• 所有路由器都具有全网的拓扑结构图，并且是一致的。相比于 RIP，OSPF 的更新过程收敛的很快

外部网关协议BGP

BGP（Border Gateway Protocol，边界网关协议）

• AS 之间的路由选择很困难，主要是由于

  • 互联网规模很大
  • AS内部采用不同协议
  • AS之间的路由选择需要考虑非效率因素，比如政治等

• BGP 只能寻找一条比较好的路由，而不是最佳路由。

• 每个 AS 都必须配置 BGP 发言人，通过在两个相邻 BGP 发言人之间建立 TCP 连接来交换路由信息。

  

---

链路层

基本问题

• 封装成帧

  • 将网络层传下来的分组添加首部和尾部，用于标记帧的开始和结束。

  

• 透明传输

  • 帧使用首部和尾部进行定界，如果帧的数据部分含有和首部尾部相同的内容，那么帧的开始和结束位置就会被错误的判定。需要在数据部分出现首部尾部相同的内容前面插入转义字符。如果数据部分出现转义字符，那么就在转义字符前面再加个转义字符。在接收端进行处理之后可以还原出原始数据。这个过程透明传输的内容是转义字符，用户察觉不到转义字符的存在。

  

• 差错检测

  • 数据链路层使用CRC循环冗余法来检查比特差错

信道

广播信道

• 一对多通信，一个节点发送的数据能够被广播信道上所有的节点接收到
• 所有的节点都在同一个广播信道上发送数据，因此需要有专门的控制方法进行协调，避免发生冲突（冲突也叫碰撞）。
  • 主要有两种控制方法进行协调，一个是使用信道复用技术，一是使用 CSMA/CD 协议。

点对点信道

• 一对一通信
• 因为不会发生碰撞，所以比较简单。使用ppp协议控制

信道复用技术

• 频分服用：

  • 频分复用的所有主机在相同的时间占用不同的频率带宽资源

• 时分复用：

  • 时分复用的所有主机在不同的时间占用相同的频率带宽资源

  

  • 使用频分复用和时分复用进行通信，在通信的过程中主机会一直占用一部分信道资源。但是由于计算机数据的突发性质，通信过程没必要一直占用信道资源而不让出给其它用户使用，因此这两种方式对信道的利用率都不高。

• 统计时分复用

  • 是对时分复用的一种改进，不固定每个用户在时分复用帧中的位置，只要有数据就集中起来组成统计时分复用帧然后发送。

  

CSMA/CD

CSMA/CD 表示载波监听多点接入 / 碰撞检测

• 多点载入：

  • 说明这是总线型网络，许多主机以多点的方式连接到总线上

• 载波监听：

  • 每个主机都必须不停的监听信道。在发送前，如果监听到信道正在使用，就必须等待

• 碰撞检测：

  • 在发送中，如果监听到信道已有其他主机正在发送数据，就表示发生了碰撞。
  • 虽然每个主机在发送数据之前都已经监听到信道为空闲，但是由于电磁破传播时延的存在，还是可能会发生碰撞

• 记端到端的传播时延为 τ，最先发送的站点最多经过 2τ 就可以知道是否发生了碰撞，称 2τ 为 争用期 。只有经过争用期之后还没有检测到碰撞，才能肯定这次发送不会发生碰撞。

  • 当发生碰撞时，站点要停止发送，等待一段时间再发送。这个时间采用 截断二进制指数退避算法 来确定。从离散的整数集合 {0, 1, .., (2k-1)} 中随机取出一个数，记作 r，然后取 r 倍的争用期作为重传等待时间。

  

MAC协议

MAC 地址是链路层地址，长度为 6 字节（48 位），用于唯一标识网络适配器（网卡）。

• 一台主机拥有多少个网络适配器就有多少个 MAC 地址。例如笔记本电脑普遍存在无线网络适配器和有线网络适配器，因此就有两个 MAC 地址。

局域网

局域网是一个典型的广播信道，主要特点是网络为一个单位所拥有，且地理范围和站点数目均有限

• 主要有以太网、令牌环网、FDDI 和 ATM 等局域网技术，目前以太网占领着有线局域网市场。
• 按照网路拓扑结构对局域网进行划分：

以太网

是一种星型拓扑结构局域网

• 目前以太网使用交换机替代了集线器，交换机是一种链路层设备，它不会发生碰撞，能根据 MAC 地址进行存储转发

• 以太网帧格式：

  • 类型：标记上层使用的协议
  • 数据：长度在46-1500之间，如果太小则需填充
  • FCS：帧检查序列，使用的是CRC

  

交换机

交换机具有自学习能力。学习的是交换表内容，交换表中存储着MAC地址到接口的映射

• 正是由于这种自学习能力，因此交换机是一种即插即用设备，不需要网络管理员手动配置交换表内容

  

虚拟局域网

虚拟局域网可以建立与物理位置无关的逻辑组，只有在同一个虚拟局域网中的成员才会收到链路层广播信息

数据库

ACID

• A：atomicity 原子性

  • 事务被视为不可分割的最小单元，事务的所有操作要么全部提交成功，要么全部失败回滚。
  • 回滚可以用回滚日志（Undo Log）来实现，回滚日志记录着事务所执行的修改操作，在回滚时反向执行这些修改操作即可。

• C:Consistency 一致性

  • 数据库在事物执行前后都保持一致性状态。在一致性状态下，所有事物对同一个数据的读取结果都是相同的

• I：isolation 隔离性

  • 一个事物所做的修改在最终提交以前对其他事物是不可见的

• D：Durability 持久性

  • 一旦事物提交，则其所做的修改将会永远保存到数据库中。即使系统发生崩溃，事务执行的结果也不能丢失
  • 系统发生崩溃可以用重做日志（Redo Log）进行恢复，从而实现持久性。与回滚日志记录数据的逻辑修改不同，重做日志记录的是数据页的物理修改。

• 只有满足一致性，事务的执行结果才是正确的。

• 在无并发的情况下，事务串行执行，隔离性一定能够满足。此时只要能满足原子性，就一定能满足一致性。

• 在并发的情况下，多个事务并行执行，事务不仅要满足原子性，还需要满足隔离性，才能满足一致性。

• 事务满足持久化是为了能应对系统崩溃的情况。

• auto commit

  • MySQL 默认采用自动提交模式。也就是说，如果不显式使用START TRANSACTION语句来开始一个事务，那么每个查询操作都会被当做一个事务并自动提交。

并发一致性问题

在并发环境下，事务的隔离性很难保证，因此会出现很多并发一致性问题。

丢失修改

• 丢失修改指一个事务的更新操作被另外一个事务的更新操作替换。一般在现实生活中常会遇到，例如：T1 和 T2 两个事务都对一个数据进行修改，T1 先修改并提交生效，T2 随后修改，T2 的修改覆盖了 T1 的修改。

  

读脏数据

• 读脏数据指在不同的事务下，当前事务可以读到另外事务未提交的数据。例如：T1 修改一个数据但未提交，T2 随后读取这个数据。如果 T1 撤销了这次修改，那么 T2 读取的数据是脏数据。

  

不可重复读

• 不可重复读指在一个事务内多次读取同一数据集合。在这一事务还未结束前，另一事务也访问了该同一数据集合并做了修改，由于第二个事务的修改，第一次事务的两次读取的数据可能不一致。例如：T2 读取一个数据，T1 对该数据做了修改。如果 T2 再次读取这个数据，此时读取的结果和第一次读取的结果不同。

  

幻读

• 幻读本质上也属于不可重复读的情况，T1 读取某个范围的数据，T2 在这个范围内插入新的数据，T1 再次读取这个范围的数据，此时读取的结果和和第一次读取的结果不同。

  

• 产生并发不一致性问题的主要原因是破坏了事务的隔离性，解决方法是通过并发控制来保证隔离性。并发控制可以通过封锁来实现，但是封锁操作需要用户自己控制，相当复杂。数据库管理系统提供了事务的隔离级别，让用户以一种更轻松的方式处理并发一致性问题。

封锁

封锁粒度

• MySQL中提供了两种封锁粒度：行级锁和表级锁
  • 应该尽量只锁定需要修改的那部分数据，而不是所有的资源。锁定的数据量越少，发生锁争用的可能就越小，系统的并发程度就越高。
  • 但是加锁需要消耗资源，锁的各种操作（包括获取锁、释放锁、以及检查锁状态）都会增加系统开销。因此封锁粒度越小，系统开销就越大。
  • 在选择封锁粒度时，需要在锁开销和并发程度之间做一个权衡。

封锁类型

• 1.读写锁

  • 互斥锁(Exclusive)，简写为X锁，又称写锁
  • 共享锁(Shared)，简写为S锁，又称读锁

• 有以下两个规定：

  • 一个事物对数据对象A加了X锁，就可以对A进行读取和更新。加锁期间其他事物不能对数据对象A加任何锁
  • 一个事物对数据对象A加了S锁，就可以对A进行读取操作，但是不能进行更新操作。加锁期间其他事物能对数据对象A加是锁，但是不能加X锁。

• 锁的兼容关系：

  

意向锁

使用意向锁（Intention Locks）可以更容易地支持多粒度封锁。

• 在存在行级锁和表级锁的情况下，事务 T 想要对表 A 加 X 锁，就需要先检测是否有其它事务对表 A 或者表 A 中的任意一行加了锁，那么就需要对表 A 的每一行都检测一次，这是非常耗时的。

  • 意向锁在原来的 X/S 锁之上引入了 IX/IS，IX/IS 都是表锁，用来表示一个事务想要在表中的某个数据行上加 X 锁或 S 锁。有以下两个规定:
    • 一个事务在获得某个数据行对象的 S 锁之前，必须先获得表的 IS 锁或者更强的锁；
    • 一个事务在获得某个数据行对象的 X 锁之前，必须先获得表的 IX 锁。
  • 通过引入意向锁，事务 T 想要对表 A 加 X 锁，只需要先检测是否有其它事务对表 A 加了 X/IX/S/IS 锁，如果加了就表示有其它事务正在使用这个表或者表中某一行的锁，因此事务 T 加 X 锁失败

• 兼容关系

  • 任意 IS/IX 锁之间都是兼容的，因为它们只表示想要对表加锁，而不是真正加锁；
  • 这里兼容关系针对的是表级锁，而表级的 IX 锁和行级的 X 锁兼容，两个事务可以对两个数据行加 X 锁。（事务 T1 想要对数据行 R1 加 X 锁，事务 T2 想要对同一个表的数据行 R2 加 X 锁，两个事务都需要对该表加 IX 锁，但是 IX 锁是兼容的，并且 IX 锁与行级的 X 锁也是兼容的，因此两个事务都能加锁成功，对同一个表中的两个数据行做修改。）

封锁协议

一级锁定协议

事物T要修改数据A时必须加X锁，直到T结束时才释放锁

• 可以解决丢失修改问题，因为不能同时有两个事物对同一个数据进行修改，所以修改不会被覆盖。

  

二级封锁协议

在一级的基础上，要求读取数据 A 时必须加 S 锁，读取完马上释放 S 锁

• 可以解决脏读问题。因为如果一个事物在对数据A进行修改，根据一级锁定协议，会加X锁，那么就不能再加S锁了，也就不会读入数据。

  

三级封锁协议

在二级的基础上，要求读取数据A时必须加S锁，直到事物结束了才释放S锁

• 可以解决不可重复读的问题。当事物读取数据A时加S锁，那么其他事物就不能对A加X锁了，也就不能对数据进行更新

  

两段锁协议

加锁和解锁分为两个阶段进行

• 可串行化调度是指通过并发控制，使得并发执行的事物结果与某个串行执行的事物结果相同，串行执行的事物互不干扰，并不会发生一致性问题
• 事务遵循两段锁协议是保证可串行化调度的充分条件。例如以下操作满足两段锁协议，它是可串行化调度
  • lock-x(A)…lock-s(B)…lock-s(C)…unlock(A)…unlock(C)…unlock(B)
• 但不是必要条件
  • lock-x(A)…unlock(A)…lock-s(B)…unlock(B)…lock-s(C)…unlock(C)

隔离级别

读未提交

事务中的修改，即使没有提交，对其它事务也是可见的。

读已提交

一个事务只能读取已经提交的事务所做的修改。换句话说，一个事务所做的修改在提交之前对其它事务是不可见的。

可重复度

保证在同一个事务中多次读取同一数据的结果是一样的。

可串行化

强制事务串行执行，这样多个事务互不干扰，不会出现并发一致性问题

• 该隔离级别需要加锁实现，因为要使用加锁机制保证同一时间只有一个事务执行，也就是保证事务串行执行。

多版本并发控制MVCC

MVCC是MySQL的InnoDB存储引擎实现隔离级别的一种具体方式，用于实现提交读和可重复读这两种隔离级别。

未提交读隔离级别总是读取最新的数据行，要求很低，无需使用 MVCC。可串行化隔离级别需要对所有读取的行都加锁，单纯使用 MVCC 无法实现。

• 基本思想

  • 在 MVCC 中事务的修改操作（DELETE、INSERT、UPDATE）会为数据行新增一个版本快照
  • 写操作更新快照，而读操作读旧版本快照

• Undo日志

  • MVCC 的多版本指的是多个版本的快照，快照存储在 Undo 日志中，该日志通过回滚指针 ROLL_PTR 把一个数据行的所有快照连接起来。

函数依赖

记 A->B 表示 A 函数决定 B，也可以说 B 函数依赖于 A。

如果 {A1，A2，… ，An} 是关系的一个或多个属性的集合，该集合函数决定了关系的其它所有属性并且是最小的，那么该集合就称为键码。

对于 A->B，如果能找到 A 的真子集 A’，使得 A’-> B，那么 A->B 就是部分函数依赖，否则就是完全函数依赖。

对于 A->B，B->C，则 A->C 是一个传递函数依赖。

范式

高级别范式的依赖于低级别的范式，1NF 是最低级别的范式。

1NF

属性不可分。

2NF

每个非主属性完全函数依赖于键码。

设计模式

单例模式

保证一个类仅有一个实例，并提供一个访问它的全局访问点。该实例被所有程序模块共享

• 单例模式有以下特点

  • 该类不能被复制
  • 该类不能被公开创造
  • 构造函数、拷贝构造函数和赋值函数必须是私有的

• 单例模式实现方式

单例模式通常分为懒汉式单例和饿汉式单例

• 懒汉式设计模式实现

  第一次访问时才会创建实例

  懒汉模式线程不安全

  • 1.静态指针 + 用到时初始化
  • 2.局部静态变量

#include <iostream>
using namespace std;

class Singleton {
private:
    // 静态成员变量，用于保存唯一实例
    static Singleton* instance;
    int data;  // 单例对象的数据

    // 构造函数私有，放置外部创建对象
    Singleton() : data(0) {
    }

public:
    // 静态成员函数,用于获取单例实例
    static Singleton* getInstance() {
        if (instance == nullptr) {
            instance = new Singleton();  // 第一次访问时创建
        }
        return instance;
    }

    void setData(int val) {
        data = val;
    }

    int getData() const {
        return data;
    }
};

// 静态成员变量需要在类外初始化
Singleton* Singleton::instance = nullptr;

int main() {
    Singleton* s1 = Singleton::getInstance();
    Singleton* s2 = Singleton::getInstance();
    s1->setData(525);
    cout << "s1:" << s1->getData() << endl;
    cout << "s2:" << s1->getData() << endl;
    return 0;
}

• 线程安全问题解决：

  • 1.上锁使用lock()函数

  • 2.synchronized

  • 3.局部静态变量

    

---

• 饿汉式设计模式

  在应用程序启动时立即创建实例，不管是否需要使用。这样可以确保在任何时候都有一个实例可用

  若存在多个单例对象且这几个单例对象互相依赖，可能出现程序崩溃的危险

  ​ 原因：静态成员的初始化顺序和析构顺序是未定义的行为

  • main函数执行之前全局作用域的类成员静态变量已经初始化，故没有多线程问题

#include <iostream>
using namespace std;

class Singleton {
private:
    static Singleton* instance;
    int data;
    Singleton() : data(0) {
    }

public:
    void setData(int val){
        data = val;
    }

    int getData(){
        return data;
    }

    static Singleton* getInstance(){
        return instance;
    }
};

Singleton* Singleton::instance = new Singleton();

int main(){
    Singleton* obj1 = Singleton::getInstance();
    Singleton* obj2 = Singleton::getInstance();

    obj1->setData(42);
    std::cout << "Data from obj1: " << obj1->getData() << std::endl; // 输出 42
    std::cout << "Data from obj2: " << obj2->getData() << std::endl; // 输出 42

    return 0;
}

• 懒汉和饿汉实现只有细微差别(多久初始化)

---

工厂设计模式

定义一个创建对象的接口，让子类决定实例化哪个类，而对象的创建统一交由工厂区生产

• 工厂设计模式的分类

  • 简单工厂模式
  • 工厂方法模式
  • 抽象工厂模式

  ---

• 简单工厂模式

  • 主要特点是需要在工厂类中做判断，从而创造相应的产品。当增加新的产品时，就需要修改工厂类

  

  • 优点：
    • 使用者不需要知道如何创建对象，降低系统耦合性
  • 缺点
    • 违反了开放封闭原则。对扩展开放，对修改封闭

• 简单工厂的UML图

  

---

• 工厂方法模式

  • 定义一个用于创建对象的接口，让子类决定实例化哪一个类。Factory Method使一个类的实例化延迟到其子类。

  

  • 优点
    • 扩展性好，符合了开闭原则。新增一种产品时，只需要增加对应的产品类和对应的工厂子类即可
  • 缺点
    • 每增加一种产品，就需要增加一个对象的工厂。如果这家公司发展迅速，推出了很多新的处理器核，那么就要开设相应的新工厂。在C++实现中，就是要定义一个个的工厂类。显然，相比简单工厂模式，工厂方法模式需要更多的类定义。

• 工程方法的UML图

  

---

• 抽象工厂模式

  • 它的定义为提供一个创建一系列相关或相互依赖对象的接口，而无需指定它们具体的类。

  

• 抽象工厂模式的UML图

  

---

装饰器模式

指在不改变现有对象结构的情况下，动态的给对象增加一些职责(一些额外的功能)的模式

• 优点：
  • 装饰器是继承的有力补充，比继承灵活，在不改变原有对象的情况下，动态的给一个对象扩展功能，即插即用
  • 通过使用不用装饰类及这些装饰类的排列组合，可以实现不同效果
  • 装饰器模式完全遵守开闭原则
• 缺点
  • 装饰模式会增加许多子类，过度使用会使程序变得负责
• 装饰模式的结构与实现
  • 通常情况下，扩展一个类的功能会使用继承方式来实现。但继承具有静态特征，耦合度高，并且随着扩展功能的增多，子类会很膨胀。如果使用组合关系来创建一个包装对象（即装饰对象）来包裹真实对象，并在保持真实对象的类结构不变的前提下，为其提供额外的功能，这就是装饰模式的目标。
• 装饰模式主要包含以下角色：
  • 抽象构建(component)角色：
    • 定义一个抽象接口以规范准备接收附加责任的对象
  • 具体构建(concrete component)角色：
    • 实现抽象构建，通过装饰角色为其添加一些职责
  • 抽象装饰（Decorator）角色：
    • 继承抽象构件，并包含具体构件的实例，可以通过其子类扩展具体构件的功能。
  • 具体装饰（ConcreteDecorator）角色：
    • 实现抽象装饰的相关方法，并给具体构件对象添加附加的责任。

下面是八股文部分

---

八股文(总结)

TCP和UDP的区别

• TCP:

TCP是面向连接(三次握手，四次挥手)的协议，只能进行点对点的通信，面向字节流

​ 面向字节流是以字节为单位发送数据，并且一个数据包可以以字节大小来拆分成多个数据包，以方便发送。

TCP首部有20字节

TCP有流量控制和拥塞控制，确保数据的可靠性

• UCP

UDP无连接，面向数据报

支持一对一、一对多、多对多

每次都需要发送固定长度的数据包

UDP首部有8个字节

---

智能指针和指针的区别

• 智能指针 shared_ptr，unique_ptr，weak_ptr

new从堆区分配内存，不需要时需要使用delete释放。智能指针可以自动完成这个过程。c++11新增三种智能指针：unique_ptr，shared_ptr，weak_ptr

• std::shared_ptr：共享指针，用于多个指针共享同一块内存资源。它使用引用计数来跟踪有多少个shared_ptr指向同一块内存。只有当所有的shared_ptr都销毁或者赋值为nullptr时，才会释放内存
• std::unique_ptr：独占指针，用于表示独占所有权的指针。每个unique_ptr拥有对内存资源的唯一所有权，当unique_ptr被销毁或者转移所有权给另一个unique_ptr时，内存资源会被释放
• 用于管理动态分配的内存资源，只可以从一个 shared_ptr 或另一个 weak_ptr 对象构造, 它的构造和析构不会引起引用记数的增加或减少。它用于解决 std::shared_ptr可能引发的**循环引用(死锁)**问题。std::weak_ptr 允许你观测到一个由 std::shared_ptr 管理的对象，但不会影响到其引用计数。

#include <iostream>
#include <memory>

class B; // 前置声明

class A {
public:
    std::shared_ptr<B> b_ptr; // A持有B的shared_ptr
};

class B {
public:
    std::weak_ptr<A> a_weak_ptr; // B持有A的weak_ptr
};

int main() {
    std::shared_ptr<A> a = std::make_shared<A>();
    std::shared_ptr<B> b = std::make_shared<B>();

    a->b_ptr = b; // A持有B的shared_ptr
    b->a_weak_ptr = a; // B持有A的weak_ptr

    // 此时a和b相互引用，但不会导致循环引用的问题，因为B持有的是weak_ptr

    // 在需要访问A或B时，需要先将weak_ptr转换为shared_ptr，并检查是否有效
    if (std::shared_ptr<A> a_shared = b->a_weak_ptr.lock()) {
        // 可以安全地访问A
    }

    return 0;
}

• 弄懂weak_ptr对shared_ptr的影响
• unique_ptr实现原理
  • 实现原理：将拷贝构造函数和赋值拷贝构造函数申明为private或delete。不允许拷贝构造函数和赋值操作符，但是支持移动构造函数，通过std:move把一个对象指针变成右值之后可以移动给另一个unique_ptr
• shared_ptr实现原理
  • 实现原理：有一个引用计数的指针类型变量，专门用于引用计数，使用拷贝构造函数和赋值拷贝构造函数时，引用计数加1，当引用计数为0时，释放资源
• weak_ptr 能不能知道对象计数为 0，为什么？

不能，weak_ptr是一种不控制对象生命周期的智能指针，它指向一个shared_ptr管理的对象，对对象进行管理的是shared_ptr。weak_ptr只是为了配合shared_ptr工作，只可以从一个shared_ptr或者另一个weak_ptr构造。

它不维护对象的引用计数，只跟踪对象是否还存在

• weak_ptr 如何解决 shared_ptr 的循环引用问题？

• 在需要相互引用的对象中，使用weak_ptr来保存另一个对象的弱引用。
• 必要时，将shared_ptr赋值给weak_ptr
• 当需要访问互相引用的对象时，首先使用weak_ptr获取shared_ptr，然后**检查是否成功(是否被释放)**，从而避免非法访问
  • shared_ptr = weak_ptr.lock()

---

为什么使用智能指针

1.new的内存需要使用delete释放。手动释放不能解决所有问题，比如在某个全局函数中new。此时，智能指针就派上了用场。使用智能指针可以很大程度上避免这个问题，因为智能指针就是一个类，当超出了类的作用域时，类会自动调用析构函数，析构函数会自动释放资源。所以，智能指针的作用原理就是在函数结束时自动释放内存空间，避免了手动释放内存空间。

智能指针

具体使用

• make_shared() 用来创建共享指针
• 构造函数：
  • std::shared_ptr< int> (new int(100));
• 对于一个未初始化的智能指针，可以使用reset函数初始化
  • std::shared_ptr< int> p1;
    p1.reset(new int(1));
• 注意：
  • reset()函数如果为空的话，将智能指针对象置空，若该智能指针有指向的对象的话，引用计数-1
  • 不能将普通的指针直接赋值给智能指针：
    • std::shard_ptr< int> p = new int(1); 这是错误的
• 避免循环引用，循环引用会导致内存泄漏，计数无法清零。使用weak_ptr解决该问题
• 多线程安全，因为多线程操作的不是同一个shared_ptr对象

• weak_ptr大概工作方式
  • 两个shared_ptr相互引用，那么这两个指针的引用计数永远不可能下降为0
  • weak_ptr和shared_ptr之间可以相互转化，shared_ptr可以直接赋值给它，它可以通过调用lock函数来获得shared_ptr

• c++11引入了3个智能指针

  • shared_ptr 共享资源所有权的指针
  • unique_ptr 独占资源所有权的指针，auto_ptr被弃置
  • weak_ptr 共享资源的观察者，需要和shared_ptr一起使用，不影响资源的生命周期

• std::unique_ptr

  • 当我们独占资源的所有权的时候，可以使用 std::unique_ptr 对资源进行管理——离开 unique_ptr 对象的作用域时，会自动释放资源。

  • unique_ptr自动管理内存，离开其作用域之后会自动释放资源

  • 独占资源，是move-only的

    

    ​ 只能使用移动赋值

• std::shared_ptr

  • shared_ptr其实就是对资源做引用计数，当引用计数为0时，自动释放资源

    

  • shared_ptr 需要维护的信息有两部分：

    • 指向共享资源的指针

    • 引用计数等共享资源的控制信息——实现上是维护一个指向控制信息的指针。

      

• std::weak_ptr

  • std::weak_ptr 要与 std::shared_ptr 一起使用。 一个 std::weak_ptr 对象看做是 std::shared_ptr 对象管理的资源的观察者，它不影响共享资源的生命周期

    • 如果需要使用 weak_ptr 正在观察的资源，可以将 weak_ptr 提升为 shared_ptr。
    • 当 shared_ptr 管理的资源被释放时，weak_ptr 会自动变成 nullptr

  • 当 shared_ptr 析构并释放共享资源的时候，只要 weak_ptr 对象还存在，控制块就会保留，weak_ptr 可以通过控制块观察到对象是否存活

    

---

move、右值/右值引用

右值没有名称，只能借助引用的方式使用，当想要修改右值时，常量左值是做不到的

所以c++11引入&& ，称为右值引用

• 一个对象被用作右值时，使用的是它的内容(值)，被当作左值时，使用的是它的地址

• 注意：

  • 和声明左值引用一样，右值引用也必须立即进行初始化操作，且只能使用右值进行初始化

    • int num = 10;
      //int && a = num;  //右值引用不能初始化为左值
      int && a = 10;
      a = 100; // 右值引用可以对右值进行修改
        * 和常量左值引用不同的是，**右值引用还可以对右值进行修改**
        
        *  **右值**引用在企业开发人员在**代码优化方面**会经常用到
        
      * **std::move**
      
        > * move的唯一功能就是**将左值强制转化为右值**，进而通过右值引用使用该值
        > * 将资源从一个对象转移到另一个对象，**没有内存的拷贝**。**避免不必要的拷贝操作**
      
      
      
      ---
      
      
      
      ### push_back和emplace_back
      
      > 两者实现的功能一样，都是向容器的末尾添加一个对象
      >
      > * 使用emplace_back() 函数可以**减少一次拷贝构造或移动构造**的过程，提升容器插入数据的效率。
      > * emplace_back()是c++11的新特性
      
      * 区别：
        * push_back()向容器尾部添加元素时，**首先创建这个元素对象**，然后再**将这个元素拷贝或者移动到容器**中(拷贝构造会事先销毁先前创建的这个元素)；
        * emplace_back()在实现时，**则是直接在容器尾部创建这个元素**，**省去了拷贝或者移动的过程**
      * ![image-20231106131731227](https://img-blog.csdnimg.cn/2248e20233604fba90e4e656c8ca8cf9.png)
        * push_back()**优先调用移动构造,没有移动构造才会调用拷贝构造**
      
      
      
      ---
      
      ### 指针和引用
      
      * 指针：
      
        > 指针是一个**变量**，这个变量存储的是一个地址，指向内存的一个存储单元
      
      * 引用
      
        > 引用跟原来的变量实质上是同一个东西，是**原变量的一个别名**，不能脱离被引用的对象而独立存在
        >
        > 引用的本质是一个**指针常量** T* const
        >
        > ​	一旦指向某一个单元就不能再指向别处
      
      ### sizeof和strlen的区别
      
      * sizeof
      
      > sizeof() 是一个运算符，在**编译时就已经计算好了**，参数可以是指针、数组、类型、对象、函数等
      >
      > * 功能是：获得保证能容纳实现所建立的**最大对象的字节大小**
      > * sizeof返回的值表示含义如下：
      >   * 数组——**编译时分配的数组空间大小**
      >   * 指针——存储该**指针所用的空间大小**（在32位机器上是4，64位机器上是8）
      >   * 类型——该**类型所占的空间大小**
      >   * 对象——**对象的实际占用空间大小**
      >   * 函数——函数的**返回类型**所占的空间大小。函数的返回类型不能是void
      
      * strlen
        * 返回字符串的具体长度及**字符个数**
        * 我们知道strlen(…)是函数，要在**运行时** 才能计算。参数必须是字符型指针（char*）。
      
      > 当**数组名作为参数传入**时，实际上**数组就退化成指针**了。
      >
      > 功能：返回**字符串的长度**
      >
      > 该字符串可能是自己定义的，也可能是内存中随机的，该函数实际完成的功能是从代表该字符串的第一个地址开始遍历，**直到遇到结束符’\0’停止**。返回的长度大小**不包括‘\0’**
      
      * 二者区别
        * sizeof() 是运算符，strlen()是库函数
        * sizeof() 在编译时计算好了，strlen()在运行时计算
        * sizeof() 计算出来的是对象使用的最大字节数，**strlen()的参数必须是字符型指针**(传入数组时自动退化为指针)
        * sizeof()的参数类型多样化（数组，指针，对象，函数都可以），strlen()的参数必须是字符型指针（传入数组时自动退化为指针）
        * **strlen 计算的是字符串的实际长度，遇到\0即停止；sizeof 计算整个字符串所占内存字节数的大小，当然\0也要+1计算；**
      
      ![image-20231103155046645](https://img-blog.csdnimg.cn/2ae48c22f6364e16897d11af16daf363.png)、
      
      
      
      ### define和inline的区别
      
      * define 宏
      
      > * 缺点：
      >   * **宏没有类型检查**，不安全
      >   * 宏是在**预处理时期**进行的**简单文本替换**，并不是简单的参数传递(很难处理一些特定的情况，如：Add(z++))
      >   * 使得代码变长
      >   * 宏不能进行调试
      >   * 当预处理搜索#define定义的符号时，字符窜常量并不被搜索
      > * 优点：
      >   * 加快了代码的运行效率
      >   * 让代码变得更加的通用
      
      * 内联函数inline
        * 为了解决频**繁调用函数**导致消耗大量栈空间的问题
        * 类中的**定义了函数体的成员函数默认是内联函数**
        * 内敛函数**不允许有循环语句和开关语句和递归调用等**，且函数体不宜过程，否则作为普通函数处理。即inline只是一个建议，是否真正内敛看编译器自己判断
        * 内联函数的**定义必须出现在第一次调用内联函数之前**，,如果在前面声明为普通函数，而在调用代码后面才定义为一个inline函数，程序可以通过编译，但该函数没有实现inline
        * **如果一个inline函数会在多个源文件中被用到，那么必须把它定义在头文件中**（注意是定义）
          * 解析：如果内联函数fun()定义在某个编译单元A中，那么其他编译单元中调用fun()的地方时，可以编译通过（此时并没有展开，结合第三条，此时虽然头文件声明了该inline函数，但此时调用时，还没定义，所以作为普通函数处理）。当链接时将无法解析该符号，出现链接错误。 因为inline函数是作为内部连接存在的，只能够被本模块访问
        * 关键字**inline 必须与函数定义体放在一起**才能使函数成为内联，仅将inline 放在函数声明前面不起任何作用。
      
      > * 缺点：
      >   * 代码变长，**占用更多内存**
      >   * 若执行时间长，效率增效就会不理想
      > * 优点：
      >   * **有类型检测**，更加的安全
      >   * 内联函数是在程序**编译时**展开，而且进行的是参数传递
      >   * 编译器可以检测定义的内联函数是否满足要求，如果**不满足就会当作普通函数调用**（内联函数不能递归，内联函数不能太大）
      
      * 相同点
      
        > 两者都加快了程序的运行效率，使代码变得更加通用
      
      * 不同点
      
        > * 内敛函数的**调用是传参**，宏定义只是**简单的文本替换**
        > * 两者都是在编译时展开，当把一个函数的声明和定义指定为inline时，编译器在编译到调用方时，会直接把inline函数的调用替换为函数体，编译器还会帮我们做合法性检测
        > * 内联函数有**类型检测更加的安全，**宏定义没有类型检测
        > * 内联函数**可调试**，宏定义不行
        > * 内联函数**可以访问类的成员变量**，宏不行
        > * 类中的**成员函数默认是内联函数**
      
      
      
      ### 初始化列表
      
      * 对于内置参数类型(int,float等)，初始化列表和构造函数体内初始化效率差不多，但是对于**类类型对象，最好使用初始化列表**。初始化列表**少调用一次默认构造函数**，对于数据密集型的类来时，效率非常高
      
      * 除了性能问题：有如下情况必须调用初始化列表
      
        * **常量成员**，因为**常量只能初始化不能赋值**，所以必须放在初始化列表里面
        * **引用类型**，引用必须在定义的时候初始化，并且**不能重新赋值**，所以也要写在初始化列表里面
        * **没有默认构造函数的类类型**，因为使用初始化列表可以不必调用默认构造函数来初始化，而是直接调用拷贝构造函数初始化
      
        ![image-20231104154308667](https://img-blog.csdnimg.cn/bfe96168f3c44666a76e1e58a4c74a91.png)
      
      * 成员变量的顺序
      
        * **成员是按照他们在类中出现的顺序进行初始化的**，而不是按照他们在初始化列表出现的顺序初始化的
      
          ![image-20231104154244904](https://img-blog.csdnimg.cn/48fa68e6e70d42a8a78f4c4e196970d0.png)
      
      
      
      
      
      ---
      
      
      
      ### epoll
      
      * epoll_create：创建一个epoll实例，返回文件描述符
      * epoll_ctl：将监听的文件描述符添加到epoll实例中，
      * epoll_wait：等到epoll事件从epoll实例中发生，并返回事件及文件描述符
      
      * epoll关键核心**数据结构**：
      
        ```cpp
        typedef union epoll_data
        {
          void *ptr;
          int fd;
          uint32_t u32;
          uint64_t u64;
        } epoll_data_t;
        
        // epoll_event 中有epoll_data
        struct epoll_event
        {
          uint32_t events;  /* Epoll events */
          epoll_data_t data;    /* User data variable */
        };
      

• 水平触发LT level-triggered

  • socket接收缓冲区不为空，有数据可读时，读事件一直触发
  • socket发送缓冲区不为满，可以继续写入数据时，写事件一直触发
  • 水平触发会一直触发

  1.就绪事件包含EPOLLIN的条件

  • 刚建立连接
  • 有数据可读
  • 断开连接

  2.就绪事件包含EPOLLOUT的条件

  • 内核发送缓冲区未满，可以写

• 边沿触发ET edge-triggered

  • socket接收缓冲区状态变化时触发读事件，即空的接收缓冲区刚接到数据时出发读事件
  • socket发送缓冲区状态变化时触发读事件，即满的接收缓冲区刚有空间时触发写事件
  • 边沿触发仅触发一次

  1.就绪事件包含EPOLLIN的条件

  • 刚建立连接
  • 内核接收到新数据
  • 断开连接

  2.就绪事件包含EPOLLOUT的条件

  • 每注册一次EPOLLOUT，下一次epoll_wait返回就绪事件的EPOLLOUT
  • 内核发送缓冲区从不可写变成可写
  • 同时注册了EPOLLIN和EPOLLOUT，如果接收到新数据时可写则就绪事件既包含EPOLLIN也包含EPOLLOUT

• 也就是说，对于ET模式的非阻塞socket，触发可读事件之后，需要一次性把socket上的数据读取干净才行
  • 如何一次性读取：while(1)循环直到recv出现错误码EWOULDBLOCK（EAGAIN）
  • (3 封私信 / 80 条消息) epoll ET模式，可写事件触发的场景？ - 知乎 (zhihu.com)
• 

• 宏事件：当套接字上有事件发生时，会触发对应的时间

  • EPOLLIN ： 表示对应的文件描述符可以读（包括对端SOCKET正常关闭）
  • EPOLLOUT： 表示对应的文件描述符可以写；
  • EPOLLPRI： 表示对应的文件描述符有紧急的数据可读（这里应该表示有带外数据到来）
  • EPOLLERR： 表示对应的文件描述符发生错误
  • EPOLLHUP： 表示对应的文件描述符被挂断
  • EPOLLET： 将 EPOLL设为边缘触发(Edge Triggered)模式（默认为水平触发），这是相对于水平触发(Level Triggered)来说的
  • EPOLLONESHOT： 只监听一次事件，当监听完这次事件之后，如果还需要继续监听这个socket的话，需要再次把这个socket加入到EPOLL队列里

• epoll高效原理

• epoll使用红黑树rb_tree去监听和维护所有文件描述符
  • 红黑树用于存储epoll_ctl传来的socket
• epoll使用双向链表存储准备就绪的事件的文件描述符
  • 当epoll_wait调用时，内核检查这个list双向链表里有没有数据。有就返回，没有就sleep，等到timeout之后即使链表中没有数据也返回。所以，epoll非常高效

• epoll的功能

  • 更改epoll检测fd集合

    • fd集合用红黑树来存储

      • why： 为什么用红黑树不用hash或者b+树

      hash的效率不比红黑树差，但是hash需要提前分配空间，当容量不够时需要开辟内存。不方便

      b+使用于磁盘索引，不适合内存索引

  • 检测部分fd有数据可读

    如何检测？epoll属于文件系统

    • 协议栈中有个TCB，当状态改变后，TCB可以找到对应的节点，将节点加入到就绪队列中(双向链表)

epoll如何做到线程安全的，红黑树如何做到线程安全的？

• 1.红黑树 如何加锁

  • 1.插入和删除，整棵树加锁
    • mutex
    • 安全。多线程下会影响性能，但是影响不是很大
  • 2.分之加锁，给正在操作的子树加锁

• 2.就绪队列 如何加锁

  • 选择自旋锁 spinlock
  • 耗时短，选择自旋锁；耗时长，选择mutex。时间长短是与线程切换比较

• 3.epoll

  • 1.rbtree
  • 2.ready queue

• mutex、乐观锁CAS、自旋锁spinlock

  

  • CAS在什么时候使用？
    • CAS是轻量级、好用的。CAS是一条指令
    • 开销小

多态

多态包括编译时多态和运行时多态

• 编译时多态体现在函数重载和模版上
• 运行时多态体现在虚函数上

• 构成条件
  • 必须通过基类或的指针调用虚函数
  • 被调用的函数是虚函数，必须完成对基类虚函数的重写
• 虚函数表–对类而言
  • 当该类有虚函数时，就会生成虚函数表。（一个存放虚函数指针的函数指针数组），一个虚函数表对应一个虚指针
  • 当派生类对虚函数进行重写后，派生类的虚函数表中函数指针的值就发生了变化
• 虚指针—类的对象
  • 同一个类，创造的不同对象，其虚指针的值是一样的，全都是指向该类的虚函数表（函数指针数组的首地址？应该是了）
  • 不同的类创建的对象的虚指针的值一定是不一样的
• 构造函数为什么不能是虚函数？
  • 因为创建一个对象时需要确定对象的类型，而虚函数是在运行时确定其类型的，而在构造一个对象时，犹豫对象还未创建成功，编译器无法知道对象的实际类型。

---

c++内存分区

• 分为5个区

• 栈

  • 存放函数的局部变量、函数参数、返回地址等，由编译器自动分配和释放

• 堆

  • 动态申请的内存空间，就是由 malloc 分配的内存块，由程序员控制它的分配和释放，如果程序执行结束还没有释放，操作系统会自动回收。

• 全局/静态(.bss 段和 .data 段)

  • 存放全局变量和静态变量，程序运行结束操作系统自动释放，在 C 语言中，未初始化的放在 .bss 段中，初始化的放在 .data 段中，C++ 中不再区分了。

• 常量存储区

  • 存放的是常量，不允许修改，程序运行结束自动释放。

• 代码区

  • 存放代码，不允许修改，但可以执行。编译后的二进制文件存放在这里

• 堆和栈的区别：
  • 栈由存储系统自动分配释放，存放函数的参数值、局部变量等。栈的效率很高；堆由程序员分配释放，效率比栈低
  • 栈空间不大，一般2MB，超过之后会报错OverFlow。堆空间很大，3GB
  • 栈空间是连续，FILO；堆空间是随机分配的，可能产生内存碎片

数据库存储引擎

• 默认innodb

• 我模仿的是myisam

• 两者区别

  • innodb支持事物，mysam不支持。
    • 在一些增删改操作中如果出错，myisam不可以回滚
  • myisam适合查询和插入为主的应用
  • innodb适合频繁修改以及设计到安全性较高的应用
  • InnoDB支持外键，MyISAM不支持
  • 删除表时，innodb不会重新建表而是一行行删除，效率很慢；myisam会重新建表

各种排序的时间复杂度和稳定性

• 不稳定的排序

选择排序、快速排序、希尔排序、堆排序是不稳定的

• 稳定的排序

归并排序、冒泡排序、插入排序。基数排序是稳定的

• 时间复杂度

深拷贝和浅拷贝

• 浅拷贝：
  • 将对象的指针进行简单的复制，原对象和副本指向的是相同的资源
• 深拷贝
  • 开辟一块新的空间，将原对象的资源复制到新的空间中，并返回该空间的地址
  • 深拷贝可以避免重复释放和写冲突。例如使用浅拷贝的对象进行释放后，对原对象的释放会导致内存泄漏或程序崩溃

c++构造函数

三种构造函数

• 默认构造
  • 默认构造函数是当类没有实现自己的构造函数时，编译器默认提供的一个构造函数
• 重载构造
  • 一个类可以有多个重载构造函数，但是需要参数类型或个数不相同。可以在重载构造函数中自定义类的初始化方式
• 拷贝构造
  • 对象复制的时候调用的

调用拷贝构造的三种情况

• 对象以值传递的方式传入函数参数
  • 如 void func(Dog dog){};
• 对象以值传递的方式从函数返回
  • Dog func(){ Dog d; return d;}
• 对象需要通过另外一个对象进行初始化

c++四种强制转换

• static_cast
  • 用于各种隐式转换，也就是各种基本数据类型之间的转换。int -> char、float -> int及派生类（子类）的指针转换成基类（父类）指针的转换。
  • 特点：
    • 没有运行时类型检查，有安全隐患
    • 在派生类指针转换到基类指针时，是没有任何问题的，在基类指针转换到派生类指针的时候，会有安全问题。
    • static_cast不能转换const，volatile等属性
• dynamic_cast:
  • 用于动态类型转换，就是在基类指针知道派生类指针或者派生类到基类指针的转换
  • dynamic_cast能够提供运行时类型检查，用于含有虚函数的类
    • dynamic_cast如果不能转换返回NULL
• const_cast
  • 用于去除const常量属性，使其可以修改 ，也就是说，原本定义为const的变量在定义后就不能进行修改的，但是使用const_cast操作之后，可以通过这个指针或变量进行修改; 另外还有volatile属性的转换。
• reinterpret_cast
  • 几乎什么都可以转，用在任意的指针之间的转换，引用之间的转换，指针和足够大的int型之间的转换，整数到指针的转换等。但是不够安全。

静态库和动态库的区别

• Windows下：

  • 静态库 .lib
  • 动态库 .dll

• Linux下：通常把库文件存放在/usr/lib或/lib目录下,文件名组成：前缀lib + 库名 + 后缀（3部分组成）

  • 静态库 .a 或者 .la
  • 动态库 .so

• 两者区别：

  • 1.载入时间不同
    • 静态库在编译时就拷贝到程序中，优点是节省时间，但占用内存
    • 动态库在运行时且调用库函数时才被载入，在内存中只有一个副本，且动态库可以在运行期间释放所占用的内存
  • 2.大小不同、是否可共享
    • 静态库可执行较大文件，动态库可分享
  • 3.库函数调用差异
    • 静态库：静态链接是把要调用的函数或者过程链接到可执行文件中，称为可执行文件的一部分
    • 动态库：动态链接所调用的函数并没有链接被拷贝到可执行文件中，仅在可执行文件中加入了函数的调用信息。在Linux管理下，应用程序与相应的.a文件之间建立链接，要执行函数时，根据重定位信息去执行代码。

GDB调试

---

volatile关键字

• volatile提醒编译器后面定义的变量随时都可能改变，因此编译后的程序每次存储或者读取该变量时不做优化，直接从变量内存地址中读取数据
  • 没有该关键词，编译器可能优化读取和存储，比如使用寄存器

• 应用场景：
  • 中断服务程序中修改的供其它程序检测的变量，需要加volatile
  • 多任务环境下各任务间共享的标志，应该加volatile
  • 跟嵌入式打交道

---

模版

模版方法

• 可以进行代码复用，比如swap，T可对应不同类型的参数之间的交换

类模版

• 同样可以进行代码复用。
• 考虑实现一个栈，对应不同类型的栈就需要实现不同类型的类，用模版可以减少类的个数

模版参数

• 模板可以有类型参数，也可以有常规的类型参数int，也可以有默认模板参数，例如

  • template<class T, T def_val> class Stack{...}
    #### 模版的偏特化
    
    * 期望对于某一种情况使用特例的时候，可以定义该情况的偏特化模版
    
      * 比如swap函数，如果类型是vector且内部有大量的元素，如果还是构造一个临时对象保存a，内存占用很大，性能下降。这时需要使用偏特化模版
    
    * ```cpp
      template<class V> void swap(std::vector<V>& t1, std::vector<V>& t2) {
          t1.swap(t2);
      }
    

  • template<>表示这是一个偏特化模版，不需要模版参数

进程和线程的区别

STL容器

序列式容器(4种)

• 1.vector
  • 数组
  • 查询效率高；插入删除效率低
• 2.forward_list
  • 单链表
• 3.deque
  • 双端队列
  • 支持随机访问和两端插入删除效率高
  • 中间插入删除效率低
• 4.list
  • 双向链表
  • 由deque实现，元素放在堆种
  • 不支持随机访问，插入和删除效率高

有序关联式容器(4种)

• set 、multiset
  • 优点：关键字查询高效，且元素唯一，以及能自动排序
  • 缺点：每次插入值的时候，都需要调整红黑树，效率有一定影响
• map、 multimap
  • 键字查询高效，且元素唯一，以及能自动排序。把一个值映射成另一个值，可以创建字典
  • 每次插入值的时候，都需要调整红黑树，效率有一定影响

无序关联式容器(4种)

• unordered_set、unordered_multiset
  • 因为内部实现了哈希表，因此其查找速度非常的快
  • 哈希表的建立比较耗费时间
• unordered_map、unordered_multimap
  • 因为内部实现了哈希表，因此其查找速度非常的快
  • 哈希表的建立比较耗费时间

容器适配器(3种)

• 1.stack
  • 适配器
  • Stack（堆栈） 是一个容器类的改编，为程序员提供了堆栈的全部功能，——也就是说实现了一个先进后出（FILO）的数据结构
• 2.queue
  • 适配器
  • queue具有先进先出的数据结构。持新增元素、移除元素、从最底端加入元素、取最顶端元素
• 3.priority_queue
  • 适配器
  • 优先队列是一种ADT，而堆是它的一种具体实现。在默认状态下，priority_queue实现的是大根堆，但你可以通过模板特化从而实现小根堆
  • 优先级队列priority_queue(仿函数)

• 优先级队列与堆类似，优先级队列每次出队的元素是队列中优先级最高的，而不是队首。

• 定义：

  • priority_queue<typename, container, functional>
    • typename：数据类型
    • container：容器类型，可以使用vector、queue等用数组实现的容器，不能用list，默认是vector
    • functional：比较方式，默认是大根堆。如果使用c++基本数据类型，可以直接使用自带的less或greater仿函数，默认是less(大根堆)
      • 使用自定义的数据类型的时候，可以重写比较函数，也可以进行运算符重载（less重载小于“<”运算符**，构造**大顶堆**；**greater**重载大于**“>”运算符，构造小顶堆）。

  //构造一个大顶堆，堆中小于当前节点的元素需要下沉，因此使用less
  priority_queue<int, vector<int>, less<int>> priQueMaxFirst;
   
  //构造一个小顶堆，堆中大于当前节点的元素需要下沉，因此使用greater
  priority_queue<string, vector<string>, greater<string>> priQueMinFirst;

• 仿函数

  • 长得像一个类或者结构体，内部定义一个函数。functional传入仿函数名

//重写仿函数，完成less的功能，也可以用class定义类，此时需要将运算符重载函数设为public
//结构体struct中默认是访问类型是public
struct cmp    
{
	bool operator() ( Data &a, Data &b) {
		return a.getId() < b.getId();
	}
};
 
int main(void){
    priority_queue<Data, vector<Data>, cmp > priQueMaxFirst;//该优先级队列维护一个大顶堆，因此最大的元素最先出队
    ...//一系列操作
    ...
    return 0;
}