C++语言的八股文

C++面向对象的特性

• 封装——隐藏对象的属性和实现细节，仅对外公开接口和对象进行交互，将数据和操作数据的方法进行有机结合。
• 继承——允许程序员在保持父类特性的基础上进行扩展，增加功能，这样产生的新类，称为子类；父类和子类存在父子关系，即：
  • 子类拥有父类的所有属性和行为
  • 子类对象可以作为父类对象使用
  • 子类中可以添加父类没有的方法和属性
• 多态——为不同数据类型的实体提供统一的接口。
  • 动态多态（dynamic polymorphism）：通过类继承机制和虚函数机制生效于运行期。可以优雅地处理异质对象集合，只要其共同的基类定义了虚函数的接口。也被称为子类型多态（Subtype polymorphism）或包含多态（inclusion polymorphism）。在面向对象程序设计中，这被直接称为多态。
  • 静态多态（static polymorphism）：模板也允许将不同的特殊行为和单个泛化记号相关联，由于这种关联处理于编译期而非运行期，因此被称为“静态”。可以用来实现类型安全、运行高效的同质对象集合操作。（通过函数重载和模板来实现）

多态的优点？

参考

• 可替换性
• 可扩充性
• 接口性
• 灵活性
• 简化性

虚函数

• 指被virtual关键字修饰的成员函数。实现多态性，通过指向派生类的基类指针或引用，访问派生类中同名覆盖成员函数。
• 在类对象的头4个字节中，有一个指向这个虚函数表的指针，称为Vptr；（一个类的多个实例共享同一个虚函数表）
• 构造函数不可以有虚函数，析构函数可以有虚函数。（析构函数常常被声明为virtual，这是因为当父类的析构函数未声明为virtual时，如果父类指针指向一个子类的对象，那么当delete该指针时，子类的析构函数不会被调用，从而造成内存泄漏）

虚继承和虚基类

• 为了解决多继承时的命名冲突和冗余数据问题，C++ 提出了虚继承，使得在派生类中只保留一份间接基类的成员。
• 虚继承的目的是让某个类做出声明，承诺愿意共享它的基类。其中，这个被共享的基类就称为虚基类（Virtual Base Class）。在这种机制下，不论虚基类在继承体系中出现了多少次，在派生类中都只包含一份虚基类的成员。

指针和引用

• 引用：引用可以看作是一个指针常量来实现的，引用是一个内存对象的别名。
• 指针：指针指向一个内存对象，保存了这个对象的内存地址。

指针和引用的不同点	指针	引用
是否可以为空	是	否
是否必须初始化	否	是
初始化后是否可以改变	是	否
是否有const	是	否
是否需要分配内存空间	是	否
访问对象的方式	间接访问	直接访问
大小	指针本身的大小，32位系统为4字节，64位系统为8字节	引用对象的大小
++自增运算符	指向下一个地址	所引用的对象执行自增操作

内置数组和指针

• 内置数组：内置数组是用于储存多个相同类型数据的集合。
• 指针：指针指向一个内存对象，保存了这个对象的内存地址。

不同点	内置数组	指针
赋值	一个个元素赋值或拷贝	同一类型的指针可以相互赋值
存储方式	连续存放于静态区或栈上。	很灵活，可以指向任意类型的数据。指针的类型说明了它所指向地址空间的内存。
sizeof大小	数组元素个数 ✖ 单个元素所占大小	根据操作系统的位数来确定，32位大小为4，64位大小为8
传参	传递指向该数组的指针	传递本身

• 易混淆点：
  • 指针数组：一个元素对象为指针的数组。
  • 数组指针：指向数组的指针。

static关键字

• 控制可见范围，不用担心重名问题。
• 保持变量内容的持久。
• 默认初始化为0。
• 类成员声明static，static成员为类所拥有，而非实例所拥有。

全局静态变量和局部静态变量的异同

• 不同点：作用域范围不同，全局静态变量具有文件作用域，局部静态变量具有块作用域。
• 相同点：生命周期都是所属模块装载到所属模块卸载。

C++11新特性

• nullptr

• 类型推导（auto和decltype），

  • auto是让编译器通过初始值来推算变量的类型（用来缩写类型和简化声明）；（auto不能传递const特性）
  • decltype在C++中，作为操作符，用于查询表达式的数据类型;主要是为泛型编程而设计，以解决泛型编程中，由于有些类型由模板参数决定，而难以（甚至不可能）表示之的问题。

• 区间迭代

for(auto ch : s){
}

• 构造函数（委托构造，继承构造）
• Lambda表达式
• 新增容器（std::array，std::forward_list，无序容器，std::tuple），
• 服务于string的正则表达式（std::regex，std::regex_match->std::match_results）

 if (std::regex_match ("subject", std::regex("(sub)(.*)") ))
    std::cout << "匹配成功\n";

• 语言级线程支持（std::thread，std::mutex/std::unique_lock，std::condition_variable，std::future/std::packaged_task）

• 右值引用和move语义

• 智能指针（unique_ptr、shared_ptr、weak_ptr）

