左右的概念

左值、右值

C++中左值与右值这两概念是从 c 中传承而来的，在 c 中，左值指的是既能够出现在等号左边也能出现在等号右边的变量(或表达式)，右值指的则是只能出现在等号右边的变量(或表达式)

在 C语言中，通常来说有名字的变量就是左值(如 a, b)，而由运算操作(加减乘除，函数调用返回值等)所产生的中间结果(没有名字)就是右值，如 3 + 4， a + b 等。

在 C++ 中，每一个表达式都会产生一个左值，或者右值，相应的，该表达式也就被称作“左值表达式”， “右值表达式”。对于内置的基本数据类型来说，左值右值的概念和 c 没有太多不同，不同的地方在于自定义的类型，具体如下：

• 对于内置的类型，右值是不可被修改的(non-modifiable)，也不可被 const, volatile 所修饰（volatile关键字的作用是防止优化编译器把变量从内存装入CPU寄存器中，保证每次取的值都是内存中值）
• 对于自定义的类型(user-defined types)，右值却允许通过它的成员函数进行修改
  2

  左值引用、右值引用

• 左值引用，Type & 左值引用名 = 左值表达式;
• 声明时必须初始化，初始化之后无法在改变；对别名的一切操作都等价于对原来变量的操作。
• 右值不能赋值给左值引用，加上const限定符即可
• c++中临时变量默认const属性，所以只能传给const引用(延长生命周期)

• 右值引用，Type && 右值引用名 = 右值表达式;
• 可以直接把左值或者右值转换成右值引用，但转换后原对象就不能使用了

1
2
3
4
5
6

int val = 10;
int & a1 = val+1;  // 错误，此时val+1（中间结果用const型的临时变量保存）等价于右值，右值不能赋值给左值引用
const int& a2 = val+1; // 正确
const int& a3 = 10;  //  正确

int && a4 = std::move(val+1); // 正确

动态内存与智能指针

• 智能指针负责自动释放所指向的对象，定义在memory头文件中
• 智能指针也是模板，创建智能指针时需要提供类型信息
• 智能指针的使用与普通指针类似
• 包括shared_ptr（允许多个指针指向同一个对象）、unique_ptr（独占所指向的对象）、weak_ptr（指向shared_ptr所指向的对象）

注意事项

• 不用相同的内置指针初始化多个智能指针
• 不delete get函数返回的值
• 不用get返回值初始化/reset另一个智能指针
• 如果智能指针管理的资源不是new分配的资源，需要传给他一个删除器

shared_ptr

1
2
3
4
5
6

shared_ptr<T> sp; // 空指针
if (p)   //  如果p指向一个对象则为true
*p
p->mem
p.get()   // 返回p中保存的指针
swap(p, q)  // 交换p和q中的指针

不要将get函数得到的内置指针用于初始化其他智能指针，可能会导致两个智能指针指向同一个对象，且他们的计数器都为1
以上操作也适用于unique_ptr，下面的操作则是shared_ptr独占：

1
2
3
4
5

make_shared<T> (args)  // 返回一个shared_ptr, 指向类型T的动态内存对象，使用args初始化
shared_ptr<T>p(q)   // p是q的拷贝；q中的计数器加一，要求q中的指针必须能转化位T*
p = q    // p,q都是shared_ptr，保存的指针必须能相互转换。p的引用计数器递减，q的递增。若p的引用计数器变为0，则将其管理的资源释放
p.unique()   //  若p.use_count()为1，返回true；否则返回false
p.use_count  // 返回与p共享对象的智能指针个数；一般用于调试

1
2
3
4
5
6

auto p1 = new auto(obj); // p指向一个与obj类类型相同的对象，该对象用obj初始化

auto p2 = new auto{a,b,c}; // 错误，括号中只能有单个初始化器

// 内存耗尽时new操作会抛出bad_alloc异常，下面的方法可以避免抛出异常
int *p = new (notthrow) int;   // 内存耗尽时返回空指针

• delete空指针没有问题
• delete之后应该重置指针

shared_ptr和new

• 可以使用new返回的指针初始化智能指针
• 接受指针参数的智能指针构造函数为explicit（不准指针隐式转换），必须使用直接初始化形式

1
2
3
4
5
6
7
8
9

shared_ptr<int> p(new int(42));
shared_ptr<int> p1 = new int(42); // 错误，可以使用reset


shared_ptr<T> p(u);  // p从unique_ptr接管对象所有权，将u置空
shared_ptr<T> p(q, d)  // p接管内置指针q所指向的对象，q必须能转换为T*，p使用可调用对象d代替delete
p.reset()   // 若p是唯一指向其对象的shared_ptr，reset释放该对象
p.reset(q)  // 若传递了参数内置指针q，令p指向q，否则将p置空
p.reset(q, d);  // 有d则使用可调用对象代替delete

unique_ptr

• 一个对象只能有一个unique_ptr，不支持拷贝（除非是返回即将要销毁或局部对象的拷贝）、赋值
• 必须采用直接初始化形式

1
2
3
4
5
6
7
8
9

unique_ptr<T, D> u // D为可调用对象，用来释放内存
unique_ptr<T, D> u(d)   // 用d代替D

u = nullptr  // 释放u指向的对象，将u置空
u.release()  // u交出控制权，返回内置指针，将u置空

u.reset()     // 释放u指向的对象
u.reset(q)   // 提供内置指针q，则令u指向这个对象；否则将u置空
u.reset(nullptr)

unique_ptr和动态数组

1
2
3

unique_ptr<T[]> u;  // u指向一个动态分配的数组
unique_ptr<T[]> u(p);  // u指向内置指针p指向的动态动态分配的数组，p类型必须能转换为T*
u[i];   // 访问数组

shared_ptr没有提供管理动态数组的功能，需要使用需要自己定义删除器。

weak_ptr

• 不能控制对象生存周期，指向由shared_ptr管理的对象，切不改变shared_ptr引用计数
• 需要用shared_ptr初始化
• 指向对象可能被释放掉，所以不能直接访问

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

weak_ptr<T> w(sp);  // 初始化

w = p; // p可以是weak_ptr或shared_ptr，赋值后两者共享对象
w.reset()  // w置空
w.use_count()  // 与w共享对象的shared_ptr的数量
w.expired()     // w.use_count() == 0返回true
w.lock()   // w.expired() 为true返回一个空shared_ptr，否则返回一个与w共享对象的shared_ptr

// 访问
if (shared_ptr<int> np = w.lock()) {  // np不为空成立
    // 使用np访问对象
}

allocator类

• 定义在memory头文件中，是一个模板
• allocator分配的内存都是未构造的

1
2
3
4
5
6

allocator<T> a;
a.allocate(n);  // 分配一段原始的、未构造的内存，保存n个类型为T的对象
a.deallocate(p, n);  // 释放从T*类型的指针p开始的内存，这块内存保存了n个T类型对象；p必须是由allocate函数返回的指针，n必须是p创建时要求的大小。调用之前，必须对这n个T对象调用destory

a.construct(p, args); // p必须是类型为T*的指针，指向一块原始内存，args被传递给类型为T的构造函数，用来在p指向的内存中构造一个对象
a.destory(p)  // 对p指向的对象指向析构函数

构造、填充未初始化内存的算法

1
2
3
4
5
6
7

uninitialized_copy(b, e, b2);  // 拷贝迭代器b、e指定范围元素到b2指定的未构造的原始内存中，b2指向的内存必须足够大
uninitialized_copy_n(b, n, b2); // 从b开始，n个元素

uninitialized_fill(b, e, t);  // 拷贝值均为t
uninitialized_fill_n(b, n, t);

// 这几个算法都返回下一个未初始化的内存位置

拷贝控制

拷贝、赋值与销毁

拷贝构造函数

• 成员类型决定拷贝方式，内置类型直接拷贝，类类型需要拷贝构造函数来拷贝
• 不应该是explicit的
• 参数是自身类类型的引用
• 编译器会为我们定义一个（如果我们没有定义）

拷贝初始化发生的时间不仅在用=定义变量时，也会发生在：

1. 将对象作为实参传递给非引用类型的形参
2. 从返回非引用类型的函数返回一个对象
3. 用花括号列表初始化一个数组中的元素或一个聚合类中的成员

拷贝赋值运算符

• 编译器会为我们定义一个（如果我们没有定义）

析构函数

• 编译器会为我们定义一个（如果我们没有定义）
• 一般为空，成员是在析构函数体之后隐含的析构阶段被销毁的
• 某些类中，析构函数也被用来阻止该类型的对象被销毁
• 需要析构函数的类也需要拷贝、赋值操作

使用=default

