C++ 标准库与泛型编程

该课程也可以叫C++ 标准库——体系结构与内核分析；课程精髓是从源代码分析C++STL之体系结构，而STL正是泛型编程最成功的作品，所以也是以STL为标准深层次的探讨泛型编程。

STL六大部件

迭代器像是泛化的指针；
迭代器串联起算法和容器；
adapter可以转换容器、迭代器和仿函数

六大部件关系 容器结构与分类 复杂度 前闭后开区间

头部为第一个元素，尾部是最后一个元素位置的下一个位置

范围访问 auto关键字 容器--结构与分类 测试程序辅助函数

序列式容器

容器array

和c语言的数组一样，大小固定，之后不能改，size大小是常量才可以

容器vector1

两倍增长 扩充，会有很多内存碎片

容器vector2 容器list

优先使用容器自带的迭代器，原因是：标准库的sort中需要使用到随机访问迭代器，而list这类数据结构无法提供随机访问能力，所以内置一个sort不使用随机访问迭代器进行排序

容器forward_list 容器slist

所属gnu c++ 非标准c++库 单向链表

容器deque1

可以向前或向后生长，分段连续
每次扩充一个buffer，buffer多大看后续？

容器deque2 容器stack 容器queue

关联式容器

容器multiset

底层数据结构是红黑树

容器multimap

底层数据结构是红黑树

容器unordered_multiset1 容器unordered_multiset2 容器unordered_multimap 容器set 容器map 容器unordered_set1

hashtable做支撑，bucket后面是一个链表（可以是单向也可以是双向），bucket一定比元素数多，如果bucket的数量与元素数量相等，那么就会扩充bucket的数量为两倍，然后重新hash

容器unordered_set2 容器unordered_map

分配器

使用分配器1 使用分配器2 使用分配器3

1代表一个元素，直接使用分配器的时候，需要自己申请和释放，不建议直接使用 分配器

基础 OOP && GP 1 OOP && GP 2 OOP && GP 3 OOP && GP 4 操作符重载1

运算符重载的标准是模拟整数的操作

操作符重载2 操作符重载3 类模板 函数模板 成员模板 特化1 特化2 特化3 偏特化4

类模板可以 局部特化，分为两种数量的偏特化和范围的偏特化，如上图，左边是数量的偏特化，右边是范围的偏特化

分配器1 分配器2 分配器3

allocator<int>() 是一个临时对象

分配器4 分配器5 分配器6 分配器7 分配器8 分配器9 分配器10 分配器11 迭代器 容器-结构与分类1 容器-结构与分类2

这里的意思是set中包含一个RB_tree;
stack是基于deque实现的
heap是基于vector实现的
priority_queue也是基于vector实现的

容器和迭代器 容器list list 迭代器1 list 迭代器2

LIST ++运算符的重载
注意：copy构造与这里的*运算符重载
运算符重载的标准是模拟整数的操作

list 迭代器3 list 迭代器4 容器list 迭代器遵循的原则

iterator_category是指迭代器的类别，（1，只能前进 ++； 2，只能后退--； 3，可以跳跃+=3 +=4；）
value_type是指迭代器所指向元素本身的类型 （string int）
difference_type 指两个迭代器距离 需要用什么类型来表现，比如 vector的difference_type 是uint32_t

迭代器提供的5种关系

指针也是一种迭代器，是一种退化的迭代器

trits特性

既然指针也是一种迭代器，所以如果传进来的类型是指针，那么就无法分辨是普通的迭代器，还是指针类型，所以使用萃取机来中转判断一下，先判断传进来的迭代器是指针类型还是普通的迭代器

iterator_traits

萃取机使用偏特化的方式实现，偏特化出指针类型的iterator_traits，即可

完整的iterator_traits 各式各样的traits 容器vector1 容器vector2

insert_aux()可能被其他函数调用所以需要再次检查空间

容器vector3

有可能要被insert()调用，所以前后的元素都要拷贝到新的空间

2.9 vector iterator

走偏特化的版本，直接萃取出类型

4.9 vector 4.9 vector iterator1

有一堆复杂的继承关系，好在大小还是12字节

4.9 vector iterator2

走泛化版本的萃取机，获取类型，实现相比4.9变得更为复杂，最终呈现的结果一样

array1 array2 forward_list deque1

deque双向开口，vector单向开口