• std::move和std::forward

  • std::move(t)用来表示对象t可以被移动，即允许t所占有的资源转移到另一对象上。比较特别使用方式是：用std::move生成一个xvalue（xvalue是定义的右值，有实体，可以被移动。）*表达式来标识它的参数t，等价于通过static_cast转换为右值引用类型（static_cast<typename std::remove_reference<T>::type&&>(t)。
  • std::forward<T>，将左值转换为左值还是右值取决于T的类型；只能将右值转换为右值，不允许右值转换为左值。

• std::bind

  • 函数模板bind为f生成一个转发调用包装器。调用这个包装器相当于调用f，并将其一些参数绑定到args上。

#include <iostream>
#include <functional>

void f(int n1, int n2, int n3, const int& n4, int n5)
{
    std::cout<< n1 << ' ' << n2 << ' ' << n3 << ' ' << n4 << ' ' << n5 << '\n';
}


int main(){
   using namespace std::placeholders;
    std::cout << "1) argument reordering and pass-by-reference: ";
    int n = 7;
    // (_1 and _2 are from std::placeholders, and represent future
    // arguments that will be passed to f1)
    auto f1 = std::bind(f, _2, 42, _1, std::cref(n), n);
    n = 10;
    f1(1, 2, 1001); // 1 is bound by _1, 2 is bound by _2, 1001 is unused
                    // makes a call to f(2, 42, 1, n, 7)

  return 0;
}
//输出为：argument reordering and pass-by-reference: 2 42 1 10 7

为什么使用C++11？

• 更友好的语法规则。（auto、lambda、std::function）
• 更强大的容器库。（无序容器）
• 更强大的性能优势。（右值引用，定制模板）
• 内存泄漏。（智能指针）
• 更清晰的代码意图。（override、final和nullptr）
• 编译期错误检查。（static_assert）

智能指针

• 智能指针主要用于管理在堆上分配的内存，它将普通的指针封装为一个栈对象。
• 当栈对象的生存周期结束后，会在析构函数中释放掉申请的内存，从而防止内存泄漏。

名称	描述
auto_ptr	这个类模板因存在潜在的内存崩溃问题在c++ 11中已弃用。取代它的是unique_ptr。
unique_ptr	实现独占式拥有或严格拥有概念，保证同一时间内只有一个智能指针可以指向该对象。
shared_ptr	实现共享式拥有概念。多个智能指针可以指向相同对象，该对象和其相关资源会在“最后一个引用被销毁”时候释放。
weak_ptr	一种不控制对象生命周期的智能指针, 它指向一个shared_ptr管理的对象，主要用作解决当两个对象互相使用一个shared_ptr成员变量指向对方，会造成循环引用，使引用计数失效，从而导致内存泄漏的问题。

shared_ptr如何实现？

• T类型为任意类型
• 需要实现的函数包括：
  • 带T类型传参的构造函数
  • 拷贝构造函数
  • 赋值构造函数
  • 析构函数
  • 解引用运算符
  • ->运算符
• 需要拥有的成员变量：
  • 指向一个整型对象的指针
  • 指向一个T类型对象的指针

template<typename T>

class SharedPtr {

public:

        SharedPtr(T* p) :countPtr(new int(1)), point(p) {}

       SharedPtr(SharedPtr<T>& other) :countPtr(&(++*other.countPtr)), point(other.point) {}

       SharedPtr<T>& operator=(SharedPtr<T>& other) {

              ++* other.countPtr;

              if (this->_ptr && 0 == -- * this->countPtr) {

                     delete countPtr;

                     delete point;

              }

              this->countPtr = other.countPtr;

              this->point = other.point;

              return *this;

       }
       T& operator*() {

              return *point;

       }

       T* operator->() {

              return point;

       }

       ~SharedPtr() {

              if (-- * countPtr == 0) {

                     delete countPtr;

                     delete point;

              }

       }

private:

       int* countPtr;

       T* point;

};

std::make_shared和std::shared_ptr<T>(new T(args...))有啥区别？

• 内存分配次数
  • 内存分配次数不同。（左：1次。右：2次）
• 弱引用
  • 如果任何std::weak_ptr在所有共享所有者的生命周期结束后引用了std::make_shared创建的控制块，T所占用的内存将持续存在，直到所有弱所有者也被销毁，如果(T)的sizeof很大，这可能是不可取的。
• 公共构造函数
  • 如果std::shared_ptr<T>(new T(args…))是在可访问的上下文中执行，可以调用T的非公共构造函数，而std::make_shared要求对所选构造函数进行公共访问。
• 删除器
  • 与std::shared_ptr构造函数不同，std::make_shared不允许自定义删除器。
• 操作符new。
  • std::make_shared使用::new，因此，如果使用类特定的operator new设置了任何特殊行为，它将不同于std::shared_ptr<T>(new T(args…))

RAII

• 全称为Resource Acquisition Is Initialization，中译为：资源获取就是初始化。C++标准保证任何情况下，已构造的对象最终会销毁，即它的析构函数最终会被调用。

野指针

• 野指针是指针指向的位置是不可知的（随机的、不正确的、没有明确限制的）。
  
  
• 出现野指针的原因：
  • 未初始化
  • 指针所指向的对象已经释放，但未将指针置为nullptr

#pragma once和#ifndef的区别

