Hashtable

三种解决冲突的方法

• 线性探测：当hash之后遇到冲突了，就在下一个位置进行寻找。问题是会遇到聚集。

• 二次探测：原先遇到冲突，在寻找下一个空位时是按照这样的顺序：H+1,H+2...H+n;而二次探测则是：H+1^2,H+22...H+n^2。

• 开链：在每个槽中维持一个链表，hash到同一个槽时就插入链表中。SGI的stl就是用这种方式。但hashtable维持的链不是stl的list，而是自行维护的__hashtable_node

hashtable的迭代器

迭代器的前进操作是从当前节点出发，前进一个位置，如果目前节点恰好是list的尾端，就进入下一个buckets内。注意，hashtable没有后退操作。

hashtable的数据结构

默认使用std::alloc。

1
2
3

template <class Value, class Key, class HashFun, 
            class ExtractKey, class EqualKey, class Alloc = alloc>
class hashtable{}

虽然使用开链法不需要指定table的大小为质数，但SGI stl还是使用了质数。做法就是提供一个函数用以查询最接近于某数n,但大于某数n的质数。

hashtable的构造与内存管理

由这一段代码可知，加入我们需要50个节点，它会返回53个节点（质数）：

1
2
3
4
5

void initialize_buckets(size_type n)
{
    const size_type n_buckets = next_size(n);
    ...
}

进行插入操作时，会判断是否需要重建（resize）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

...::resize(size_type num_elementsz_hint)
{
    //比较新老的size
    const size_type old_n = buckets.size();
    if (num_elementsz_hint > old_n) { //如果新的size比较大
        const size_type n = next_size(num_elementsz_hint);
        if (n > old_n) {
            vector<node*, A> tmp(n, (node*) 0);
            //处理每一个旧的buckets
            //首先是获取bucket的起始节点
            //迭代地将每个节点插在tmp（也就是新的buckets）的起始位置
        }
    }
}

hashfunction

在使用hashfunction时，SGI将其封装成bkt_num()，再由它来调用hash function。通常来说，stl只对char,long,int,short等进行处理。如果要处理其它类型的，必须要提供hashfunction，比如hash

#copy constructor 的建构操作

在以下的三种情况下，会以一个对象的内容去初始化另外一个对象：

• 明确的初始化操作，如 X xx = x;
• 对象被当做函数参数传入函数中；
• 函数返回一个对象时；

形式：

1
2
3

X::X(const X& x);
//可以是多参数模式，但第二个参数及其之后的参数都要以默认值提供
Y::Y(const Y& y, int x = 0);

Default Memberwise Initialization

如果一个类没有显式的定义拷贝构造函数，那么在发送以其它对象进行初始化就会进行所谓的default memberwise initialization行为。也就是把内部的数据成员的值一个一个地拷贝都被初始化的类对象中，如果其中有其他类的对象成员，那么就会递归地对该类进行default memberwise initialization。

而所谓的memberwise initialization分为两种：Bitwise Copy and Copy Constructor。

Bitwise Copy Semantics

在C++中，默认进行的就是Bitwise Copy。例如这种情况只包含原生的数据成员，就是进行Bitwise Copy：

1
2
3
4
5
6
7
8

Class Word {
public:
    Word(const char* );
    ~Word(){delete []str;}
private:
    int cnt;
    char *str;
};

但这种情况下，会出现的问题就是：由于只是单纯地拷贝指针的值，在进行拷贝之后，会出现两个对象的内部的指针指向了同一块内存。如果某个对象被销毁了，那么指针所指向的内存也回收了。这样另外一个对象的指针就变成了野指针。

不要Bitwise Copy Semantics

在以下的情况下，一个类不表现出Bitwise Copy Semantics：

• 当class内含一个member object，而后者的class声明有一个copy constructor时（不论是用户自己定义的，还是编译器生成的）
• 当class继承自一个base class而后者存在一个copy constructor时（再次强调，不论是显示声明或编译器合成）
• 当class声明了一个或多个virtual functions时
• 当class派生自一个继承串链时，其中有一个或多个virtual base classes时

