AOAPC 读书笔记 Ⅲ

C++ 与 STL 入门

从C 到 C++

与其把 C++ 学得一知半解，还不如先把 C 语言的基础打好；
C++ 的精华与糟粕并存。

C++ 版框架

使用 C 头文件：在 C 头文件前加一个小写的 c 字母，然后去掉 .h 后缀；
C++ 流最大的缺点就是运行太慢；
如果两个函数的参数类型完全相同，则是不能重载的，解决方案是：分别把函数写在各自的命名空间里；
使用了 using namespace std 语句，可以用 cin 代替 std::cin，cout 代替 std::cout；
使用 const 声明常数，而不是用 #define；
仍然可以用 int 来表示真假，但是用 bool 可以让程序更清晰。

引用

C++ 中的引用就是变量的“别名”，可以在一定程度上代替 C 中的指针；
在参数名之前加一个“&”符号，表示这个参数按照传引用（by reference）的方式传递，而不是传值（by value）的方式传递。在函数内改变参数的值，也会修改到函数的实参。

字符串

C 语言中的字符串就是字符数组，不是“一等公民”。字符串拼接：

不能在函数中定义一个数组然后返回它的地址，必须申请新的内存空间以存放结果；
字符串数组本身并不保存长度。为了避免不必要的 strlen 调用，需在某个变量中保存字符串的长度。

C++ 的 cin/cout 可以直接读写 string 类型，string 类型还可以像整数那样“相加”。可以把 string 作为流进行读写，定义在 sstream 头文件中；
string 很慢，sstream 更慢。

再谈结构体

C++ 不再需要用 typedef 的方式定义一个 struct。一般用 struct 定义“纯数据”类型，用 class 定义“拥有复杂行为”的类型；
struct 和 class 的区别：默认访问权限和继承方式不同。

struct Point
{
    int x, y;
    Point(int x=0, int y=0):x(x),y(y)) {}
};

结构体 Point 中定义了一个函数，函数名也叫 Point，但是没有返回值，这样的函数称为构造函数（ctor）；
C++ 中的结构体可以有一个或多个构造函数，在声明变量时调用；
:x(x),y(y)：是一个简单的写法，表示“把成员变量 x 初始化为参数 x，成员变量 y 初始化为参数 y”。
也可以写成：

1	Point(int x=0, int y=0) {this->x = x; this->y = y;}

this 是指向当前对象的指针，this->x 的意思是“当前对象的成员变量 x”，即 (*this).x。

模版

int sum(int *begin, int *end)
{
    int *p = begin;
    int ans = 0;
    for(int *p = begin; p != end; p++)
        ans += *p;
    return ans;
}

这个函数没有错误，但比较局限。只能求整数数组的和，不能求 double 数组的和，更不能求 Point 数组的和。
可以用模版进行改造：

template <typename T>
T sum(T *begin, T *end)
{
    T *p = begin;
    T ans = 0;
    for(T *p = begin; p != end; p++)
        ans = ans + *p;
    return ans;
}

STL 初步

排序与检索

sort 可以给任意对象排序，包括内置类型和自定义类型；
待排序／查找的元素可以放在数组里，也可以放在 vector 里；
lower_bound 的作用是查找“大于或者等于 x 的第一个位置”。

不定长数组：vector

vector 就是一个不定长数组，把一些常用操作封装在了 vector 类型内部；
vector<int> 是一个类似于 int a[] 的整数数组，而 vector<string> 就是一个类似于 string a[] 的字符串数组；
vector 之间可以直接赋值或者作为函数的返回值，像是“一等公民”一样。

集合：set

set 就是数学上的集合，自定义类型也可以构造 set，但必须定义小于运算符；
iterator 的意思是迭代器，是 STL 的重要概念，用法类似于指针。

映射：map

map 就是从键（key）到值（value）的映射。因为重载了 [] 运算符，map 像是数组的“高级版”，也称为关联数组；
没有良好的代码设计，是无法发挥 STL 的威力的。

栈、队列与优先队列

所谓栈，就是符合“后进先出”（LIFO）规则的数据结构。
定义：

1	stack<int> s;

队列是符合“先进先出”（FIFO）原则的公平队列。
定义：

1	queue<int> s;

优先队列是一种*抽象数据类型 *（ADT），越小的整数优先级越低；
只要元素定义了“小于”运算符，就可以使用优先队列。
定义：

1	priority_queue<int> s;

在 C++ 中，重载了“()”运算符的类或结构体叫做仿函数（functor）。

测试 STL

使用之前测试库是一个好习惯。
cstdlib 中的 rand() 可以生成闭区间 [0, RAND_MAX] 内均匀分布的随机整数，RAND_MAX 最大为 32767；
若要生成更大的随机整数，可以用 rand() 的结果放大得到；
可以用 cstdlib 中的 srand 函数初始化随机数种子，并用 ctime 中的 time(NULL) 为参数调用 srand。即在随机数程序最开始时，执行一次 srand(time(NULL))；
time 函数返回的是自 UTC 时间 1970 年 1 月 1 日 0 点以来经过的秒数。

把 vector 作为参数或者返回值时，应尽量改成用引用方式传递参数，以避免不必要的复制。

C++ 支持函数重载，但函数的参数类型必须不同（不能只是返回值类型不同）；
assert(表达式)：当表达式为假时强行终止程序，并给出错误提示，为真时无变化；
vector、set、map 都很快。

题目举例

可以给结构体重载赋值运算符，使得用起来更方便；
给结构体声明一些属于该结构体类型的静态成员变量，方法是加上 static 修饰符。静态成员变量在结构体外部使用时，要写成结构体名::静态成员变量名；
unique 必须在 sort 之后调用，而且 unique 本身不会删除元素，而只是把重复的元素移到了后面。

sort、set、map 都依赖于类型的“小于”运算符。