什么是大O

n表示数据规模，则表示运行算法所需要执行的指令数，和成正比。

一个算法有多个步骤，每个步骤规模相同但时间复杂度不同，最终的时间复杂度以最高的那个为准。

对数据规模的概念

如果想要在1s之内解决问题：

• 的算法可以处理大约级别的数据；
• 的算法可以处理大约级别的数据；
• 的算法可以处理大约级别的数据；

这个结论只是执行简单的数据操作，实际还需要再低估一下。

空间复杂度

• 多开一个辅助数组：;
• 多开一个辅助的二维数组：
• 多开常数空间：;

需要注意：递归调用是有空间代价的，递归的深度就是空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//计算n以内数据的和

//空间复杂度O(1)
int sum1(int n)
{
    assert(n >= 0);
    int ret = 0;
    for(int i=0;i<=n;i++)
    {
        ret += i;
    }
    return ret;
}

//递归调用：空间复杂度O(n)
int sum2(int n)
{
    assert(n>=0);
    if(n == 0)
        return 0;

    return n + sum2(n-1);
}

简单的时间复杂度分析

O(1)

常数级的算法很简单，没有数据规模的变化

1
2
3
4
5
6
7

// O(1)
void swapTwoInts(int &a , int &b){
    int temp = a;
    a = b;
    b = temp;
    return;
}

O(n)

O(n)的算法典型的特征就是有个循环，并且循环的次数和n相关。

其实正常来说，应该是，其中C是个常数，且不一定大于1

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

// O(n)
int sum(int n){

    assert(n >= 0);

    int ret = 0;
    for( int i = 0 ; i <= n ; i ++ )
        ret += i;
    return ret;
}

//字符串反转，只需要进行1/2次的swap操作即可
void reverse(string &s){

    int n = s.size();
    for(int i = 0 ; i < n/2 ; i ++)
        swap( s[i] , s[n-1-i] );
    return;
}

O(n^2)

见到算法内部有双重循环，每层循环都是n相关基本就八九不离十了。

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

//选择排序算法
void selectionSort(int arr[], int n){

    for(int i = 0 ; i < n ; i ++){
        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;

        swap( arr[i] , arr[minIndex] );
    }
}

千万要注意两层循环都要和n相关，不要看到双重循环就认为是

1
2
3
4
5
6
7
8
9
10

//第二重循环哪怕循环300w次，这个也是O(n)
void printInformation(int n){

    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= 30 ; j ++ )
            cout << "Class " << i << " - " << "No. " << j << endl;
    return;
}

O(logn)

经典的二分查找法：

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

