C++语言模块基础

C++细节探究

模板在编译的时候是怎么编译的?

什么是模板？为什么会有模板？

继承和包含并不总是满足重用代码的需要。所以会有模板

C++的类模板是一种生成通用类声明的更好的方法。
模板怎么提供通用的类声明

方法是通过提供参数化类型，将类型名作为参数传给接收方来建立类或函数

函数模板和类模板的举例

//函数模板
template<typename T>
int compare(const T& left, const T& right) {
    if (left < right) {
        return -1; 
    }
    if (right < left) {
        return 1; 
    }
    return 0;
}

compare<int>(1, 2); //使用模板函数

// 类模板
template<class T>
    class Human {
        T t;
    public:
        Human(T test) : t(test){}
    }
Human<int>(1); //使用类模板

零值比较
- bool: if(ok)
- int: if(ok == 0)
- pointer: if(ok == null)
- float: if(ok <= 1e-5 && ok >= -1e-5)
sizeof 和 strlen的不同
- 运算符和标准库函数
- sizeof 可以运算任何类型的大小 strlen只能得到”\0”结尾的字符串的大小
- sizeof的大小要提前指定好，因为在编译期间就要确定下来
对象之间的复制(类默认赋值函数)
- 可以赋值，当存在指针成员变量时，要提前的深拷贝
- 深拷贝和浅拷贝的区别
static的作用
- 全局静态变量限制了变量的作用域，只能在本文件中被使用
- 局部静态变量由于存储在静态区，延长了变量的使用时间，只有程序结束的时候，该变量的生命周期才结束。
- 修饰类成员(变量和函数) 所有的实例共有
- 满足函数在不同调用期的通信，满足不同类对象之间的通信-> 单例模式
- static的默认值是0
结构体和类的区别
- 结构体的默认访问权限是pubic 类是private
malloc 和 new 的区别
- malloc和free 是标准库函数， new和delete是运算符
- malloc分配空间后，不能吊起构造函数， free也不能吊起构造函数； new吊起构造函数， delete调起析构函数
- malloc返回void指针， new返回对应类指针
指针和引用的区别
- 引用只是给变量起了一个别名，不占内存空间。指针是新分配了一个指针的空间
- 引用声明时必须初始化，指针可以先申明再初始化
- 引用只能指定一个变量，指针可以先指向一个变量，然后再指向另一个变量
- 引用必须指向一个变量的实体，指针可以是一个空指针
宏定义和函数的区别
- 宏定义在预编译时就替换了代码，相当于直接插入了代码，运行时不需要跳转；函数运行需要跳转
- 宏定义没有类型检查；函数有类型的检查
宏定义和const的区别
- 宏定义在预编译阶段；const在编译的阶段
- 宏没有类型检查； const有类型检查
- 没有分配空间，直接代码插入； const要占据内存空间
宏定义和typedef的区别
- 宏定义主要用于常量和复杂函数的表示；typedef主要用于类型的别名
- 编译前替换；typedef还是在编译期间
宏定义和内联函数的区别
- 内联函数也是函数，在编译期间起作用，也可以做类型检查
- 具有函数的重载等功能
- 内联函数可以作为类的成员函数使用类的保护成员和私有成员
数组名和指针的区别
- 可以将数组名理解为常量指针，所以没有自增和自减的操作
- 数组名传递给一般指针后就退化了，sizeof就计算不出整个数组的大小

面向对象基础

三大特性
- 封装性
- 继承性
- 多态性
- 模板特性(c++)
public/protected/private的区别
- public ，类的内部和外部都可以访问
- protected，只有类的内部成员或者派生类中可以访问
- private，类的内部成员访问派生类内部不可以访问
对象的存储空间
- 非静态成员的数据类型大小之和
- 编译器额外加入的虚函数指针变量，指向虚表，虚表保存的是虚函数的地址的列表
- 还有一些对齐的padding
空类的大小和有哪些成员函数？
- 空类的大小为1字节
- 成员函数有：
  - 构造函数
  - 析构函数
  - 默认拷贝函数
  - 默认赋值运算符
  - 取地址函数
构造函数和析构函数必须是基类指针吗？
- 构造函数
  - 构造函数不能是虚函数，虚函数的作用在于通过子类的指针或引用来调用父类的那个成员函数。而构造函数是在创建对象时自己主动调用的，不可能通过子类的指针或者引用去调用。
