1.C++标准库

C++ 标准库（C++ Standard Library）是一个类库和函数的集合
- 提供了若干泛型容器、函数对象、泛型字符串和流、常用函数等
- 声明在 std 名字空间中 using namespace std;
- 吸收了 ISO C90 C 标准程序库
  原有的 C 标准库中的所有头文件，都移去末尾的 .h 并在开头加上 c，如 <stdio.h> 变为 <cstdio>
C++ 标准模板库（C++ Standard Template Library，STL）
- 是 C++ 标准库的一个子集
- 包括容器、算法、迭代器和函数对象

包含标准库声明的一些头文件关系：

2.C++标准库模板

C++ 中主要有两个方面体现了重用
- 面向对象的设计思想，包括继承和多态，以及标准类库
- 泛型程序设计（generic programming）的思想，包括模板机制，以及标准模板库（STL）
泛型程序设计，简单来说就是使用模板的程序设计法
- 将一些常用的数据结构（如链表、队列、二叉树）和算法（如排序、查找）写成模板，无论数据结构里放的是什么类型的对象
标准模板库（Standard Template Library，STL）就是一些常用数据结构和算法模板的集合
- STL大致可以视为由四部分组成：容器、迭代器、算法、函数对象

2.1.容器

容器是可容纳各种数据类型的数据结构
- 包括顺序容器和关联容器
- 还有一类不提供真正的用于存储元素的数据结构实现，称作容器适配器
- 容器适配器不支持迭代器，由使用者选择合适的底层数据结构

在顺序容器中，元素的插入位置与元素的值无关：

vector （声明于 < vector>）

顺序表：实现了一个动态数组，可以在常数时间内完成随机存取元素，可以自动调整大小，在尾端增删元素时具有较佳的性能
array （C++11 中新增，声明于 < array>）
顺序表：封装了一个静态数组，只能在初始化时指定大小
deque （声明于 < deque>）
双端队列：实现了一个动态数组，可以在常数时间内完成随机存取元素，可以快速地在数组的头尾两端增删元素
list （声明于 < list>）
双向链表：不支持随机存取，但在任何位置增删元素都能在常数时间完成
forward_list （ C++11 中新增，声明于）
单向链表：list 类的单链表版，去掉了一些操作

在关联容器中，元素的插入位置与元素的值有关，必须按相应的排序准则来确定，在查找元素时具有非常好的性能:

set / multiset （声明于 #include<set>）

集合：实现了一棵平衡二叉搜索树，使用元素本身作为键值（key）；set 容器中不允许存在相同元素，multiset 容器中允许存在相同的元素
map / multimap （声明于 #include<map>）
映射表：实现了一棵平衡二叉搜索树，存放的是成对的键值和数据（key / value），并根据键值对元素进行排序，可快速地根据键值来检索元素；map 容器中不允许存在键值相同的元素，而 multimap 容器中则允许
C++11 中新增的 unordered_set / unordered_multiset （声明于 < unordered_set>）和 unordered_map / unordered_multimap （声明于 < unordered_map>）
映射表：通过哈希表实现，功能与 set/multiset 和 map/multimap 相似，但不对键值排序

在容器适配器中，不提供真正的用于存储元素的数据结构实现，不支持迭代器，由使用者选择合适的底层数据结构：

stack （声明于 #include<stack>）
栈：是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项，即按照后进先出的原则
queue （声明于 #include<queue>）
队列：插入只可以在尾部进行，删除、检索和修改只允许从头部进行，即按照先进先出的原则
priority_queue （声明于 #include<queue>）
优先队列：最高优先级元素总是第一个出队，可视作堆

所有 STL 容器的共有的成员函数：

operator = / < / <= / > / >= / == / != ：比较元素大小
empty() ：判断容器中是否有元素
max_size() ：容器中最多能装多少元素
size() ：容器中的元素个数
swap()：交换两个容器对象中的内容

只在顺序容器和关联容器中的成员函数：

begin()：返回指向容器中第一个元素的迭代器
end()：返回指向容器中最后一个元素后面的位置的迭代器
rbegin()：返回指向容器中最后一个元素的迭代器
rend()：返回指向容器中第一个元素前面的位置的迭代器
erase()：从容器中删除一个或几个元素
clear()：从容器中删除所有元素