• #ifndef的方式受C/C++语言标准支持。它不光可以保证同一个文件不会被包含多次，也能保证内容完全相同的两个文件（或者代码片段）不会被不小心同时包含。
• #pragma once一般由编译器提供保证：同一个文件不会被包含多次。——pragma的中文含义是编译指示，在这个语句中指示编译器只编译一次该文件。

new和malloc

特征	new/delete	malloc/free
分配内存的位置	自由存储区	堆
内存分配成功的返回值	完整类型指针	void*
内存分配失败的返回值	默认抛出异常	返回NULL
分配内存的大小	由编译器根据类型计算得出	必须显式指定字节数
处理数组	有处理数组的new版本new[]	需要用户计算数组的大小后进行内存分配
已分配内存的扩充	无法直观地处理，可以用vector实现	使用realloc简单完成
是否相互调用	是	否
分配内存时内存不足	客户能够指定处理函数或重新制定分配器	无法通过用户代码进行处理
是否允许函数重载	是	否
是否调用构造函数与析构函数	是	否

内存管理

名称	作用
栈区	由编译器自动分配释放，存放为函数运行的局部变量，函数参数，返回数据，返回地址等。操作方式与数据结构中的类似。
堆区	一般由程序员分配释放，若程序员不释放，程序结束时可能由OS回收。分配方式类似于链表。
全局数据区	也叫做静态区，存放全局变量，静态数据。程序结束后由系统释放。
文字常量区	可以理解为常量区，常量字符串存放这里。程序结束后由系统释放。
程序代码区	存放函数体的二进制代码。但是代码区中也分为代码段和数据段。

堆和栈

不同点	堆	栈
管理方式	堆中资源由程序员控制（容易产生memory leak）	栈资源由编译器自动管理，无需手工控制
系统响应	对于堆，应知道系统有一个记录空闲内存地址的链表，当系统收到程序申请时，遍历该链表，寻找第一个空间大于申请空间的堆结点，删除空闲结点链表中的该结点，并将该结点空间分配给程序（大多数系统会在这块内存空间首地址记录本次分配的大小，这样delete才能正确释放本内存空间，另外系统会将多余的部分重新放入空闲链表中）	对于栈，只要栈的剩余空间大于所申请空间，系统为程序提供内存，否则报异常提示栈出。
空间大小	堆是不连续的内存区域（因为系统是用链表来存储空闲内存地址，自然不是连续的），堆大小受限于计算机系统中有效的虚拟内存（32bit 系统理论上是4G），所以堆的空间比较灵活，比较大。	栈是一块连续的内存区域，大小是操作系统预定好的，windows下栈大小是2M（也有是1M，在 编译时确定，VC中可设置）。
碎片问题	对于堆，频繁的new/delete会造成大量碎片，使程序效率降低。	对于栈，它是一个先进后出的线性表，进出一一对应，不会产生碎片。
生长方向	堆向上，向高地址方向增长。	栈向下，向低地址方向增长。
分配方式	堆都是动态分配（没有静态分配的堆）。	栈有静态分配和动态分配，静态分配由编译器完成（如局部变量分配），动态分配由alloca函数分配，但栈的动态分配的资源由编译器进行释放，无需程序员实现。
分配效率	堆由C/C++函数库提供，机制很复杂。所以堆的效率比栈低很多。	栈是机器系统提供的数据结构，计算机在底层对栈提供支持，分配专门寄存器存放栈地址，栈操作有专门指令。

内存对齐的原因

• 平台原因(移植原因)：不是所有的硬件平台都能访问任意地址上的任意数据的；某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。
• 性能原因：数据结构(尤其是栈)应该尽可能地在自然边界上对齐。原因在于，为了访问未对齐的内存，处理器需要作两次内存访问；而对齐的内存访问仅需要一次访问。

Cast变换

• C++为了规范C中的类型转换,加强类型转换的可视性，引入了以下四种类型转换。

名称	作用
const_cast	去除const（volatile）属性，将只读变为可读写。
dynamic_cast	在进行下行转换时，dynamic_cast具有类型检查的功能，弥补了static_cast类型不安全的缺陷，比static_cast更安全。 多用于有虚函数的基类与其派生类之间的转换，特点是进行运行时检测转换类型是否安全，如果转换失败返回nullptr，依赖于RTTI技术，但是有额外的函数开销。
static_cast	代替隐式转换，基类与派生类的转换，派生类转换成基类是安全的，基类转换成派生类是不安全的。编译期转换。
reinterpret_cast	代替显示转换。

构造函数有那些？

• 默认构造函数
• 带参数的构造函数
• 委托构造函数
• 拷贝构造函数和拷贝赋值运算符
• 移动构造函数和移动赋值运算符

vector是不是线程安全的？

参考

• vector不是线程安全的，并发读写导致读方的迭代器失效。

• 处理线程安全的方法：

  • 加锁。
  • 固定vector的大小。

shared_ptr是线程安全的吗？

是，为了满足线程安全需求，引用计数器通常使用std::atomic::fetch_add和std::memory_order_relaxed的等价递增(递减需要更强的顺序来安全地销毁控制块)。

std::map和std::unordered_map的实现原理

