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 情形：
- O(1)或O(c)：常数时间 constant time
- O(n)：线性时间 linear time
- O(log2 n)：次线性时间 sub-linear time
- O(n^2)：平方时间 quadratic time
- O(n^3)：立方时间 cubic time
- O(2^n) : 指数时间 exponential
- 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封装测试代码，
变量声明和定义在测试时尽量不重排以提示应用位置。
网友评论