除前述共同操作外，顺序容器还有以下共同操作：

front()：返回容器中第一个元素的引用
back()：返回容器中最后一个元素的引用
push_back()：在容器末尾增加新元素
pop_back()：删除容器末尾的元素

2.2.迭代器

迭代器用于指向顺序容器和关联容器中的元素，实际上就是泛化的指针，有 const 和非 const 两种：

const_iterator 对于遍历 const 容器是必需的，允许以只读方式访问容器的底层元素；
通过迭代器可以读取它指向的元素，通过非 const 迭代器还能修改其指向的元素，用法和指针类似。

使用“容器类名::iterator ”或“容器类名::const_iterator ”声明：

例如 vector<int>::iterator it; 或 set<string>::const_iterator it;
读取元素时就可以用 *it 来实现

迭代器上可以执行自增（++）操作，以指向容器中的下一个元素：

如果迭代器到达了容器中的最后一个元素的后面，则迭代器变成 past-the-end 值，其与 NULL 的含义类似。

不同容器上支持的迭代器功能强弱有所不同，按功能由弱到强，可以将迭代器分为 5 种：

输入迭代器 Input iterators 和输出迭代器 Output iterators
提供对数据的只读或只写访问
正向迭代器 Forward iterators
提供读写操作，并能一次一个地向前推进迭代器
双向迭代器 Bidirectional iterators
提供读写操作，并能一次一个地向前和向后移动
随机访问迭代器 Random access iterators
提供读写操作，并能在数据中随机移动

注意：强迭代器拥有弱迭代器的所有功能，能当作弱迭代器使用。

不同迭代器所能进行的操作如下所示：

所有迭代器： ++p、p++
输入迭代器： *p、p = q、p == q、p != q
输出迭代器： *p、p = q
正向迭代器：以上所有
双向迭代器：以上所有，以及 --p、p--
随机访问迭代器：以上所有，以及移动 i 个单元（p += i、p -= i、p + i、p – i）、大小比较（p < q、p <= q、p > q、p >= q）、数组下标访问p[i]（p 后面的第 i 个元素的引用）

容器所支持的迭代器类别如下：

示例：

#include <vector>
#include <iostream>
using namespace std;
int main()  {
    vector<int> v;   // 一个存放 int 型元素的向量，一开始是空的
    // 依次放入 1 2 3 4
    v.push_back(1);  v.push_back(2); 
    v.push_back(3);  v.push_back(4);
   
    // 使用常量迭代器打印这个容器中的元素
    vector<int>::const_iterator i;
    for (i = v.begin(); i != v.end(); ++i) cout << *i << " ";
    cout << endl;    // 输出 1 2 3 4
    
    // 非常量迭代器修改容器中的元素
    vector<int>::iterator j;
    for (j = v.begin(); j != v.end(); ++j) *j = 100;
   
    // 再次使用常量迭代器打印这个容器中的元素
    for (i = v.begin(); i != v.end(); i++) cout << *i << " ";
    cout << endl;    // 输出 100 100 100 100
    return 0;
}

2.3.算法

算法就是一个个函数模板，STL 中提供了能在各种容器中通用的算法，如插入、删除、查找、排序等，约有70种标准算法。算法可以处理容器，也可以处理内置类型的数组。

算法通过迭代器来操纵容器中的元素，许多算法需要两个参数，一个是起始元素的迭代器，一个是终止元素的后面一个元素的迭代器。有的算法返回一个迭代器，比如 find() 算法，其功能是在容器中查找一个元素，并返回一个指向该元素的迭代器。

头文件 #inlcude<algorithm> 中实现了一些常见的针对序列区间的算法：包括不修改值的序列操作、修改值的序列操作、分割与合并、查找与排序、堆操作、排列相关操作等。

头文件 #include<numeric> 中则实现了一些特别针对数值序列的算法

accumulate()：累加一个区间中的值
adjacent_difference()：依次计算一个区间内每一对相邻元素的差
inner_product()：计算两个向量的内积

下面介绍一些< algorithm>中实现的常见算法：