• std::map：红黑树（一种特殊的平衡二叉树），特性如下：
  • 只有红、黑两种节点。
  • 根节点为黑节点。
  • 叶子节点为黑节点，并且是nil节点。
  • 红节点的子节点都是黑节点。
  • 对于任意结点而言，其可达的叶子节点上的每条路径都包含相同数目的黑结点。
• std:unordered_map：哈希表，哈希冲突的处理方式：
  • 采取链表的形式存储相同哈希值的对象。
  • 根据负载因子来控制是否rehash来调整哈希表的表长。

std::condition_variable::wait为什么需要一个unique_lock<mutex>的变量lck？

• wait函数的实现：
  • 执行lck的unlock()方法（其他线程不再被阻塞）
  • 沉睡等待唤醒
  • 其他线程调用了notify系列方法
  • 沉睡线程被唤醒，执行lck.lock()

源代码到可执行程序过程

• 预处理
  • 宏定义指令（#define）
  • 条件编译指令（#ifdef）
  • 头文件包含指令（#include）
  • 特殊符号（LINE、FILE）
• 编译
  • 语法分析，词法分析，语义分析，符号汇总，然后生成汇编代码文件
• 汇编
  • 把汇编语言代码翻译成目标机器指令
• 链接
  • 将有关的目标文件彼此相连接，也即将在一个文件中引用的符号同该符号在另外一个文件中的定义连接起来，使得所有的这些目标文件成为一个能够被操作系统装入执行的统一整体。

锁的种类有那些？

• 互斥锁（std::mutex）
  • 可以避免多个线程在某一时刻同时操作一个共享资源，标准C++库提供了std::unique_lock类模板，实现了互斥锁的RAII惯用语法：

       std::unique_lock<std::mutex> lk(mtx_sync_);

• 条件锁（std::condition_variable）

  • 条件锁等同于条件变量，某一个线程因为某个条件未满足时可以使用条件变量使该程序处于阻塞状态。一旦条件满足了，即可唤醒该线程(常和互斥锁配合使用)，唤醒后，需要检查变量，避免虚假唤醒。

• 读写锁（std::shared_lock）

  • 也被称作“共享-独占锁”，当读写锁以读模式锁住时，它是以共享模式锁住的；当它以写模式锁住时，它是以独占模式锁住的。

• 递归锁（std::recursive_mutex）

  • std::recursive_mutex 允许同一个线程对互斥量多次上锁（即递归上锁）

• 自旋锁（spin_mutex）

  • 自旋锁是一种基础的同步原语，用于保障对共享数据的互斥访问。与互斥锁相比，在获取锁失败的时候不会使得线程阻塞而是一直自旋尝试获取锁。当线程等待自旋锁的时候，CPU不能做其他事情，而是一直处于轮询忙等的状态。自旋锁主要适用于被持有时间短，线程不希望在重新调度上花过多时间的情况。

class spin_mutex {
       std::atomic<bool> flag = ATOMIC_VAR_INIT(false);
public:
       spin_mutex() = default;
       spin_mutex(const spin_mutex&) = delete;
       spin_mutex& operator= (const spin_mutex&) = delete;
       void lock() {
              bool expected = false;
              while (!flag.compare_exchange_strong(expected, true))
                     expected = false;
       }
       void unlock() {
              flag.store(false);
       }
}

C++与Lua的相互调用

Lua和C++ 交互机制的基础在于Lua提供了一个虚拟栈，C++ 和Lua之间的所有类型的数据交换都通过这个栈完成。无论何时C想从Lua中调用一个值，被请求的值将会被压入栈，无论何时C想要传递一个值给Lua，首先将整个值压栈，然后就可以在Lua中调用。

• C++调用Lua：
  • 获取Lua值：调用lua_getglocal获取值->压栈->调用该C API lua_toXXX将栈中元素取出转成相应的C类型的值
  • 调用Lua函数：调用lua_getglobal获取函数->压栈->参数入栈->lua_pcall调用对应函数->返回值入栈
• Lua调用C++：
  • 包装成Lua_CFunction->调用lua_register完成注册->根据注册名调用

生产者和消费者简易实现

参考

条件变量和互斥锁（C++11）

#include <iostream>           
#include <queue>
#include <thread>             
#include <mutex> 
#include <condition_variable> 
using namespace std;

mutex mtx;
condition_variable produce, consume;  // 条件变量是一种同步机制，要和mutex以及lock一起使用

queue<int> q;     // shared value by producers and consumers, which is the critical section
int maxSize = 20;

void consumer()
{
    while (true)
    {
        this_thread::sleep_for(chrono::milliseconds(1000));
        unique_lock<mutex> lck(mtx);
        consume.wait(lck, [] {return q.size() != 0; });     // wait(block) consumer until q.size() != 0 is true

        cout << "consumer " << this_thread::get_id() << ": ";
        q.pop();
        cout << q.size() << '\n';

        produce.notify_all();                               // nodity(wake up) producer when q.size() != maxSize is true
    }
}

void producer(int id)
{
    while (true)
    {
        this_thread::sleep_for(chrono::milliseconds(1000));      // producer is a little faster than consumer  
        unique_lock<mutex> lck(mtx);
         produce.wait(lck, [] {return q.size() != maxSize; });   // wait(block) producer until q.size() != maxSize is true

        cout << "producer " << this_thread::get_id() << ": ";
        q.push(id);
        cout << q.size() << '\n';

        consume.notify_all();                                   // notify(wake up) consumer when q.size() != 0 is true
    }
}