deque2 deque iterator deque insert1 deque insert2 deque模拟连续空间1 deque模拟连续空间2 deque模拟连续空间3 deque模拟连续空间4 deque模拟连续空间5 4.9版deque1 4.9版deque2 容器queue 容器stack queuq&stack底层结构1

stack queue都不允许遍历，也不提供迭代器
都可选择list 和deque作为底层数据结构 deque更快，性能好

queuq&stack底层结构2

关于能选那个容器作为底层数据结构，只要调用的时候底层数据结构都有对应的实现就可以调用
stack可以选择vector作为底层数据结构
queue不可选择vector作为底层结构，但是也并非完全不可以

queuq&stack底层结构3

不可选择map或者set作为底层数据结构

容器rb_tree1 容器rb_tree2

4+4+1=9 对齐之后是12字节，1是空类的大小（compare functor）

容器rb_tree3

identity是gnu c++编译器独有，less是编译器都有
unary_function和binary_function是adapter

容器rb_tree 用例1 容器rb_tree 用例2 容器rb_tree 用例3 容器rb_tree 类图

4.9新版的所有的容器实现中，严格遵守了面向对象oo的设计思想，handle-body的实现模式（桥接模式），对外的类只有接口，具体的实现隐藏在impl指针指向的类中

容器set & multiset 容器set

set可以当作container adapter stack和queue也可以被称作adapter 因为不做事，把事情全部交给底层的数据结构

vc6 容器set

vc6没有identity，但是自己实现了一个inner class kfn的东西和identity差不多

使用容器multiset 容器map & multimap 容器map

这里可以清楚的看到value=key+data 这里用pair对key+data进行了组装

vc6 容器map 使用容器multimap 容器map【】

[]会先找到map中当前元素的第一个位置，或者最适和插入该元素的位置，所以这里性能很不错，有优化，
不过insert更加快一点，因为[]最后插入的时候也是调用的insert

使用容器map 容器hashtable1 容器hashtable2

bucket数量一般为质数，gnu-C中起始值为53
当元素个数和bucket数量一样是，bucket数量翻倍
bucket数量扩充是扩充为多大是写死的，存在一个static数组中

容器hashtable3

hashtable迭代器中有两个指针 一个指向链表中的元素，一个指向bucket，用来支持遍历操作

容器hashtable4 hash-function & hash-code 1 hash-function & hash-code 2 modelus运算 hash-function & hash-code 2 2.9 hashtable用例 4.9 hashtable用例 hash容器改名为unordered容器 容器 unordered_set1 容器 unordered_set2 c++ 标准库算法简介 iterator_category1

模板函数可以和普通函数重名？这种不算特化，叫重载？

调用函数时会进行严格的类型匹配，但是模板函数不会进行自动类型转换，而普通函数具有隐式的类型转换。
其调用顺序应该是：

1. 首先寻找参数完全匹配的普通函数，如果找到了就调用它
2. 若1不存在则寻找一个函数模板，将其实例化，产生一个匹配的模板函数，若找到了，就调用它
3. 若1,2都皆不存在，会寻找低一级的对函数的重载方法，例如通过类型转换可产生参数匹配等，若找到了，就调用它
4. 若1,2,3均未找到匹配的函数，则是一个错误的调用
   参考

iterator_category2 iterator_category1 typeid

获取c++语言本身给类型的名字 typeid().name ，得到的是编译器给这个类型的名字

iterator_category of istream_iterator

三个版本接口一样

这里有一个神奇继承关系，itertor是一个只有内嵌类型（typedef）的类，没有function，没有data，ostream_iterator继承之后，也只是为了继承iterator中的内嵌类型

iterator_category of ostream_iterator iterator_category 影响算法1

根据迭代器的类型，选择不同的计算迭代器之间距离的方法

iterator_category 影响算法2

根据迭代器的类型，选择 +n 前进 (或者-n 后退)的方法

iterator_category && type traits 影响算法1

根据迭代器的类型选择copy的方法，总是会选择最合适的办法去做拷贝动作
type traits .....? 使用type traits判断是否has trival operate=(拷贝赋值到底重不重要) 后面会讲---

iterator_category && type traits 影响算法2

根据迭代器的类型选择destroy的方法

iterator_category && type traits 影响算法3

根据迭代器的类型选择destroy的方法

iterator_category && type traits 影响算法4

output_iterator write only
input_iterator read only
stl有针对传入不同迭代器进行专门的处理

算法源码中对iterator_category的暗示