前两种操作，必须把成员对象或者基类对象的拷贝构造代码插入到合成的拷贝构造函数中；

至于后面两种情况

重新设定virtual table的指针

由于如果类中有虚函数，那么需要为该类增加一个虚表，并且为该类的每个对象增加一个指针，指向虚表。

这就是为什么编译器需要合成一个拷贝构造函数，主要目的就是为了为新的对象增加一个指针。

这样可以避免了这种情况，子啊这种情况中，base内含的指针应该是指向基类的虚表，如果是Bitwise Copy，那就变成派生类的虚表了

1

Base base = derived;

virtual base class subject

这种情况跟上面的差不多，也是为了保证virtual base class subobject的位置在编译器被确定下来，而合成拷贝构造函数。这种情况一般也是发送在用派生类对象去初始化基类，因为这样如果没有合成拷贝构造函数，将会难以确定virtual base class subobject的位置。

字符串

旋转字符串

• 题目描述

给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符'a'和'b'移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。

• 解答

可以先在原地进行旋转，例如ab旋转为ba，cdef旋转为fedc，此时变为bafedc，然后再旋转cdefab。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void ReverseString(char* s,int from,int to)
{
    while (from < to) {
        char c = s[from];
        s[from++] = s[to];
        s[to--] = c;
    }
}

void LeftRotateString(char* s,int n,int m)
{
    m %= n;
    ReverseString(s, 0, m-1);
    ReverseString(s, m, n-1);
    ReverseString(s, 0, n-1);
}

字符串转换成整数

• 题目描述

输入一个由数字组成的字符串，把它转换成整数并输出。例如：输入字符串"123"，输出整数123。 给定函数原型int StrToInt(const char *str) ，实现字符串转换成整数的功能，不能使用库函数atoi。

• 解答

本题的关键是三个部分：防止空指针，避免无效字符，解决溢出问题

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

int StrToInt(const char* str)
{
    if (!str) return 0;
    static const int MAX_INT = (int)((unsigned)~0 >> 1);
    static const int MIN_INT = -(int)((unsigned)~0 >> 1) - 1;
    int n = 0;
    while (isspace(*str)) str++;

    int sign = 1;
    if (*str=='-'||*str=='+') {
        if (*str == '-') sign = -1;
        str++;
    }

    while (isdigit(*str))
    {
        int tmp = *str - '0';

        if (sign > 0 && (n>MAX_INT/10 || (n == MAX_INT/10 && tmp>MAX_INT%10) )) return MAX_INT;
        else if (sign < 0 && (n>(unsigned)MIN_INT/10 || (n == MIN_INT/10 && tmp>(unsigned)MIN_INT%10))) return MIN_INT;

        n = n * 10 + tmp;
        str++;
    }
    return n*sign;
}

回文判断

• 题目描述

回文，英文palindrome，指一个顺着读和反过来读都一样的字符串，比如madam、我爱我，这样的短句在智力性、趣味性和艺术性上都颇有特色，中国历史上还有很多有趣的回文诗。 那么，我们的第一个问题就是：判断一个字串是否是回文

• 解答

用两个指针，分别指向首尾，进行遍历；或者两个指针从中间往两边遍历：

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

bool IsPalindrome1(const char *s, int n)
{
    if (!s||n<1) return false;
    const char *front, *last;

    front = s;
    last = s + n - 1;
    while (front < last) {
        if (*front != *last) return false;
        front++;
        last--;
    }
    return true;
}

bool IsPalindrome2(const char *s, int n)
{
    if (!s || n < 1) return false;
    if (s && n == 1) return true; 

    int mid = n / 2 - 1;
    const char *front, *last;

    front = s + mid;
    last = s + (n-1) - mid;

    while (front >= s) {
        if (*front != *last) return false;
        front--;
        last++;
    }

    return true;
}

