C++ 标准库与泛型编程

2024-04-01 本文已影响0人陈星空

该课程也可以叫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不存在则寻找一个函数模板，将其实例化，产生一个匹配的模板函数，若找到了，就调用它
若1,2都皆不存在，会寻找低一级的对函数的重载方法，例如通过类型转换可产生参数匹配等，若找到了，就调用它
若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";