git分布式版本控制系统
我们一般管理 同一个文件可以按照日期的先后命名 来管理文件。而且多人修改一个项目需要人为手工合并。
SVN是集中式版本控制系统，每个人电脑上只有一个 文件副本，每次修改前都需要去 中央服务器下载最新的文件版本，修改完毕后提交给中央服务器，存在单点故障问题。
git是分布式版本控制系统，每个电脑都有一个git仓库，Git 本质上是每个电脑上的 一串提交记录commit（快照链），分支 master 其实是一个指向某个 commit（如 C）的指针：
| 创建分支 | git branch dev |
| 切换分支 |
|
| 删除分支 | git branch -d dev |
| 合并分支 | git merge dev |
Git 的三个核心结构
| 名称 | 描述 |
|---|---|
| 工作区（Working Directory） | 当前你编辑的项目文件 |
| 暂存区（Index / Stage） | Git 即将提交的变更列表（你用 git add 添加的） |
| 本地仓库（Repository） | 你提交（git commit）后永久保存快照的地方 |
1.源程序到可执行程序的阶段
1.预处理
#include头文件包含，#define定义标识符和宏替换，注释的删除。__LINE__ 和 __FILE__ 是 C/C++ 中的两个预定义宏，也在该阶段进行替换。
2.编译
词法分析，语法分析，语义分析，汇总每个文件的符号。
静态链接编译时将所有依赖的库代码复制到可执行文件中。
动态链接编译时只记录依赖库的信息。
3.汇编
生成每个文件符号表，为他们分配地址
4.链接
默认采用动态链接。
合并段表。在链接过程中就会把每个obj文件对应的段通过某种规则合并起来。
合并符号表。将每个源文件的符号表进行合并，若不同源文件的符号表中出现了相同的符号，则取合法的地址为合并后的地址（重定位）。
如果你是在开发嵌入式系统或要求部署便捷性，通常更倾向于静态链接；如果希望节省磁盘空间并且能灵活更新库，则偏向动态链接。同时动态链接可以通过更新共享库来修复漏洞或增加功能
2.#defline定义宏和标识符
#define MAX 100
#define SQUARE(x) ((x)*(x)*MAX)宏就是将参数 插入到文本之中
3. topk问题，求解数组中第k大的数字
1.建立 包含k个数字的小堆，O(logK)，后面的数字依次入堆，堆顶元素。
2. 快排过程中，每次前面m个数字比pivot小，看left - begin + 1与k的大小关系再做比较。
4.环形链表问题
判断是否有环：
if (fast == slow)//相遇
{
return true;
}找到相遇点：L=nc-x，所以推断该点一定是相遇点。
if (fast == slow)//相遇
{
struct ListNode* meet = fast;//相遇点
while (head != meet)
{
head = head->next;//一个指针从出发点开始走
meet = meet->next;//一个指针从相遇点开始走
}
return meet;//两个指针相遇，返回当前结点
}
5.排序问题
希尔排序：选择gap值 (N/2)，间隔gap的值进行排序，再缩小gap。
堆排序：从最后一个非叶子节点向前采用 “向下调整算法”，时间复杂度 O(N),然后交换根节点和最后一个节点，再对根节点使用向下调整算法。
//堆排序
void HeapSort(int* a, int n)
{
//排升序，建大堆
//从第一个非叶子结点开始向下调整，一直到根
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
int end = n - 1;//记录堆的最后一个数据的下标
while (end)
{
Swap(&a[0], &a[end]);//将堆顶的数据和堆的最后一个数据交换
AdjustDown(a, end, 0);//对根进行一次向下调整
end--;//堆的最后一个数据的下标减一
}
}计数排序：准备一个 count数组，统计每个数字出现的次数。然后按照 a[i++] = j + min;放回原来数组中。
6.内部类
内部类是外部类的友元类，同时在外部函数中定义需要A::B b，当然在A内部不需要
1、内部类可以定义在外部类的public、private以及protected这三个区域中的任一区域。受类域限制
2、内部类可以直接访问外部类中的static、枚举成员，不需要外部类的对象/类名。
3、外部类的大小与内部类的大小无关。
7.动态内存管理
new T[N]的原理
1、调用operator new[ ]函数，在operator new[ ]函数中实际调用operator new函数完成N个对象空间的申请。
2、在申请的空间上执行N次构造函数。
delete[ ] 的原理
1、在空间上执行N次析构函数，完成N个对象中资源的清理。
2、调用operator delete[ ]函数，在operator delete[ ]函数中实际调用operator delete函数完成N个对象空间的释放。
malloc/free和new/delete的区别？
共同点：
都是从堆上申请空间，并且需要用户手动释放。
不同点：
- 1、malloc和free是函数，new和delete是操作符。
- 2、malloc申请的空间不会初始化，new申请的空间会初始化。
- 3、malloc申请空间时，需要手动计算空间大小并传递，new只需在其后跟上空间的类型即可。
- 4、malloc的返回值是void*，在使用时必须强转，new不需要，因为new后跟的是空间的类型。
- 5、malloc申请失败时，返回的是NULL，因此使用时必须判空，new不需要，但是new需要捕获异常。他会抛出 bad_alloc异常。
- 6、申请自定义类型对象时，malloc/free只会开辟空间，不会调用构造函数和析构函数，而new在申请空间后会调用构造函数完成对象的初始化，delete在释放空间前会调用析构函数完成空间中资源的清理。
8.string，vector，list序列容器
string
string在底层实际是：basic_string模板类的别名，typedef basic_string<char, char_traits, allocator> string;
实现string需要一个size，一个capacity，一个堆区指针
vs下string的结构:
string总共占28个字节，内部结构稍微复杂一点
先是一个虚基类指针：4个字节.
再是有一个联合体，联合体用来定义string中字符串的存储空间：当字符串长度小于15（数组尾部存储一个\0字符）时，使用内部固定的字符数组来存放当字符串长度大于等于16时，从堆上开辟空间。故其一共16个字节.
大多数情况下字符串的长度都小于16，那string对象创建好之后，内部已经有了16个字符数组的固定空间，不需要通过堆创建，效率高
union _Bxty
{ // storage for small buffer or pointer to larger one
value_type _Buf[_BUF_SIZE]; // 16字节缓冲区，当string长度小于15，用这个字符数组保存string
pointer _Ptr;
char _Alias[_BUF_SIZE]; // to permit aliasing
} _Bx;最后还有一个size_t字段保存字符串长度，一个size_t字段保存从堆上开辟空间总的容量。
一共就是4+16+4+4=28.,所以我们vs平台下我们sizeof一个string对象的大小是28
而g++下string的结构：
G++下，string是通过写时拷贝实现的，string对象总共占4个字节，内部只包含了一个指针，该指针将来指向一块堆空间，内部包含了如下字段：
1.空间总大小 2.字符串有效长度 3.引用计数 4.指向堆空间的指针，用来存储字符串
vector
迭代器是原生指针或者对指针进行封装，然后在类的内部进行typedef。而reverse迭代器是按照适配器模式适配出来，传入原生迭代器，适配reverse迭代器。const迭代器传入const类型即可。
template <class T>
struct _vector_reverse_iterator
{
typedef _vector_reverse_iterator<T> self;
_vector_reverse_iterator(T *ptr=nullptr)
:_ptr(ptr)
{
}
T& operator*()
{
return *_ptr;
}
//重载前置++
T* &operator++()
{
_ptr = _ptr - 1;
return _ptr;
}
T* operator++(int)
{
T*tmp = _ptr;
_ptr = _ptr - 1;
return tmp;
}
bool operator!=(self it)
{
return _ptr != it._ptr;
}
T* _ptr;
};迭代器失效 是当出现增删操作时，迭代器就可能失效了。使用迭代器时，永远记住一句话：每次使用前，对迭代器进行重新赋值。
list
list是一种可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立结点当中，在结点中通过指针指向其前一个元素和后一个元素。
与其他容器相比，list通常在任意位置进行插入、删除元素的执行效率更高。它比vector多了头部删除和头部插入的接口。
9.queue，stack，priority_queue
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque容器，容器适配器是直接调用 其余容器中的方法实现。
stack和queue既可以使用顺序表实现，也可以使用链表实现。在这里我们若是定义一个stack，并指定使用vector容器，则定义出来的stack实际上就是对vector容器进行了包装。记住：类模板加指定类型才是具体的类。
priority_queue
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中的元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。它也是容器适配器。
10.函数与类模板
模板就是template加上<class T>,T就是模板参数。 模板不支持分离编译，即.h文件和.cpp文件分开写是不支持的。
普通模板：
template<class T>
void swap(T&a,T&b)非类型模板参数：
template<class T, size_t N> //N：非类型模板参数
class StaticArray
{
public:
size_t arraysize()
{
return N;
}
private:
T _array[N]; //利用非类型模板参数指定静态数组的大小
};
函数模板特化意义不大，类模板特化如下：（需要原先有一个类模板）
//对于T1是double，T2是int时进行特化
template<>
class Dragon<double, int>
{
public:
//构造函数
Dragon()
{
cout << "Dragon<double, int>" << endl;
}
private:
double _D1;
int _D2;
};
11 .二叉搜索树
二叉搜索树又称为二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树,左子树严格小于根节点的值，右子树节点严格大于根节点的值。 包含一个节点类和一个Tree类。
AVL树可以是一棵空树，也可以是具有以下性质的一棵二叉搜索树，左右两端的高度差不超过1.
平衡因子bf=右子树高度-左子树高度
AVL树插入结点时有以下三个步骤：
- 按照二叉搜索树的插入方法，（parent和cur不断往下搜索），找到待插入位置。
- 找到待插入位置后，将待插入结点插入到树中。
- 如果父亲平衡因子为0，则break，如果bf==1或者-1，则向上更新平衡因子，如果bf==2或者-2，则需要进行旋转，旋转之后直接break，不需要再向上更新。主要看插入节点的parent的平衡因子。
我们可以将旋转处理分为以下四类：
- 当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋。
- 当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋。
红黑树
红黑树是一种二叉搜索树，但在每个结点上增加了一个存储位用于表示结点的颜色，这个颜色可以是红色的，也可以是黑色的，因此我们称之为红黑树。
红黑树的节点定义如下：
template<class K, class V>
struct RBTreeNode
{
//三叉链
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
//存储的键值对
pair<K, V> _kv;
//结点的颜色
int _col; //红/黑
//构造函数
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
红黑树插入结点的逻辑分为三步：
- 按二叉搜索树的插入方法，找到待插入位置。
- 将待插入结点插入到树中。
- 若插入结点的父结点是红色的，则需要对红黑树进行调整。
红黑树调整时具体应该如何调整，主要是看插入结点的叔叔（插入结点的父结点的兄弟结点），根据插入结点叔叔的不同，可将红黑树的调整分为三种情况。
情况一：插入结点的叔叔存在，且叔叔的颜色是红色。
此时为了避免出现连续的红色结点，我们可以将父结点变黑，但为了保持每条路径黑色结点的数目不变，因此我们还需要将祖父结点变红，再将叔叔变黑。这样一来既保持了每条路径黑色结点的数目不变，也解决了连续红色结点的问题。 此时父亲变黑，还需要继续往上递归。
情况二三：插入结点的叔叔存在，且叔叔的颜色是黑色或者叔叔节点不存在
需要先旋转再变色。
红黑树的封装：
node存储了 T类型的data。RBTree<K,T,KeyOfT,Compare>存储一个root, 因为提供了find(K key)和insert(T data)的接口，后面map与set需要传给这个红黑树对应的参数，同时map与set还需要实现迭代器，其
map与set
底层红黑树，set 的红黑树节点是key，map 的红黑树节点是pair。这两个都不允许键值冗余。
map的插入：
pair<iterator,bool> insert (const value_type& val);
[ ]运算符重载函数的参数就是一个key值，返回值是 树中节点的 mapped_type类型。
mapped_type& operator[] (const key_type& k)
{
//1、调用insert函数插入键值对
pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
//2、拿出从insert函数获取到的迭代器
iterator it = ret.first;
//3、返回该迭代器位置元素的值value
return it->second;
}
unordered_map和unordered
底层哈希表，只支持前向遍历，哈希函数可使用除留余数法，解决哈希冲突可以使用 开散列解决。字符串转成整数的方式有 BKDRHash、APHash 和 DJBHash。还有位图与布隆过滤器等。
12. 继承与多态
访问限定符和继承方式 有以下三种：
- public访问
- protected访问
- private访问
而基类的private成员在派生类当中不可见。在使用继承的时候也可以不指定继承方式，使用关键字class时默认的继承方式是private，使用struct时默认的继承方式是public。
继承中的作用域
在继承体系中的基类和派生类都有独立的作用域。若子类和父类中有同名成员，子类成员将屏蔽父类对同名成员的直接访问，这种情况叫隐藏，也叫重定义。
父类中的fun和子类中的fun不是构成函数重载，因为函数重载要求两个函数在同一作用域，而此时这两个fun函数并不在同一作用域。为了避免类似问题，实际在继承体系当中最好不要定义同名的成员。
派生类的六个默认成员函数
创建派生类对象时是先创建的基类成员再创建的派生类成员，编译器为了保证析构时先析构派生类成员再析构基类成员的顺序析构，所以编译器会在派生类的析构函数被调用后自动调用基类的析构函数。
若基类当中定义了一个static静态成员变量，则在整个继承体系里面只有一个该静态成员。无论派生出多少个子类，都只有一个static成员实例。
菱形继承的解决
虚拟继承 会改变BC的对象模型，其第一个数据为 虚基类指针。
D类对象当中的_a成员被放到了最后，而在原来存放两个_a成员的位置变成了两个指针，这两个指针叫虚基表指针，它们分别指向一个虚基表。
虚基表中包含两个数据，第一个数据是为多态的虚表预留的存偏移量的位置（这里我们不必关心），第二个数据就是当前类对象位置距离公共虚基类的偏移量。
也就是说，这两个指针经过一系列的计算，最终都可以找到成员_a。
多态
一旦定义了virtual函数，则对象模型会有虚函数表。
基类和派生类对象的虚表模型如下：
在单继承关系当中，派生类的虚表生成过程如下：
- 继承基类的虚表内容到派生类的虚表。
- 对派生类重写了的虚函数地址进行覆盖，比如func1。
- 虚表当中新增派生类当中新的虚函数地址，比如func3和func4。
13.左值与右值引用
- 左值是一个表示数据的表达式，如变量名或解引用的指针。
- 右值本质就是一个临时变量或常量值，比如代码中的10就是常量值，表达式x+y和函数fmin的返回值就是临时变量，这些都叫做右值。
左值是可以进行取地址，右值是不能取地址的， 不能作为赋值语句的左边，给右值进行引用之后，会导致右值存储到一个特定位置，这个引用就变成左值了，从而可以取地址。
C++11新增 移动构造和移动赋值
string(string&& s)
:_str(nullptr)
, _size(0)
, _capacity(0)
{
cout << "string(string&& s) -- 移动构造" << endl;
swap(s);
}
C++11新增 右值引用版本的插入函数
实现内部需要使用完美转发（将何种引用类型进行完美转发）。模板参数T中的T&& t类型表示万能引用，既能接收左值，也能接收右值。
template<class T>
void WanNengYinYong(T&& t)
{
//完美转发
Func(std::forward<T>(t));
}14.模板的可变参数
可以看成一种或多种特定类型 Args... ，看成 T去使用。
int printf ( const char * format, ... );
template<class ...Args>
void func(Args ...args)
{
}emplace和emplace_back等接口中使用，传参数包可以直接构造底层节点，减少拷贝。
传参数包时使用()进行传递，会自动展开参数包。
int main()
{
list<pair<int, string>> mylist;
pair<int, string> kv(10, "111");
mylist.push_back({ 30, "333" }); //列表初始化
mylist.emplace_back(kv); //传左值 构造+拷贝
mylist.emplace_back(pair<int, string>(40, "444")); //传右值 构造+移动构造
mylist.emplace_back(50, "555"); //传参数包，高效，直接构造底层节点，无拷贝或者移动构造
return 0;
}emplace系列接口的工作流程如下：
空间配置器开辟空间，对空间进行初始化，使用定位new传入用户参数 进行构造底层node，将node插入对应数据结构当中。
lambda表达式
它是一个匿名函数。
语法形式：[]()-> {}, 其中函数体和捕获列表必须要有，可以使用传值或者传引用的方式捕捉外部变量。lambda表达式需要被调用。
int main()
{
int a = 10, b = 20;
auto Swap = [&]
{
int tmp = a;
a = b;
b = tmp;
};
Swap(); //调用，交换a和b
return 0;
}
lambda表达式的底层原理
实际编译器在底层对于lambda表达式的处理方式，完全就是按照函数对象的方式处理的。函数对象就是我们平常所说的仿函数，就是在类中对()运算符进行了重载的类对象。