经典算法
未读概念二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
简单来说，AVL树的任何一个节点作为根节点来看的话，它左右子树的最高层数和最低层数差值只能小于等于1
AVL树的实现由于要实现AVL树的增删改查，所以定义AVL树的节点，就需要定义parent，否则插入节点时，不知道要链接到树里面哪个节点下面。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505 ...
经典书籍学习
未读C++一直以来都包含一些可以被用来进行编译器计算的简单方法。模板则进一步增加了编译器计算的可能性，而且该语言进一步的发展通常也都是在这一工具箱里进行的。比较简单的情况是，可以通过它来决定是否启用某个模板，或者在多个模板之间做选择。不 过如果有足够多的信息，编译器甚至可以计算控制流的结果。
模板元编程模板的实例化发生在编译期间（而动态语言的泛型是在程序运行期间决定的）。事实证明 C++模板的某些特性可以和实例化过程相结合，这样就产生了一种 C++自己内部的原始递归 的“编程语言”。因此模板可以用来“计算一个程序的结果”。
下面的代码在编译期间就能判断一个数是不是质数：
1234567891011121314151617181920template<unsigned p, unsigned d> // p: number to check, d: current divisor struct DoIsPrime { static constexpr bool value=(p%d!=0)&&DoIsPrime<p,d-1>::va ...
I/O复用使得程序能够同时监听多个文件描述符，这对提高程序的性能至关重要
客户端程序程序要同时处理多个socket
要同时处理用户输入和网络连接
TCP服务器要同时处理监听socket和监听
需要指出的是，I/O复用虽然能同时监听多个文件描述符，但它本身是阻塞的。并且当多个文件描述符同时就绪时，如果不采取额外的措施，程序就只能按顺序依次处理其中的每一个文件描述符，这使得服务器程序看起来像是串行工作的。如果要实现并发，只能使用多进程或多线程等编程手段。
本章只讨论epoll
epoll系列系统调用内核事件表epoll是Linux特有的I/O复用函数。它在实现和使用上与select、poll有很大差异。首先，epoll使用一组函数来完成任务，而不是单个函数。其次，epoll把用户关心的文件描述符上的事件放在内核里的一个事件表中，从而无须像select和poll那样每次调用都要重复传人文件描述符集或事件集。但epoll需要使用一个额外的文件描述符，来唯一标识内核中的这个事件表。这个文件描述符使用如下epoll_create函数来创建:
12#include <sys/epoll.h ...
题目给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：
0 表示草地。
1 表示着火的格子。
2 表示一座墙，你跟火都不能通过这个格子。
一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟，你可以移动到 相邻 的草地格子。每次你移动 之后 ，着火的格子会扩散到所有不是墙的 相邻 格子。
请你返回你在初始位置可以停留的 最多 分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你 总是 能到达安全屋，请你返回 109 。
注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。
如果两个格子有共同边，那么它们为 相邻 格子。
提示：
m == grid.length
n == grid[i].length
2 <= m, n <= 300
4 <= m * n <= 2 * 104
grid[i][j] 是 0 ，1 或者 2 。
grid[0][0] ...
经典算法
未读介绍队列具有先进先出的特性，添加元素只能在队尾插入，删除只能删除队首元素。
优先级队列出队只能是队列中优先级最高的元素，而不是队首的元素。
出队后优先级队列需要重新维护。
因此，优先级队列和堆很类似。
优先级队列的定义12template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;
123456//不写后面两个参数默认为vector，lesspriority_queue<int> pq1;//建立一个优先级队列(大堆)，数据类型是int，利用vector容器实现，less（降序）实现priority_queue<int, vector<int>, less<int>> pq2;//建立一个优先级队列(小堆)，数据类型是int，利用vector容器实现，greater（降序）实现priority_queue<in ...
从一开始，C++就提供了按值传递（call-by-value）和按引用传递（call-by-reference）两种参 数传递方式，但是具体该怎么选择，有时并不容易确定：通常对复杂类型用按引用传递的成本更低，但是也更复杂。C++11 又引入了移动语义（movesemantics），也就是说又多了一 种按引用传递的方式。
按值传递当按值传递时，原则上所有参数都会被拷贝，因此每一个参数都会是被传递实参的一份拷贝，对于class对象，会通过class拷贝构造函数去初始化
调用拷贝构造函数成本会很高，我们可以通过移动语义去优化，如下所示：
12345template<typename T> void printV (T arg) { // ...}
参数arg会变成是残的一次拷贝，但是不是所有情况都回调用拷贝构造函数：
123456std::string returnString(); std::string s = "hi"; printV(s); //copy constructor printV(std::string("hi ...
这一章是全书的核心，也是后续章节的总览，在这一章节中，我们将服务器解构为如下三个主要模块：
I/O处理单元 四种I/O模型和两种高效事件处理模式
逻辑单元 本章将介绍逻辑单元的两种高效并发模式以及高效的逻辑处理方式：有限状态机
存储单元 本章不讨论存储单元
服务器模型C/S模型TCP/IP协议在设计和实现上并没有客户端和服务端的概念，在通信过程中所有机器都是对等的，由于资源都被资源提供者垄断，所以所有网络应用几乎都很自然的采用了C/S模型，如下图所示：
CS模型的逻辑很简单。服务器启动后，首先创建一个（或多个）监听socket，并调用 bind函数将其绑定到服务器感兴趣的端口上，然后调用listen函数等待客户连接。服务器稳定运行之后，客户端就可以调用connect 函数向服务器发起连接了。由于客户连接请求是随机到达的异步事件，服务器需要使用某种IO模型来监听这一事件。IO模型有多种，下图中，服务器使用的是I/O复用技术之一的select系统调用。当监听到连接请求后，服务器就调用accept 函数接受它，并分配一个逻辑单元为新的连接服务。逻辑单元可以是新创建的子进程、子线程或者其 ...
除了网络通信外，服务器程序还需要考虑其他细节问题，比如：
Linux服务器程序一般以后台进程形式进行，又称守护进程，没有控制终端，因而不会意外接收到用户输入，父进程通常为init进程
Linux服务器通常有一套日志系统，能输出日志到文件
Linux服务器程序一般以某个专门的非root身份运行，比如mysqld/httpd等后台进程，分别拥有自己的运行账户
Linux服务器程序通常可配置
Linux通常会启动时生成一个PID文件存入目录中，记录该后台进程的PID
Linux服务器程序通常要考虑系统资源和限制，预测自身能承受多大负荷
日志用户信息用户信息对于服务器程序的安全性来说是很重要的，比如大部分服务器就必须以root身份启动，但不能以root身份运行。下面这一组函数可以获取和设置当前进程的真实用户ID(UID)、有效用户ID (EUID)、真实组ID(GID）和有效组ID （EGID):
进程间关系进程组Linux下每个进程都隶属于一个进程组，因此它们除了PID信息外，还有进程组ID(PGID)。我们可以用如下函数来获取指定进程的PGID:
12#include <uni ...
移动语义（movesemantics）是 C++11 引入的一个重要特性。在 copy 或者赋值的时候，可以 通过它将源对象中的内部资源 move（“steal”）到目标对象，而不是 copy 这些内容。当然 这样做的前提是源对象不在需要这些内部资源或者状态（因为源对象将会被丢弃）。移动语义对模板的设计有重要影响，在泛型代码中也引入了一些特殊的规则来支持移动语义。本章将会介绍移动语义这一特性。
完美转发假设希望实现的泛型代码可以将被传递参数的基本特性转发出去：
可变对象被转发之后依然可变
Const 对象被转发之后依然是 const 的
可移动对象（可以从中窃取资源的对象）被转发之后依然是可移动的。
不适用模板的时候，达成这一目的需要对这三种情况分别编程，如下所示是将调用f()时传递的参数转发给g()：
1234567891011121314151617181920212223242526272829303132333435363738#include <utility> #include <iostream> class X { … } ...