int main()
{
    thread consumers[2], producers[2];

    // spawn 2 consumers and 2 producers:
    for (int i = 0; i < 2; ++i)
    {
        consumers[i] = thread(consumer);
        producers[i] = thread(producer, i + 1);  //thread：第一个参数是task任务，第二个参数是task函数的参数 
    }

    // join them back: (in this program, never join...)
    for (int i = 0; i < 2; ++i)
    {
        producers[i].join();
        consumers[i].join();
    }

    system("pause");
    return 0;
}

信号量（C++20）

#include <iostream>           
#include <queue>
#include <thread>             
#include <semaphore>
using namespace std;

queue<int> q;     // shared value by producers and consumers, which is the critical section
int maxSize = 20;

counting_semaphore semaphore(0);

void consumer()
{
    while (true)
    {
        this_thread::sleep_for(chrono::milliseconds(1000));
        semaphore.acquire();

        cout << "consumer " << this_thread::get_id() << ":";
        q.pop();
        cout << q.size() << '\n';
    }
}

void producer(int id)
{
    while (true)
    {
        this_thread::sleep_for(chrono::milliseconds(1000));      // producer is a little faster than consumer  
        
        cout << "producer " << this_thread::get_id() << ":";
        q.push(id);
        cout << q.size() << '\n';
        semaphore.release();
    }
}

int main()
{
    thread consumers[2], producers[2];

    // spawn 2 consumers and 2 producers:
    for (int i = 0; i < 2; ++i)
    {
        consumers[i] = thread(consumer);
        producers[i] = thread(producer, i + 1);  //thread：第一个参数是task任务，第二个参数是task函数的参数 
    }

    // join them back: (in this program, never join...)
    for (int i = 0; i < 2; ++i)
    {
        producers[i].join();
        consumers[i].join();
    }

    system("pause");
    return 0;
}

无锁队列

参考

• 重要思想（CAS）

CAS是英文单词Compare and Swap的缩写，翻译过来就是比较并替换。
CAS机制中使用了3个基本操作数：内存地址V，旧的预期值A，要修改的新值B。
更新一个变量的时候，只有当变量的预期值A和内存地址V当中的实际值相同时，才会将内存地址V对应的值修改为B。

• 通过atomic类来实现

template偏特化

参考

template偏特化是相对于template全特化而言的，即只特化了部分模板参数。

• 类模板偏特化

template <typename T, typename Allocator_T>
class MyVector {
public:
    MyVector() {
        std::cout << "Normal version." << std::endl;
    }
};

template <typename T>
class MyVector<T, DefaultAllocator> {
public:
    MyVector() {
        std::cout << "Partial version." << std::endl;
    }
};

• 函数模板偏特化（C++20）

template <typename A, typename B>
void f(A a, B b) {
    std::cout << "Normal version." << std::endl;
}

template <typename A, typename B>
requires std::integral<B>
void f(A a, B b) {
    std::cout << "Partial version." << std::endl;
}

类的函数后面加一个const

意味着只能修改static或mutable成员。

左值和右值

• glvalue：一个表达式，它的求值决定了一个对象或函数的标识。
• prvalue：求值的表达式。1.计算内置操作符的操作数的值。2.初始化一个对象。
  结果对象可能是一个变量、一个由new创建的对象、临时物化物或者它的一个成员。需注意，非void的丢弃表达式有一个结果对象(物化的临时表达式) ，此外，每个类和数组prvalue都有一个结果对象，除非它是decltype的操作数。
• xvalue：(一个“即将过期”的值)是glvalue的一种，它表示一个对象的资源可以被重用;

左值：是glvalue但不是xvalue。
右值：是prvalue或者xvalue。

可重入

可重入函数主要用于多任务环境中，一个可重入的函数简单来说就是可以被中断的函数，也就是说，可以在这个函数执行的任何时刻中断它，转入OS调度下去执行另外一段代码，而返回控制时不会出现什么错误。

C++17新特性

• 类型擦除（std::any）

计算机网络的八股文

OSI七层模型

• 应用层
  • 网络服务与最终用户的一个接口。
  • 协议有：HTTP FTP TFTP SMTP SNMP DNS TELNET HTTPS POP3 DHCP
  • 数据单元为：消息
• 表示层
  • 数据的表示、安全、压缩。
  • 格式有，JPEG、ASCll、EBCDIC、加密格式等。
  • 数据单元为：消息
• 会话层
  • 建立、管理、终止会话。
  • 对应主机进程，指本地主机与远程主机正在进行的会话。
  • 数据单元为：消息
• 传输层
  • 定义传输数据的协议，端口号，以及流控和差错校验。
  • 协议有：TCP UDP，数据包一旦离开网卡即进入网络传输层。
  • 数据单元为：数据段
• 网络层
  • 进行逻辑地址寻址，实现不同网络之间的路径选择。
  • 协议有：ICMP IGMP IP（IPV4 IPV6）
  • 数据单元为：数据报