字符串的全排列

• 题目描述

输入一个字符串，打印出该字符串中字符的所有排列。 例如输入字符串abc，则输出由字符a、b、c 所能排列出来的所有字符串abc、acb、bac、bca、cab 和 cba。

• 解答

递归实现，每次固定首个字符，然后递归对后面的字符进行全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void CalcAllPermutation(char* perm, int from, int to)
{
    if (to < 1) return;
    if (from == to) {
        for (int i = 0; i <= to;i++)
            std::cout << perm[i];
        std::cout << std::endl;
    }
    else{
        for (int i = from; i<=to; i++)
        {
            std::swap(perm[i], perm[from]);
            CalcAllPermutation(perm, from+1, to);
            std::swap(perm[i], perm[from]);
        }
    }
}

基本的TCPt套接字编程

socket函数

1

int socket(int family, int type, int protocol);

执行网络IO的第一步就是要执行socket函数，通过指定期望的通信协议，并返回socketfd（套接字描述符，与文件描述符类似）

connect函数

1

int connect(int sockfd, const struct sockaddr *serveraddr, socklen_t addrlen);

客户在调用connect之后会激发TCP的三次握手过程，使得当前套接字从CLOSED转移到SYN_SEND，若成功即转移到ESTABLISHED，但其中有三种出错情况：

• 客户端没有收到响应，那么会进行超时重发；
• 客户端收到的响应为RST（表示复位），也就是服务端并没监听指定端口；
• 客户发出的SYN在某个路由器上引发了不可到达的ICMP错误，内核会进行超时重发；

而一旦connect失败了，当前的套接字将不再可用，必须先close，再重新调用socket。

bind函数

1

int bind(int sockfd, const struct sockaddr* myaddr, socklen_t addrlen);

bind函数的作用就是把协议族赋予给套接字。对于TCP来说，bind函数既可以指定IP地址，也可以指定端口，甚至可以两者都指定。但一般来说，为了实现特定的服务，我们都需要指定一个端口，而不是由内核来选择临时端口。

至于通配地址，内核会在连接上建立或者在套接字上发出数据报才会选择一个本地IP地址，对于IPv4和IPv6来说，有不同的指定方式：

1
2
3
4
5
6

//IPv4,INADDR_ANY是一个常量值
struct sockaddr_in servaddr;
servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
//IPv6, in6addr_any是一个结构
struct sockaddr_in6 servaddr;
servaddr.sin6_addr = in6addr_any;

绑定非通配符地址的例子，通常是为多个组织提供web服务器的主机上。

listen函数

1

int listen(int sockfd, int backlog);

listen函数能够把一个主动套接字转换成一个被动套接字。至于backlog参数，我们需要知道的是内核为任何一个给定的监听套接字维护两个队列：

• 未完成连接队列：在三次握手开始后，完成前，队列中会维护一项；
• 已完成队列：在三次握手成功后，未完成队列的一项将会转移到该队列的末尾；

而backlog就是指两个队列之和。

accept函数

1

int accept(int sockfd, struct sockaddr *cliaddr, socklen_t *addrlen);

accept函数由TCP的服务器调用，用于从已连接的队列头中返回一项。如果队列为空，则进入睡眠状态。另外，accept调用成功的话会返回一个已连接套接字。

fork和exec函数

1

pid_t fork(void);

fork函数在父进程中返回子进程的pid，因为父进程可能有多个子进程，所以必须通过返回值记录pid；而在子进程中则返回0，这是因为子进程只有一个父进程，因此可以通过函数getppid()取得父进程的pid。

并发编程

看一个简单的并发编程代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

pid_t pid;
int listenfd, connfd;
listenfd = Socket(...);
Bind(listenfd, ...);
Listen(listenfd, LISTENQ);
for (;;) {
    connfd = Accept(listenfd, ...);
    if ( (pid = Fork()) == 0) {
        Close(listenfd);
        doit(connfd);
        Close(connfd);
        exit(0);
    }
    Close(connfd);
}