• 将拷贝控制成员定义为=default可以显式地要求编译器生成合成的版本
• 类内使用`=default’修饰的成员将隐式地声明为内联的
• 如果不希望内联，则只对类外的定义使用=default。

阻止拷贝

• 在函数第一次声明后面写上=delete表示删除的函数，不希望定义这些成员
• 拷贝构造函数、拷贝赋值运算符定义为删除的函数可以阻止拷贝
• 析构函数不能是删除的成员，因为存在对象无法销毁的问题
• 但如果你真的这么干了：如果一个类有数据成员不能默认构造、拷贝、复制、销毁，则对应的成员函数将被定义为删除的

动态内存管理类

• 在运行时分配可变大小内存的空间
• 以vector为例，添加元素的成员函数检查是否有更多空间，没有则申请新的空间，将已有元素移到新空间，释放旧空间，添加新元素

移动构造函数和std::move

• 移动构造函数通常是将资源从给定对象“移动”而不是拷贝到正在创建的对象
• 调用标准库函数move（utility头文件）表示希望使用移动构造函数

右值引用

• 右值引用是指必须绑定到右值的引用，通过&&获得
• 右值引用只能绑定到将要销毁的对象，因此可以将一个将要销毁的资源移动到另一个对象中
• 左值引用不能绑定到要求转换的表达式、字面常量、返回右值的表达式（变量是左值）
• 右值引用有相反的要求；一般右值生命周期短（字面常量、临时对象等）
• 通过move函数显式地将左值转换为对应的右值引用类型，使用move不用using声明，直接用std::move
• 右值引用做形参时不能为const，因为需要窃取他的数据

1
2
3
4

int &&r1 = 42; // correct
int &&r2 = r1;  // wrong, 变量表达式r1是左值
// 调用move后，意味着除了对r1赋值、销毁外，将不再使用它
int &&r3 = std::move(r1); // ok

移动构造函数、移动赋值运算符

• 移动构造函数的第一个参数是该类型的一个右值引用
• 必须确保移动后，源对象处于销毁无害的状态，也就是说源对象必须不再指向被移动的资源（指针置为nullptr，因为源对象可以被销毁，如果它的指针还指向被移动的资源，执行析构函数时就会将被移动的资源释放）
• 移动操作通常不抛出异常。编写不抛出异常的移动操作，应该使用noexcept通知标准库，免去其为了处理可能存在的异常做的额外工作（可能出现异常的还是不要写比较好）
• noexcept出现在参数列表之后；如果是构造函数，其在初始化列表的:之前

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

A::A(A &&a) noexcept : x(a.x), y(x.y) {
    a.x = a.y = nullptr;
}

A &A::operator=(A && a) noexcept {
    if (this == &a) return *this;  // 自赋值
    free();   // 释放现在对象的资源
    x = a.x;
    y = a.y;
    a.x = a.y = nullptr;  // 重置源对象的指针
    return *this;
}

• 只有当一个类没有定义任何自己版本的拷贝控制成员，且类的每个非static数据成员都可以移动时，编译器才会为它合成移动构造函数或移动赋值运算符。编译器可以移动内置类型的成员；也可以移动有对应移动操作的类成员
• 移到构造函数永远不会隐式地定义为删除的函数（delete）
• 如果显式要求编译器生成=default的移动操作，但编译器不能移动所有成员，则编译器将移动操作定义为删除的
• 类本身的析构函数为删除的、不可访问的，则其移动构造函数为删除的
• 如果类成员是const的或者是引用，则类的移动赋值运算符定义为删除的

1
2
3
4
5
6
7
8
9
10

struct X {
    int i;               // 内置成员可以移动
    std::string s;   //  string有自己的移动操作
};
struct Y {
    X mem;     // X有合成移动操作
};

X x1, x = std::move(x1);   // 合成移动构造函数
Y y1, y = std::move(y1);   // 使用合成移动构造函数

• 既有拷贝构造函数也有移动构造函数时，遵循移动右值，拷贝左值的方法
• 没有移动构造函数时，右值也被拷贝

1
2
3
4

A  a1, a2;
a1 = a2;  // a2是左值，使用拷贝
A getA(istream& is);  // 函数getA返回一个右值
a2 = getA();      // 返回右值，使用移动赋值

移动迭代器

• 一般的迭代器解引用操作返回一个指向元素的左值，移动迭代器的解引用操作生成一个右值引用
• 调用make_move_iterator将一个普通迭代器转化为一个移动迭代器，原迭代器的所有操作在移动迭代器中都正常工作

1
2
3

auto first = alloc.allocate(new_capacity);
// 使用移动构造函数来构造每个元素
auto last = uninitialized_copy(make_move_iterator(begin()), make_move_iterator(end()), first);

右值、左值引用成员函数、重载和引用函数

• 类成员函数的参数列表后可以放置&或&&，称为引用限定符
• 引用限定符指出this可以指向一个左值或右值
• 引用限定符只能用在非static成员函数中（类似const限定符），且必须在声明、定义中都出现
• 引用限定符就是限制调用成员函数的对象有引用限定
• &限定的函数，只能将这个函数用于左值；&&则只能用于右值
• 同时有const限定符的函数，引用限定符应该在const限定符之后const &
• 引用限定符可以区分重载版本（const也可以），表示其对象是右值还是左值
• 定义两个及以上具有相同名字和参数列表的函数，就必须对所有函数加上引用限定符，或者所有都不加。（有的加，有的不加不行）

右值执行排序，可以直接进行，因为右值没有其他用户，可以改变；但是，对const右值、左值进行排序时，不能改变对象，所以先拷贝再排序。

重载运算与类型转换

• 运算符作用域内置类型的运算对象时，运算符的含义无法改变（不能重载）
• 只能重载已有的运算符
• 不能被重载的运算符包括:: .* . ?:
• 下标运算符[]返回的是元素的引用

输入输出运算符

• 输入、输出运算符必须是非成员函数
• 一般地，重载输出运算符<<函数的第一个参数是一个非常量ostream对象引用（非常量是因为向流写入内容会改变其状态，引用是因为ostream不能拷贝），第二个参数一般是要打印对象的常量引用；函数返回ostream的形参
• 重载输入运算符函数的第二个参数非常量对象的引用，返回istream的形参
• 重载输入运算符要处理可能失败的情况，输出则不需要

1
2
3
4
5
6
7
8
9

ostream& operator<<(ostream& os, const A& a) {
    // ...
    return os;
}

istream& operator>>(istream& is, A& a) {
    // .... 包括处理失败情况
    return is;
}

递增递减运算符

• 区分前置、后置的办法是：后置版本有一个不被使用的int类型形参
• 后置版本需要先记录对象的状态，操作完成后返回之前记录的状态
• 后置运算符返回对象的原值，不是引用
• 显式调用后置运算符需要多加一个参数: a.operator++(0);

1
2
3
4
5
6
7
8

A& operator++();    // 前置
A operator++(int);  // 后置，有形参，返回原值

A A::operator++() {
    A ret = *this;
    ++*this;
    return ret; // 返回之前的记录
}

成员访问运算符

• 包括解引用*和箭头运算符->两种
• ->必须是类成员，解引用通常是类成员

1
2
3
4
5
6
7
8
9
10

string& operator*() const {
    // 检查curr是否在有效范围内，如果是，返回curr所知元素的引用
    auto p = check(curr, "dereference past end");
    return (*p)[curr];          // *p是对象所指的vector
}

string * operator->() const{
    // 将工作委托给解引用运算符
    return & this->operator*();
}

函数调用运算符

• 重载函数调用运算符就可以向调用函数一样使用类对象
• 由于可以像使用函数对象那样使用，重载调用运算符可以替代lambda表达式

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

struct absInt() {
    int operator()(int val) const {   // 注意参数放在后面的括号里
        return val<0? -val:val;
    }
}
absInt ai;
ai(-10);  // 返回10


stable_sort(words.begin(), words.end(), [](const string& s1, const string& s2){return s1.size < s2.size()};);
// 类似于
class short_string {
public:
    bool operator()(const string& s1, const string& s2) const{
        return s1.size < s2.size();
    }
}
// short_string()构造一个对象，由于重载了调用运算符，就可以看作"可调用对象"使用
stable_sort(words.begin(), words.end(), short_string());

标准库定义的函数对象

标准库定义了一组表示算术运算符、关系运算符和逻辑运算符的类，每个类分别定义了一个执行命名操作的调用运算符（所以其对象也可以被“调用”）。

1
2
3
4
5
6
7
8
9
10

plus<int> intadd;
intadd(10, 15);  // 25

negate<int> intnegate;
intnegate(10);  // -10
intnegate(intadd(10,15));  // -25

sort(vec.begin(), vec.end(), greater<string>());
// 如果vector里面是string*也照样可以
sort(vec.begin(), vec.end(), greater<string*>());

可调用对象与function

C++中的可调用对象包括：函数、函数指针、lambda表达式、bind创建的对象、重载了调用运算符的类

• function类型定义在functional头文件中，是一个模板

1
2
3
4
5
6
7
8
9
10

function<T> f;  // f是用来存储可调用对象的空的function，T限定函数类型（T就是`返回值 (各个参数)`）
function<T> f(nullptr);  //  显式构造一个空的function
function<T> f(obj);  // f中存储可调用对象obj的副本
f                               // f中有可调用对象为真，否则为假
f(args);                    // 调用f中的对象，args是参数

// 定义为function<T>的成员类型
result_type       // 可调用对象的返回类型
argument_type // T一个实参时，实参的类型
first_argument_type, second_argument_type

使用示例

1
2
3
4
5
6
7

function<int(int, int)> f1 = add;    // 函数指针
function<int(int, int)> f2 = divide(); // 重载了调用运算符的类的对象
function<int(int, int)> f3 = [](int i, int j) {return i+j;};  // lambda表达式

f1(3,4);
f2(3,4);
f3(3,4);

重载、类型转换与运算符

• 可以通过定义类类型转换运算符达到类类型转换的效果
• 转换构造函数和类型转换运算符共同定义了类类型转换

类型转换运算符

• 类型转换运算符是类成员函数
• 可以面向除了void*之外的任意类型进行定义，只要该类型能作为函数的返回类型（数组、函数类型就不行）
• 一般形式operator type() const
• 类型转换运算符是隐式执行的，没有形参，不能传递实参，不能指定返回类型
• 可能产生意外结果

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

class smallInt {
public:
    smallInt(int i=0) : val(i) {
        if (i<0 || i>255) throw std::out_of_range("Invalid value");
    }
    operator int() const {return val;}
    int operator int() const; // wrong，不能有返回类型
    operator int(int = 0) const; // wrong，不能有形式参数

private:
    std::size_t val;
}
smallInt si;
si = 4;  // 先将4隐式转换为smallInt，再调用赋值运算符
si+3;    // 先将si隐式转换为int，再执行整数加法

smallInt s = 3.14;  // 内置类型转换double->int，再调用smallInt(int)构造
s+3.14                // smallInt先转成int，内置类型再将int转换成double

由于隐式转换可能会带来意想不到的结果，所以有时候需要使用显式的类型转换运算符。定义显式类型转换运算符只需要加上explicit即可，但转换时就行必须使用显式的强制转换方式。
有一个例外：当表达式被用作条件判断（if, while, do, for, &&, ||, !, ?:），编译器会将显式的类型转换自动用于它，也就是会隐式执行

1
2
3
4
5

explicit operator int() const {return val;}  // 改变的类型转换运算符

smallInt si = 3; // ok
si+3                 // wrong，此处需要隐式转换，但转换函数是显式的
static_cast<int>(si) + 3  // 显示请求转换

IO类型可以向void*转换，C++11下支持将IO类型向bool显式类型转换，IO类型向bool的转换一般定义成显式（explicit），因为通常用在条件判断部分，所以也可以隐式执行。

二义性问题

二义性类型转换的途径

• 两个类提供了相同的类型转换（分别通过构造函数和类型转换运算符）
• 定义了多个转换规则，这些转换涉及的类型本身可以通过其他类型转换联系在一起

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

struct A {
    A(int = 0); // 最好不要创建两个转换源都是算术类型的类型转换
    A(double);
    operator int() const;  // 最好不要创建两个转换对象都是算术类型的类型转换
    operator double() const;
    // other member
}
void f2(long double);

A a;
f2(a);  // 二义性错误，两个类型转换函数都可以

long lg;
A a2(lg);  // 二义性，编译器无法区分long转int和double的好坏

short s = 42;
A a3(s);  //ok, 使用A::A(int)

但是short转int确实比short转double好

重载函数于转换构造函数

• 如果两个或多个类型的转换都提供了同一种可行的匹配，则这些类型转换一样好
• 即使其中一个能精确匹配，另一个需要额外的标准类型转换，编译器也会将其表示为二义性错误

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

struct C {
    C(int);
    ...
}
struct D {
    D(ing);
    ...
}

void f(const C&);
void f(const D&)
f(10);  //二义性

// ---------------------------------分割线----------------------------------

struct E {
    E(double);
    ...
}
void f(const C&);
void f(const E&);
f(10);  // 依旧二义性错误，即使其中一个能精确匹配，另一个需要额外的标准类型转换，编译器也会将其表示为二义性错误

函数匹配与重载运算符

• 表达式中运算符的候选函数集包括成员函数和非成员函数
• 如果对同一个类既提供了转换目标是算术类型的类型转换，也提供了重载的运算符，则将会遇到重载运算符与内置运算符的二义性

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

class A {
friend A operator+(const A& a, const A& b);
public:
    A(int = 0);
    operator int() const {return val};
private:
    size_t val;
}

A a1, a2;
A a3 = s1 + s2;  // 使用重载的operator+
int i = s3 + 1;    //  二义性错误

面向对象程序设计 OOP

• OOP的核心思想是数据抽象、继承和动态绑定

基类与派生类（父类与子类）

• 子类经常覆盖父类中的虚函数，如果不覆盖，子类将直接继承父类的版本
• 能把子类对象当成父类对象来用，也能把父类的指针或引用绑定到子类对象的父类部分上
• 子类构造函数先初始化父类部分，然后按照声明顺序依次初始化子类成员
• 派生类可以访问基类的公有和受保护成员

• 基类中的静态成员在整个继承体系中都只存在该成员的唯一定义，如果是private的，派生类就不能访问
• 声明派生类时不能加上派生列表
• 派生类一定要有定义，类不能派生自己
• 使用final关键字可以禁止类被继承

1
2
3

class father {};
class A final : public father {};  // ok, 但A不能被继承
class B : public A{};  // 错误，A是final的

• 派生类向基类的自动类型转换只对指针、引用类型有效
• 用派生类对象为基类对象初始化或者赋值时，其派生类独有的部分会被忽略

虚函数

• 运行时动态绑定
• 所有虚函数都必须有定义
• 派生类中的虚函数可以不加virtual关键字，因为一旦某个函数被声明为虚函数，他在所有派生类中都是虚函数
• 覆盖基类虚函数的派生类函数必须在形参上与派生类完全一致
• override关键字用来说明派生类中的虚函数
• final关键字阻止函数派生类覆盖此函数
• 如果虚函数使用默认实参，实参由本次调用的静态类型决定（使用基类的指针就用基类的虚函数默认实参），所以最好定义派生类、基类虚函数的默认实参一致
• 回避虚函数机制，可使用作用域运算符机制

1
2
3
4
5
6
7
8
9
10

class A {
virtual void f1() const;
};
class B : A {
virtual void f1() const final;  // 不允许后续的其他类覆盖f1
};

A * a = new B();
a->f1();  // 调用B类中的虚函数f1
a->A::f1();  // 无论a类型是什么，都是用A中的虚函数f1

抽象基类

• 抽象基类负责定义接口，不能直接创建其对象

纯虚函数

• 在函数声明加上=0就可以将函数声明为纯虚函数
• 纯虚函数无需定义，非要定义的话必须在类的外部

访问控制与继承

受保护的成员 protected

• 类的用户不能访问受保护的成员，私有的更不行
• 派生类的成员、友元可访问继承来的protected、public成员，private不行
• 派生类的成员、友元只能通过派生类对象访问基类的受保护成员。派生类无法访问基类对象中的受保护成员

1
2
3
4
5
6
7
8
9
10
11

class base {
protected:
    int mem;
};
class sneak : base {
    friend void get(sneak&);  // 可以通过自身对象访问基类的受保护部分
    friend void get(base&);   // 不能访问基类对象中的受保护成员
    int j; // private
};
void get(sneaky& s){s.j = s.mem = 0;}
void get(base &b) {b.mem = 0;}  // 错误，不能访问

• 派生类对其继承而来的成员的访问权限收到两个因素影响：
  • 基类中该成员的访问说明符
  • 派生类的派生列表中的访问说明符
• 派生访问说明符对于派生类的成员及其友元能否访问直接基类的成员没什么影响，其对基类成员的访问权限只与基类中的访问说明符有关
• 派生访问说明符的目的是控制派生类用户（包括派生类的派生类）对于基类成员的访问权限
  • 如果继承是公有的，成员遵循原有的访问说明符
  • 如果继承是私有的，则所有对象都是私有的
  • 如果继承是protected的，原本public的称为protected的

派生类向基类转换的可访问性（假定D继承自B）

• 只有继承方式是public，用户代码才能使用派生类向基类的转换
• 无论以什么方式继承，D的成员和友元都能使用派生类向基类的转换
• 如果D以public或protected方式继承B，则D的派生类的成员和友元可以使用D向B的转换
• 要改变个别成员的可访问性，可使用using关键字

1
2
3
4
5
6
7
8
9
10

class base {
protected:
    int mem, n;
};
class derived : private base{
public:
    using base::mem;
protect:
    using base::n;
};

友元与继承

• 友元关系不能继承

继承中的类作用域

• 先名字查找再类型检查（p->mem(), obj.mem()）
  1. 确定p的静态类型，因为调用的是成员，该类型必然是类类型
  2. 在p的静态类型对应的类中查找mem，找不到则直接基类中查找直到继承链最顶端。还是找不到就报错
  3. 一旦找到mem，就进行常规的类型检查以确认本次调用是否合法
  4. 如果调用合法，则编译器将根据调用的是否是虚函数产生不同的代码
• 内层作用域的函数不会重载声明在外层作用域的函数
• 名字查找过程中，派生类会隐藏基类的同名成员（即使形参列表不一样）

1
2
3
4
5
6
7
8
9
10

class base {
int f();
};
class derived : private base{
int f(int);  // 隐藏了基类的f()
};

base b; derived d;
d.f(10);  // ok
d.f();      // wrong，参数列表为空的f函数被隐藏了

拷贝函数与拷贝控制

虚析构函数

• 派生类会继承基类析构函数的虚属性
• 基类虚析构函数能保证delete基类指针时使用正确的析构函数版本
• 定义了虚析构函数的类，编译器就不会为其合成移动操作

派生类中删除的拷贝控制与基类的关系

• 基类中的默认构造函数、拷贝构造函数、拷贝赋值运算符或析构函数是被删除的或不可访问的，则派生类中对应的成员将是删除的
• 基类中的析构函数是不可访问或删除的，那么派生类中的合成的默认和拷贝构造函数都是删除的
• 基类中对应操作是删除的，派生类中的也会是删除的（比如说移动构造函数）

移动操作与继承

• 带有虚析构函数的类，编译器不会为其合成移动操作，所以其子类也没有
• 确实需要移动操作时，可以显式地定义（可以使用合成版本）

1
2
3
4
5
6
7
8
9
10

class A {
public:
    A() = default;   // 默认构造
    A(const A&) = default;   // 拷贝构造
    A(A&&) = default;        // 移动构造
    A& operator=(const A&) = default;   // 拷贝赋值
    A& operator=(A&&) = default;        // 移动赋值
    virtual ~A();
    // ......
}

派生类的拷贝控制

• 派生类在拷贝、移动的同时要拷贝、移动基类部分(显式地)
• 派生类赋值运算符的处理方法也类似
• 派生类的析构函数只负责销毁派生类自己分配的资源

1
2
3
4
5
6
7
8
9
10
11

class base {};
class D : private base{
    D(const D& d) : base(d), /*D的成员初始值*/ {...} // d作为参数将被绑定到类型为base&的实参上
    D(D&& d) : base(std::move(d)), /*D的成员初始值*/ {...}
};

D& D::operator= (const D& d) {
    base::operator=(d);  // 为基类部分赋值
    // 酌情处理自赋值、释放已有资源
    return *this;
}

在构造函数和虚构函数中调用虚函数

• 如果构造函数或析构函数调用了某个虚函数，则程序会执行与调用构造函数或析构函数所属类型相对应的虚函数版本
• 这个例子：创建派生类对象时，先调用基类的构造函数，此时对象的派生类部分是未被初始化的，调用派生类的虚函数存在风险，所以应该调用基类的虚函数。

继承的构造函数

• 一个类可以继承其直接基类的构造函数
• 类不能继承默认、移动、拷贝构造函数
• 继承方式是使用using base::base;就可以继承base的构造函数，对于基类的构造函数，编译器将会为派生类与之对应的派生类版本derived(params) : base(args) {}
• 构造函数的using声明不会改变该构造函数的访问级别（私有还是私有，公有还是共有）
• 当基类构造函数有默认实参，派生类将获得多个构造函数，每个构造函数省略掉一个含有默认实参的形参
• 派生类不继承某些构造函数的原因可能是：
  • 派生类自己定义了有相同参数列表的构造函数
  • 默认、移动、拷贝构造函数按照正常规则被合成

容器与继承

• 不能把具有继承关系的对象放在一个容器中
• 在容器中放置（智能）指针而非对象
• 派生类的（智能）指针可以隐式转换为基类的（智能）指针

1
2
3

vector<shared_ptr<quote>> basket;
basket.push_back(make_shared<quote>("00001", 50));
basket.push_back(make_shared<derived_quote>("972719", 35, 21, 7));

多重继承与虚继承

多重继承

• 每个基类包含一个可选的访问说明符
• 关键字class的默认访问说明符是private，struct的默认访问说明符是public
• 派生类的对象包含每个基类的子对象，派生类的构造函数初始值只能初始化它的直接基类
• 基类的构造顺序与派生列表中的基类出现的顺序一致
• 多重构造在析构时，顺序与构造时相反，派生类的析构函数只负责销毁自己的部分
• 派生列表中，同一个基类只能出现一次

多重继承构造函数的继承

• C++11中允许派生类从他的基类中继承构造函数
• 如果继承的多个构造函数相同（形参列表完全相同），程序产生错误
• 如果不想上述错误出现，这个类必须为该构造函数定义它自己的版本

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

struct base1 {
    base1() = default;
    base1(const string&);
};
struct base2 {
base2() = default;
base2(const string&);
};
// D1尝试继承两个基类中的参数为 const string& 的构造函数
struct D1 : public base1, public base2 {
    using base1::base1;  // 继承base1
    using base2::base2;  // 继承base2
};

struct D2 : public base1, public base2 {
    using base1::base1;  // 继承base1
    using base2::base2;  // 继承base2
    // 定义自己的 参数为 const string& 的构造函数
    D2(const string& s) : base1(s), base2(s);
    D2() = default;  // 一旦D2定义了自己的构造函数，就必须出现这个
};

类型转换与多个基类

• 可以使某个可访问的基类的指针、引用直接指向一个派生类的对象
• 编译器认为基类们向派生类的转换不分优劣，因此可能会产生二义性错误

虚继承

• 派生类可能通过直接基类间接继承自同一个间接基类，所以派生类对象会包含两份间接基类的对象
• 虚继承可以解决上述问题，其目的是令某个类作出声明，承诺愿意共享它的基类
• 共享的基类称为虚基类
• 含有虚基类的对象构造顺序：虚基类总是先于非虚基类构造
• 先虚：虚子对象按照他们在派生列表中出现的顺序从左向右出现，然后才是非虚对象从左向右

1
2
3

// base是D1、D2的虚基类
class D1 : public virtual base {};
class D2 : virtual public base {};

class Character {};
class BookCharacter : public Character{};
class ZooAnimal {};
class Bear : public ZooAnimal{};
class ToyAnimal{};
class TeddyBear : public BookCharacter, public Bear, public virtual ToyAnimal{};
// 构造TeddyBear时，构造顺序如下：
ZooAnimal();
ToyAnimal();
Character();
BookCharacter();
Bear();
TeddyBear();

标准库特殊设施

bitset类

#include <bitset>

定义与初始化

操作

随机数

#include <random.h>

随机数引擎类和随机数分布

随机数引擎是函数对象类，定义了调用运算符，该运算符不接收参数并返回一个随机unsigned整数

1
2

default_random_engine e;
e();

随机数引擎操作如下：

为了得到一个指定范围内的数，使用一个分布类型的对象

1
2
3
4
5

// 0-9之间的均匀分布
// u是一个调用运算符，接受一个随机数引擎作为参数
unifrom_int_distribution<unsigned> u(0, 9);
default_random_engine e;
cout << u(e) << endl;

其他随机数分布

• 使用uniform_real_distribution<double>类型的对象生成随机浮点数，用法类似上面
• uniform_real_distribution<>默认为double类型
• 高斯分布：normal_distribution<> n(u, sigma); // 均值为u，标准差为sigma
• lround(a)函数对a进行四舍五入转化为整数，来自头文件cmath
• bernoulli_distribution b(p)一次成功概率为p。它不是模板类（没有<>）

BM介绍

KMP算法是一种利用模式串前缀移动的字符串匹配算法，时间复杂度为O(n)。
BM算法是一种使用了两个跳转表的字符串匹配算法，单模式匹配有更加出色的表现。

上图表述了BM算法的大致过程，模式串是AT-THAT，于KMP不同，BM算法对每一次匹配尝试从后向前匹配的方法。

1. 第一次匹配从第7位开始。第7为不能匹配，移动模式串，注意到目标串第7为为F，F不在模式串中，所以可以直接将模式串的首位移到目标串第8位。

2. 接着从后向前匹配，目标串的14位-与模式串最后一位不匹配，但是-在模式串中，所以将模式串中最靠后的-移到与目标串的14位对齐。

3. 再从后向前匹配，目标串的第18位T与模式串的最后一位匹配，向前看一位，17位L不匹配，且L不在模式串中，所以把模式串第一位移到目标串第18位。

4. 接着从后向前匹配，第23、24位匹配，22位不匹配，由于模式串的前两位等于后两位，所以将模式串移动使其前两位到后两位的位置上。

坏字符规则

假设目标串T长度为n，模式串P长度为m

坏字符规则分为两种情况：

• 坏字符没出现在模式串中，这时可以把模式串首移动到坏字符的下一个字符
• 坏字符出现在模式串中，这时可以把模式串第一个出现的坏字符和母串的坏字符对齐（当然，这样可能造成模式串倒退移动）

使用一个数组bad，bad['k']表示坏字符在模式串中最左侧的字符'k'距离模式串末尾的长度，如果字符’k’不在模式串中，bad['k']=m。那么遇到坏字符时模式串可以移动的距离为：bad[T[i]]-(m-1-i).

1
2
3
4
5
6
7

// m为模式串长度
void get_bad (const char* P, int m, int* bad) {
    for (int i=0; i<256; i++)
         bad[i] = m;
    for (int i=0; i<m; i++)
        bad[P[i]] = m-i-1;
}

好后缀规则

发现某个字符不匹配的同时，已有部分字符匹配成功。假设模式串P已经匹配成功的部分为Q

• 模式串中有子串匹配上好后缀，此时移动模式串，让该子串和好后缀对齐即可，如果超过一个子串匹配上好后缀，则选择最靠左边的子串对齐
• 模式串中没有子串匹配上好后缀，此时需要寻找模式串的一个最长前缀，并让该前缀等于好后缀的后缀，寻找到该前缀后，让该前缀和好后缀对齐即可
• 模式串中没有子串匹配上后后缀，并且在模式串中找不到最长前缀，让该前缀等于好后缀的后缀。此时，直接移动模式到好后缀的下一个字符

为了实现好后缀规则，需要定义一个数组suffix[]，其中suffix[i] = s 表示以i为右边界，与模式串后缀匹配的最大长度为s，即P[i-s:s]==P[m-s:m]，

1
2
3
4
5
6
7
8
9

void suffixes(const char *P, int m, int *suff) {
    suff[m-1]=m;
        for (i=m-2；i>=0；--i){
            q=i;
            while(q>=0&&P[q]==P[m-1-i+q])
                --q;
            suff[i]=i-q;
    }
}

定义good[]数组表示遇到好后缀时，模式串应该移动的距离。其中i表示好后缀前面一个字符的位置（也就是坏字符的位置）.对应上面三种情况，good数组构建方法如下：

上面的三种情况，移动的距离是逐渐增大的，在满足不止一种情况时，应该移动最小的距离。所以分三部分考虑，

• 对第三种情况，移动距离就是P的长度
• 对第二种情况，我们要找前缀，所以如果位置i到第一个是满足条件的话，必然有suff[i]=i+1，满足条件时，坏字符出现在[0,m-1-i)位置上时都可以移动m-1-i位使得模式串前i+1位与后i+1位重叠。对于i，从大到小计算是因为越长的前缀意味着越小的移动步数，我们希望找到小的，更新时判断good[j]==m也是为了不多次更新。
• 对第一种情况，我们知道当m-1-suff[i]位置为坏字符时，需要移动m-i-1位

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

void get_good(const char *P, int m, int bmGs[]) {
    int i, j, suff[256];
    suffixes(x, m, suff);
    // 第三种情况
    for (i = 0; i < m; ++i)
        good[i] = m;
    j = 0;
    // 第二种情况
    for (i = m - 1; i >= 0; --i)
        if (suff[i] == i + 1)
            for (; j < m - 1 - i; ++j)
            if (good[j] == m)
                good[j] = m - 1 - i;
     // 第一种情况
     for (i = 0; i <= m - 2; ++i)
          good[m - 1 - suff[i]] = m - 1 - i;
}

最后给出BM算法，对于出现无法匹配的时候，移动步数取好后缀和坏字符两种情况的最大值。完整代码如下：

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

void BM(char *P, int m, char *S, int n) {
    int i, j, good[m], bad[256], k=0;
 
    /* Preprocessing */
    get_bad(P, m, bad);
    get_good(P, m, good);
    i = j = m-1;
    /* Searching */
    j = 0;
    while (j <= n - m) {
        while (i!=0 && P[i]==S[j]) {  // 从后向前匹配、直到找到不匹配或者完全匹配
            --i;
            --j;
        }
        // 找到一个匹配
        if (i==0 && P[i]==S[j]) {
            m++;
            j += good[0];  // 找到匹配算是好后缀情况
        } else {
            j += good[i]>bad[S[j]] ? good[i] : bad[S[j]];
        }
        i = m-1;
   }
}

决策树模型

• 决策树是一种基本的分类与回归的方法
• 决策树由节点和有向边组成
• 节点分为内部节点和叶节点
• 决策树的学习其实就是特征选择的过程

决策树学习

决策树学习算法包含特征选择、决策树的生成和决策树的剪枝过程

给定数据集$D=\lbrace (x_1,y_1),…,(x_m,y_m) \rbrace$其中$m$为样本容量，$x_i=(x_i^{(1)},…,x_i^{(n)})$，$n$为特征个数；$y_i\in \lbrace 1,2,…,K \rbrace$为类标记。

信息增益

统计学中，熵是随机变量不确定性的度量，即混乱程度。假设$X$是一个取有限个值的离散随机变量，其概率分布为$P(X=x_i)=p_i,i=1,..,N$，那么$X$的熵定义为$H(X)=-\sum_{i=1}^n p_i log p_i$条件熵$H(Y|X)$可以表示为已知随机变量$X$的条件下，随机变量$Y$的不确定性，也可以表示成$H(Y|X)=\sum_{i=1}^N p_iH(Y|X=x_i)$其中$p_i=P(X=x_i)$。当熵和条件熵中的概率由数据估计得到时，则分别称之为经验熵和条件经验熵，如果出现0概率，则令$0log0=0$。

信息增益表示在得知特征$X$的情况下而使得$Y$的不确定性减少的程度，形式化表述为：特征$A$对训练数据集$D$的信息增益$g(D,A)$，定义为$g(D,A)=H(D)-H(D|A)$这里的信息增益等价于训练数据集中类与特征的互信息。计算信息增益的算法如下：

输入：数据集$D$和特征$A$

1 计算数据集$D$的经验熵$H(D)=-\sum_{k=1}^K \frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$
2 计算特征$A$对数据集$D$的经验条件熵$H(D|A)=\sum_{i=1}^N \frac{|D_i|}{|D|}H(D_i)=-\sum_{i=1}^N \frac{|D_i|}{|D|}\sum_{k=1}^K\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|}$
3 计算信息增益$g(D,A)=H(D)-H(D|A)$.

输出信息增益

信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，使用信息增益比可以缓解这个问题。特征$A$对训练数据集$D$的信息增益比定义为其增益信息$g(D,A)$与训练数据集$D$关于特征$A$的值的熵$H_A(D)$之比，即

其中，$H_A(D)=-\sum_{i=1}^{A_n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$，$A_n$是特征$A$取值的个数。

ID3

ID3算法采用自上而下递归式的算法构建决策树，它使用信息增益作为特征选择的标准。停止条件是节点所有特征的信息增益都很小（阈值$\epsilon$）或没有特征可以选择为止。

输入：训练数据集$D$，特征集$A$，阈值$\epsilon$

1 若$D$中所有实例属于同一类$C_k$，$T$为单节点树，$C_k$为该节点的类标记，返回$T$
2 若$A=\emptyset$则$T$为单节点树，将$D$中实例数最大的类$C_k$作为该节点的类标记，返回$T$
3 否则，分别计算$A$中各特征对$D$的信息增益，选择信息增益最大的特征$A_g$
4 如果$A_g<\epsilon$，则置T为单节点树，将$D$中实例数最大的类$C_k$作为该节点的类标记，返回$T$
5 否则，对$A_g$的每一个可能值$a_i$，根据$A_g=a_i$将$D$分割成若干非空子集$D_i$，将$D_i$中实例数最大的类作为标记，构建子节点，由节点及其子节点构成树$T$，返回$T$
6 对每个子节点$i$，以$D_i$为训练集，以$A-A_g$为特征集，递归调用以上步骤

输出：决策树$T$

C4.5

C4.5与ID3的差异在于C4.5使用信息增益比进行选择选择

基尼指数

基尼指数表示不确定程度，基尼指数越大，样本集的不确定程度就越大、纯度越低。

分类问题中，假设有$K$个类，样本点属于第$k$类的概率为$p_k$，则概率分布的基尼指数定义为$Gini(p)=1-\sum_{k=1}^K p_k^2$对于给定的样本集$D$，其基尼指数为$Gini(D)=1-\sum_{k=1}^K\left( \frac{|C_k|}{|D|} \right)^2$其中$C_k$表示第$k$类的样本子集。表示集合$D$的不确定性。

假设样本集$D$根据特征$A$的不同取值被分成$A_n$个部分，则定义在特征$A$下集合$D$的基尼指数为

CART

CART分类树
使用基尼指数作为划分属性的标准，每次选择基尼指数最小的属性。

CART回归模型
假设已将输入空间划分为$M$个单元$R_1,…,R_M$，并且在每个单元$R_m$上有一个固定的输出值$c_m$，回归树模型可以表示为$f(x)=\sum_{m=1}^Mc_mI(x\in R_m)$当输入空间划分确定时，可以用平方误差$\sum_{x_i}(y_i-f(x_i))^2$表示训练误差, $c_m$输出值为对应$R_m$上所有样本输出值的均值。

使用启发式的方法划分输入空间，遍历输入变量和可能的切分变量找到最优的切分变量$j$和切分点$s$，即找到切分后部分的误差最小：

其中$c_1,c_2$是划分后部分中输出值的均值。最小二乘回归树算法描述如下：

输入：训练集$D$

1. 选择最优切分变量$j$与最优切分点$s$，求解$\min_{j,s} \left[ \min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2 + \min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2 \right]$
2. 用选定的对$(j,s)$划分区域并决定相应输出值：$R_1,R_2,c_1,c_2$
3. 继续对两个子区域调用步骤1、2直至满足停止条件
4. 将输入空间划分为$M$个区域$R_1,…,R_M$，生成CART树$f(x)=\sum_{m=1}^Mc_mI(x\in R_m)$

输出：$f(x)$

决策树的剪枝

以上方法可能会产生过拟合现象，适当剪枝会使得决策树的泛化效果变得更好
剪枝分为预剪枝和后剪枝两种，预剪枝指的是在决策树生成的过程中进行剪枝，后剪枝则是在生成决策树之后再进行剪枝。

预剪枝

大致过程描述：对于一个节点，考虑其剪枝或者不剪枝的情况，看这两种情况下哪种正确率高（一个节点的类别由其包含同类样本数最多的决定），由此决定是否剪枝。

预剪枝基于贪心本质禁止某些节点展开，而这些节点第一次展开效果可能不好，但后续表现可能显著提高，所以会带来欠拟合的风险。

后剪枝

大致过程描述：自下而上，叶节点不考虑，考虑其父节点F是否需要剪枝，可以仅仅通过父节点包含的样本，在剪枝和不剪枝的情况下分别计算准确率，然后确定是否需要剪枝。

下面是令一种后剪枝的方法（我不是很了解）：
通过极小化决策树整体的损失函数来实现。设树的叶节点个数为$|T|$，$t$是树$T$的叶节点，此叶节点上有$N_t$个样本，属于类$C_k$的样本有$N_{tk}$个，$H_t(T)$为叶节点$t$上的经验熵，$\alpha \ge 0$为参数，则决策树学习的损失函数可以定义为

其中经验熵为$H_t(T)=-\sum_k \frac{N_{tk}}{N_t}log_2 \frac{N_{tk}}{N_t}$。$C(T)$表示模型对训练数据的预测误差，|T|表示模型的复杂度。剪枝算法描述如下：

输入：决策树$T$，参数$\alpha$

1 计算每个节点的经验熵
2 递归地从树的节点向上回溯，如果保留子节点的损失函数更大，剪枝以父节点作为叶子
3 返回2直到不能继续为止

输出：修建后的决策树$T_{\alpha}$

朴素贝叶斯分类器

输入空间$\mathbb{R}$为$n$维向量的集合，输出空间为类标记集合$\mathcal{Y}=\lbrace c_1,c_2,…,c_K \rbrace$，给定训练数据集$T=\lbrace (x_1,y_1),...,(x_N,y_N) \rbrace$由联合概率分布$P(X,Y)$独立同分布产生。

朴素贝叶斯分类器旨在最大化后验概率，即

由于对于每一个不同的类别，上式中的分母都是一样的，所以上面的目标公式可以写成

对于这个优化目标，可做如下统计

朴素贝叶斯分类器对条件概率分布进行了条件独立性的假设 而$P(X=x|Y=c_k)$可以分解为

所以上式可以分开考虑，即在满足$Y=c_k$的集合中分别考虑，$P(X^{(1)}=x^{(1)}|Y=c_k)$就等于$Y=c_k$的集合中第一个属性为$x^{(1)}$样本所占的比例，所以上式可以写成

所以，经过统计，就可以使用后验概率最大准则进行分类。

当然，也可以使用极大似然估计对单个属性和属性进行建模，用$D_c$表示数据集中第$c$类样本的集合，参数$\theta_c$表示对第$c$类样本的建模，所以有

对$P(x|\theta_c)$进行适当建模，比如$P(x|\theta_c) \sim \mathcal{N}(\mu_c, \sigma^2_c)$，然后用经典的极大似然估计进行估值即可。

贝叶斯估计

对于朴素贝叶斯分类器，做如下统计计算时

分子、分母可能为0，所以这里使用拉普拉斯平滑，所以统计方法如下

其中，$K$是分类类别总数，而$K_j$表示第$j$个属性的可能取值数，$\lambda$是平滑参数，为1时则为Laplace平滑。

变量和基本类型

初始化

列表初始化

C++11中，一下初始化方法都是成立的

1
2
3
4

int x = 0;
int x = {0};
int x{0};
int x(0);

使用花括号初始化变量在C++11中得到全面应用，但是用于内置类型的变量时，使用花括号初始化形式有个重要的特点：

使用列表初始化且初始化存在丢失信息的风险，编译器将报错

比如

1
2
3

double db = 3.141592653;
int x{db};              // 错误，转换存在丢失信息的风险
int y(db);              // 正确，转换执行，丢失部分信息

默认初始化

如果内置类型的变量未被显示初始化，它的值由定义的位置决定。定义与任何函数体之外的变量初始化为0，定义于函数体内部的内置类型将不会被初始化。

定义与声明

• 声明使得名字为程序所知，定义负责创建与名字关联的实体
• 只声明一个变量而非定义它，使用extern关键字，不要显示初始化
• 任何包含了显示初始化的声明即成了定义
• 变量只能定义一次，但是可以声明多次

1
2
3

extern int i;     // 声明
int j;            // 声明且定义
extern int k = 2; // 定义

复合类型

引用

• 引用必须被初始化，因为引用是要和初始值绑定到一起的
• 引用不能被重新绑定到另一个对象
• 引用不能被绑定到字面值、表达式计算结果
• 引用类型要与绑定对象类型严格匹配，只在极少数情况下有例外
• 因为引用不是对象，所以不能创建引用的引用

1
2
3
4
5
6
7

int x=10, &y = x, z=20;
&y = z;         // 错误，不能重新绑定
y = z;          // 正确，相当于赋值

int &i = 10;   // 错误
double j = 2.55;
int &k = j;    // 错误，类型不匹配

指针

• 指针是一个对象，可以有指针的指针，且无需定义时赋初值
• 指针类型要与其指向对象类型严格匹配，只在极少数情况下有例外

1
2
3
4

// 生成空指针的方法
int *p1 = nullptr;
int *p2 = 0;
int *p3 = NULL;

void*指针

• 可以存放任意对象的地址
• 不能直接操作void*指针指向的对象，因为不知道其类型

const

• const对象必须初始化，一旦创建，不能修改
• 利用一个对象去初始化另一个对象，无论他们是不是const都无关紧要，因为拷贝不会改变什么
• 默认情况下，const变量尽在文件内有效
• 多个文件共享的方法：声明、定义都添加extern关键字

1
2
3
4
5

// file 1，定义、初始化
extern const int x = getSize();

// file 2，再次声明一下，与file 1中的是同一个
extern const int x;

const引用

• 不能通过引用改变常量的值
• 初始化常量引用时允许用任意表达式作为初始值，只要表达式结果能转换成引用类型即可
• 允许为一个常量引用绑定非常量对象、字面值，甚至表达式，非常量不行

1
2
3
4
5

int i = 42;
const int &r1 = i; // correct
const int &r2 = 42; // correct
const int &r3 = r1*2; // correct
int &r4 = r1*2;     // 错误，r4是非常量引用

指针和const

指向常量的指针

• 允许指向常量的指针指向非常量对象
• 常量对象的地址只能存在指向常量的指针里

常量指针

• 常量指针是常量，必须初始化，且一旦初始化就不能改变，但其指向的对象可以被改变

顶层const
顶层const表示指针本身是个常量，顶层const表示指针指向一个常量
左为底，右为顶即可分辨

1

const int k=0; // 这个也是顶层const

constexpr和常量表达式

• 常量表达式的值不会改变，且在编译时期就能得到结果
• C++11中将变量声明为constexpr类型，由编译器验证变量的值是否为常量表达式
• 声明为constexpr的变量一定是常量，且必须用常量表达式初始化
• 一个constexpr指针的初始值必须是nullprt或者0，或是存储与某个固定地址（比如全局变量，局部变量不行）中的对象
• constexpr声明的指针，仅对指针有约束，不能约束指向的对象，顶层const

1

constexpr int * p = nullptr; // p是指向整数的常量指针

处理类型

类型别名

typedef和别名声明

1
2
3

typedef double wage, *p; // wage是double同义词，p相当于double*

using vi = vector;

auto

• auto定义的变量必须有初始值
• auto可以一次声明多个变量，但是这些变量的初始基本数据类型必须一样
• auto推断的类型与原始类型可能会不太一样，比如auto会忽略掉顶层const
• 引用类型也可以是auto，原来初始化规则适用

1
2
3
4
5
6
7

const int i = 0;
auto a = i;       // a是一个整数，顶层const被忽略
const auto b = i; // b是一个const int

auto &c = i;
auto &d = 42; // 错误
const auto &e = 42; // 正确

decltype

• decltype的作用是选择并返回操作数的严格基本类型
• 如果decltype使用的表达式是一个变量，则decltype返回该变量的类型（包括const和引用）
• 如果表达式内容是解引用，decltype得到引用类型
• 如果变量名加上了一层或多层括号，就会被当成表达式，会得到引用类型

1
2
3
4
5
6
7
8
9
10

const int ci=0, &cj=ci;
decltype(ci) x=0;  // x为const int
decltype(cj) y=x;  // y为const int&，y绑定到x
decltype(cj) z;    // 错误，z是引用，必须初始化

int i=42, *p=&i;
decltype(*p) c;    // 错误，c是int&，必须初始化

decltype(i) m;     // 正确，一个未初始化的int
decltype((i)) n;   // 错误，int& 必须初始化

字符串，向量，数组

数组不允许直接拷贝、赋值

字符数组

字符数组可以使用字符串字面值进行初始化，但字符串结尾处还有一个空字符'\0'，这个空字符也会被拷贝到数组中去

1
2
3
4

char a1[] = {'c','+', '+'};         // 长度为3
char a2[] = {'c','+', '+', '\0'};  // 长度为4
char a3[] = "c++";              // 长度为4
char a4[3] = "c++";            // 错误，数组空间不足

负载数组声明

1
2
3
4

int * ptr[10];           // 含义10个整型指针的数组 
int &refs[10]=/*...*/  // 不存在引用的数组
int (*Parray)[10];     // 指向一个10个整型元素数组的指针
int (&arrRef)[10]     // 引用一个10个整型元素数组的指针

显式类型转换

static_cast

static_cast可以完成任何具有明确定义的类型转换(支持强制转换)，只要不包含底层const

1
2
3
4
5

int i=2,j=1;
double slope = static_cast<double>(j) / i;

void* p = &d;
double *dp = static_cast<double*>(p);

const_cast

const_cast只能改变运算对象的底层const，通常用于有函数重载的上下文中

1
2
3
4
5
6
7

const char *pc;
char *p = const_cast<char*>(pc);

const char *cp;
char *q = static_cast<char*>(cp);  // 错误，static_cast不能转换掉const性质
static_cast<string>(cp);           // 正确，字符串字面值转换成string属性
const<string>(cp);                 // 错误，const_cast只改变常量属性

reinterpret_cast

reinterpret_cast通常为运算对象的位模式提供较低层次上的重新解释，容易引发错误

1
2

int *ip;
char *cp = reinterpret_cast<char*>(ip); // 虽然转换，但pc所指对象依旧是int型

函数

参数传递

• 用实参初始化形参时会忽略掉顶层const，也就是说给形参传递常量对象或者非常量对象都可以
• 由于顶层const被忽略，只有形参顶层const差异的函数会被当成同一个函数
• 可以使用一个非常量初始化一个底层const对象，但是反过来不行
• 普通引用必须用同类型的对象初始化

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

int func(int i){...}        //
int func(const int i){...}  // 错误，重复定义func

//————————————————————————————————————————————————————————

void reset(int &i){i=0;}

int i=0;
const int ci = i;
string::size_type ctr = 0;
reset(&i);           // 调用形参类型是int*的reset函数
reset(i);            // 调用形参类型是int&的reset函数
reset(&ci);          // 错误，普通引用必须用同类型的对象初始化
reset(ci);           // 错误，普通引用必须用同类型的对象初始化
reset(42);           // 错误，普通引用必须用同类型的对象初始化
reset(ctr);          // 错误，普通引用必须用同类型的对象初始化

引用返回左值

• 一般函数的返回值均为右值，但也有返回左值的函数
• 由函数的返回值类型决定，具体来说，调用一个返回引用的函数得到左值，其他类型为右值
• 左值可以被赋值，右值不行
• 如果返回值类型是常量引用，那么就不能赋值了（常量不能修改啊）

1
2
3
4
5

char &get_val(string &s, string::size_type ix) { //返回的是引用
    return s[ix];
}
string s("hello world");
get_val(s,3) = 'A';       // 可以对左值进行赋值

返回数组指针

普通的数组指针声明如下

type (*name)[dimension]

返回数组指针的函数形式如下

type ( *function(parameter_list) ) [dimension]

类型别名

也可以考虑使用类型别名

typedef int arrT[10];
using arrT = int[10];
arrt* func(int i);

尾置返回类型

• 任何函数都可以使用尾置返回类型
• 这种返回方法对复杂的返回类型比较有效
• 尾置返回类型跟在形参列表后面，以->开头，在原本返回类型出现的地方加上auto

1

auto func(int i) -> int(*) [10];

使用decltype

1
2
3
4
5
6

int odd[] = {1,3,5,7,9};
// decltype(odd) 返回的是数组，需要在加一个*变成指针
decltype(odd) * func(int i) {
    // ...........
    return &odd;
}

函数重载

• 重载函数的名字肯定一样，需要形参类型或者数量上有差异
• 仅仅返回值不一样不是重载函数，而是重定义
• 仅有顶层const的差异不构成重载，底层const可以

1
2
3
4
5

int func(const int i);
int func(int i);      // 顶层const，重复定义

int func(const int * i);
int func(int *i);     // 底层const，重载函数，指针换引用也一样

作用域

• 如果在内层作用域中声明名字，它将隐藏外层作用域中所有同名的实体
• 声明在内部作用域的名字可能会是外部作用域中同名的所有重载函数失效（不声明名字就没事）
• 不同的作用域中无法承载函数名

默认语言用途

默认实参

• 默认实参填补函数调用缺少的尾部实参，所以默认形参都在尾部
• 尾部参数没省略时，中间参数不能省略
• 给定作用域中，一个形参只能被赋予一次默认实参
• 局部变量不能成为默认实参

1
2

int screen(sz, sz, char=' ');
int screen(sz, sz, char='*');  // 错误，重复声明

函数匹配

• 优先选择精确匹配、最匹配，所谓最匹配要看实参与形参的接近程度
• 有且只有一个函数满足以下条件，则匹配成功
  • 该函数每个函数的匹配都不劣与其他函数需要的匹配
  • 至少有一个实参的匹配优于其他可行函数提供的匹配
• 上面两步检查后没有函数脱颖而出，那么判定为二义性，报错

1
2
3
4

int f(int, int);
int f(double, double);

f(2,2.5);

上面的例子中，对于第一个实参，f(int,int)好；对于第二个实参，f(double,double)好。最终判断此调用具有二义性，拒绝请求。

实参到形参的类型转换分为几个等级，如下

1. 精确匹配
   • 实参、形参类型相同
   • 实参从数组或函数类型转化成对应的指针
   • 向实参添加顶层const、从实参中删除顶层const
2. 通过const转换实现的匹配（比如创建指向非常量的常量指针、引用）
3. 通过类型提升实现的匹配（short+int=int整型提升）
4. 通过算术类型转换（int转double，所有算术类型转换级别一样）或指针实现的匹配
5. 通过类类型转换实现的匹配

inline和constexpr

• inline函数编译时，一般适用于代码量很少的函数
• const是指用于常量表达式的函数，返回类型及所有形参都必须是字面值类型，并且要求有且只有一个return语句
• inline函数和constexpr函数可以多次定义，且通常定义在头文件内

调试帮助

assert

assert的用法是assert(expr);，如果表达式expr的值为true，assert什么也不做；否则，assert输出信息并终止程序执行。

NDEBUG

如果定义了NDEBUG，那么调试模式就关闭了，assert就不能起作用了。此外，NDEBUG也有助于开发者编写自己的调试代码。

1
2
3
4
5

#define NDEBUG  // 表示关闭了调试模式

# ifndef NDEBUG  // 没有关闭调试模式
// 。。。。
# endif

函数指针

• 函数指针也是指针，可以赋值为nullptr、0等
• 指向不同函数类型的函数指针不存在类型转换
• 定义重载函数指针时，指针类型必须与重载函数中的某一个精确匹配

1
2
3
4
5
6
7

bool func(int);
// 定义函数指针
bool (*pf)(int) = func;     // 定义指向函数func的函数指针
bool (*pf)(int) = &func   // 与上面等价
// 使用函数指针
pf(1);
(*pf)(2);

C++中，形参和返回值都不能是函数，但可以是函数指针，使用类型别名、decltype等可以使得函数指针的声明变得简单

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

// 等价的两种定义方式，funcp可以使用在函数实参、返回值
typedef bool (*funcp) (int);
typedef decltype(func) *funcp;

// 使用using、尾置返回类型
using pf = bool(*) (int);  // pf是函数指针
pf f1(int);
using f  = bool (int);     // f类型是函数
f *f1(int);                    // 显示指定返回类型是指向函数的指针

auto f1(int) -> bool(*) (int); // 尾置返回类型指定返回类型
decltype(func) *f1(int);        // 知道返回的函数是哪一个更方便

类

定义抽象数据类型

const成员函数

• const成员函数不能改变调用它的对象的内容

1
2
3
4
5
6
7
8
9
10
11

double const_func(int a, int b) const {}

// 返回this对象的函数
// 返回值是引用
New_Class& New_Class::hello () {
    //....
    attribute += 1;
    return *this;
}
New_Class nc;
nc.hello();  // nc的attribute属性已经改变了

类相关的非成员函数

• 这里的相关非成员函数包括但不限于read、print等
• 如果非成员函数是类接口的组成部分，这些函数的声明应当与类在同一个头文件内

1
2
3
4
5
6
7
8
9
10

// IO类型不能拷贝，所以只能以引用的形式加入形参
// 最后需要返回IO类型的引用
// ostream、print也类似，定义输出函数应该尽量减少对格式的控制
istream &read(istream &is, New_Class &item) {
    is >> item.a1 >> item.a2 >> item.a3;
    return is;
}
// 调用
istream &is;
read(is, *this)

构造函数

• 构造函数不能为const
• const对象和引用都应该在初始值列表中初始化
• 初始化列表：成员初始化的顺序与类定义中的顺序一致
• 构造const对象时，知道构造函数完成其初始化过程，对象才能取得其“常量”属性
• 默认构造函数的规则如下：
  • 如果有别的构造函数，编译器不会生成默认构造函数
  • 如果存在类内初始值，用它来初始化成员
  • 否则，默认初始化（string为””，int块外为0，块内未定义）
• C++11中，如果需要默认行为可以在参数列表之后写上 =default要求编译器生成默认构造函数
• 当某个数据成员被构造函数初始值列表忽略时，它将以合成默认构造函数相同的方式隐式初始化

1
2
3
4
5

// 有其他构造函数的情况下，还想要默认构造函数可以这样
New_Class() = default;

// 通过默认参数也等与实现了默认构造函数
New_Class(string s = " "):name(s){}

委托构造函数就是利用其他构造函数执行自己的初始化过程，其在参数列表初始化位置调用其他构造函数

1

New_Class() : New_Class("zhangsan"){}

隐式类类型转换

• 通过一个实参调用的构造函数定义一条从构造函数参数类型向类类型隐式转换的规则
• 只允许一步类类型转换，隐式转换可能会出错
• 抑制隐式转换的方法是在构造函数前加上关键字explicit
• 使用static_cast这样的显式转换也能达到转换的效果

  1 2 3 4

  string lisi = "lisi"; New_Class zhangsan("zhangsan"); // playWith函数的参数类型是New_Class zhangsan.playWith(lisi);

访问控制与封装

• class和struct定义类时的唯一区别就是默认访问权限
• struct默认为public，而class默认为private

友元

• 类中使用friend关键字可以使其他类或者函数成为它的友元
• 成为友元的类、函数可以访问当前类的非公有成员
• 友元不是类的成员，不受其所在区域访问控制级别的约束
• 类内友元函数的声明并非普通意义上的声明，所以在其他地方还得声明一次，即便定义在类内部也还要在外面声明
• 友元函数也可以定义在类内部，隐式inline
• 友元关系不存在传递性

1
2
3
4

class Class2 {
friend class Class1;
friend istream & read(istream &is, Class2 & c2);
}

其他特性

• 定义在类内部的成员函数自动是inline类型的
• mutable成员用于不会是const，即使在const成员函数内他也是可以被改变的
• 返回*this的函数返回的是左值引用（返回类型是引用），返回的是对象本身而不是副本

聚合类

• 所有成员都是public
• 没有定义任何构造函数
• 没有类内初始值
• 没有基类、没有虚函数

1
2
3
4
5

struct data {
    int x;
    char c;
    string s;
}

类的静态成员

• 静态成员于类本身直接相关
• 静态成员函数不包含this指针、也不能显式、隐式地使用this指针（不能操作非静态成员）
• 静态成员函数不能声明成const
• 在类的外部定义静态成员时，不能重复static关键字
• 静态成员变量应该在类的外部定义
• 静态数据成员可以是不完全类型（类在声明之后、定义之前称为不完全类型）
• 静态成员可以是默认实参，非静态的不可以

1
2
3
4
5

class A {
private:
    static A a;  // 正确，静态成员可以使不完全类型
    A b;           // 错误，数据成员必须是完全类型，不过可以定义指针、引用
}

IO库与容器库

string流

sstream包含三个支持string读写的类型，分别是istringstream、ostringstream和stringstream。
sstream的使用可以如下

1
2
3
4
5

sstream strm;
sstream strm(s); // strm是sstream的对象，保存string s的拷贝

strm.str()           // 返回strm所保存的string的拷贝
strm.str(s)         // copy string s to strm, return void

istringstream、ostringstream的用法也很简单，如下所示

1
2
3
4

string line("suck my balls"), word;
istringstream is(line);
while (is >> word)
    cout << word << endl;

向ostringstream对象写入string其实就是将string添加字符。

array

• array容器的大小是一定的，其大小也是类型的一部分
• array容器与普通数组不同的是，array支持拷贝与赋值

1
2
3
4
5

array<int> arr;  // 错误，缺少大小
array<int, 10> arr1 // 正确

array<int, 3> arr = {0, 1, 2};
array<int, 3> arr1 = arr;  //正确，类型一定要一致

顺序容器的操作

seq.assign(b,e); // 将seq中的元素替换成迭代器b、e所表示范围中的元素
seq.assign(il);   // 将seq中的元素替换成初始化列表il中的元素，比如il={1,2,3,4}，为值列表
seq.assign(n,t); // 将seq中的元素替换成n个元素t

c.insert(p, t); // 在迭代器p之前添加元素t，返回添加元素的迭代器
c.insert(p, n, t); // 在迭代器p之前添加n个元素t，返回第一个添加的元素的迭代器
c.insert(p, b, e); // 在迭代器p之前添加迭代器b、e之间的元素
c.insert(p, il);

向一个vector、string、deque插入元素会使所有的指向容器的迭代器、引用和指针失效

• emplace_front, emplace_back, emplace分别对应push_front, push_back, insert
• 这些函数可以构造元素

1
2
3
4
5
6
7
8
9

class person{
public:
    string name;
    int age;
    person(string nm, int ag);
}
c.emplace_front("zhangsan", 10); // 插入10岁的zhangsan的元素
c.push_front("zhangsan", 10); // 错误，没有接受三个参数的push_front版本
c.push_front(person("zhangsan",10)); // 正确，先构造对象

顺序容器还支持关系运算符，从头向尾比较，比较直观。

swap

c1.swap(c2);
swap(c1, c2);

• swap交换元素很快，因为元素本身没有交换，swap只是交换了两个容器的内部数据结构
• array是个例外，swap真正交换元素，所以交换所需时间与元素数目成正比

改变容器大小、容量

改变size：size是容器当前大小，采用多退少补的方法

• 函数resize可以改变改变容器大小resize(n)，也可以将新添加的元素设置为t resize(n,t)
• array不支持

改变capacity：capacity是容器的最大容量

• capacity()获取容量
• reserve(n)分布至少能容纳n个元素的内存空间
• shrink_to_fit()将capacity减少为size大小

string的搜索操作

其中args的形式为包括（pos默认为0）

c, pos ：    pos为开始查找的位置，c是一个字符
s2, pos：    s2是字符串
cp, pos：    cp是指向c风格的字符串的指针（以'\0'结尾）
cp, pos, n： n表示只看前n个字符

搜索失败则返回一个名为string::npos的static成员，其值初始化为-1.

string数制转换

容器适配器

适配器是一种机制，能使某种事物的行为看起来像另外一种事物
标准库中有三个顺序容器适配器，stack、queue、priority_queue

泛型算法

• 泛型算法定义在头文件numeric中

几个基本的泛型算法

• find(iter1, iter2, val); // 元素查找，iter1、iter2迭代器至少查找的范围，val是查找的元素。查找失败返回iter2，否则返回对应的迭代器
• accumulate(iter1, iter2, sum); // 元素累加，执行+运算，sum是和的初值，返回最终的和
• equal(iter1, iter2, another_iter); // 比较两个序列元素是否完全一致，一致返回true。another_iter表示第二个序列的起始迭代器
• fill(iter1, iter2, val); // 将迭代器范围中的每个值置为val
• fill_n(iter, n, val); // 将从iter起的n个元素置为val（必须保证有n个元素）
• copy(iter1, iter2, another_iter); // 将iter1-iter2范围内的元素拷贝到以another_iter起始的位置上，要求another_iter对应的容器大小不能比iter1对应的容器小，返回another_iter的位置迭代器位置
• replace(iter1, iter2, val, new_val); // 迭代器范围内，将所有的val换成 new_val
• replace_copy(iter1, iter2, new_iter, val, new_val); // 保持iter1对应的容器不变，将替换后的结果写入new_iter对应的容器中
• unique(iter1, iter2); // 去重，返回指向不重复区域之后一个位置的迭代器

定制操作

lambda表达式

[捕获列表] (参数列表) -> 返回类型 {函数体};

• lambda可以理解成未命名的inline函数
• 捕获列表：表达式所在函数的局部变量列表，局部变量间以,分隔，通常为空。&引用捕获，=
• 参数列表、返回类型、函数体和普通函数一个意思
• 参数列表和返回类型可以忽略，但捕获列表和函数体必须存在
• lambda表达式的返回值是一个可调用对象，不接收参数，直接带括号调用。可调用对象包括函数、函数指针、lambda表达式等

1
2

auto f = []{return 0;} // f是可调用对象
cout << f() << endl;

bind函数

• 头文件为functional
• 接受一个可调用对象，生成一个新的可调用对象来适应原对象的参数列表
• 可以看成一个通用的函数适配器

• bind在绑定过程中都是采用参数拷贝的方式，所以对于需要引用的类型，可以使用ref、cref函数表示引用（常量c）

  auto newCallable = bind(callable, arg_list);

arg_list中可能包含_n这样的名字（n是整数），这些是占位符，表示newCallable的参数。_n表示第n个参数。

1
2
3
4
5
6
7
8
9
10

// f是有5个参数的可调用对象
auto g = bind(f, a, b, _2, c, _1);
// 传递给g的参数会被分别绑定到_1、_2位置上
// g(X, Y) 等价于 f(a, b, Y, c, X)

ostream &print(ostream &os, string &s, char c) {
    return os << s << c;
}
for_each(words.begin(), words.end(), bind(print, os, _1, ' '));  // 错误，os不能拷贝
for_each(words.begin(), words.end(), bind(print, ref(os), _1, ' '));  //正确

特殊迭代器

插入迭代器

包括back_inserter, front_inserter, inserter三种，分别创建使用push_back, push_front, insert的迭代器。
使用 inserter(c, iter)时，插入元素位置在iter位置之前，并且插入前后，iter指向的元素不变；但是front_inserter(c)就一直在容器头部插入。

1
2
3
4
5
6

list<int> lst = {1,2,3,4};
list<int> lst2, lst3;
// 插入后lst2为 4 3 2 1
copy(lst.begin(), lst.end(), front_inserter(lst2));
// 插入后lst3为 1 2 3 4
copy(lst.begin(), lst.end(), inserter(lst3, lst3.begin()));

iostream迭代器

• 使用流迭代器，必须指定读写对象的类型
• istream_iterator迭代器要读取的内容必须定义了>>运算符，ostream_iterator迭代器要读取的内容必须定义了<<运算符
• 默认初始化istream_iterator迭代器，创建一个当作尾后值使用的迭代器
• 流迭代器不支持递减--操作
• istream_iterator迭代器支持++, *, ->, ==, !=运算符
• ostream_iterator迭代器支持++, =, *运算符

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

istream_iterator<T> in(is);  // 迭代器对象in从输入流is中读取类型为T的值
istream_iterator<T> eof;     // 尾后迭代器
vector<T> vec(in, eof);  // 从迭代器范围构造vector对象
accumulate(in, eof, 0);   // 求和

ostream_iterator<T> out(os);  // out将类型为T的输出值写入到输出流os中
ostream_iterator<T> out(os, d);  // out将类型为T的输出值写入到输出流os中，每个值后面都额外输出一个d（d是C风格的字符串）
for (anto e : vec)
    *out++ = e;  // 直接写out=e;也可以，不过不推荐这么写
cout << endl;
copy(vec.begin(), vec.end(), out);
cout << endl;

反向迭代器

• 在容器中从尾元素向首元素反向移动的迭代器
• 其递增、递减的操作是反过来的，即++会向前移动，前也是相对移动方向的
• 除了forward_list外都支持，使用rbegin(),crbegin()等

链表类容器的特殊方法

list、forward_list

谓词是返回可以转换为bool类型值的函数。元对应参数个数

关联容器

• 关联容器支持高效的关键字查询和访问，可以分为有序集合和无序集合两种
• map和set的迭代器都不允许修改关键字

  分类

  | 有序类型 | 说明 |
  |————|————|
  | map | 关联数组，保存（key, value）对 |
  | set | 只保存关键字 |
  |multimap| 关键字可重复出现的map|
  |multiset| 关键字可重复出现的set |

1
2
3
4
5
6
7
8

vector<int> vec;
for (int i=0; i<10; i++) {
    vec.push_back(i);
    vec.push_back(i);
}

set<int> iset(vec.cbegin(), vec.cend());  // 10个元素
multiset<int> imset(vec.cbegin(), vec.cend());  // 20个元素

关键字类型要求

• 有序元素的关键字类型必须定义元素比较的方法
• 不支持比较的复杂类型需要自定义比较函数

1
2
3
4

// compareClass1是进行Class1对象比较的函数，定义时需要添加比较函数的函数指针
// 直接使用compareClass1也行，因为函数名会转化为函数指针
// 构造函数也使用比较函数的函数指针
set<Class1, decltype(compareClass1)*> cls(compareClass1);

关联容器额外的类型别名

key_type : 容器的关键字类型
value_type : 对于set，与key_type相同；map则是pair<key, value>
mapped_type : 关键字关联的类型

添加元素

c.insert(v);
c.emplace(args);
c.insert(iter1, iter2);
c.insert(il);  // 花括号列表，返回void
c.insert(iter, v); // 迭代器指示搜索新元素存储应该存储的位置。返回一个迭代器，指向具有给定关键字的元素
c.emplace(iter, args);

对于不包含重复关键字的容器，添加单一元素的inert和emplace返回一个pair，指示插入操作是否成功。pair的首元素（first）是一个迭代器，指向具有指定关键字的元素；second是一个bool值，指示元素成功插入还是已经存在于容器中，成功插入为true，否则为false。

1
2
3

auto ret = word_count.insert({"hello", 1}); 尝试插入
if (!ret.second) // 元素已经存在map中
    ++ret.first->second;  //  ret.first是指向“hello”关键字的迭代器，迭代器指向的second元素是原本"hello"对应的数目，加一即可

访问元素

c.find(k);  // 返回指向第一个key为k的迭代器
c.count(k);  // 返回关键字k的个数
c.lower_bound(k); // 返回一个迭代器，指向第一个关键字不小于k的元素
c.upper_bound(k);  // 返回一个迭代器，指向第一个关键字大于k的元素
c.equal_range(k);   //  返回一个迭代器pair，表示关键字等于k的元素的范围。如不存在，则pair的两个成员均为c.end()

lower_bound和upper_bound只适用于有序容器
通过下标访问元素返回左值，既可以读，也可以写回

无序容器

• 无序容器在存储上组织为一组桶，每个桶保存0个或多个元素

• 无序容器的性能依赖于哈希函数的质量和桶的大小

  c.bucket_count(); // 正在使用的桶数目
  c.max_bucket_count(); // 容器能容纳的最多的桶的数量
  c.bucket_size(n); // 第n个桶中有多少个元素
  c.bucket(k); // 关键字为k的元素在哪个桶中

  local_iterator // 访问桶中元素的迭代器
  const_local_iterator // const版本
  c.begin(n), c.end(n) // 桶n元素的首、尾迭代器
  c.cbegin(n), c.cend(n)

  c.load_factor(); // 每个桶的平均元素数量，float类型
  c.max_load_factor(); // 最大平均桶元素数量，每个桶的平均元素数量大于这个值就需要添加新的桶
  c.rehash(n); // 重组存储，使得bucket_count >= n且bucket_count>size/max_load_factor
  c.reserve(n); // 重组存储，使得c可以保存n个元素且不必rehash

无序容器对关键字的要求

• 无序容器使用==运算符比较元素
• 使用hash<key_type>类型的对象生成每个元素的哈希值

1
2
3
4
5
6
7
8
9

size_t hasher(const Class1 & cls) {
    return hash<string>()(cls.name);
}
bool eqop(const Class1 & cls1, const Class1 & cls2) {
    return cls1.name == cls2.name;
}
using clsset = unordered_set<Class1, hasher, eqop>;
// 42是桶大小
clsset s(42, hasher, eqop);

H-Index I

H-Index

维基百科上H-Index的定义如下

一个科学家的H-Index为h，如果他一共有N篇文章，其中有h篇文章每一篇都至少有h次引用，其他N-h篇论文每一篇都不超过h次引用

比如给定citations = [3, 0, 6, 1, 5]，表示当前研究者有5篇论文，其引用为citations中。因为这些论文中有3篇论文每篇都至少有3次引用，其他2篇都没有3次应用，所以他的H-Index为3。

题目描述

给定某个科学家论文引用数目的数组（非负），输出他的H-Index

解题方案

首先，一个拥有N篇论文的科学家，他的H-Index不可能会超过N，最大就是N，最小是0。所以如果一篇论文的引用超过N，那么这篇论文的引用在计算H-Index时和N个引用是一样的；如果引用小于N，不妨设置为t，这篇论文只在H-Index小于等于t时有用，如果H-Index大于t，这篇论文不能被计数。

所以，设置一个长度为N+1的辅助数组array，扫描citations数组，对于每个引用t，如果

• t < N : array[t]++
• t >= N : array[N]++

得到数组array数组，从后向前，判断方式为如果$ \sum_{k=i}^{N} array[k] >= i $，那么返回$i$，否则继续向前寻找。

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

int hIndex(vector<int> & citations) {
    int N = citations.size();
    if (N == 0) return 0;
    vector<int> array(N+1, 0);
    for (int i=0; i<N; i++) {
        if (citations[i] > N) array[N]++;
        else array[citations[i]]++;
    }
    int sum = 0;
    for (int i=N; i>0; i--) {
        sum += array[i];
        if (sum >= i) return i;
    }
    return 0;
}

H-Index II

题目描述

在H-Index的基础上，假设给定的citations数据是按升序排序的。求H-Index

解题方案

对于第k篇论文，其引用为citations[k]，引用数大于等于citations[k]的论文数量为N-k，所以对应的H-Index为min(N-k, citations[k])。从前向后考虑，开始时始终有citations[k]<N-k，对应的候选H-Index为citations[k]，到后面有citations[k]>N-k，对应的H-Index为N-k。也就是说候选H-Index经历了先增大后减小的过程，转折过程就是citations[k]第一次大于等于N-k的时候。由于H-Index也限制“其他N-h篇论文每一篇都不超过h次引用”，所以我们的目标就是找到第一个citations[k]>=N-k的序号k，因为此时k对应的候选H-Index为N-k，而k-1对应的候选H-Index肯定小于N-k+1，所以k必对应着最优解。

现在有了O(n)复杂度的算法，考虑到引用数据是严格有序的，所以可以使用类似于二分搜索的方法。此时，可以稍微换个角度思考。对于第k篇论文，其引用为citations[k]，如果N-k>=citations[k]，那么citations[k]就是合格的H-Index，此时应该向右尝试寻找更大的H-Index（因为左边的citations小）；如果N-k<citations[k]，那么citations[k]就不是一个当前合法的H-Index（N-k是），所以要向左尝试寻找。

出现N-k=citations[k]直接结束了。否则必然存在k满足citations[k]<N-k && citations[k+1]>N-k-1，现在考虑k,k+1,left,right最终的可能关系，如下

| k       k+1    |            k     k+1 |  k    k+1            |  k   k+1                   |                   k    k+1  |
| left     right | left    right        |       left     right |              left    right |  left    right               |
后面两种情况不可能出现，前三种情况的最终结果都是 `N-left`

再来考虑停止条件，两种情况left=right或者left+1=right。

1. 当第一种情况出现，mid=left，此时如果citations[mid] > N-mid，那么mid=left就是最佳位置，H-Index为N-mid；否则最佳位置在left后一位，此时将left=mid+1后，N-left就是最佳H-Index。
2. 当第二种情况出现，left+1=right，mid=left，此时如果citations[mid] > N-mid，那么mid=left就是最佳位置，H-Index为N-mid；否则，设置left=mid+1，回到了第一种情况。

1
2
3
4
5
6
7
8
9
10
11

int hIndex(vector<int>& citations) {
    int N=citations.size(), left=0, right=N-1, ret=0;
    if (N == 0) return 0;
    while (left <= right) {
        int mid = left + (right-left)/2;
        if (citations[mid] == N-mid) return N-mid;
        else if (citations[mid] > N-mid) right = mid-1; // 向左寻找
        else left = mid+1;                                     // 向右寻找
    }
    return N-left;
}

partition函数

partition函数是快速排序的核心部分，选定一个基准，然后将大于和小于基准的数分别放置于基准的两边，有多种实现方式，以下是参考

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

// start, end表明作用范围
// pivotIndex表示基准的位置
int partition(vector<int> & A, int start, int end){
    int i = start, j = end;
    int pivotIndex = rand() % (end-start+1) + start; // 随机选择基准位置
    int pivot = A[pivotIndex];
    // 把基准换到最后
    swap<int>(A[end], A[pivotIndex]);
    while(i < j){
        while(i < j && A[i] < pivot) ++i;
        if (i > j) break;
        while(i < j && A[j] >= pivot) --j;
        if (i > j) break;
        if(i < j) swap<int>(A[i], A[j]);
    }
    swap<int>(A[end], A[i]);
    return i;
}

再提供另一种实现方式

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

// arr[]为数组，start、end分别为数组第一个元素和最后一个元素的索引
// povitIndex为数组中任意选中的数的索引
int partition(int arr[], int start, int end, int pivotIndex) {
    int pivot = arr[pivotIndex];
    swap(arr[pivotIndex], arr[end]);
    int storeIndex = start;
    for(int i = start; i < end; ++i) {
        if(arr[i] < pivot) {
            swap(arr[i], arr[storeIndex]);
            ++storeIndex;
        }
    }
    swap(arr[storeIndex], arr[end]);
    return storeIndex;
}

Partition函数的应用

快速排序

1
2
3
4
5

void quick_sort(vector<int> &A, int start, int end) {
    int mid = partition(A, start, end);
    if (mid-start > 2) quick_sort(A, start, mid-1);
    if (end-mid > 2) quick_sort(A, mid+1, end);
}

Top K问题

给定未排序数组A，求排好序的数组中的第k个大个数。因为上面的partition函数是左小右大，所以我们考虑寻找第A.size()-k小的数。
思路是调用partition函数，返回基准位置，如果基准位置正好是k，那么返回其对应的值
否则，如果基准在k左侧，则考虑基准右边的元素；否则考虑左边的元素。

1
2
3
4
5
6
7
8
9

int findKthLargest (vector<int> &A, int k) {
    int start=0, end=A.size()-1;
    while (start < end) {
        int mid = partition(A, start, end);
        if (mid == k-1) return A[k-1];
        else if (mid < k-1) start = mid+1;
        else end = mid-1;
    }
}

题目描述

给定数组nums，和滑动窗口的长度k，输出滑动窗口一次一个元素地向前滑动时每一时刻滑动窗口内的最大值。要求在O(n)复杂度内完成。

nums = [1,3,-1,-3,5,3,6,7],  k = 3
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
---------------               -----
output [3,3,5,5,6,7]

解题思路

滑动窗口内添加新元素简单，但是删除时比较麻烦，所以简单使用堆的思路不行。

双端队列对滑动窗口有比较好的模拟，其尾部、头部都可以添加和删除元素（也有受限的应用版本）。

本题使用的方法也称作单调队列，其定义如下：

队列中元素之间的关系具有单调性，而且，队首和队尾都可以进行出队操作，只有队尾可以进行入队操作

以单调不减队列为例，队列内的元素$(e_1,e_2,…,e_n)$存在$(e_1\le e_2\le…\le e_n)$的关系，所以队首元素$e_1$一定是最小的元素。与优先队列不同的是，当有一个新的元素$e$入队时，先要将队尾的所有大于$e$的元素弹出，以保证单调性，再让元素$e$入队尾。

所以本题的方法描述如下：

• 队列元素如果超过了k的限制，那么从队头剔除
• 从队尾起，如果队尾的元素小于当前需要添加的元素，那么剔除队尾元素（它不可能成为最大值），直到队尾元素大于等于当前需要添加的元素。
• 此时，队列是非递减队列，所以队头元素就是最大值

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

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> ret;
    deque<int> window;
    if (nums.size()<1 || k<=0) return ret;
    for (int i=0; i<nums.size(); i++) {
        if (!window.empty() && window.front()<i-k+1)
            window.pop_front();
        while (!window.empty() && nums[window.back()]<nums[i])
            window.pop_back();
        window.push_back(i);
        if (i >= k-1) ret.push_back(nums[window.front()]);
    }
    return ret;
}

Callable与Runnable

Java中的多线程实现可以通过继承Thread或者实现Runnable接口来实现，但是这两种方法都不能将执行结果取回。Runnable接口定义如下：

1
2
3

public interface Runnable {
    public abstract void run();
}

由于run()方法返回值为void类型，所以在执行完任务之后无法返回任何结果。

Callable位于java.util.concurrent包下，它也是一个泛型接口，在它里面也只声明了一个方法call()，返回的类型就是传递进来的V类型：

1
2
3
4
5
6
7
8
9

public interface Callable<V> {
    /**
     * Computes a result, or throws an exception if unable to do so.
     *
     * @return computed result
     * @throws Exception if unable to compute a result
     */
    V call() throws Exception;
}

Callable一般情况下是配合ExecutorService来使用的，在ExecutorService接口中声明了若干个submit方法的重载版本：

1
2
3
4
5

<T> Future<T> submit(Callable<T> task);

<T> Future<T> submit(Runnable task, T result);

Future<?> submit(Runnable task);

这三个方法中，常用的是第一个和第三个。

Future

Future是一个接口，位于java.util.concurrent包下，定义如下

1
2
3
4
5
6
7

public interface Future<V> {
    boolean cancel(boolean mayInterruptIfRunning);
    boolean isCancelled();
    boolean isDone();
    V get() throws InterruptedException, ExecutionException;
    V get(long timeout, TimeUnit unit) throws InterruptedException, ExecutionException, TimeoutException;
}

Future就是对于具体的Runnable或者Callable任务的执行结果进行取消、查询是否完成、获取结果。必要时可以通过get方法获取执行结果，此方法会阻塞直到任务返回结果。上述方法中：

1 cancel方法用来取消任务，如果取消任务成功则返回true，如果取消任务失败则返回false。参数mayInterruptIfRunning表示是否允许取消正在执行却没有执行完毕的任务，如果设置true，则表示可以取消正在执行过程中的任务。如果任务已经完成，则无论mayInterruptIfRunning为true还是false，此方法肯定返回false，即如果取消已经完成的任务会返回false；如果任务正在执行，若mayInterruptIfRunning设置为true，则返回true，若mayInterruptIfRunning设置为false，则返回false；如果任务还没有执行，则无论mayInterruptIfRunning为true还是false，肯定返回true

2 isCancelled方法表示任务是否被取消成功，如果在任务正常完成前被取消成功，则返回 true

3 isDone方法表示任务是否已经完成，若任务完成，则返回true

4 get()方法用来获取执行结果，这个方法会产生阻塞，会一直等到任务执行完毕才返回

5 get(long timeout, TimeUnit unit)用来获取执行结果，如果在指定时间内，还没获取到结果，就直接返回null

FutureTask

由于Future是个接口，所以其不能实例化，FutureTask应运而生，也是Future接口的唯一实现类。

FutureTask类实现了RunnableFuture接口

1
2
3
4
5

public class FutureTask<V> implements RunnableFuture<V> {}

public interface RunnableFuture<V> extends Runnable, Future<V> {
    void run();
}

RunnableFuture继承了Runnable接口和Future接口，而FutureTask实现了RunnableFuture接口，关系如图所示。所以它既可以作为Runnable被线程执行，又可以作为Future得到Callable的返回值。

FutureTask提供了2个构造器

1
2
3
4
5

public FutureTask(Callable<V> callable) {
}

public FutureTask(Runnable runnable, V result) {
}

使用方法

使用Callable + Future获取执行结果

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

ExecutorService executor = Executors.newCachedThreadPool();
Task task = new Task();
Future<Integer> result = executor.submit(task);
executor.shutdown();

try {
    System.out.println("task运行结果"+result.get());
} catch (InterruptedException e) {
    e.printStackTrace();
} catch (ExecutionException e) {
    e.printStackTrace();
}

class Task implements Callable<Integer>{
    @Override
    public Integer call() throws Exception {
        System.out.println("子线程在进行计算");
        Thread.sleep(3000);
        int sum = 0;
        for(int i=0;i<100;i++)
            sum += i;
        return sum;
    }
}

使用Callable + FutureTask获取执行结果

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

ExecutorService executor = Executors.newCachedThreadPool();
Task task = new Task();
FutureTask<Integer> futureTask = new FutureTask<Integer>(task);

executor.submit(futureTask);
executor.shutdown();

try {
    System.out.println("task运行结果"+futureTask.get());
} catch (InterruptedException e) {
    e.printStackTrace();
} catch (ExecutionException e) {
    e.printStackTrace();
}

class Task implements Callable<Integer>{
    @Override
    public Integer call() throws Exception {
        System.out.println("子线程在进行计算");
        Thread.sleep(3000);
        int sum = 0;
        for(int i=0;i<100;i++)
            sum += i;
        return sum;
    }
}

ThreadPoolExecutor

构造方法

java.uitl.concurrent.ThreadPoolExecutor类是线程池中最核心的一个类，继承自AbstractExecutorService，AbstractExecutorService是一个抽象类，它实现了ExecutorService接口。ThreadPoolExecutor的构造方法如下：

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

public class ThreadPoolExecutor extends AbstractExecutorService {

    public ThreadPoolExecutor(int corePoolSize,int maximumPoolSize,long keepAliveTime,TimeUnit unit,
            BlockingQueue<Runnable> workQueue);
    public ThreadPoolExecutor(int corePoolSize,int maximumPoolSize,long keepAliveTime,TimeUnit unit,
            BlockingQueue<Runnable> workQueue,ThreadFactory threadFactory);

    public ThreadPoolExecutor(int corePoolSize,int maximumPoolSize,long keepAliveTime,TimeUnit unit,
            BlockingQueue<Runnable> workQueue,RejectedExecutionHandler handler);

    public ThreadPoolExecutor(int corePoolSize,int maximumPoolSize,long keepAliveTime,TimeUnit unit,
        BlockingQueue<Runnable> workQueue,ThreadFactory threadFactory,RejectedExecutionHandler handler);

}

前面三个构造器都是调用的第四个构造器进行的初始化工作，参数介绍如下：

1 corePoolSize : 核心池的大小。默认情况下，在创建了线程池后，线程池中的线程数为0，当有任务来之后，就会创建一个线程去执行任务，当线程池中的线程数目达到corePoolSize后，就会把到达的任务放到缓存队列当中。（正式工）
2 maximumPoolSize : 线程池最大线程数，表示在线程池中最多能创建多少个线程。最大线程数意味着当核心池不够用时可以额外开辟新线程，但这些新加入的线程在空闲时可以销毁（临时工）。
3 keepAliveTime : 线程没有任务执行时最多保持多久时间会终止。默认情况下，只有当线程池中的线程数大于corePoolSize时，keepAliveTime才会起作用，直到线程池中的线程数不大于corePoolSize，即当线程池中的线程数大于corePoolSize时，如果一个线程空闲的时间达到keepAliveTime，则会终止，直到线程池中的线程数不超过corePoolSize。但是如果调用了allowCoreThreadTimeOut(boolean)方法，在线程池中的线程数不大于corePoolSize时，keepAliveTime参数也会起作用，直到线程池中的线程数为0。
4 unit : keepAliveTime的时间单位. 包括

TimeUnit.DAYS
TimeUnit.HOURS
TimeUnit.MINUTES
TimeUnit.SECONDS
TimeUnit.MILLISECONDS
TimeUnit.MICROSECONDS
TimeUnit.NANOSECONDS

5 workQueue : 一个阻塞队列，用来存储等待执行的任务。可以是如下三种，其中ArrayBlockingQueue和PriorityBlockingQueue使用较少，一般使用LinkedBlockingQueue和Synchronous。线程池的排队策略与BlockingQueue有关。

ArrayBlockingQueue：基于数组的先进先出队列，此队列创建时必须指定大小
LinkedBlockingQueue：基于链表的先进先出队列，如果创建时没有指定此队列大小，则默认为Integer.MAX_VALUE
SynchronousQueue：不会保存提交的任务，而是将直接新建一个线程来执行新来的任务
PriorityBlockingQueue

6 threadFactory ：线程工厂，主要用来创建线程
7 handler ：表示当拒绝处理任务时的策略，可以是

ThreadPoolExecutor.AbortPolicy:丢弃任务并抛出RejectedExecutionException异常
ThreadPoolExecutor.DiscardPolicy：也是丢弃任务，但是不抛出异常
ThreadPoolExecutor.DiscardOldestPolicy：丢弃队列最前面的任务，然后重新尝试执行任务（重复此过程）
ThreadPoolExecutor.CallerRunsPolicy：由调用线程处理该任务

继承结构

Executor是一个顶层接口，在它里面只声明了一个方法execute(Runnable)，返回值为void，参数为Runnable类型，从字面意思可以理解，就是用来执行传进去的任务的。

ExecutorService接口继承了Executor接口，并声明了一些方法：submit、invokeAll、invokeAny以及shutDown等。

抽象类AbstractExecutorService实现了ExecutorService接口，基本实现了ExecutorService中声明的所有方法。

ThreadPoolExecutor继承了类AbstractExecutorService。在ThreadPoolExecutor类中有几个非常重要的方法：

1 execute() : execute()方法实际上是Executor中声明的方法，在ThreadPoolExecutor进行了具体的实现，这个方法是ThreadPoolExecutor的核心方法，通过这个方法可以向线程池提交一个任务，交由线程池去执行。

2 submit() : submit()方法是在ExecutorService中声明的方法，在AbstractExecutorService就已经有了具体的实现，在ThreadPoolExecutor中并没有对其进行重写，这个方法也是用来向线程池提交任务的，但是它和execute()方法不同，它能够返回任务执行的结果(Future)

3 shutdown() : 关闭线程池，不再接受新的任务，等到所有线程完成任务关闭线程池

4 shutdownNow() : 立即结束所有线程，关闭线程池

线程池实现原理

线程状态

ThreadPoolExecutor中定义了一个volatile变量volatile int runState表示当前线程池的状态，它是一个volatile变量用来保证线程之间的可见性。还有几个static final变量表示runState可能的几个取值：

static final int RUNNING    = 0;
static final int SHUTDOWN   = 1;
static final int STOP       = 2;
static final int TERMINATED = 3;

创建线程池后，初始时，线程池处于RUNNING状态。
调用了shutdown()方法，则线程池处于SHUTDOWN状态，此时线程池不能够接受新的任务，它会等待所有任务执行完毕。
调用了shutdownNow()方法，则线程池处于STOP状态，此时线程池不能接受新的任务，并且会去尝试终止正在执行的任务。
当线程池处于SHUTDOWN或STOP状态，并且所有工作线程已经销毁，任务缓存队列已经清空或执行结束后，线程池被设置为TERMINATED状态。

任务执行

ThreadPoolExecutor类中其他的一些比较重要成员变量如下：

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

private final BlockingQueue<Runnable> workQueue;  //任务缓存队列，用来存放等待执行的任务

private final ReentrantLock mainLock = new ReentrantLock(); //线程池的主要状态锁，对线程池状态（比如线程池大小、runState等）的改变都要使用这个锁

private final HashSet<Worker> workers = new HashSet<Worker>();  //用来存放工作集

private volatile long  keepAliveTime;    //线程存货时间

private volatile boolean allowCoreThreadTimeOut;   //是否允许为核心线程设置存活时间

private volatile int   corePoolSize;     //核心池的大小（即线程池中的线程数目大于这个参数时，提交的任务会被放进任务缓存队列）

private volatile int   maximumPoolSize;   //线程池最大能容忍的线程数

private volatile int   poolSize;       //线程池中当前的线程数

private volatile RejectedExecutionHandler handler; //任务拒绝策略

private volatile ThreadFactory threadFactory;   //线程工厂，用来创建线程

private int largestPoolSize;   //用来记录线程池中曾经出现过的最大线程数

private long completedTaskCount;   //用来记录已经执行完毕的任务个数

任务提交执行依靠execute()方法，submit()也是提交任务的方法，但是它也是调用了execute()方法。execute()方法处理方法的逻辑如下：

1
2
3
4
5
6
7
8
9
10
11

public void execute(Runnable command) {
    if (command == null)
        throw new NullPointerException();
    if (poolSize >= corePoolSize || !addIfUnderCorePoolSize(command)) {
        if (runState == RUNNING && workQueue.offer(command)) {
            if (runState != RUNNING || poolSize == 0)
                ensureQueuedTaskHandled(command);
        } else if (!addIfUnderMaximumPoolSize(command))
            reject(command); // is shutdown or saturated
    }
}