C++的特性与轨迹

• C++ 的特性（C++11及以上）
  • 需要在不同的平台上进行编译
  • 编译后的程序可以在操作系统上直接运行
  • 可以面对过程和面对对象两种设计方式
  • 可以直接操作本地的系统库
  • 可以直接使用操作系统提供的接口
  • 编译后仅对变量的类型进行了存储，不可以进行类似反射的操作
  • 支持无符号整型
  • 变量类型的字节长度受操作系统影响
  • 支持指针、引用、值传递
  • 没有默认提供的 GC 系统
  • 由程序员负责管理变量所储存的位置
  • 严格的 RAII
  • 支持重写、重载，包括运算符的重载
  • 多重继承
  • 支持预编译，编译宏定义
  • 支持函数指针，函数对象，lambda 表达式
• C++ 11 新增的特性
  • foreach
  • auto 自动类型推断
  • lambda 匿名函数
  • 后置返回类型
  • override 关键字
  • nullptr 代替原来的 NULL
    • 当存在 void a(int x); 和 void a(char *x) 时，若使用 a(NULL) 则会调用前者，这与通常的理解不同，而使用 a(nullptr) 则会明确的调用后者
  • 元组 tuple，可以使用 get<>() 取出其中的一个值，或者使用 tie() 装包或解包

struct 和 class

• 区别
  • struct 默认使用 public 而 class 默认使用 private
  • struct 可以直接使用 {} 进行初始化，而 class 则需要所有成员变量都是 public 的时候才可以使用

堆和栈的区别

• 操作系统角度
  • 堆是操作系统为进程所分配的空间，在 C、C++ 语言中用来存放全局变量。由程序员管理，主动申请以及释放的空间，可能会出现内存泄漏。在进程结束后，由操作系统回收
  • 栈是由编译器进行管理，由编译器进行申请，释放的空间，通常比堆要小很多，在 C、C++ 语言中，当调用一个函数时会创建一个栈，当函数结束时则会回收栈的空间
• 数据结构的角度
  • 堆是一棵完全二叉树，常见的有最大堆和最小堆，以最大堆为例，其满足二叉树中的任意一个节点的孩子节点都比此节点小。通常用来实现优先队列的效果，插入和删除的复杂度均为 O(logN)
  • 栈是一种线性数据结构，满足先进后出的特点，即最先进入的数据最后离开，常见于 DFS 中。也可以通过单调栈的方式求解一些问题。插入和删除的复杂度均为 O(1)

虚函数

• 虚函数
  • 虚函数由 virtual 标记
  • 普通的虚函数仍然需要进行实现，所有继承此类的派生类可以重新实现此函数也可以不实现
• 纯虚函数
  • 纯虚函数在普通的虚函数后，加上 =0
  • 当一个类拥有纯虚函数后，则此类变成抽象类，不可以进行实例化
  • 纯虚函数不需要实现，且所有继承自此类的派生类必须实现此函数，否则派生类也是抽象类，不可以实例化
• 虚函数的实现原理
  • 在类中保存一张虚函数表，表内保存了函数所在的代码段
  • 当其他类继承自此类时，复制一份此虚函数表。当其中的虚函数进行实现后，将虚函数表中此函数的指针指向新的函数的地址
  • 定义类的实例的时候，在类的开头保存了一个指向此虚函数表的指针，当需要调用此函数的时候，通过此指针找到对应的函数地址

静态函数和虚函数

• 静态函数和虚函数的区别
  • 静态函数在编译时就确定了运行的时机，而虚函数则是在运行的过程中动态的得知虚函数地址

vector

• 扩容规则
  • 当空间不足的时候，vector 会扩容至当前空间的 2(GCC下)/1.5(MSVC)
• 为什么这样扩容
  • 以两倍空间为例，当扩容次数为 30 次左右时，vector 的空间达到 1e9 （十亿）而通常每次扩容，都会需要在堆上重新分配空间，需要重新移动整个数组到新的空间。由此，可以得出重新分配空间的次数越少越好，同时也要节约内存的占用，因为按照此增长，其内存的重复的分配次数始终在常数范围内，所以采用了上述的扩容方式。