• 数据链路层
  • 建立逻辑连接、进行硬件地址寻址、差错校验等功能。（由底层网络定义协议）
  • 将比特组合成字节进而组合成帧，用MAC地址访问介质，错误发现但不能纠正。
  • 数据单元为：帧
• 物理层
  • 建立、维护、断开物理连接。（由底层网络定义协议）
  • 数据单元为：比特

http和https的区别

https 主要由两部分组成：http + ssl / tls，也就是在 http 上又加了一层处理加密信息的模块。服务端和客户端的信息传输都会通过 tls 进行加密，所以传输的数据都是加密后的数据。

• https协议需要到CA申请证书，一般免费证书较少，因而需要一定费用。
• http是超文本传输协议，信息是明文传输，https则是具有安全性的ssl/tls加密传输协议，所以https相对安全。
• 连接方式和端口不同：
  • http：连接是无状态的，端口是80。
  • https：连接也是无状态的，不过存在身份验证环节，并且传递数据存在加密解密环节，端口是443。

https加密算法

参考

• 对称加密算法：
   需要对加密和解密使用相同密钥的加密算法。所谓对称，就是采用这种加密方法的双方使用方式用同样的密钥进行加密和解密。密钥是控制加密及解密过程的指令。算法是一组规则，规定如何进行加密和解密。

• 非对称加密算法：
   非对称加密算法需要两个密钥：公开密钥（publickey:简称公钥）和私有密钥（privatekey:简称私钥）。公钥与私钥是一对，如果用公钥对数据进行加密，只有用对应的私钥才能解密。如果用公钥对数据进行加密，只有用对应的私钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。

• 散列/哈希算法：
   指把数据通过某种公开的算法变成固定长度的hash值，这个过程可以使用密钥也可以不使用，这种加密算法是不可逆的，也就是说不能从加密后的hash值解密还原成明文，因此，这种算法通常用于验证数据是否被篡改和数据是否一致。因为同样的明文加密后得到是相同的hash值。典型的算法有MD5，SHA，Base64等

  TCP和UDP对比

差异点	TCP	UDP
包头大小	20字节	8字节
是否基于连接	是	否
是否可靠	是	否
对系统资源的要求	较多	较少
速度	较慢	较快

TCP如何保证可靠性

• 检验和
• 序列号/确认应答
• 超时重传
• 最大消息长度
• 滑动窗口控制
• 拥塞控制
• 等等

TCP三次握手和四次挥手

• 三次握手：建立连接

  
  image.png

• 四次挥手：断开连接

  
  image.png

如何实现tcp拥塞控制？

参考

• 慢开始算法
  • 拥塞窗口由初始大小为1，指数式增大到慢开始门限（ssthresh）或出现拥塞为止。若增大到慢开始门限（ssthresh），便开始采取拥塞避免算法；若出现拥塞，将慢开始门限（ssthresh）减半，并将拥塞窗口置为1，然后再采取慢开始算法。
• 拥塞避免算法
  • 发送数据每得到接收方确认，拥塞窗口大小增1。
• 快重传算法
  • 数据传输时(数据被分成报文，每个报文都有个序号)，中间的一部分丢失接收方没收到，接收方连续接到后面的数据，则发回对丢失前的数据的重复确认，这样发送方就知道有部分数据丢失了，于是从丢失处重传数据。
• 快恢复算法
  • 快恢复是与快重传配合的算法，在发生数据丢失时，发送方收到接收方发回的三个重复确认信息时，就把每次传输的数据量减为原来的一半，拥塞窗口也修改为这个值,然后又开始采取拥塞避免算法策略。

什么是tcp粘包？如何处理？

• tcp粘包就是指发送方发送的若干包数据到达接收方时粘成了一包，从接收缓冲区来看，后一包数据的头紧接着前一包数据的尾。
• 处理方法：
  • 发送方关闭Nagle算法（用于自动连接许多的小缓冲器消息）。
  • 接收方应用层格式化数据或显示声明数据长度。

网址输入会发生什么？

• DNS解析->基于TCP连接的HTTP请求->服务器处理请求->浏览器解析响应数据后渲染页面->关闭TCP连接

什么是DNS协议？

• 全称为Domain Name System，中译为域名系统，端口为53。DNS一种可以将域名和IP地址相互映射的层次结构的分布式数据库系统。

Protobuf Union

参考

Protobuf没有提供union类型，如果希望使用union类型，可以采用enum和optional属性定义的方式。

为什么采用Protobuf？

• Protobuf优点
  • 传输效率快（据说在数据量大的时候，传输效率比xml和json快10-20倍），序列化后体积相比Json和XML很小，支持跨平台多语言，消息格式升级和兼容性还不错，序列化反序列化速度很快。
• Protobuf缺点
  • 使用不太方便。

Protobuf Lua 的序列化和反序列化

• 序列化：SerializeToString
• 反序列化：ParseFromString

计算机操作系统的八股文

进程和线程

• 进程：是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位。程序是指令、数据及其组织形式的描述，进程是程序的实体。
• 线程：CPU调度的最小单位，线程的特点就是在不需要独立资源的情况下就可以运行。

进程间通信方式

• 管道

  • 匿名管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
  • 有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。

• 消息队列

  • 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

• 信号

  • 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

• 信号量

  • 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

• 共享内存

  • 共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。