因为算法源码都是模板实现，所以理论上不区分迭代器类型，但是有相应的暗示，如上图所示，如果传入的迭代器类型不符合要求，可能会编译失败

先前示例中出现的算法 算法 accumulate 算法 for_each 算法replace replace_if replace_copy 算法count count_if 算法find find_if 算法sort reverse iterator，rbegin()，rend() 算法binary_search 仿函数functors1 仿函数functors2 仿函数functors3 仿函数 可适配条件

stl中多处使用内嵌内型，如下，子类继承父类之后拥有同样的定义

template <class arg, class result>
struct unary_function{
  typedef arg argument_type;
  typdef result result_type;
};

多种adapter

adapter都是包含的关系，adapter适配器的意思就是内涵一个东西，然后对这个东西进行改造，如下图

容器适配器 stack queue

stack queue 内含一个deque，然后进行改造，比如push_back（）改名为push（）

函数适配器 binder2nd

多处使用模板编程的技巧，typedef内嵌类型

函数适配器 Not1 新型适配器 bind-1

所以std::bind是一个适配器 非常有趣
std::bind返回值是function object

新型适配器 bind-2

bind用法详解 可以绑定4种东西，返回是function object

迭代器适配器--reverser_iterator

rbegin() rend()也都是适配器

迭代器适配器--inserter

接管赋值操作，将普通赋值操作变成insert操作

X适配器--ostream_iterator

这里有一个神奇的示例，建议测试一下，详细看下代码！！！

    for(int i=0; i<10; ++i){
        v.push_back(i*10);
    } 
    std::ostream_iterator<int> out_it(std::cout, ",");
    std::copy(v.begin(), v.end(), out_it);

X适配器--istream_iterator 1

    double v1, v2;
    std::cout<<"input two valus: "<<std::endl;
    std::istream_iterator<double> eos;
    std::istream_iterator<double> iit(std::cin);
    if(iit!=eos) v1=*iit;
    ++iit;
    if(iit!=eos) v2=*iit;
    
    std::cout<<"v1: "<<v1<<"v2: "<<v2<<"\n";

X适配器--istream_iterator 2

istream_iterator构造的时候 已经在等待输入！！！！！！！！！！！！！

万用的hash function1

虚线框起来的是上面函数的类型

万用的hash function2

很多技巧：
1 变参模版函数参数，拆分
2 同名函数递归调用
3 pass by reference seed值
4 最后的hash code是seed值
5 seed计算方式采用了黄金比例计算公式，详见下图

万用的hash function3 万用的hash function4 万用的hash function5 偏特化的hash function1 偏特化的hash function2 tuple 用例

tuple的一些神奇用法
1 tie
2 tuple_size
3 tuple_element
4 make_tuple
5 get<0>()

tuple源码

这里同样使用了很多技巧， 关键的技巧就是variadic template 可变参数模板 （自动递归）
1 私有继承
2 一层层剥离模板参数列表
3 tail返回值，this会被强转

type traits1

2.9版本type_traits 需要自己补充自定义类型的的萃取机制

type traits2

4.9 新版本中定义了一大堆萃取机，不需要补充自定义类型的萃取机制

type traits3 type traits 测试1 type traits 测试2 type traits 测试3 type traits 测试4 type traits 测试5 type traits 测试6 type traits 测试7 type traits 实现is_void type traits 实现is_integral type traits 实现 is_class is_union is_enum is_pod

编译器 在其中实现了一些函数，因为编译器知道一个类是否具有拷贝构造，拷贝赋值，是不是一个类型等这些问题

type traits 实现is_move_assignable 2,9 cout

2.9版本中，cout就是ostream对象对操作符的重载“<<”

4.9 cout

同样4.9版本中，cout就是ostream对象对操作符的重载“<<”

moveable 元素对vector速度效能的影响

cctor是copy构造 mctor是移动构造 后者性能强很多；
具体差多少跟当前内存情况有关

moveable 元素对list速度效能的影响 moveable 元素对deque速度效能的影响 moveable 元素对multiset速度效能的影响 moveable 元素对unordered_multiset速度效能的影响 moveable class 实现示例1 moveable class 实现示例2

所以移动语意其实是浅拷贝，所以需要注意的是：
使用移动语意之后，原来的object是不可使用的

moveable class 测试函数 vector的copy构造

这个是深copy

vector的move构造

这个是浅copy

string具有移动语意

以上是string的构造函数，拷贝构造，移动构造