语言类
volatile
易变性
所谓的易变性，在汇编层面反映出来，就是两条语句，下一条语句不会直接使用上一条语句对应的volatile变量的寄存器内容，而是重新从内存中读取。
“不可优化”特性
volatile告诉编译器，不要对我这个变量进行各种激进的优化，甚至将变量直接消除，保证程序员写在代码中的指令，一定会被执行。
顺序性
能够保证Volatile变量间的顺序性，编译器不会进行乱序优化。
C/C++ Volatile变量，与非Volatile变量之间的操作，是可能被编译器交换顺序的。
C/C++ Volatile变量间的操作，是不会被编译器交换顺序的。
哪怕将所有的变量全部都声明为volatile，哪怕杜绝了编译器的乱序优化，但是针对生成的汇编代码，CPU有可能仍旧会乱序执行指令，导致程序依赖的逻辑出错，volatile对此无能为力。
extern
在C语言中，修饰符extern用在变量或者函数的声明前，用来说明“此变量/函数是在别处定义的，要在此处引用”。
注意：
extern声明的位置对其作用域也有关系，如果是在main函数中进行声明的，则只能在main函数中调用，在其它函数中不能调用。
要调用其它文件中的函数和变量，只需把该文件用#include包含进来即可，为啥要用extern？因为用extern会加速程序的编译过程，这样能节省时间。
在C++中extern还有另外一种作用，用于指示C或者C＋＋函数的调用规范。比如在C＋＋中调用C库函数，就需要在C＋＋程序中用extern “C”声明要引用的函数。这是给链接器用的，告诉链接器在链接的时候用C函数规范来链接。主要原因是C＋＋和C程序编译完成后在目标代码中命名规则不同，用此来解决名字匹配的问题。
常用库函数
|
|
void * memcpy(void * dest,void * src,size_t n) { assert((dest != NULL) && (src != NULL)); char * dest_t = (char*)dest; char * src_f = (char*)src; while(n-- > 0) { *(dest_t++) = *(src_f++); } return dest; } |
memcpy会完成n个字节的拷贝strcpy遇到\0则结束拷贝
|
|
char * strcpy(char * dest,char * src) { if (dest = NULL || src == NULL) return NULL; char * res = dest; while(*src != '\0') { *dest = *src; dest++; src++; } *dest = '\0'; return res; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
char * strcat(char * dest,char * src) { if (dest == NULL) return NULL; if (src == NULL) return dest; char * head = dest; while(*dest != '\0') dest++; while(*src != '\0') { *dest = *src; dest++; src++; } *dest = '\0'; return head; } |
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 |
int strcmp(const char * str1,const char * str2) { assert((str1 != NULL)&&(str2!=NULL)); while((*str1 != '\0') && (str2 != '\0')) { if (*str1 == *str2) { str1++; str2++; } else { if (*str1 > *str2) return 1; else return -1; } } if (*str1 == '\0') && (str2 == '\0') return 0; else if (*str1 == '\0') && (str2 != '\0') return -1; else return 1; } |
|
|
size_t strlen(const char * str) { assert(str != NULL); int num = 0; while(*str != '\0') { str++; num++; } return num; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
const char* strstr(const char * str1,const char * str2) { if (str1 == NULL || str2 == NULL) return NULL; const char * temp = str1; const char * res = str2; while (*str1 != '\0') { temp = str1; res = str2; while(*temp == *res) { temp++; res++; } if (*res == '\0') return str1; str1++; } return NULL; } |
STL六大组件
container（容器） 通过 allocator（配置器） 取得数据储存空间，algorithm（算法）通过 iterator（迭代器）存取 container（容器） 内容，functor（仿函数） 可以协助 algorithm（算法） 完成不同的策略变化，adapter（配接器） 可以修饰或套接 functor（仿函数）。
关于虚函数
当调用一个虚函数时，被执行的代码必须和调用函数的对象的动态类型相一致。编译器需要做的就是如何高效的实现提供这种特性。不同编译器实现细节也不相同。大多数编译器通过vtbl（virtual table）和vptr（virtual table pointer）来实现的。
理解：
当用一个含有虚函数的类的具象化对象完成了初始化时，这个对象的动态类型也就确定了下来，而这些信息，存放在虚函数表里面，编译器通过将这个对象的类型信息和虚函数表里面对应的动态类型信息比较，就知道调用的是哪个。
如果子类覆盖了父类的虚函数，将被放到了虚表中原来父类虚函数的位置
在多继承的情况下，每个父类都有自己的虚表。子类的成员函数被放到了第一个父类的表中
为什么 C++里访问虚函数比访问普通函数慢?
单继承时性能差不多，多继承的时候会慢
从调用过程解读性能：
通过对象的 vptr 找到类的 vtbl。这是一个简单的操作,因为编译器知道在对象内 哪里能找到 vptr(毕竟是由编译器放置的它们)。因此这个代价只是一个偏移调整(以得到 vptr)和一个指针的间接寻址(以得到 vtbl)。
找到对应 vtbl 内的指向被调用函数的指针。这也是很简单的, 因为编译器为每个虚函数在 vtbl 内分配了一个唯一的索引。这步的代价只是在 vtbl 数组内 的一个偏移。
在单继承的情况下，调用虚函数所需的代价基本上和非虚函数效率一样，在大多数计算机上它多执行了很少的一些指令，所以有很多人一概而论说虚函数性能不行是不太科学的。在多继承的情况下，由于会根据多个父类生成多个vptr，在对象里为寻找 vptr 而进行的偏移量计算会变得复杂一些，但这些并不是虚函数的性能瓶颈。
关于纯虚函数
原因：
- 为了方便使用多态特性，我们常常需要在基类中定义虚拟函数。
- 在很多情况下，基类本身生成对象是不合情理的。例如，动物作为一个基类可以派生出老虎、孔雀等子类，但动物本身生成对象明显不合常理。
意义：
定义纯虚函数的目的在于，使派生类仅仅只是继承函数的接口。
纯虚函数的意义，让所有的类对象（主要是派生类对象）都可以执行纯虚函数的动作，但类无法为纯虚函数提供一个合理的缺省实现。所以类纯虚函数的声明就是在告诉子类的设计者，“你必须提供一个纯虚函数的实现，但我不知道你会怎样实现它”。
关于虚析构函数
一般情况下类的析构函数里面都是释放内存资源，而析构函数不被调用的话就会造成内存泄漏。这样做是为了当用一个基类的指针删除一个派生类的对象时，派生类的析构函数会被调用。
当然，并不是要把所有类的析构函数都写成虚函数。因为当类里面有虚函数的时候，编译器会给类添加一个虚函数表，里面来存放虚函数指针，这样就会增加类的存储空间。所以，只有当一个类被用来作为基类的时候，才把析构函数写成虚函数。
操作系统
Linux虚拟内存的实现需要6种机制的支持：
- 地址映射机制
- 内存分配回收机制
- 缓存和刷新机制
- 请求页机制
- 交换机制
- 内存共享机制
内存管理程序通过映射机制把用户程序的逻辑地址映射到物理地址。当用户程序运行时，如果发现程序中要用的虚地址没有对应的物理内存，就发出了请求页要求。如果有空闲的内存可供分配，就请求分配内存(于是用到了内存的分配和回收)，并把正在使用的物理页记录在缓存中(使用了缓存机制)。如果没有足够的内存可供分配，那么就调用交换机制；腾出一部分内存。另外，在地址映射中要通过TLB(翻译后援存储器)来寻找物理页；交换机制中也要用到交换缓存，并且把物理页内容交换到交换文件中，也要修改页表来映射文件地址。
大小端
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 |
//c程序辨别系统是16位or32位 法一：int k=~0; if((unsigned int)k >63356) cout<<"at least 32bits"<<endl; else cout<<"16 bits"<<endl; 法二：//32为系统 int i=65536; cout<<i<<endl; int j=65535; cout<<j<<endl; //c程序辨别系统是大端or小端字节序 1) Little-Endian就是低位字节排放在内存的低地址端，高位字节排放在内存的高地址端。 2) Big-Endian就是高位字节排放在内存的低地址端，低位字节排放在内存的高地址端。 举一个例子，比如数字0x12 34 56 78在内存中的表示形式为： 1)大端模式： 低地址 -----------------> 高地址 0x12 | 0x34 | 0x56 | 0x78 2)小端模式： 低地址 ------------------> 高地址 0x78 | 0x56 | 0x34 | 0x12 32bit宽的数0x12345678在Little-endian模式以及Big-endian模式）CPU内存中的存放方式（假设从地址0x4000开始存放）为： 内存地址 小端模式存放内容 大端模式存放内容 0x4000 0x78 0x12 0x4001 0x56 0x34 0x4002 0x34 0x56 0x4003 0x12 0x78 4)大端小端没有谁优谁劣，各自优势便是对方劣势： 小端模式 ：强制转换数据不需要调整字节内容，1、2、4字节的存储方式一样。 大端模式 ：符号位的判定固定为第一个字节，容易判断正负。 |
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 |
BOOL IsBigEndian() { int a = 0x1234; char b = *(char *)&a; //通过将int强制类型转换成char单字节，通过判断起始存储位置。即等于 取b等于a的低地址部分 if( b == 0x12) { return TRUE; } return FALSE; } 联合体union的存放顺序是所有成员都从低地址开始存放，利用该特性可以轻松地获得了CPU对内存采用Little-endian还是Big-endian模式读写： BOOL IsBigEndian() { union NUM { int a; char b; }num; num.a = 0x1234; if( num.b == 0x12 ) { return TRUE; } return FALSE; } 一般操作系统都是小端，而通讯协议是大端的。 常见CPU的字节序 Big Endian : PowerPC、IBM、Sun Little Endian : x86、DEC ARM既可以工作在大端模式，也可以工作在小端模式。 |
信号
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
信号机制是进程之间相互传递消息的一种方法，信号全称为软中断信号，也有人称作软中断。 进程之间可以互相通过系统调用kill发送软中断信号。 SIGHUP 1 A 终端挂起或者控制进程终止 SIGINT 2 A 键盘中断（如break键被按下） SIGQUIT 3 C 键盘的退出键被按下 SIGILL 4 C 非法指令 SIGABRT 6 C 由abort(3)发出的退出指令 SIGFPE 8 C 浮点异常 SIGKILL 9 AEF Kill信号 SIGSEGV 11 C 无效的内存引用 SIGPIPE 13 A 管道破裂: 写一个没有读端口的管道 信号机制是异步的；当一个进程接收到一个信号时，它会立刻处理这个信号，而不会等待当前函数甚至当前一行代码结束运行。信号有几十种，分别代表着不同的意义。信号之间依靠它们的值来区分，但是通常在程序中使用信号的名字来表示一个信号。在Linux系统中，这些信号和以它们的名称命名的常量均定义在/usr/include/bits/signum.h文件中。（通常程序中不需要直接包含这个头文件，而应该包含<signal.h>。） 信号事件的发生有两个来源：硬件来源(比如我们按下了键盘或者其它硬件故障)；软件来源，最常用发送信号的系统函数是kill, raise, alarm和setitimer以及sigqueue函数，软件来源还包括一些非法运算等操作。 发送信号的主要函数有：kill()、raise()、 sigqueue()、alarm()、setitimer()以及abort()。 |
|
|
进程可以通过三种方式来响应一个信号：（1）忽略信号，即对信号不做任何处理，其中，有两个信号不能忽略：SIGKILL及SIGSTOP；（2）捕捉信号。定义信号处理函数，当信号发生时，执行相应的处理函数；（3）执行缺省操作 |
守护进程
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 43 |
守护进程最重要的特性是后台运行。 1. 在后台运行。 为避免挂起控制终端将Daemon放入后台执行。方法是在进程中调用fork使父进程终止，让Daemon在子进程中后台执行。 if(pid=fork()) exit(0); //是父进程，结束父进程，子进程继续 2. 脱离控制终端，登录会话和进程组 有必要先介绍一下Linux中的进程与控制终端，登录会话和进程组之间的关系：进程属于一个进程组，进程组号（GID）就是进程组长的进程号（PID）。登录会话可以包含多个进程组。这些进程组共享一个控制终端。这个控制终端通常是创建进程的登录终端。控制终端，登录会话和进程组通常是从父进程继承下来的。我们的目的就是要摆脱它们，使之不受它们的影响。方法是在第1点的基础上，调用setsid()使进程成为会话组长： setsid(); 说明：当进程是会话组长时setsid()调用失败。但第一点已经保证进程不是会话组长。setsid()调用成功后，进程成为新的会话组长和新的进程组长，并与原来的登录会话和进程组脱离。由于会话过程对控制终端的独占性，进程同时与控制终端脱离。 3. 禁止进程重新打开控制终端 现在，进程已经成为无终端的会话组长。但它可以重新申请打开一个控制终端。可以通过使进程不再成为会话组长来禁止进程重新打开控制终端： if(pid=fork()) exit(0); //结束第一子进程，第二子进程继续（第二子进程不再是会话组长） 4. 关闭打开的文件描述符 进程从创建它的父进程那里继承了打开的文件描述符。如不关闭，将会浪费系统资源，造成进程所在的文件系统无法卸下以及引起无法预料的错误。按如下方法关闭它们： for(i=0;i 关闭打开的文件描述符close(i);> 5. 改变当前工作目录 进程活动时，其工作目录所在的文件系统不能卸下。一般需要将工作目录改变到根目录。对于需要转储核心，写运行日志的进程将工作目录改变到特定目录如 /tmpchdir("/") 6. 重设文件创建掩模 进程从创建它的父进程那里继承了文件创建掩模。它可能修改守护进程所创建的文件的存取位。为防止这一点，将文件创建掩模清除：umask(0); 7. 处理SIGCHLD信号 处理SIGCHLD信号并不是必须的。但对于某些进程，特别是服务器进程往往在请求到来时生成子进程处理请求。如果父进程不等待子进程结束，子进程将成为僵尸进程（zombie）从而占用系统资源。如果父进程等待子进程结束，将增加父进程的负担，影响服务器进程的并发性能。在Linux下可以简单地将 SIGCHLD信号的操作设为SIG_IGN。 signal(SIGCHLD,SIG_IGN); 这样，内核在子进程结束时不会产生僵尸进程。这一点与BSD4不同，BSD4下必须显式等待子进程结束才能释放僵尸进程。 |
标准库函数和系统调用
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
1、系统调用 系统调用提供的函数如open, close, read, write, ioctl等，需包含头文件unistd.h。以write为例：其函数原型为 size_t write(int fd, const void *buf, size_t nbytes)，其操作对象为文件描述符或文件句柄fd(file descriptor)，要想写一个文件，必须先以可写权限用open系统调用打开一个文件，获得所打开文件的fd，例如fd=open(/"/dev/video/", O_RDWR)。fd是一个整型值，每新打开一个文件，所获得的fd为当前最大fd加1。Linux系统默认分配了3个文件描述符值：0－standard input，1－standard output，2－standard error。 系统调用通常用于底层文件访问（low-level file access），例如在驱动程序中对设备文件的直接访问。 系统调用是操作系统相关的，因此一般没有跨操作系统的可移植性。 系统调用发生在内核空间，因此如果在用户空间的一般应用程序中使用系统调用来进行文件操作，会有用户空间到内核空间切换的开销。事实上，即使在用户空间使用库函数来对文件进行操作，因为文件总是存在于存储介质上，因此不管是读写操作，都是对硬件（存储器）的操作，都必然会引起系统调用。也就是说，库函数对文件的操作实际上是通过系统调用来实现的。例如C库函数fwrite()就是通过write()系统调用来实现的。 这样的话，使用库函数也有系统调用的开销，为什么不直接使用系统调用呢？这是因为，读写文件通常是大量的数据（这种大量是相对于底层驱动的系统调用所实现的数据操作单位而言），这时，使用库函数就可以大大减少系统调用的次数。这一结果又缘于缓冲区技术。在用户空间和内核空间，对文件操作都使用了缓冲区，例如用fwrite写文件，都是先将内容写到用户空间缓冲区，当用户空间缓冲区满或者写操作结束时，才将用户缓冲区的内容写到内核缓冲区，同样的道理，当内核缓冲区满或写结束时才将内核缓冲区内容写到文件对应的硬件媒介。 2、库函数调用 标准C库函数提供的文件操作函数如fopen, fread, fwrite, fclose,fflush, fseek等，需包含头文件stdio.h。以fwrite为例，其函数原型为size_t fwrite(const void *buffer,size_t size, size_t item_num, FILE *pf)，其操作对象为文件指针FILE *pf，要想写一个文件，必须先以可写权限用fopen函数打开一个文件，获得所打开文件的FILE结构指针pf，例如pf=fopen(/"~/proj/filename/",/"w/")。实际上，由于库函数对文件的操作最终是通过系统调用实现的，因此，每打开一个文件所获得的FILE结构指针都有一个内核空间的文件描述符fd与之对应。同样有相应的预定义的FILE指针：stdin－standard input，stdout－standard output，stderr－standard error。 库函数调用通常用于应用程序中对一般文件的访问。 库函数调用是系统无关的，因此可移植性好。 由于库函数调用是基于C库的，因此也就不可能用于内核空间的驱动程序中对设备的操作 |
海量数据
- bitmap
- Map-Reduce原理，
- BloomFilter原理
它实际上是一个很长的二进制向量和一系列随机映射函数（Hash函数）。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。Bloom Filter广泛的应用于各种需要查询的场合中，如Orocle的数据库，Google的BitTable也用了此技术。
Bloom Filter特点：
不存在漏报（False Negative），即某个元素在某个集合中，肯定能报出来。
可能存在误报（False Positive），即某个元素不在某个集合中，可能也被爆出来。
确定某个元素是否在某个集合中的代价和总的元素数目无关。
- Trie树原理、
- 单词搜索树
- B+树原理
- LSM树原理
- 大数据处理