• 套接字

  • 套接字也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同设备及其间的进程通信。

共享内存实例

参考

• Windows实例
  需注意字符集：使用多字节字符集

#include <windows.h>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int main()
{
    string strMapName("ShareMemory");                // 内存映射对象名称
    string strComData("This is common data!");        // 共享内存中的数据
    LPVOID pBuffer;                                    // 共享内存指针

    // 首先试图打开一个命名的内存映射文件对象
    HANDLE hMap = ::OpenFileMapping(FILE_MAP_ALL_ACCESS, 0, strMapName.c_str());
    if (NULL == hMap)
    {    // 打开失败，创建之
        hMap = ::CreateFileMapping(INVALID_HANDLE_VALUE,
                                   NULL,
                                   PAGE_READWRITE,
                                   0,
                                   strComData.length()+1,
                                   strMapName.c_str());
        // 映射对象的一个视图，得到指向共享内存的指针，设置里面的数据
        pBuffer = ::MapViewOfFile(hMap, FILE_MAP_ALL_ACCESS, 0, 0, 0);
        strcpy((char*)pBuffer, strComData.c_str());
        cout << "写入共享内存数据：" << (char *)pBuffer << endl;
    }
    else
    {    // 打开成功，映射对象的一个视图，得到指向共享内存的指针，显示出里面的数据
        pBuffer = ::MapViewOfFile(hMap, FILE_MAP_ALL_ACCESS, 0, 0, 0);
        cout << "读取共享内存数据：" << (char *)pBuffer << endl;
    }

    getchar();            // 注意，进程关闭后，所有句柄自动关闭，所以要在这里暂停

    // 解除文件映射，关闭内存映射文件对象句柄
    ::UnmapViewOfFile(pBuffer);
    ::CloseHandle(hMap);
    system("pause");
    return 0;
}

参考

• Linux实例

#include <iostream>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <vector>
#include <unistd.h>
#include <cstring>

#define KEY_OF_SHM 8888
#define TEXT_SIZE 1024

struct ShmDataStruct {
    int readable_;
    char text_[TEXT_SIZE];
};

using namespace std;

int main(){
    //获取shm_id，在不同进程中这是唯一的，获取和KEY有关
    int shm_id = shmget(KEY_OF_SHM, sizeof(struct ShmDataStruct), 0666 | IPC_CREAT);

    string strComData("This is common data!");        // 共享内存中的数据
    void *addr_to_shm;                                  // 共享内存指针

    struct ShmDataStruct *shm_data;
      //将addr_to_shm连接到系统分配的共享内存，也就是将共享内存（物理地址）挂到当前进程的内存空间（虚拟地址）
    addr_to_shm = shmat(shm_id, (void*)0, 0);

     //将获得的void*类型的转为我们需要的data struct
    shm_data = (struct ShmDataStruct*)addr_to_shm;

    // char buffer[TEXT_SIZE];
    if(shm_data->readable_ == 0){
        shm_data->readable_ = 1;
        strncpy(shm_data->text_, strComData.c_str(), strComData.size());
         cout << "写入共享内存数据：" << (char *)shm_data->text_ << endl;
    }
    else{
        
        cout << "读取共享内存数据：" << (char *)shm_data->text_ << endl;
    }

    shm_data->readable_ = 1;

    getchar();            // 注意，进程关闭后，所有句柄自动关闭，所以要在这里暂停

    //把共享内存从当前进程分离，也就是将其从进程内存空间的页表中除掉
    shmdt(addr_to_shm);

    //删除共享内存
    shmctl(shm_id, IPC_RMID, 0);
    exit(EXIT_SUCCESS);
    return 0;
}

线程间通信方式

参考

• 两个进程间的线程通信等同于进程通信。
• 单个进程间的线程通信：
  • 互斥锁
  • 条件变量
  • 信号量
  • 读写锁shared_lock。

多线程的应用场景？

• 多线程处理后台任务
• 多线程异步处理任务
• 多线程分布式计算

协程

• 类似于子例程，与线程不同的是，从当前协程切换到其他协程由当前协程来控制。

死锁

• 死锁是指集合中的每一个进程都在等待只能由本集合中的其他进程才能引发的事件。

• 产生死锁的四个条件：

  • 互斥
  • 请求和等待
  • 不剥夺
  • 环路等待

• 死锁避免：银行家算法

• 死锁检测：定时检测、效率低时检测、进程等待时检测。

• 死锁解除：撤销或挂起一些进程。

• 开发中如何避免死锁？

  • 采取原子操作
  • 利用局部变量的生命周期（RAII）
  • try_lock

物理地址和逻辑地址

• 物理地址：加载到内存地址寄存器中的地址，内存单元的真正地址。
• 逻辑地址：CPU所生成的地址。

虚拟内存

• 虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

作业调度策略

• FIFO全称为：First Come First Serve，中译为：先来先服务
• SJF全称为：Shortest Job First，中译为：短作业优先
• 时间片轮转
• 多级反馈队列
• 高响应比优先

页面置换算法

• OPT全称为：Optimal Replacement Algorithm，中译为：最佳置换算法
• FIFO全称为：First In First Out，中译为：先进先出置换算法
  • Belady现象：采用FIFO算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。