• MSVC下的 1.5 倍的空间相对于 GCC 下的 2 倍有什么好处和坏处
  • 好处：因为 2 倍空间下，任意一个空间都大于之前所有分配过的空间之和，这就意味着每次进行扩容的时候都需要分配一个新的空间。而在 1.5 倍下，可以重复使用之前的空间，1.5 倍相对会节约内存
  • 坏处： 1.5 倍下的重新分配次数更多，也就意味着需要更多的重新分配空间和重新移动的次数，更加浪费时间
• clear 的复杂度
  • 复杂度与已有的元素数量成线性，因为每个元素都需要析构
  • clear 后，并不会改变 vector 的容量上限，只会更新 vector 内的 size 大小

队列和堆栈的模拟

• 用两个堆栈模拟队列
  • 将两个堆栈命名为 A、B
  • 若 B 堆栈为空，则将 A 堆栈的所有值都推入 B 中
  • 若需要推入，则推入到 A 中
  • 若需要推出，则从 B 中推出
• 用两个队列模拟堆栈
  • 将两个队列命名为 A、B
  • 若需要推入，则推入到 A 中
  • 若需要弹出，则将 A 中的值除了最后一个，其他都推入到 B 中，且仅留下一个值，然后弹出这个值，并将 A、B 队列命名为 B、A 队列

四个类型转换

三个访问限制

下面这段代码最终结果是

1
2
3
4

main () {
    printf("xxx");
    fork();
}

• 为 xxxxxx
• 由于有输出缓存，实际上在 fork 的时候，并没有输出至屏幕，而是保存在缓存中，当程序结束时，将缓存中的值输出至终端，所以得到 xxxxxx

static

• static 变量的特点
  • 该变量在全局数据区分配内存
  • 未经初始化的静态全局变量会被程序自动初始化为0（自动变量的值是随机的，除非它被显式初始化）
  • 静态全局变量在声明它的整个文件都是可见的，而在文件之外是不可见的

指针和引用

• 指针和引用的区别
  • 指针有自己的内存空间，是一个变量类型，而引用没有占用内存空间，只是一个别名
  • 使用 sizeof 可以求得在 32 位操作系统下，指针的大小为 $4$ 个字节，而引用则为原对象的大小
  • 指针可以初始化为任意正整数值，而引用必须初始化为一个已经存在的变量
  • 参数传递时，指针需要先进行指针转为引用然后再使用，而引用可以直接操作原对象
  • 指针可以有 const 属性，而引用没有 const 属性
  • 指针可以重新赋值，而引用不可以更改
  • 指针可以进行多级指针，而引用只有一级
  • 指针可以引用进行 ++（自增）操作的逻辑和结果都不同
  • 当需要返回动态内存分配的对象时，需要使用指针而不是引用，因为引用可能会产生内存泄漏

平面几何问题

• 判断一个点是否在一个三角形内
  • 定义三角形为 $ \vartriangle ABC$，点为 $P$，计算 $ S{\vartriangle ABC} = S{\vartriangle ABP} + S{\vartriangle ACP} + S{\vartriangle BCP}$ 是否成立。而三角形面积可以通过割补法或者叉积求

c++智能指针

• auto_ptr（已弃用）
  • 采用所有权模式，任何一个 new 的对象只能由一个 auto_ptr 来指向，进行赋值操作会使得原来的指针丢失指向的对象
• unique_ptr
  • 与 auto_ptr 相同，但是进行赋值操作时，会直接报错，而 auto_ptr 不会
• shared_ptr
  • 共享指针，允许多个指针指向此对象，同时当所有指向此对象的指针都被析构后，此对象将会被删除
• weak_ptr
  • 弱共享指针，允许指向其他的 shared_ptr 对象，此指针不会影响 shared_ptr 的析构行为，通常用来避免相互指向问题

构造函数

• 构造函数有哪些特征
  • 名字和类名相同
  • 没有返回值
  • 生成类的自动执行，不需要调用
• 为什么构造函数不可以是虚函数
  • 因为虚函数表指针是在构造函数期间创建的，没有虚函数表就没有办法调用虚函数

析构函数

• 析构函数的作用
  • 如果一个类中有指针，且这个指针指向了一段由此类的实例请求分配的空间，那么需要由析构函数来实现对这块区域的释放，否则会造成内存泄漏
• C++ 为什么习惯把析构函数定义为虚函数
  • 当这个类需要作为父类派生的时候，如果程序得到的是此父类的指针，那么此时就无法析构子类，出现内存泄漏
• C++ 为什么默认的析构函数不是虚函数
  • 虚函数需要额外的虚函数表和虚函数表指针，对于不会派生的类而言，浪费空间