在上面的例子中，注意两个close操作。由于每个套接字其实都会有一个引用计数，而引用计数就是在文件标表项中维护着。在fork出一个新的进程后，connfd和listenfd的引用计数都变成了2。但我们的模型中更希望的是，listenfd在父进程中，connfd在子进程，所以我们分别执行了close操作。

close函数

1

int close(int sockfd);

这个函数的功能在上面已经说了，就是使得套接字描述符的引用计数减一。如果子进程关闭了connfd，而父进程没有，那么在一定时间之后，套接字描述符将会被用完。

总结

大多数TCP服务器都是并发的，堆每个待处理的客户连接调用一个fork派生一个子进程。而大多数UDP都是迭代的。

lexical analysis

goals

converts from phsical description of a program into sequence of tokens. (token: one logical piece of the source file)

• Each token associated with a lexeme
• have opitional attributes

choosing good tokens

依赖于不同的语言：

选择关键词； 将lexeme分成不同组的id，如数字，字符串等； 丢弃无用的信息，如空格，注释等；

扫描的困难

• 如何判断哪一个的lexeme对应于tokens
• 有多种扫描方式来堆输入扫描，如何取舍
• 如何高效获得想要的

正则表达式

定义：用来捕捉某些语言的一系列描述

符号ε用来匹配空字符串，符号a用来匹配a；

符合型：

• 如果R1和R2是正则表达式，那么R1R2就表示R1R2的级联；
• 如果R1和R2是正则表达式，那么R1|R2就表示R1和R2任意取一个；
• 如果R是正则表达式，那么R*就表示R的闭包；

实现正则表达式

正则表达式能通过有限自动机来实现。

而有限自动机有两种： NFA(nondeterministic finite automa) DFA(deterministic finite automa)

以图表示的话，圆圈表示状态，箭头表示转移，双圆圈表示结束:

如果一个状态有多个transitions，那么多条transitions都要进行。

Epsilon transition: 不消耗任何输入,但会进行transitions。

Simulating an NFA

1. 有限初始化，追踪开始状态和所有可以通过ε转移到达的状态；
2. 对于输入的每一个字符

• 维持一个集合表示下一个状态，初始为空
• 对于每一个当前状态，跟踪针对输入字符可以到达的状态,并添加进集合中

3. 添加可以新状态集合中通过ε的状态

解决匹配冲突

通常情况下选择最长match.

具体做法是，将所有正则表达式转化为NFA，然后合并成一个状态机，扫描输入，记录上一个已知的匹配。选择更高优先级的。

DFA

与NFA不同，DFA的每一个状态只有一个与某个字符相关的转移，并且没有ε transitions

• Make the DFA simulate the NFA

(q0是开始状态)

Step 1: Initially Q’ = ɸ.

Step 2: Add q0 to Q’.

Step 3: For each state in Q’, find the possible set of states for each input symbol using transition function of NFA. If this set of states is not in Q’, add it to Q’.

Step 4: Final state of DFA will be all states with contain F (final states of NFA)

参考资料：https://www.geeksforgeeks.org/theory-of-computation-conversion-from-nfa-to-dfa/

Introduction

compilers & interpreters

• compilers：输入程序，输出执行文件。offline

• interpreters：输入程序和数据，输出结果。online

five aspects

• lexical analysis: divides program text into "words" or "tokens"

• parsing: understand the program structrue

• semantic analysis: perform limited semantic analysis to catch inconsistencies; should define strict rules to avoid ambiguties

• optimization: like editing, to run faster and use less memory; x = y*0 == x = 0(x is int)

• code generation: produces assembly code(usually)

The Semantics of Constructors

Default Constructor的建构操作

默认构造函数会在需要的时候被编译器产生出来。这里的关键是：被谁需要，做什么事情。

被谁需要

当编译器需要的时候才会合成，但编译器不会为数据成员进行初始化，也就是不会在默认构造函数中进行初始化。考虑下面的代码：