• LRU全称为：Least Recently Used，中译为：最近最久未使用置换算法

大端和小端

• 大端：字数据的高字节存储在低地址中，字数据的低字节则存放在高地址中。
• 小端：字数据的低字节存储在低地址中，字数据的高字节则存放在高地址中。

孤儿进程和僵尸进程

• 孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
• 僵尸进程：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵尸进程。

进程响应信号有那些方式？

• 忽略
• 执行默认
• 捕获

数据结构与算法的八股文

二叉树的应用场景

• C++ STL中的set、map，数据压缩（哈夫曼编码），海量数据并发查询（平衡二叉树）

用两个小球来判断100层高的楼会被摔坏的最低楼层

• 采用动态规划的思想
• dp(n,2) = max(k,dp(n-k,2)+1)，dp(1,2) = 1 临界点：k == dp(n-k,2)+1
  *当n == 1 + 2 + 3 + ... + k时，dp(n,2) = k。

最短路径算法

• 单源最短路径算法：
  • Dijkstra算法（单源、无负权、有向图、无向图最短路径）
  • Bellman-Ford算法（单源、可有负权、有向图、无向图最短路径）
• 多源最短路径算法：
  • Floyd算法（多源、可有负权、有向图、无向图最短路径）

计算机操作系统的八股文

简述CPU执行一条指令的过程

• 取指令阶段：将一条指令从主存中取到指令寄存器的过程。
• 指令译码阶段：在指令译码阶段，指令译码器按照预定的指令格式，对取回的指令进行拆分和解释，识别区分出不同的指令类别以及各种获取操作数的方法。
• 执行指令阶段：此阶段的任务是完成指令所规定的各种操作，具体实现指令的功能。为此，CPU的不同部分被连接起来，以执行所需的操作。
• 访存取数阶段：根据指令地址码，得到操作数在主存中的地址，并从主存中读取该操作数用于运算。
• 结果写回阶段：把执行指令阶段的运行结果数据“写回”到某种存储形式。

页面分页和分段的不同点

• 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率；或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。
  段是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好的满足用户的需要。
• 页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面。
  段的长度却不固定，决定于用户所编写的程序，通常由编辑程序在对源程序进行编辑时，根据信息的性质来划分。
• 分页的作业地址空间是维一的，即单一的线性空间，程序员只须利用一个记忆符，即可表示一地址。
  分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

其他

opengl渲染管线

• 顶点着色器
  • 它把一个单独的顶点作为输入。顶点着色器主要的目的是把3D坐标转为另一种3D坐标，同时顶点着色器允许我们对顶点属性进行一些基本处理。
• 图元着色器
  • 将顶点着色器输出的所有顶点作为输入（如果是GL_POINTS，那么就是一个顶点），并所有的点装配成指定图元的形状。
• 几何着色器
  • 图元装配阶段的输出会传递给几何着色器(Geometry Shader)。几何着色器把图元形式的一系列顶点的集合作为输入，它可以通过产生新顶点构造出新的（或是其它的）图元来生成其他形状。
• 光栅化
  • 几何着色器的输出会被传入光栅化阶段(Rasterization Stage)，这里它会把图元映射为最终屏幕上相应的像素，生成供片段着色器(Fragment Shader)使用的片段(Fragment)。在片段着色器运行之前会执行裁切(Clipping)。裁切会丢弃超出你的视图以外的所有像素，用来提升执行效率。
• 片段着色器
  • 片段着色器的主要目的是计算一个像素的最终颜色，这也是所有OpenGL高级效果产生的地方。通常，片段着色器包含3D场景的数据（比如光照、阴影、光的颜色等等），这些数据可以被用来计算最终像素的颜色。
• 测试与混合
  • 在所有对应颜色值确定以后，最终的对象将会被传到最后一个阶段，我们叫做Alpha测试和混合(Blending)阶段。这个阶段检测片段的对应的深度（和模板(Stencil)）值，用它们来判断这个像素是其它物体的前面还是后面，决定是否应该丢弃。这个阶段也会检查alpha值（alpha值定义了一个物体的透明度）并对物体进行混合(Blend)。所以，即使在片段着色器中计算出来了一个像素输出的颜色，在渲染多个三角形的时候最后的像素颜色也可能完全不同。

为什么DrawCall多了会影响帧率？

DrawCall：CPU调用图形编程接口。

• CPU会把大量时间花费在提交DrawCall命令上。（CPU在每次DrawCall前会做准备工作，包括向GPU发送数据、状态、命令以及检查渲染状态等）

求P点是否在三角形ABC内？

• 三角和法
• 三个小三角形PAB, PBC, PAC的面积之和 = ABC的面积
• 同向法：利用叉乘来判断P点是否在AC、CB、BA的另一点的同测。
• 重心法：

P = A + u * (C – A) + v * (B - A)
v0 = C - A，v1 = B - A，v2 = P - A。
u = ((v1•v1)(v2•v0)-(v1•v0)(v2•v1)) / ((v0•v0)(v1•v1) - (v0•v1)(v1•v0))
v = ((v0•v0)(v2•v1)-(v0•v1)(v2•v0)) / ((v0•v0)(v1•v1) - (v0•v1)(v1•v0))

未完待续