- 析构函数
  - 析构函数一般都要为虚函数，
  - 只有当析构函数为虚函数时，delete调一个基类指针的类时，才会调起对应的子类的析构函数
构造函数和析构函数的调用顺序是？
- 构造函数(从初始化列表的运行顺序可看出)
  - 基类构造函数：多层基类则先构造最上层的基类，依次向外，如果是多继承则从左到右
  - 成员变量的构造函数：先构造成员变量的构造函数，然后调用本类的构造函数
  - 派生类的构造函数
- 析构函数
  - 析构顺序与构造顺序相反
拷贝构造函数和赋值运算函数的区别？
- 拷贝构造函数是函数，赋值运算符是运算符重载。
- 拷贝构造函数会生成新的对像，赋值运算符不会
- 在形参传递的时候是调用拷贝构造函数，因为生成了本地的新对象
覆盖、隐藏和重载的区别
- 重载，在相同的类或作用域下，当函数名相同，参数不同的情况就发生了函数的重载
- 覆盖，当虚函数在派生类中对虚函数进行了实现的时候，派生类的虚函数地址对原虚函数的地址进行了覆盖
- 隐藏，派生类本来是集成了基类的成员函数，当派生类又实现了基类函数，而且这个基类成员函数还不是虚函数的情况下，就会把基类成员函数给隐藏，不管参数时候相同。
哪几种情况需要用到初始化列表
- 初始化const成员
- 初始化一个reference成员
- 调用基类的构造函数，并且该函数需要参数
- 调用数据成员对象的构造函数，而该函数需要参数

STL(标准模板库)

Vector

定义：
	vector<T> vec;
插入元素：
	vec.push_back(T);
	vec.insert(iterator, T);
删除元素：
	vec.pop_back();
	vec.erase(iterator);
修改元素:
	vec[position] = T;
遍历容器：
for(auto it = vec.begin(); it < vec.end(); it++){

}
其他：
	vec.empty();
	vec.size();
	vec.capacity();
	vec.begin();
	vec.end();

实现：

线性表，数组实现：
- 支持随机访问
- 插入删除操作需要大量的移动元素
需要连续的物理存储空间
当空间不够及 size < capacity 的时候，需要空间拓展*2

迭代器失效：

插入元素：
- 尾后插入，当size < capacity时，首迭代器不失效，其他失效。

map

实现：
- 树状结构，插入和删除操作不需要数据的复制，不连续的内存空间
- 操作复杂度和树的高度相关
红黑树的基本概念：
- 红黑树是二叉排序树
  - 左子树的所有元素都比根节点小
  - 右子树所有节点都比根节点大
  - 左右子树也都是二叉排序树
- 而且还要满足几点要求
  - 树中所有节点非黑即红
  - 根节点必须是黑色
  - 红色节点的子节点必须为黑
  - 从根到NULL的任何路径上黑节点的数量必须相同
- 查找时间都是O(logn)
- 红黑树节点的定义
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  enum Color {
  red = 0;
  black = 1;
  };
  struct RBTreeNode{
  struct RBTreeNode* left, *right, *parent;
  int key;
  int data;
  Color col;
  };
  1. 相对于平衡二叉树，平衡性稍差但是旋转次数会降低
  2. 相对于普通的二叉查找树，平衡性要好，查找效率要高

set

常用操作

unordered_set<int> st;
st.insert(1);
st.erase(1);

st.find(1);
st.count(1);

编程基础

为什么会有C++，相对于C语言的升级在哪？
- 添加了了面向对象编程
- 继承了C语言高效、简洁、快速和可移植的特点。
- 添加了泛型编程方法
C/C++语言的历史发展和必要性
条件编译#ifdef, #else, #endif作用？
- 通过#ifdef来判断，将某些具体的模块包括到要编译的内容，只判断之前是否有该宏定义
- 子程序前加#define DEBUG 用于程序调试
- 应对硬件的设置
- 条件编译可以减少被编译的语句

编译和调试

编译

预处理

宏定义的替换 #define
条件编译语句过滤代码 #ifdef
处理#include指令，插入对应的文件到指令的位置 #include
过滤所有的注释的语句
添加行号和文件名标识
保留所有的#program编译器指令 #program

