C++和STL

C++和STL按照【游戏开发面经汇总】- 计算机基础篇中总结的顺序复习，参考之前的笔记。

位运算

按位与&：可以理解为串联，都为1才得1：1&1=1，1&0=0，0&1=0，0&0=0；
按位或|：可以理解为并联，有一个1就得1：1&1=1，1&0=1，0&1=1，0&0=0；
按位异或^：不相同得1，相同得0：1&1=0，1&0=1，0&1=1，0&0=0；
**按位取反~**：顾名思义，1得0，0得1；
**按位左移<<**：二进制数左移n位，高位溢出则舍弃，低位补0；
按位右移>>：二进制数右移n位，低位舍弃，对于无符号数高位补零，对于有符号数，原来符号位为0（正数）则也移入0，原来符号位为1（负数）移入0或1要看计算机系统，移入1的称为算数移位，移入0的称为逻辑移位。

设计模式

单例模式

懒汉式：只在第一次调用getInstance时才创建单例对象；

class MyClass{
public:
   static MyClass& getInstance(){  // 静态函数可以在在类外得到单例对象 MyClass::getInstance();
      static MyClass instance;  // 静态局部变量，存储在静态存储区，其他函数不能访问，生命周期只到程序结束
      return instance;
   }
private:
   MyClass(); // 防止类外构造
   ~MyClass(); // 防止类外析构
   MyClass(const MyClass& myclass)(); // 防止类外拷贝构造
   const MyClass& operator=(const MyClass& myclass); // 防止类外赋值构造
}

懒汉式：程序一开始就创建单例对象，需要的时候用getInstance取得

class MyClass{
public:
   static MyClass& getInstance(){
      return singleInstance;
   }
private:
   static MyClass singleInstance;
private:
   MyClass(); // 防止类外构造
   ~MyClass(); // 防止类外析构
   MyClass(const MyClass& myclass); // 防止类外拷贝构造
   const MyClass& operator=(const MyClass& myclass); // 防止类外赋值构造
}

使用时：

1
2
3

{
   MyClass::getInstance().func1(); // 通过唯一的单例对象调用其成员函数
}

工厂模式

C++深入浅出工厂模式（初识篇）

简单工厂模式

优点： 封装了创建具体产品对象的函数
缺陷： 扩展性差，每次添加新的产品要修改工厂类

/*-----------------产品------------------*/
class Shoes{ // 抽象产品类
public:
   virtual ~Shoes();
   virtual void Show()=0;
};
class NikeShoes{  // 具体产品类
public:
   virtual void Show() override{
      cout<<"NikeShoes"<<endl;
   }
};
class AdidasShoes{  // 具体产品类
public:
   virtual void Show() override{
      cout<<"AdidasShoes"<<endl;
   }
};
/*-----------------工厂------------------*/
enum SHOES_TYPE{
   NIKE,
   ADIDAS
}
class ShoesFactory{
public:
   Shoes* createShoes(SHOES_TYPE type){
      switch (type){
         case NIKE:
            return new NikeShoes();
         case ADIDAS:
            return new AdidasShoes();
         default:
            return nullptr;
            break;
      }
   }
};

工厂方法模式

将产品生产分配给多个工厂（生产线），但是每个工厂只生产一种产品；

优点： 添加新产品时添加对应的具体工厂即可
缺陷： 需要定义很多类，一个具体工厂只能生产一种产品

/*-----------------产品------------------*/
// ... 
/*-----------------工厂------------------*/
class ShoesFactory{ 
public:
   virtual Shoes* createShoes()=0;
};
class NikeProducer : public ShoesFactory{ // 生产具体产品的生产线
public:
   virtual Shoes* createShoes() override {
      return new NikeShoes();
   }
}
class AdidasProducer : public ShoesFactory{ // 生产具体产品的生产线
public:
   virtual Shoes* createShoes() override {
      return new AdidasShoes();
   }
}

抽象工厂模式

将产品生产分配给多个工厂，每个工厂可以生产多种产品；

模板工厂模式

针对工厂方法模式封装成模板工厂类，那么这样在新增产品时，是不需要新增具体的工厂类，减少了代码的编写量。

对象池

思想与 内存池 一样，提前分配一些对象等待使用；
对于那些需要频繁创建和销毁的对象，对象池的思想是，首先从对象池中寻找有没有可用的对象，如果没有，就创建对象来使用，然后当一个对象不使用的时候，不是把它删除，而是将它设置为不激活的状态并放入对象池中，等待需要使用的时候再去对象池中寻找，并把它激活。

template<typename T>
class ObjectPool {
public:
    ObjectPool(int n) {  // 构造函数时生成一些对象放入对象池
        m_objNum = n;
        for (int i = 0; i < n; i++) {
            m_objPool.push(new T(i));
        }
    }
    ~ObjectPool() {  // 析构函数要负责删除对象池中的对象
        for (int i = 0; i < m_objNum; i++) {
            delete(m_objPool.front());
            m_objPool.pop();
        }
        m_objNum = 0;
    }
    T* getObj() {  // 允许外界从对象池中获得对象
        T* obj = nullptr;
        if (m_objNum > 0) {
            m_objNum--;
            obj = m_objPool.front();
            m_objPool.pop();
        }
        else {
            obj = new T(0);
        }
        return obj;
    }
    void returnObj(T* obj) {  // 允许外界归还对象到对象池
        m_objNum++;
        m_objPool.push(obj);
    }
private:
    int m_objNum;
    queue<T*> m_objPool;
};