1
2
3
4
5
6
7

class Foo {public: int val; Foo *pnext; };

void foo_bar()
{
    Foo bar;
    if (bar.val||bar.pnext)//...do someting
}

注意这样的情况下，编译器并没有对var和pnext进行初始化。

什么时候需要

• “带有默认构造函数的成员类对象”

如果一个类没有构造函数，但它有一个成员对象，该成员对象拥有默认构造函数。那么编译器会为该类合成默认构造函数，但要到需要使用的时候才会合成。考虑如下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Foo  
{  
    public:  
        Foo(); //构造函数  
        ...  
};  
  
class Bar  
{  
public:  
    Foo foo; //是一个member object, 而其class Foo 拥有default constructor.  
    char *str;  
};  
  
void foo_bar()  
{  
    Bar bar //合成constructor  
} 

另外，如果一个类内部含有多个拥有默认构造函数的对象，那么类会按照声明顺序调用对象的默认构造函数。

如果类内已经有默认构造函数，那么编译器会对默认构造函数进行扩张，初始化类内成员对象。

• 带有默认构造函数的基类

如果一个没有任何构造函数的类派生自一个带有默认构造函数的基类，那么派生类中会合成一个默认构造函数，用来调用基类的构造函数。

另外如果派生类中有其它构造函数（但没有默认构造函数），那么编译器会扩张所有的构造函数，来调用基类的默认构造函数。

• 带有一个virtual function的class

考虑这两种情况，会合成默认构造函数：

1. class声明一个virtual function
2. class派生自一个继承链，其中有一个以上的virtual base class

这种情况是因为编译器需要为类生成virtual table和指向virtual table的指针。因此把这两个操作放在合成的构造函数中进行。

• 带有一个virtual base class的class

因为编译器必须要使得每个派生类的对象都能够拥有虚基类的偏移位置，所以也需要在合成的默认构造函数执行操作。

总结

常见的两个误解：

1. 一个类没有定义默认构造函数，就会合成。
2. 编译器合成的默认构造函数会为每个成员设定初始值。

unix基础知识

unix体系结构

内核的接口称之为系统调用； 公用函数库建立在系统调用上，用户既可以调用函数库函数，也可以使用系统调用； shell是特殊的应用程序，为其它应用程序提供接口；

登录

登录项通常在/etc/passwd文件中，但加密口令不在此；

文件和目录

目录是一个包含目录项的文件，而目录项包含一个文件名和相关的文件属性；

工作目录：当前目录

起始目录：登陆后的当前目录

输入和输出

文件描述符：一个非负整数，用来标识一个特定进程正在访问的文件；

标注输入、输出、错误：0,1,2；

不带缓冲的IO：open、read、write、lseek、close；

带缓冲：fgets、fgetc、printf等等；

程序与进程

程序：磁盘上的可执行文件，内核通过exec将程序读入内存；

进程：程序的执行实例；

线程：线程的ID只在本进程下有效；

出错处理

当Unix的系统函数出错时，会返回一个负数，同时errno变量会被设置为一定的相关值。

用户标识

用户ID为0的是root；组ID的登录项在/etc/group；

信号

处理信号的三种方式：忽略信号，按照系统默认终止进程，提供一个函数去处理信号

套接字编程简介

概述

socket编程的基础就是socket结构，几乎所有的API都会用到。而socket通常只会在两个方向上传递——进程到内核和内核到进程。

套接字地址结构

先看看IPV4的结构

1
2
3
4
5
6
7
8
9
10
11

struct in_addr {
    in_addr_t s_addr;
};

struct sockaddr_in {
    uint8_t sin_len;
    sa_family_t sin_family;
    in_port_t sin_port;
    struct in_addr sin_addr;
    char sin_zero[8];
};

在sockaddr_in这个结构体，通常只需要三个字段: sin_family、sin_addr和sin_port（POSIX标准）。另外sin_zero这个字段一般不会使用，我们直接把其置为０即可