//二分查找法
int binarySearch(int arr[], int n, int target){

    int l = 0, r = n-1;
    while( l <= r ){
        int mid = l + (r-l)/2;
        if(arr[mid] == target) return mid;
        if(arr[mid] > target) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

将数字整形转化为字符串：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

string intToString(int num){

    string s = "";
    string sign = "+";
    if(num < 0){
        num = -num;
        sign = "-";
    }

    while(num){
        s += '0' + num % 10;
        num /= 10;
    }

    if(s == "")
        s = "0";

    reverse(s);
    if(sign == "-")
        return sign + s;
    else
        return s;
}

分析算法思想，核心在" num /= 10"步中，就是n经过几次“除以10”操作后等于0，那么就是;

虽然上面两个例子，一个是以2为底，一个是以10为底，但都是，这个可以通过对数函数的换底公式来理解：有换底公式，可见和之间只相差一个常数，在时间复杂度下可以直接理解为

还需要注意，双重循环也可能出现logN的复杂度，需要注意量增长的规模：

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

//复杂度:O(nlogn)
void hello(int n){

    for( int sz = 1 ; sz < n ; sz += sz )
        for( int i = 1 ; i < n ; i ++ )
            cout << "Hello, Algorithm!" << endl;
}

//外层循环每次增长可以理解为sz*2
//其实就可以理解为n经过几次“除以2”的操作后等于1，外层循环复杂度O(logn)
//内层循环复杂度是O(n)
//合起来是O(nlogn)



//判断是否为素数
// O(sqrt(n))
bool isPrime(int num){

    if( num <= 1 ) return false;
    if( num == 2 ) return true;
    if( num % 2 == 0 ) return false;

    for(int x = 3 ; x * x <= num ; x += 2)
        if( num%x == 0 )
            return false;

    return true;
}

//

递归算法的复杂度分析

面对递归算法需要具体问题具体分析。

递归中只会进行一次递归调用

如果递归函数中只进行一次递归调用，递归深度为depth，在每个递归函数中的时间复杂度为T，则总体的时间复杂度为，既只需关注递归的深度

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

//递归调用的二分查找法
int binarySearch(int arr[], int l, int r, int target){

    if(l > r)
        return -1;

    int mid = l + (r - l) / 2;
    if(arr[mid] == target)
        return mid;
    else if(arr[mid] > target)
        return binarySearch(arr, l, mid - 1, target);
    else
        return binarySearch(arr, mid + 1, r, target);

}

  二分查找法很容易用递归实现，上述代码每次调用时，内部要么直接返回，要么数组左半边调用递归，要么数组右半边调用递归，只会调用一次，所以分析时间复杂度只有看递归的深度即可。

  每次调用数组减少一半，是典型的logn情况，所以复杂度为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// sum,O(n)
int sum(int n){

    assert(n >= 0);

    if(n == 0)
        return 0;
    return n + sum(n - 1);
}

// 求x的n次方：O(logn)
double pow(double x, int n){

    assert(n >= 0);

    if(n == 0)
        return 1.0;

    double t = pow(x, n / 2); //每次减半，logn
    if(n % 2)
        return x * t * t;

    return t * t;
}

递归中进行多次递归调用

当递归中有多次递归调用时，就需要关注递归调用的次数了。如果递归中只调用一次，深度就是次数，但如果调用了多次，那么深度和次数就是两个概念了。

1
2
3
4
5
6
7
8
9
10
11

//O(2^n)
//这个是指数级的算法，是个非常慢的算法
int f(int n)
{
    assert(n >= 0);

    if(n == 0)
        return 1;

    return f(n-1) + f(n-1);
}

均摊复杂度分析

  有时候会遇到这种情况：解决某个问题时运用了一系列算法，某个算法的复杂度很高，但这个算法可以降低其他算法的复杂度，这时候就需要计算分摊复杂度。

  均摊复杂度的经典问题就是动态数组vector。

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
44
45
46
47
48
49
50
51
52
53
54

template <typename T>
class MyVector{

private:
    T* data;
    int size;       // 存储数组中的元素个数
    int capacity;   // 存储数组中可以容纳的最大的元素个数

    // 复杂度为 O(n)
    void resize(int newCapacity){

        assert(newCapacity >= size);
        T *newData = new T[newCapacity];
        for( int i = 0 ; i < size ; i ++ )
            newData[i] = data[i];
        delete[] data;

        data = newData;
        capacity = newCapacity;
    }

public:
    MyVector(){

        data = new T[100];
        size = 0;
        capacity = 100;
    }

    ~MyVector(){

        delete[] data;
    }

    // 平均复杂度为 O(1)
    void push_back(T e){
        //当元素到达容量上限时，需要调用resize扩大空间
        if(size == capacity)
            resize(2 * capacity);

        data[size++] = e;
    }

    // 平均复杂度为 O(1)
    T pop_back(){

        assert(size > 0);
        size --;

        return data[size];
    }

};

  上面的代码只在push操作时resize了空间，但是没有在pop操作时resize空间。我们当然可以参考push操作，在pop到capacity一半时resize容量，但这里涉及一个问题，就是要防止复杂度震荡。

  考虑这个问题：当push到临界点时resize一倍空间，然后立即pop，此时又resize为一半，然后立即push，这种极端场景下时间复杂度无法均摊，会退化为。

  如果想避免这种场景，可以不再临界点处resize，当pop操作到达capacity的1/4处时，resize为1/2

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

// 平均复杂度为 O(1)
T pop_back(){

    assert(size > 0);
    T ret = data[size-1]; //这里一定要提前拿出来，resize操作会修改data
    size --;

    // 在size达到静态数组最大容量的1/4时才进行resize
    // resize的容量是当前最大容量的1/2
    // 防止复杂度的震荡
    if(size == capacity / 4)
        resize(capacity / 2);

    return ret;
}

进程调度

  进程调度是指计算机通过决策决定哪个就绪进程可以获得CPU使用权。前提是多道程序设计。

  进程调度有两个步骤：

1. 保留旧进程的运行信息，请出旧进程；
2. 选择新进程，准备运行环境并分配CPU；

  操作系统提供了三个机制来负责进程调度：

• 就绪队列的排队机制：

  为了提高进程调度的效率，操作系统事先将就绪进程按照一定的方式排成队列，以便调度程序可以最快找到就绪进程。

• 选择运行进程的委派机制：

  调度程序以一定的策略选择就绪进程，将CPU资源分配给它。

• 新老进程的上下文切换机制：

  保存当前进程的上下文信息，装入被委派执行进程的运行上下文。

  如果进程调度触发时，老进程还没有执行完毕的场景怎么办？为此有两种进程调度的方式：

• 非抢占式的调度：

  处理器一旦分配给某个进程，就让该进程一直使用下去，调度程序不以任何原因抢占正在被使用的处理器。直到进程完成工作或因为IO阻塞才会让出处理器。

• 抢占式的调度：

  允许调度程序以一定的策略暂停当前运行的进程，保存好旧进程的上下文信息，分配处理器给新进程。

进程调度算法

• 先来先服务算法：

  这个算法比较简单，在就绪队列中按照先来先服务的原则，优先取出队列最前面的就绪进程来调度，之后依次执行。

• 短进程优先调度算法：

  调度程序优先选择就绪队列中估计运行时间最短的进程。短进程优先调度算法不利于长作业进程的执行。

• 高优先权优先调度算法：

  进程附带优先权，调度程序优先选择权重高的进程。这个算法使得紧迫的任务可以优先处理。

  系统中分为前台进程和后台进程，一般来说前台进程的优先级都比后台进程大，因为前台进程需要和用户交互，要保证用户使用时不会卡顿。

• 时间片轮转调度算法：

  按照先来先服务的原则排列就绪队列，然后每次从队列头部取出待执行的进程，分配一个时间片执行，每个进程分配的时间片都是一样的。这是相对公平的调度算法，但是不能保证及时响应用户操作。

死锁

  死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞现象。若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

死锁的产生

  第一个死锁产生的原因是资源竞争。当共享资源数量不满足各个进程需求时，各个进程之间就会因为共享资源的竞争而导致死锁。每个进程都在等待请求的资源被释放，但自身占用的资源又不会主动释放。如果此时增加多余的系统资源，死锁就会解开。

  第二个原因是进程调度顺序不当。如下图，进程1和进程2都要申请打印机和传真机资源。如果调度的顺序是A->B->C->D，那么就会发生死锁。如果适当的改变调度顺序，改为A->D->B->C，那么就可以正常调度。

  死锁产生的必要条件有四个，必须同时满足：

1. 互斥条件：进程对资源的使用是排他性的使用。某个资源只能由一个进程使用，其他进程需要使用只能等待。
2. 请求保持条件：进程至少保持一个资源，同时又提出新的资源请求。此时新资源被占用，请求被阻塞，但被阻塞的进程不释放自己保持的资源。
3. 不可剥夺条件：进程获得的资源在未完成使用前不能被剥夺，获得的资源只能由进程自身释放。
4. 环路等待条件：发生死锁时，必然存在“进程-资源”的环形等待链。

死锁的处理

预防死锁的方法

  死锁产生的必要条件有四个，我们只需要破坏其中一个或多个即可预防死锁产生。互斥条件我们不能破坏，其余三个我们都有方法破坏：

1. 摒弃请求保持条件：系统规定进程运行之前，一次性申请所有需要的资源。这样在进程运行期间不会再提出资源请求。
2. 摒弃不可剥夺条件：当一个进程请求新的资源得不到满足时，必须释放占有的资源。
3. 破坏环路等待条件：可用资源按照线性排列，申请必须按照需要递增申请，线性申请就不再形成环路。

银行家算法

  以银行借贷系统分配策略为基础的算法，是一个可操作的著名的避免死锁的算法。客户申请的贷款是有限的，每次申请需声明最大资金量。银行在能够满足贷款时，都应该给用户贷款；客户在使用贷款后，能够及时归还贷款。

  银行家算法需要有三个数据结构：已分配资源表、所需资源表、可分配资源表。如下图，表格中A、B、C、D四列表示可申请的四个共享资源，P1、P2、P3、P4是四个进程，第一张表内部的数字表示当前进程拥有的资源数量，第二张表内部的数字表示当前进程还需要资源的数量，第三张表内部数字表示当前系统还剩的资源数量。

  当我们把所需资源表减去已分配资源表，就可以得到一张还需要分配的资源表:

  此时我们把还需分配资源表中每个进程依次和可分配资源表比较，如果有一个进程当前满足运行条件，则直接把资源分配给它。等进程运行完毕归还资源后，重新再比较。

预处理器

C预处理器处理程序的源代码，在编译器运行之前运行，通常以符号"#"开头。

C预言的预处理主要有三个方面的内容：

1. 宏定义与宏替换
2. 文件包含
3. 条件编译

宏定义与宏替换

  “宏”是借用汇编预言中的概念，为的是在C语言程序中方便的做一些定义和扩展。这些语句以“#define”开头，分为两种：符号常量的宏定义和带参数的宏定义

• 符号常量的宏定义和宏替换

1

#define 标识符 字符串

  其中标识符就是宏名称，注意宏定义末尾不加分号.

  由于预处理是在编译之前的处理，而编译工作的任务之一就是语法检查，所以预处理是不做语法检查的。且宏定义不分配内存，变量定义才分配内存。

• 带有参数的宏定义及其替换

  对带有参数的宏定义进行宏替换时，不仅对宏标识符作字符串替换，还必须作参数的替换。有时为了避免发生错误，需要在宏参数上加括号。

1
2
3
4
5
6

#define 标识符(参数列表) 字符串


#define FUN(x) (x*x)  //FUN(a+b)将被替换为a+B*a+B

#define FUN(x) ((x)*(x))  //FUN(a+b)将被替换为(a+B)*(a+B)

  宏替换的本质就是文本替换，需要注意：

1. 宏名一般用大写，宏名和参数的括号间不能有空格，宏定义末尾不加分号；
2. 宏替换只坐替换，不做语法检查、不做计算、不做表达式求解；
3. 宏替换在编译前进行，不分配内存；函数调用在编译后的程序运行时进行，且分配内存；
4. 函数只有一个返回值，利用宏则可以设法得到多个值；
5. 宏替换会使源程序变长，函数调用不会；
6. 宏替换不占用运行时间，只占用编译时间；函数调用占用运行时间(内存分配、保留现场、值传递、返回值)

  实际工程中应尽量少用宏替换。C++中宏替换实现的符号常量功能由const、enum代替，带参数的宏替换可由模板内联函数代替。

文件包含

1
2

#include <func.h>
#include "func.h"

  如果头文件名在尖括号<>中，那么认为该头文件是标准头文件。编译器将会在预定义的位置集合中查找该头文件，这些预定义的位置可以通过设置查找路径和环境变量或者修改命令行选项来修改；

  如果头文件在一对引号中，则认为它是非系统头文件，非系统头文件的查找通常开始于源文件所在的路径中；

条件编译

  提供条件编译措施使得同一源程序可以根据不同编译条件(参数)选择不同的目标代码，其作用在于便于调试和移植。

1
2
3
4

#if/ifdef/ifndef
#elif
#else
#endif

全局变量和局部变量

  全局变量也称为外部变量，在函数的外部定义。它属于一个源程序文件，作用域是整个源程序。

  在不同的文件中引用一个已经定义过的全局变量，可以用头文件引用的方式，也可以用extern关键字。假设变量写错了，如果使用头文件包含的方式，那么编译期间会报错；如果使用extern关键字，编译期间不会报错，链接期间报错。

1
2
3
4
5
6

//file_1.cpp
int counter;

//file_2.cpp
extern int counter;  //使用file_1中的counter
++counter;

  局部变量指在程序中，只在特定过程或函数中可以访问的变量，是相对全局变量而言的。在面向过程的语言中，局部变量可以和全局变量重名，但局部变量会屏蔽全局变量。

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

int count = 3;  //语句1

int main()
{
    int i, sum, count = 2;  //语句2
    for(i = 0;i < count; i+=2, count++)     //判断条件count是语句2的count
    {
        static int, count = 4;  //语句3
        count++;    //用的是语句3的count
        if(i % 2 == 0)
        {
            extern int count;
            count++;    //因为用了extern，这里的count是语句1的count
            sum += count;   //因为用了extern，这里的count是语句1的count
        }
        sum += count;   //语句3的count
    }

    printf("%d %d\n", count, sum);  //语句2的count
    return 0;
}

static

普通的static

普通的static作用有三个：

1. 隐藏：当我们同时编译多个文件时，所有未加static的全局变量和函数都具有全局可见性，其他的源文件也可以访问。如果加了static前缀，则全局变量和函数对其他源文件隐藏，只在当前文件生效。
2. 默认初始化为0，包括未初始化的全局静态变量和局部静态变量。全局未初始化的变量本身也具备这个属性，未初始化的全局变量和未初始化的静态变量都在BSS段内，所有的字节默认为0x00;
3. 保持局部变量内容的持久。函数内的普通的局部变量退出作用域就消失了，但静态的局部变量退出函数后仍然存在，生存周期为整个源程序的周期。static的局部变量特点是只进行一次初始化且具有“记忆性”。不过虽然生存周期是整个程序，但作用域仍然和普通局部变量相同，出了函数虽然还存在，但不能使用。

类中的static

  C++重用了static关键字，并赋予了不同的含义：类中的static表示属于一个类但不属于此类的任何特定对象的变量和函数。static的成员变量和成员函数都独立于类对象存在。

• 静态数据成员：

  普通数据成员存在于该类的每个对象中，但static数据成员独立于该类的任意对象存在：static数据成员是与类关联的对象，二不与该类的对象相关联。当某个类的实例修改了该静态成员变量，修改后的值被该类的所有实例所见。

  静态数据成员和普通数据成员一样，也遵从public、protected、private的访问规则。

  静态数据成员也存储在全局(静态)存储区。静态数据成员定义时要分配空间，所以不能在类声明中定义，必须在类定义体的外部定义。

1
2
3
4
5
6
7
8
9
10
11

class Account
{
public:
    void apply();
    static double rate() {return interestRate;}
private:
    std::string owner;
    static double interestRate;
};

double Account::interestRate = 10; //类外定义

使用static成员变量而不是全局变量有三个优点：

1. static成员的名字还在类的作用域中，可以避免全局冲突；
2. static成员可以声明为私有的，实施封装；
3. 阅读方便，可以明确看出static成员与类是关联的

• 静态成员函数：

  和静态成员变量一样，静态成员函数是类的内部实现，属于类定义的一部分，为类服务而不是为类的具体对象服务。

  普通成员函数服务于具体的对象，所以普通的成员函数都隐含了一个this指针指向类的对象本身；静态成员函数不与对象关联，所以不具有this指针。所以静态成员函数无法访问属于类对象的非静态数据成员，也无法访问非静态成员函数，只能调用类其余的静态成员函数与访问静态数据成员。不过非静态的成员函数可以任意访问静态的成员函数和变量。由于没有this的开销，静态成员函数相比普通的成员函数速度上有少许增长。

  static成员变量可以被声明为const，但static成员函数不可以。const成员函数的意思是承诺不修改该函数所属的对象，但static成员函数不属于任何对象。

  static成员函数也不能被声明为虚函数、volatile。

const

常量

  C++中const限定符把一个对象转换为常量，常量定义后不允许修改，所以定义时必须初始化。

1

const int bufSize = 512; //必须初始化

  全局变量在整个程序中都可以访问，但全局的const变量是定义该变量的文件的局部变量。如果想被其他文件访问，需要声明extern。

  C和C++中的const有区别。常量引进是在早期的C++版本中，当时标准C规范正在制定。C中的const意思是“一个不能被改变的普通变量”，在C中总是占用存储，C编译器不能把const视为一个编译器的常量：

1
2
3

//以下写法在C中是错误的，C++中是允许的
const bufSize = 100;
int buf[bufSize];

  C默认const是外部连接的，C++默认const是内部连接的，如果想在C+中完成于C同样的事情，需要加extern变成外部连接：

1
2
3
4
5

//C语言可以这么写，C编译器只把他当作声明，C++编译器必须初始化，不能这么写
const int size;

//C++必须加extern
extern const bufSize; //只声明

  const最初的动机是取代#define的值替换功能，使用const取代#define的优点如下：

1. const常量有数据类型，宏常量没有数据类型，所以编译器可以对const常量进行类型安全检查；
2. 预处理会盲目的将宏常量进行代码替换，可能导致代码中多出很多个备份，所以使用const常量可能比使用#define产生更小的目标代码；
3. const可以执行常量折叠：常量折叠是编译期间简化常量表达式的过程，简单说就是将常量表达式计算求值，并用求得的值替换表达式放入常量表。

指针和const

  需要区分指向const的指针和const指针：

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

//指向const的指针：
const double *cptr;
// cptr是个指针，它指向一个const double
// cptr可以指向任何东西，所以不需要初始化，但是它所指的东西不能改变


//const指针
//使指针成为const，要把const标明的部分放在*右边
double d = 1.0;
double* const cptr = &d;
// cptr是个指针，这个指针是指向double的const指针
// 指针本身是const，所以必须初始化
// 在指针寿命期间内，指向的地址不可以改变，但地址里的内容可以变更

const修饰函数参数和返回值

  在一个函数声明式内，const可以和函数返回值、各参数、类成员函数函数自身产生关联：

• const修饰返回值：

  若返回值是值类型，则对于内部数据类型来说，返回值是否是常量并没有关系，const修饰返回值通常用于处理用户定义的类型；除了值类型，还可以返回指针。正常的函数不能返回指向局部变量的指针，因为函数返回后指针就无效了，栈也被情理了，但如果返回的指针是指向对中分配的存储空间的指针或者是指向静态存储区的指针，在返回后仍然有效。

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
44
45

//错误！！
// p是数组在栈上，返回的是指向栈内存的指针，
//返回的地址不是NULL，但内容已经被清除了
char* GetMemory()
{
    char p[] = "hello world";
    return p;
}


//正确
//数组在静态存储区，可以通过函数返回
char* GetMemory()
{
    static char p[] = "hello world";
    return p;
}



//正确
//p指向全局静态存储区，可以通过函数返回
//因为p指向常量，这里最好加上const修饰
//如果不加const，函数外面如果对返回的字符串做修改就崩溃了
const char* GetMemory()
{
    char p* = "hello world";
    return p;
}


//不太好的写法
//p指向堆内存的地址，可以通过函数返回
//但是需要外部来delete[]释放内存
char* GetMemory()
{
    char* p = (char*)malloc(12);
    if(p == NULL){
        return NULL;
    }
    else{
        p = "hello world";
    }
    return p;
}

• const修饰函数参数：

  参数加上const可以明确告知编译器参数在函数体内部不会也无法改变。如果是值传递，加const意义不大，但如果是传递地址，那么都应该尽可能的用const修饰。

const与类

• const成员函数：

1
2
3
4

class base{
    void func1();
    void func2() const;
}

  被const修饰的类成员函数改变了隐含的this形参的类型，使得this形参指向的对象为const类型。this本身的类型是base* const，被const修饰后变成了const base* const。const成员函数不能修改调用该函数的对象。

  const成员函数的目的是为了确保该成员函数可以作用于const对象身上。const对象、指向const对象的指针或引用只能调用其const成员函数；非const对象可以调用所有成员函数。显然，若不存在const成员函数，那么const对象的操作就变的极为困难，无法调用任何成员函数了。

  要注意，如果类成员函数只是常量性质不同，其余都一样，是可以被重载的：

1
2
3
4

class base{
    void func1();
    void func1() const;
}

• const数据成员：

  如果一个类的数据成员声明为const，那么必须在构造函数的初始化列表中进行初始化，且必须具有构造函数。不过如果数据成员同时具有static和const属性，那么也可以使用外部初始化。const数据成员也不可以在类定义处初始化，因为const数据成员只是在某个对象的生存周期内是常量，对于整个类而言是可变的，不同的对象可以有不同的值，如果在类声明中初始化const数据成员，因为类对象还没有创建，编译器不知道const数据成员的值是什么。

1
2
3
4
5
6

class Thing{
public:
    Thing():valueB(1){}
private:
    const int valueB;
}

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

class Test
{
public:
    Test():a(0){}
    enum {
        size1 = 100,
        size2 = 200
    };

private:
    const int a;    //只能在构造函数初始化列表中初始化
    static int b;   //在类外定义并初始化
    const static int c;
    //也可以写作static const int c;
    //c这里是整型，所以也可以在这里初始化，但仍需要在类外进行定义
    //如果c不是整形(char、short、int、long)，就不允许在这里初始化
};

int Test::b = 0;    //static成员变量不允许在类内初始化，不属于某个对象
const int Test::c = 0;  //给const static成员变量赋值时可以不加static，但必须加const

内存管理与释放

  C/C++程序，用户主要使用的内存主要分为：栈区、堆区、全局(静态)存储区、文字常量区、代码区。

  堆区和栈区的区别：

• 栈区：由编译器自动分配和释放，存放函数的参数值、局部变量的值等。操作方式类似于数据结构中的栈，速度较快；
• 堆区：一般由程序员分配释放，若程序员不释放，程序结束时由操作系统回收。要注意和数据结构中的堆是两回事，它的分配方式类似链表。一般速度比较慢，而且容易产生内存碎片，不过用起来方便。

1
2
3
4
5
6
7

//C语言
char* p1 = (char*)malloc(10);

//C++
char* p2 = new char[10];

//要注意p1和p2本身是栈上的变量，只是指向堆上分配的内存

  每一个程序执行时都占用一块可用的内存空间，用于存放动态分配的对象，这个内存空间就是堆。C语言使用标准库函数malloc和free在堆区分配存储空间，C++语言使用new和delete表达式实现。

动态创建对象的初始化

  通常，动态创建的对象如果不提供显式的初始化，那么对于类对象，用该类的默认构造函数初始化，当然也可以使用显式初始化；而内置类型的对象则无初始化；

  对于提供了默认构造函数的类的类型，没有必要对其对象进行显式初始化，操作结果一样；但如果是内置类型或者是没有默认构造函数的类型，不同的初始化方式有显著的差别：

1
2
3
4
5
6
7
8
9

//std::string类有默认构造函数
//无论是隐式的还是显式的，结果都是调用默认构造
string* ps = new string;    //调用默认构造函数初始化
string* ps = new string();  //调用默认构造函数初始化


//int是内置类型的，隐式的和显式的有区别
int* pi = new int;  //隐式的，无初始化
int* pi = new int();    //显式的，pi指向一个初始化为0的int值

  动态创建的对象用完后，程序员必须显式的将该对象占用的内存释放，否则就会内存泄漏，C语言提供了free函数，C++使用delete表达式。回收用new分配的单个对象的内存空间用delete，回收用new[]分配的一组对象的内存空间时用delete[];

1
2
3

char* p = new char[64];
delete[] p;
p = nullptr;

const对象的动态分配和回收

1

const int* pci = new const int(1024);

  C++允许动态创建const对象。与其他常量一样，动态创建的const对象必须在创建时初始化，且一经初始化其值不可再修改。

  对于一个类的const动态对象，如果该类提供了默认的构造函数，则此对象可以隐式初始化；内置类型对象或者未提供默认构造函数的类对象必须显式初始化：

1
2
3
4

//std::string有默认的构造函数
//new表达式没有显式的初始化pcs所指的对象
//而是隐式的将pcs所指的对象初始化为空string
const string *pcs = new const string;

  尽管程序员不能改变const对象的值，但是可以撤销对象本身。如同其他对象一样，const动态对象也可以使用指针释放：

1
2

const string *pcs = new const string;
delete pci;

new/delete和malloc/free比较

相同点：都可以用于申请动态内存和释放内存

不同点：

1. malloc和free是C/C++语言的标准库函数，new/delete是C++的运算符；
2. new自动计算需要分配的空间，而malloc需要手工计算字节数；
3. new是类型安全的，malloc不是；
4. new和delete可以调用相关对象的构造和析构，malloc和free不行；
5. malloc和free需要库文件支持，new和delete不需要

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

malloc和free由于是库函数，不在编译器控制权限之内，所以无法执行类的构造函数和析构函数；



new的执行过程：
1.用operator new的标准库函数(operator new对应malloc)，分配足够大的原始的未类型化的内存，以保存指定类型的一个对象；
2.运行该类的一个构造函数，用指定初始化式构造对象
3.返回指向新分配并构造的对象的指针；

delete的执行过程：
1.首先对指针指向的对象运行适当的析构函数；
2.调用operator delete的标准库函数释放该对象用的内存(operator delete对应free)；



malloc的函数原型如下：
void* malloc(size_t size);
用malloc申请一块长度为length的整数类型的内容程序如下：
int* p = (int*)malloc(sizeof(int) * length);
可见malloc返回值的类型是void*，所以在调用malloc时一定要显式类型转换；
且malloc函数本身并不识别要申请的内存类型，只关心总字节数

free函数的原型如下：
void free(void* memblock);
用free(p)来释放内存，如果p是NULL，那么free(p)操作多少次也不会出问题；
但如果p不是NULL，那么连续free(p)两次就会导致程序运行错误



new内置了sizeof、类型转换和类型安全检查功能，所以使用简单
int* p2 = new int[length];

内存池

  通常我们直接使用new、malloc等申请内存，这样做有个缺点：由于所申请的内存块大小不定，当频繁使用时会造成大量的内存碎片降低性能。

  内存池是一种内存分配方式，在真正使用内存之前，先申请分配一定数量的、大小相等(一般情况下)的内存块留作备用。当有新的内存需求时，就从内存池中分出一部分内存块，若内存块不够再继续申请新的内存。

进程

进程概念

  在没有操作系统之前，计算机只能运行一个程序，全部的资源都属于当前运行的程序。配置了操作系统后，引入了多道程序设计的概念，进程可以合理的隔离资源和运行环境、提升资源利用率。

• 进程是系统进行资源分配和调度的基本单位；
• 进程作为程序独立运行的载体保障程序正常执行；
• 进程的存在使得操作系统资源的利用率大幅提升；

进程实体

  主存中的进程是一个连续的存储空间，称为进程控制块(PCB)。进程控制块是用于描述和控制进程运行的通用数据结构。进程控制块中存有进程状态、优先级、程序计数器、内存指针、上下文数据、IO状态信息、记账信息等多个进程当前状态和控制进程的信息：

• 标识符：唯一标记一个进程，用于区别其他进程；
• 状态：标记进程的运行状态
• 程序计数器：指向进程即将被执行的下一条指令的地址；
• 内存指针：程序代码、进程数据相关的指针；
• 上下文数据：存储进程执行时处理器中的数据；
• IO状态信息：被进程IO操作所占用的文件列表；
• 记账信息：存储进程使用处理器的时间、时钟数总和等信息；

  除了上面的内容，进程还有一些其他信息。所有信息可以分为四大类：进程标识符、处理机状态、进程调度信息、进程控制信息。进程控制块使得进程是能够独立运行的基本单位，操作系统通过进程控制块信息来调度和控制进程。进程控制块是常驻内存的，存放在系统专门开辟的PCB区域内。

进程与线程

  进程(Process)和线程(Thread)是一对多的关系，一个进程内可以有一个或多个线程。

  进程是系统进行资源分配和调度的基本单位，而线程是操作系统进行运行调度的最小单位。线程包含在进程之中，是进程中实际运行工作的单位。一个进程可以并发多个线程，每个线程执行不同的任务。

  进程拥有资源，而线程不拥有资源，进程内部的线程共享进程资源。

五状态模型

• 就绪状态：

  当进程被分配到除CPU以外的所有必要资源后，就处于就绪状态。只要再获得CPU的使用权，就可以立即运行。在一个系统中多个处于就绪状态的进程通常排成一个队列，称为就绪队列。

• 执行状态：

  进程获得CPU，其程序开始执行，这个状态为执行状态。在单处理机中，某个时刻只能有一个进程是处于执行状态。

• 阻塞状态：

  进程因为某种原因，比如其他设备未就绪而无法执行，从而放弃CPU的状态称为阻塞状态。和就绪队列一样，操作系统也有阻塞队列，存放所有阻塞的进程。

• 创建状态：

  进程创建分为两步，第一步分配PCB，第二步插入就绪队列。创建进程时拥有PCB但其他资源尚未就绪的状态称为创建状态。无论是系统创建的进程还是用户创建的进程都是一样的，操作系统提供fork接口创建进程。

• 终止状态：

  进程终止也分为两步：首先进行系统清理，然后进行PCB归还。进程结束由系统清理或者归还PCB的状态称为终止状态。

进程同步

生产者-消费者模型

  有一群生产者进程在生产产品，并将这些产品提供给消费者进程进行消费。生产者进程和消费者进程可以并发执行，在两者之间设置了一个具有n个可缓冲区的缓冲池，生产者进程需要将所生产的产品放到其中一个缓冲区中，消费者进程可以从缓冲区中取走产品进行消费。

  生产者消费者模型在宏观上是没有问题的，当生产一个产品时缓冲区+1，当消费一个产品时缓冲区-1。但是计算机系统中是有问题的。计算机中的缓冲区位于高速缓存Cache上，生产者或消费者如果要操作缓冲区需要三个步骤：

1. 把缓冲区中的信息取出来放入寄存器：register = count
2. 如果生产register+1；如果消费register-1
3. 把寄存器信息放回缓冲区里：count = register

  这三个步骤但从生产者或消费者程序看没有问题，但两者并发执行时就会出差错:

哲学家进餐问题

  有五个哲学家，他们的生活方式是交替的进行思考和进餐。哲学家们共同使用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五支筷子。平时哲学家们只进行思考，饥饿时则试图取靠近他们的左、右两支筷子，只有两支筷子都被拿到时才能进餐，进餐完毕后分别放下左、右的筷子继续思考。

  通常的情况下，假设一个哲学家饿了，首先拿起左边的筷子，如果发现右边的筷子被拿走，则需要等待右边的筷子释放，释放后才能拿起筷子吃饭。但有一种极端情况：五个哲学家同时拿起左边的筷子，此时发现他们右边的筷子都被拿走，所以五个哲学家都需要等待右边筷子释放，最终的结果就是五个哲学家被饿死。

进程同步

  上面两个问题是操作系统中的经典问题，问题的根源在于：彼此之间没有通信。如果生产者通知消费者已经完成了一件生产，或者哲学家向旁边的哲学家说我要进餐了，就可以避免这些问题。

  进程的同步用于解决这种对竞争资源在多进程间进行使用次序的协调，使得并发的多个进程之间可以有效使用资源和相互合作。

进程同步原则

  临界资源指的是一些虽然作为共享资源却无法同时被多个线程共同访问的共享资源。当有进程在使用临界资源时，其他进程必须依据操作系统的同步机制等待占用进程释放该共享资源才可重新竞争使用共享资源。为了对临界资源进行约束，提出了进程同步的四个原则：

1. 空闲让进：资源无占用时允许进程使用；
2. 忙则等待：资源有占用，其他请求进程需要等待；
3. 有限等待：保证有限等待时间能够使用资源；
4. 让权等待：进程等待时，需要让出CPU；

线程同步

  和进程同步一样，一个进程内有多个线程并发使用，也会产生生产者-消费者问题和哲学家进餐问题，所以进程内的多线程也需要同步。

Linux的进程管理

进程类型

  Linux下进程分为三种类型：前台进程、后台进程、守护进程。

• 前台进程：

  Linux下有一个重要概念，就是终端Shell，我们使用命令行来使用Linux时就是通过终端Shell来实现。前台进程就是具有终端Shell，可以和用户交互的进程。前台进程占用终端Shell但不一定有输出。

• 后台进程：

  和前台进程相对，没有占用终端的就是后台进程。后台进程基本上不和用户交互，优先级比前台进程低。Linux下将需要执行的命令以“&”符号结束来启动后台进程。

• 守护进程：

  守护(daemon)进程是特殊的后台进程。很多守护进程在系统引导的时候启动，一直运行到系统关闭。Linux下进程名字以d结尾的进程一般都是守护进程，比如定时任务守护进程crond、http服务守护进程httpd、ssh登录的守护进程sshd、数据库守护进程mysqld。

进程标记

• 进程ID：

  进程的唯一标识符，每个进程拥有不同的ID。进程ID表现为一个非负整数，最大值由操作系统限定。

  操作系统提供fork接口创建进程，进程可以多层创建，这些进程是父子进程的关系。进程父子关系可以用pstree命令查看。

  需要记住几个特殊的进程：ID为0的进程为idle进程，是系统创建的第一个进程；ID为1的进程为init进程，是0号进程的子进程，完成系统的初始化。init进程也是所有用户进程的祖先进程；

• 进程标记：

  和Windows系统类似，Linux下的进程也有不同的进程状态，我们可以通过man ps命令来查看进程状态的所有标记，Linux进程状态很多，常见的有以下几种：

Linux操作进程命令

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

+ ps命令：用于显示进程信息的常用命令，常用选项如下：
  + -e：显示所有进程，包括系统进程
  + -f：显示完整进程信息，包括进程的详细信息
  + -l：显示更多的列，包括进程的状态、CPU使用情况等
  + -u：显示指定用户的进程信息
  + -aux：结合-a和-u选项，显示所有用户的所有进程，并显示详细信息
  + -p：显示指定进程号PID的进程信息
  + -k --sort：按指定的列排序进程信息，常见的排序屁啊包括%cpu(CPU使用率)、%mem(内存使用率)等
  + -c：根据命令行显示进程信息
  + -o：自定义输出格式，可以指定要显示的列
  + --forest：以树状结构显示进程间的父子关系

ps命令可以和其他命令结合：
ps -aux | grep '进程名'：查找指定进程的信息

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

+ top命令：系统监视工具，查看进程状态，常用选项如下：
  + -d：秒数，指定top命令每个几秒更新
  + -b：使用批处理模式输出，一般和"-n"选项合用，用于把top命令重定向到文件中
  + -n：次数，指定top命令执行的次数，和"-"选项合用
  + -p：仅查看指定PID的进程
  + -s：使top命令在安全模式中运行，避免在交互模式中出现错误
  + -u：用户名，只监听某个用户的进程

在top命令的显示窗口中，还可以使用如下按键进行交互操作：
+ ?或h：显示交互模式的帮助
+ c：按照CPU的使用率排序，这个是默认的
+ M：按照内存使用率排序
+ N：按照PID排序
+ T：按照CPU的累积运算时间排序
+ k：按照PID给予某个进程一个信号，一般用于终止某个进程
+ r：按照PID给某个进程重设优先级
+ q：退出top命令


使用top命令后展示的进程信息关键字含义如下：
+ PID：进程标识符
+ USER：运行进程的用户名
+ PR：进程的优先级
+ NI：进程的优先级调整值
+ VIRT：进程使用的虚拟内存大小
+ RES：进程实际使用的物理内存大小
+ SHR：进程的共享内存大小
+ %CPU：进程占用CPU的使用率
+ %MEM：进程占用内存的使用率
+ TIME+：进程的累计CPU时间
+ COMMAND：进程命令行

1
2
3
4
5
6

kill命令：给进程发送信号时使用

kill -l：查看操作系统支持的所有信号
//只有SIGKILL 9信号可以无条件终止进程，其他信号进程有权忽略

eg：kill -9 PID :给指定PID进程发送9信号，用于强制退出进程

进程同步方法

• 消息队列
• 共享存储
• 信号量

线程同步的方法：

1. 互斥量
2. 读写锁
3. 自旋锁
4. 条件变量