C++STL标准库与泛型编程

---

使用一个东西，却不明白它的道理，不高明
——林语堂

• level 0：浅尝C++标准库
• level 1：深入认识C++标准库
• level 2：良好使用C++标准库
• level 3：扩充C++标准库

C++ Standard Library vs. Standard Template Library

Standard Library 包含 Standard Template Library。

标准库以header files 形式呈现

• C++标准库的 header files 不带副档名 .h
• 新式 C header files 不带副档名 .h
• 旧式 C header files （带有副档名 .h）仍然可用
• 新式 headers 内的组件封装于 namespace "std"
• 旧式 headers 内的组件不封装于 namespace "std"

不同编译器所带的标准库，使用起来毫无区别。

STL体系结构基础

---

STL六大部件（Components）：

• 容器（Containers）：放置数据
• 分配器（Allocators）：为数据对应分配内存
• 算法（Algorithms）：操作数据
• 迭代器（Iterators）：算法和容器的桥梁，一种泛化的指针
• 适配器（Adapters）：做转换
• 仿函式（Functors）：作用像一种函数

一般容器有allocator默认值，容器填充类型和分配器分配类型要一致。
迭代器可以参考指针的方式应用。此函数适配器将less（a, b）比较a与b，bind2nd将第二个参数绑定为40，not1取非转换为>=。

复杂度

描述程序执行快慢，和应用情景相关，在工业级数据量下，才体现出威力。

常见的 Big-oh 情形：

1. O(1)或O(c)：常数时间 constant time
2. O(n)：线性时间 linear time
3. O(log2 n)：次线性时间 sub-linear time
4. O(n^2)：平方时间 quadratic time
5. O(n^3)：立方时间 cubic time
6. O(2^n) : 指数时间 exponential
7. O(n*(log2 n))：介于线性及二次方成长的中间模式

前闭后开区间

容器的 begin() 指向容器中的第一个，end()指向容器中最后一个之后的下一个。
容器不一定在一段连续空间内，不管是什么容器，内存如何安排，都会提供 begin() 和 end() 。
所有容器都具有自己的迭代器实现。

range-based for statement （since C++11）

for(decl : coll) {  //declaration : collection
    statement
}

遍历容器内元素逐一操作。

auto keyword (since C++11)

编译器自动推导变量类型，
主要通过赋值操作进行类型推导。

容器——结构与分类

---

容器，如何在内存中实现，如何描述元素间关系，对我们判断不同算法对它的效率很关键。

分类

Sequence Containers

• Array：将C语言中的数组封装成类，声明大小的连续内存空间，前后不可扩充。
• Vector：起点不能动，尾部可扩充。需要增长时，调用分配器自动扩充。
• Deque：双向队列，两端可进可出。
• List：双向环状链表。环状只是为了实现方便。
• Forward-List：单向链表。

Associative Containers：可以快速通过 key 找到 value

以红黑树（一种高度平衡的二叉树，实现需要自我调整）实现，以避免查找时出现高度不对称的奇异情况。
事实上，C++标准库并未规定这两种容器的实现方式，只是由于红黑树自身的优越性，为各家编译普遍采用

• Set/Multiset：value 既是 key，也是 value。
• Map/Multimap：有 key 和 value，key 用于查找，value 作为数据。
  Multi 表示可以重复。

Unordered Containers（可归类到 2）：不定序元素，hash table separate chaining实现

容器测试

array

vector

两倍增长：放入元素，出现空间不足时，就分配是已有空间的两倍的一份新空间，将原有元素逐一移动过去，最后所占空间总大小对应capacity()，size()表示存入的元素。
出现分配超荷载，用abort()退出

deque

buffer：分组存储数据段，长度指定
通过分段连续结构，来将分散的代码段，模拟成连续的一样。（以建立map映射指针表的形式）

Tips

用namespace封装测试代码，
变量声明和定义在测试时尽量不重排以提示应用位置。