实现对象池时，要注意析构函数;

观察者模式

操作系统

参考小林coding-图解系统

进程管理

进程

我们编写的代码只是一个存储在硬盘的静态文件，通过编译后就会生成二进制可执行文件，当我们运行这个可执行文件后，它会被装载到内存中，接着 CPU 会执行程序中的每一条指令，那么这个运行中的程序，就被称为「进程」（Process）。

上图表现得就是并发，下图展示出并发与并行的区别：

进程状态分为：运行态，阻塞态，就绪态，挂起态等状态，完整的状态间切换过程如图：

运行态，阻塞态，就绪态的概念很好理解，这里介绍一下挂起状态，如果有很多进程处于阻塞状态，那么他们还是会在内存中，而没有被执行会占用大量的内存空间，所以我们希望当阻塞发生时，把阻塞状态的进程换出到外存（硬盘）中，等需要再次运行时再换入到物理内存；
那么，就需要一个新的状态，来描述进程没有占用实际的物理内存空间的情况，这个状态就是挂起状态。

阻塞挂起状态：发生了阻塞换出到外存，等待事件完成
就绪挂起状态：进程在外存中，只要进入内存就能立刻运行

线程

线程是比进程更小的能独立运行的基本单位。线程之间可以并发运行且共享相同的地址空间。同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。

线程的实现分为几种不同的方法，这里介绍两种：用户线程和内核线程，实现原理如下：

进程与线程的区别（⭐）

进程是运行时的程序，是系统进行资源分配的基本单位，实现了系统的并发；线程是进程的子单位，是CPU调度的基本单位，也是最小的独立运行的基本单位，实现了进程内的并发；
进程拥有独立的内存空间，同一个进程内的线程共享资源，只拥有独立的寄存器和栈；
线程的切换开销比进程小很多，因为不需要切换共享的资源，只需要切换现成的私有数据，寄存器等不共享数据；

进程调度算法

先来先服务：非抢占式；
最短作业优先：非抢占式，会导致长作业饥饿；
高响应比优先：非抢占式，等得越久越容易被执行；
最高优先级：先执行优先级高的作业，会导致低优先级作业饥饿；
时间片轮转：抢占式，时间片用完切换下一个进程
多级反馈队列：是「时间片轮转算法」和「最高优先级算法」的综合和发展；

进程间通信

每个进程的用户地址空间都是独立的，一般而言是不能互相访问的，但内核空间是每个进程都共享的，所以进程之间要通信必须通过内核。

管道

所谓管道就是内核中的一串缓存，写入到管道就是缓存到内核中，管道传输的数据是无格式的流且大小受限，且是先进先出的；

匿名管道只能实现存在父子关系的进程，命名管道可以在不相关的进程间通信；

消息队列

消息队列是保存在内核中的消息链表，在发送数据时，会分成一个一个独立的数据单元，也就是消息体（数据块），消息体是用户自定义的数据类型，消息的发送方和接收方要约定好消息体的数据类型，所以每个消息体都是固定大小的存储块；

可以理解为发邮件，同时也就像发邮件一样通信不及时，大小也有限制；

共享内存

共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中

信号量

由于共享同一片物理内存，那么就要处理多进程冲突和同步问题，这里就引入了信号量，信号量就是一个整型计数器：

P操作：信号量减1，如果信号量<0表示资源被占用
V操作：信号量加1，相加后如果信号量<=0，则表明当前有阻塞中的进程，将该进程唤醒运行，如果相加后信号量>0，则表明没有阻塞中的进程。

P、V操作必须成对出现！

信号量又分为两种：

互斥信号量，信号量初始化为1：
同步信号量，信号量初始化为0，可以保证进程间执行的顺序：

线程互斥

由于线程共享资源，如果多个线程同时对某个资源进行修改，就会出错，因此需要保证同一时间只有一个线程可以操作共享资源；这就是线程的互斥；

乐观锁和悲观锁：
悲观锁认为多个线程同时访问一个资源的概率较高，因此在修改之前先加锁，防止别的线程修改，如互斥锁，读写锁；
乐观锁认为冲突的概率并不高，就直接修改，修改之后再对比修改过程中是否其他线程也修改了该资源；如git；

死锁（⭐）

死锁就是多个进程并发执行，在各自占有一定资源的情况下，希望获得其他进程占有的资源以推进执行，但是其他资源同样也期待获得另外进程的资源，大家都不愿意释放自己的资源，从而导致了相互阻塞、循环等待，进程无法推进的情况。

死锁条件：

互斥：一个资源只能被一个进程使用
请求并保持：请求其他资源但是不释放已有资源
不可剥夺
循环等待

死锁防止：

死锁预防：打破以上四个死锁条件
死锁避免：银行家算法
死锁检测：检测到了死锁直接抢占资源或终止进程