不修改值的序列操作
for_each()：遍历一个区间内的元素
find()：在一个区间中进行查找指定的元素
count()：在一个区间中计数指定元素
search()：在一个区间中查找指定的子序列
修改值的序列操作
copy()：复制一个区间的内容
swap()：交换两个对象的值
replace()：替换一个区间中的某个值
unique()：去重，删除相邻的相同元素
random_shuffle()：随机洗牌，重排区间中的元素
分割与合并
partition()：将一个区间根据指定规则分割为两个
merge()：将有序区间合并
set_intersection()：找出两个区间中相同的元素
set_difference()：找出两个区间中不同的元素
查找
binary_search()：二分查找
min_element()：查找最小的元素
max_element()：查找最大的元素
排序
sort()：用快速排序算法给一个区间中的元素排序
堆（Heap）
make_heap()：根据指定序列构建堆
push_heap()：向堆中插入元素
pop_heap()：弹出堆顶元素
排列
next_permutation()：产生指定序列的下一个排列
prev_permutation()：产生指定序列的上一个排列

2.4.函数对象

函数对象即重载了操作符 () 的对象，类的实例都可以称作为函数对象，本身是对象，但是用起来看上去象函数调用，实际上也执行了函数调用。

STL 中的头文件 < functional> 里实现了一些函数对象类模板，例如 equal_to< T>、greater< T>、less< T> 等这些模板都可以用来生成函数对象。

函数对象可以包含其他成员变量或成员函数，函数对象的优点是可以在对象内部修改而不用改动外部接口，可以存储先前调用结果的数据成员，编译器可通过内联函数对象来增强性能。

例如下面声明了一个函数对象 average 计算均值：

class Average {
public:
    double operator()(int a1, int a2) {
        return (double)(a1 + a2) / 2;
    }
    double operator()(int a1, int a2, int a3) {
        return (double)(a1 + a2 + a3) / 3;
    }
};  // 重载 () 运算符时，参数可以是任意多个
int main() {
    Average average;  // 函数对象
    // 调用 average.operator(2, 3, 5)
    // 但是使用时看上去象普通函数调用
    cout << average(2, 3, 5) << endl; // 输出 3.33333
    cout << average(7, 11) << endl;   // 输出 9
    return 0;
}

例2：

class IntMod {
    int p;
public:
    IntMod(int _p) : p(_p) { }
    bool operator() (int v1, int v2) {
        return v1 % p >= v2 % p;
    }
    bool operator() (float v1, float v2) {
        return (int)(v1) * p % 10 >= 
               (int)(v2) * p % 10;
    }
};  
//IntMod 类重载了 ()对于 int 型，比较 %p 之后的大小
//对于 float 型，先转换成 int 型，然后比较 *p 后 %10 的大小

template <class T>
T myMax(T *pV, int n, IntMod fun) {
  T result = *pV;
  for (int i = 1; i < n; ++i) {
      if (!fun(result, *(pV + i))) {
          result = *(pV + i);
      }
  }
  return result;
}
//函数模板 myMax() 寻找最大值，可以处理不同类型的数组
//根据 IntMod 类中定义的大小关系，找到不同类型数组中的最大值

int main(){
    int a[5] = {3, 9, 12, 5, 20};
    float b[5] = {3, 9, 12, 5, 20};
    IntMod obj1(8), obj2(3);
    cout << myMax(a, 5, obj1) << endl;
    //第一行输出对应 int 型数组 a，数组长度为 5，对 8 模后取余
    //即找到 %8 之后最大的整数，因此最大值是 5，输出 5
    
    cout << myMax(b, 5, obj1) << endl;
    //第二行输出对应 float 型数组 b，数组长度为5,*8后对10模后取余
    //即找到 *8 %10 之后最大的数，因此最大值是 12，输出 12
    
    cout << myMax(a, 5, obj2) << endl;
    //第三行输出对应 int 型数组 a，数组长度为 5，对 3模后取余
    //即找到 %3 之后最大的整数，若有相等的情况找靠前的那个，因此最大值是 5，输出 5
    
    cout << myMax(b, 5, obj2) << endl;  //输出3
    return 0;
}