通常套接字地址结构，由于我们传递给socketAPI的是指针，所以这些API通常要处理各种支持不同协议的套接字地址，又因为套接字函数出来的时候，ANSI C还没有提出，也就无法使用通常指针void *。所以我们每次传入套接字函数，都需要转为以下的结构：

1
2
3
4
5
6
7
8

struct sockaddr {
    uint8_t sa_len;
    sa_family_t sa_family;
    char sa_data[14];
};

struct sockaddr_in serv;
bind(sockfd, (struct sockaddr *) &serv, sizeof(serv));

另外在IPv6提出之后，有了新的同样套接字地址结构，并且可以支持任何套接字结构，这里就不表了，可以搜一下：struct sockaddr_storage

值——结果参数

• 从进程到内核传递套接字地址的函数有３个：bind, connect和sendto，参数是指向结构的指针，和结构的大小；

• 从内核到进程传递套接字的函数有４个：accept, recvfrom, getsockname, getpeername，参数是指向结构的指针和直线结构大小变量的指针；

字节排序函数

这个是因为在不同的主机系统中，采用大小端模式是不同的，比如linux中是小端序，而apple中是大端序。这两种字节序转换用以下４个函数：

1
2
3
4
5

#include <netinet/in.h>
uint16_t htons(uint16_t host16bitvalue);
uint32_t htonl(uint32_t host32bitvalue);
uint16_t ntohs(uint16_t net16bitvalue);
uint32_t ntohl(uint32_t net32bitvalue);

字节操作函数

没什么好说的，主要关注bzero，memset，memcpy等几个函数

inet_aton, inet_addr, inet_ntoa函数和inet_pton，inet_ntop函数

这些函数，是用来在ASCII字符串中和网络字节序的二进制值进行转换的。这两个函数——inet_pton，inet_ntop，针对IPv6和IPv4都是适用的。

关键词带来的困扰

这里需要区分的是struct和class，通常情况下我们认为在C的struct和C++支持的class之间，关键词本身并没有提供了差异。

另外一个需要的注意的问题是，有一些在C中可用的trick，用在C++里可能出现意想不到的问题。例如我希望一个struct有可变的长度

1
2
3
4
5

struct mumble {
    char pc[1];
};

struct mumble* p_mumble = (struct mumble* )malloc(sizeof(mumble)+sizeof(string)+1);

但如果是用class来声明，由于多个区域之间的顺序内存布局是不一定的，也就无法这样精细地控制内存。

对象的差异

C++程序设计模型支持三种programming paradigms:

• prodedural model
• ADT
• object-oriented model

需要多大的内存来保存一个class的大小：

• 其所有nonstatic data members的大小；
• 由于alignment而需要进行padding的大小，有可能在数据成员上填补，也可能在集合体上进行填补；
• 为了支持virtual function而带来的额外负担；

指针的类型，例如一个指向对象的指针和一个指向整数的指针，一个指向template array的指针有什么区别？关键不在于指针内容的不同，而是通过指针寻址出来的对象不同，也就是指针类型告诉了编译器应该如何解释特定内存地址的内容和大小。

而一个指针类型为void*的指针，其仅仅代表一个地址，通过转型cast，使得编译器能够解释指出内存的大小和位置。

考虑这种情况：

1
2
3

Bear b;
ZooAnimal *pz = &b;
Bear *pb = &b;

上面的两个指针都执行了Bear object的第一个字节，但不同的是，pz涵盖的只有Bear object的ZooAnimal部分。而pb则涵盖了整个Bear object;也就是你无法通过pz去使用Bear的任何members。除非使用虚函数机制；

也就是通过pz所指向的类型去调用某个函数，这里的关键是类型信息并不是存储在pz里，而是存储pz所指向的对象的虚指针和虚指针所指向的虚表里。

而如果直接把派生类的对象塞进基类的对象里，派生类对象会被切割，也就是失去了多态的功能，