银行家算法（⭐）：
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。安全的状态指的是一个进程序列{P1,P2,…Pn}，对于每一个进程Pi，它以后尚需要的资源不大于当前资源剩余量和其余进程所占有的资源量之和。

内存管理

虚拟内存

如果没有虚拟内存，两个程序要同时运行在内存中就必须保证不使用同一个位置的物理内存；这样编程会很麻烦，因为要时刻注意两端程序是否引用了相同的物理内存地址；于是，操作系统提供了虚拟内存，如上图所示，每个进程都有一套“虚拟地址”，互不干扰，操作系统负责把虚拟地址映射到物理地址，这样程序员就完全不用关心物理内存。

总结虚拟内存的优势：

虚拟内存可以使进程的运行内存超过物理内存的大小，因为程序运行符合局部性原理，那些没有被经常使用到的内存就可以把它换出到外存；
每个进程都有自己的页表，也就是说每个进程的虚拟内存空间就是相互独立的，解决了多进程之间地址冲突的问题；

内存分段

我们知道程序的存储本身就是分区的，如堆区，栈区，代码区等等，因此直接的想法就是按照这些分区进行分段映射：

这样就解决了程序本身不需要关心物理内存地址的问题，但是有一些问题：

内存碎片
内存交换效率很低

内存分段管理可以做到段根据实际需求分配内存，所以有多少需求就分配多大的段，所以不会出现内部内存碎片。但是由于每个段的长度不固定，所以多个段未必能恰好使用所有的内存空间，会产生了多个不连续的小物理内存，导致新的程序无法被装载，所以会出现外部内存碎片的问题。要解决内存碎片需要 内存交换，先把程序写到外存，再写回来并且紧跟上一段内存，就没有内存碎片了，但是内存交换效率很低；

内存分页

为了解决内存碎片的问题，可以使用内存分页式存储，把物理地址划分为相同的页，每次都是以页为单位进行内存分配，这样就不会有很小的内存碎片出现了。

内存分页保证物理内存没有内存碎片，但是如果一个程序不足一页大小也会分配一个页，会出现页内内存浪费，会有内部内存碎片；

简单的内存分页也有问题，那就是页表太大，虚拟内存本就很大，分成很多个页都需要存储页表项；而且每个进程都有自己的页表，加起来分配给页表的内存就很大了；

多级页表：

多级页表的思想就是既然页表太大了，那就对页表再分页，一级页表中存储1024个页表项（二级页表），每个二级页表中存储1024个页表项对应物理页号；
并且，根据程序的局部性原理，如果一级页表中没有用到某一个页表项，那就不需要创建这个页表项对应的二级页表了，需要时再创建；

TLB(Translation Lookaside Buffer)，页表缓存，快表

多级页表解决了存储问题，但是多了几次地址转换，降低了转换速度，因此同样根据局部性原理，程序经常访问的内存比较固定，那就把这些经常访问的内存页存到快表中，先在快表中找，没有再去多级页表中找；

段页式内存管理

段页式就是将段式和分页式结合起来，先分段，再对每个段分页；

浮点数和负数

负数

负数使用补码表示，即正数按位取反再加1；

这样表示是为了统一加法操作；

浮点数

小数的表示是整数部分使用除二取余，小数部分使用 乘二取整：

因此可以发现，对于一些小数我们无法得到准确的二进制数，比如0.1的二进制数就是无限循环的，这样就会造成浮点数精度误差的问题；

浮点数之所以叫浮点数，是因为其小数点是可以移动的；比如 1000.101 这个二进制数，可以表示成 1.000101 x 2^3，类似于数学上的科学记数法。因此就可以使用下图的形式存储浮点数，指数为就是3，尾数就是000101；

但是这里的指数位不是简单的存浮点的移动位数，而是存 移动位数+127，这是因为指数有正有负，如1010.101应该右移3位，此时指数就是+3，如果对于0.000101应该左移4位，此时指数就是-4；我们不想对指数区分正数负数，因此就加上偏移量，保证都是正数；

大端小端

大端指的是将高位字节存储在低位地址上，而小端则是将低位字节存储在低位地址上。

注意：大端更顺眼！

判断方法：

bool IsBigEndian(){
   int a = 0x1234;
   int p = *((char*)&a);
   if(p==0x12){
      return true;
   }else{
      return false;
   }
}

计算机网络

TCP

TCP是面向连接的，可靠的，基于字节流的传输层通信协议；

面向连接的：一定是 一对一 才能连接，不能像UDP协议可以一个主机同时向多个主机发送消息；
可靠的：无论网络链路中出现了怎样的链路变化，TCP都可以保证一个报文一定能到达接收端；
字节流：用户消息通过 TCP 协议传输时，消息可能会被操作系统「分组」成多个的 TCP 报文，如果接收方的程序如果不知道「消息的边界」，是无法读出一个有效的用户消息的。并且 TCP 报文是「有序的」，当「前一个」TCP 报文没有收到的时候，即使它先收到了后面的 TCP 报文，那么也不能扔给应用层去处理，同时对「重复」的 TCP 报文会自动丢弃