编译

词法分析
- 读取源程序的字符，生成词法单元序列
语法分析
语义分析
中间语言生成汇编
目标代码生成与优化二进制代码

链接

各个源代码模块独立的被编译，然后将他们组整起来，组装的过程就是链接。将所有目标文件的代码段拼接到一起，然后将所有对符号地址的引用加以修正。

静态链接

在编译时和静态库(lib**.a)链接在一起成为完成的程序。通常静态库就是对多目标文件(.o)文件的打包。细节：静态链接被用到的目标文件都会复制到最终生成的可执行文件中。这种方式的好处是在运行时，可执行文件已尽装载完毕，速度比较快。

静态文件是对多目标文件的打包，这里介绍些打包命令。
1
2
3
gcc -c test1.c // 生成test1.c
gcc -c test2.c // 生test2.c
ar cr libtest.a test1.o test2.o
在生成可执行文件需要使用到它的时候只需要在编译时加上即可。
1
gcc -o main main.c -ltest
动态链接

多个程序都需要某个静态库，在每个程序中都需要拷贝一份，所以出现动态链接来解决这个问题。

首先打包成动态库，文件名为lib + 动态库名+ .so 后缀。编译时加上-fPIC选项，打包时加上-shared选项。
1
2
3
gcc -fPIC -c test1.c
gcc -fPIC -c test2.c
gcc -shared test1.o test2.o libtest.so
使用动态链接的用法和静态链接相同
1
gcc -o main main.c -ltest
静态链接库和动态链接库的对比
- 动态链接库运行时会先检查内存中是否存在该库的拷贝，若有则共享拷贝，标准模版库就是动态链接库。
- 动态链接库的升级更新很容易
- 静态链接库执行效率会比较高
静态联编和动态联编的区别

makefile编写

自动化编译的工具

基本规则
1
2
A:B
(tab)<command>
A是语句最后生成的文件，B是生成A所依赖的文件，比如生成test.o依赖test.c 和 test.h, 则写成 test.o:test.c test.h。接下来一行的开头必须是tab ，再往下就是实际的命令, 比如 gcc.c -c test.c -o test.o 。
变量

在文件中可以定义变量，在之后需要使用的时候只需要写一个$符号加上变量名即可。
自动寻找依赖

第一条目标即为编译输出的目标，程序会依次寻找依赖的关系，当依赖不存在时，贼寻找下面的生成目标形成隐形的依赖生成

调试

符号解析

可重定位目标文件 (relocatable file)

独立编译后的(.o)文件，其ELF文件格式包括：
- ELF头，指定文件的大小及字节序
- .text，代码段
- .rodata, 只读数据区
- .data，已初始化数据区
- .bss，未初始化数据区
- .symtab，符号表
解析符号表
- 将每个引用和文件中的符号表的一个符号定义联系起来

重定位

合并节

多个可重定向目标文件中的相同的节合并成一个完整的聚合节，例如多个目标文件的.data节合并为可执行文件的.data节。
重定位符号引用

修改全部代码节和数据节对每个符号的引用，执行正确的运行时地址。

可执行目标文件

ELF头部

描述文件的总体格式，并且包括程序的入口点，即第一条指令地址
段头部表

描述了可执行文件数据段、代码段等各段的大小、虚拟地址、段对其、执行权限等。通过段头部表描绘了虚拟存储器运行时存储映像，比如每个unix程序的代码段总从虚拟地址的Ox0804800开始。
其他段

和可重定位目标文件相同，但是完成了多个节的合并和重定位的工作

加载

克隆

新程序的执行首先要父进程fork()得到一个子进程，该子进程除了pid等标识不同其他基本均与父进程相同。
重新映射

当子进程执行自己的系统调用时，会先清空子进程现有的虚拟存储段(不再映射到父进程到各个段)，之后重新创建子进程虚拟存储器各段和可执行文件各段的映射。可理解为对复制进来的父进程页表进行重写，映射到外存中的各个段。
虚页调入

加载器跳转到入口地址_start开始执行程序，接下来的过程需要配合虚拟存储器来完成。CPU获得了指令的虚拟地址后，若该指令不再内存中，则从外存中调入。