重载和覆盖

• 重载和覆盖的区别
  • 重载：两个相同的函数名，但是参数列表不同
  • 覆盖：父类创建的虚函数，派生类重新定义

锁

• C++ 中的锁类型
  • 互斥锁：对于同一个变量只允许一个线程进行读写，若不满足时则会进入阻塞，并且 CPU 不会进入忙等
  • 条件锁：当满足某个条件时，再唤醒此线程，否则一直处于阻塞状态
  • 自旋锁：不断的检查锁是否满足条件，不释放 CPU，比较耗费 CPU
  • 读写锁：允许有读锁的时候再加读锁，但是有写锁时不再能加任何锁
  • 递归锁：允许同一个线程对同一个锁进行多次加锁

new和malloc

• new 和 malloc 的区别
  • new 是一个 c++ 关键字，不需要头文件支持，而 malloc 是一个函数，需要头文件支持
  • malloc 需要给出需要的空间大小，而 new 不需要
  • new 返回的是对象的指针，而 malloc 返回的是 void* 类型的指针
  • new 分配失败时会抛出错误，而 malloc 失败时返回空指针
  • new 会调用被构造的类型的构造函数，而 malloc 只是分配内存空间
  • 可以重载 new 操作，但是不能重载 malloc 操作
• delete 和 free 的区别
  • delete 会调用析构函数，而 free 直接回收空间

C++ 编译

• 从源文件到可执行文件的过程
  • 预处理，宏定义替换
  • 编译，生成汇编代码
  • 汇编，将汇编代码转为机器代码，生成目标文件
  • 链接，将多个目标文件连接成最终可执行文件

内存管理

• C++ 的内存分布
  • 代码段：存储机器代码和字符串常量
  • 数据段：存储程序中已初始化的全局变量和静态变量
  • BSS段：存储未初始化的全局变量和静态变量，以及所有被初始化为 0 的全局变量和静态变量
  • 堆区：调用 new/malloc 函数时动态管理分配的内存，同时需要用 delete/free 来手动释放
  • 栈区：使用栈空间存储的函数的变量和返回值等
  • 映射区：存储动态链接库以及调用 mmap 函数进行的文件映射
• C++ 内存泄漏检查
  • 通过 valgrind 检查一个调试程序
  • valgrind 可以检查出内存泄漏、越界访问、未初始化内存

静态方法

• 静态方法和实例方法有何不同
  • 调用时，静态方法既可以用 类名.方法名 和 对象名.方法名，而实例方法只能用后者
  • 静态方法只能访问静态变量，而实例方法可以访问静态变量和成员变量

右值引用

• 如何确定一个值是左值还是右值
  • 提供了地址的为左值，左值可以没有值，但是一定有地址
  • 提供了值的为右值，右值可以没有地址，但是一定有值
• 右值引用的功能
  • 移动语句
  • 完美转发
• 更详细的内容见此处

C++ hash

• C++ 的内置 hash 函数的实现
  • 对于基础变量，hash 函数返回值为此变量的值，不做修改
  • 对于 string，hash 函数对每四个字节(64位操作系统下)进行位运算最终得到结果，实际的内部过程使用了两个特殊的固定值，下面是 C++ 的字符串 hash 函数的实际内部实现（C++11）

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

    inline std::size_t unaligned_load(const char *p) { std::size_t result; __builtin_memcpy(&result, p, sizeof(result)); return result; } size_t _Hash_bytes(const void *ptr, size_t len, size_t seed = 0xc70f6907UL) { const size_t m = 0x5bd1e995; size_t hash = seed ^len; const char *buf = static_cast<const char *>(ptr); // Mix 4 bytes at a time into the hash. while (len >= 4) { size_t k = unaligned_load(buf); k *= m; k ^= k >> 24; k *= m; hash *= m; hash ^= k; buf += 4; len -= 4; } // Handle the last few bytes of the input array. switch (len) { case 3: hash ^= static_cast<unsigned char>(buf[2]) << 16; [[gnu::fallthrough]]; case 2: hash ^= static_cast<unsigned char>(buf[1]) << 8; [[gnu::fallthrough]]; case 1: hash ^= static_cast<unsigned char>(buf[0]); hash *= m; }; // Do a few final mixes of the hash. hash ^= hash >> 13; hash *= m; hash ^= hash >> 15; return hash; }