标准库与泛型编程

内容提示：泛型编程（GP)与面向对象编程(OOP)的根本差异，模板的意义以及运用。

课程目标：

1.浅尝C++标准库

2.深入认识C++标准库

3.良好使用C++标准库

4.扩充C++标准库

STL vs CSL（标准模板库 vs C++标准库）：CSL=STL+else（其他内容）

header files的写法标准

注1：编译器不影响标准库的使用

注2：学习网址推荐

【1】 http://www.cplusplus.com/
【2】 http://en.cppreference.com/w/
【3】 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2118.html

STL六大部件

六大部件

容器（Containers）：用来存放数据。

分配器（Allocator）：负责空间配置与管理，实现动态空间的分配、管理、释放。

算法（Algorithms）：模板编程，问题处理的策略、方法。

迭代器（Iterator）：泛化指针，扮演容器与算法间的“粘合剂）。

仿函数（Functors）：行为类似函数，可作为算法的某种策略。

适配器（Adapters）：修饰容器/仿函数/迭代器接口的东西，所有操作由底层的deque提供。

STL六大部件 应用举例

复杂度介绍：

big O

container 区间介绍

container 前闭后开区间

for loop的新用法

语法规则

auto keyword

auto 分析

容器结构分析

三类容器

Sequence containers（序列式容器）按照放入次序排列

are ordered collectionsin which every element has a certain position. This position depends on the time and place of the insertion, but it is independent of the value of the element

Array：内存连续容器，无法扩容
Vector:分配器负责处理内存。增长方式为2的n次方（可能造成浪费）。
扩充方式，尾部自动扩充。
Deque：双向队列，两端都可以扩充。

Deque 内存申请方式

list：双向链表（内存不联系）
forward-List：单向链表。内存<双向链表。

Associative containers（关联式容器）

are sorted collectionsin which the position of an element depends on its value (or key, ifit’s a key/value pair) due to a certain sorting criterion.

使用范围：快速查找（用key查找）底部为红黑树（高度平衡），map包含key，value（key！=value），set（key==value）set/map无法放入相同的元素，Multimap/multiset，元素可以相同。

Unordered (associative) containers（无序容器—特殊关联容器）

are the hash function isfast. But because such a fast perfect hash function is not always possible or mightrequire that the array consumes a huge amount of memory, multiple elements might have the same position. For thisreason, the elementsin the array are linked lists so that you can store more than one element at each array position.

底层：hash table制作。bucket个数>element的个数。元素位置相同，方成链表，链表不能太长（影响查找速度），如果太长自动调整。

Unordered containers

容器举例：

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

分配器

分配器代码

分配器建议搭配容器使用。小额内存 new()与delete（）以及malloc（）搭配free（）使用。如果直接用分配器申请内存，还需要记住申请的个数（使用不方便）

OOP & GP

OOP（class 继承， 虚函数）：数据与方法放在同一个类里。
GP：数据与方法分离。通过迭代器，实现方法对数据的调用。

Paste_Image.png

GP的优势：容器和算法的开发各自独立，不需要考虑对方的问题，效率提高。届时二者直接通过接口实现数据调用。

举例：通过模板实现（比大小的方法）

Paste_Image.png

STL基础：1、Operator Overloading（操作符重载）2、Templates（模板）

操作符重载规则

操作符重载规则

**模板：参照上一课程

参考书籍

容器、结构与分类

容器 list

Paste_Image.png

Paste_Image.png

Paste_Image.png

Iterator (1.typedef 2.操作符重载）

Paste_Image.png

Paste_Image.png

traits

Paste_Image.png

Paste_Image.png

Paste_Image.png

容器 vector（动态增长的数组）

自动扩充，重新申请一个两倍大的数组。非原地扩充

三个指针（start 、finish、end_of_storage)，sizeof（vector）=3×指针大小。默认分配器alloc

Paste_Image.png

vector 成长的实现

查看finish与end

Paste_Image.png

vector使用会大量调用构造及析构函数，如果数据量大，要考虑时间成本

vector‘s iterator

G2.9版本

【4.9 暂时放弃看，没必要】

Paste_Image.png

Paste_Image.png

Paste_Image.png

容器 array（固定大小的数组）

Paste_Image.png

连续空间，只需用指针做迭代器，不需要特殊设计。

【4.9 暂时放弃看，没必要】

Paste_Image.png

容器forward_list（参考list看）

Paste_Image.png

容器 deque（分段连续空间）G2.9

双向扩充的实现：迭代器跳到边界时，node指向下一个缓冲区。

Paste_Image.png

map控制中心是一个vector

2.9版允许指定缓冲区的大小，通过BufSiz指定

deque插入元素时，可以自动判断，距离头近还是尾部近。然后移动短的一段。节省时间

Paste_Image.png

Paste_Image.png

deque模拟连续空间的方式

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

【G4.9】

Paste_Image.png

Paste_Image.png

容器queue&stack

queue

stack

用list做底部支撑，也能实现stack与queue的功能，代码如下：

用list做底部支撑，也能实现stack与queue的功能

但是执行效率没有deque高？（猜测）

stack可以选择vector做底部支撑，vector不支持queue的c.pop（）函数

Paste_Image.png

完全不能用map做底部支撑

完全不能用map做底部支撑

————————————————————————————————————————————————

关联式容器

rb_tree（相当于小型数据库）

特点，高度平衡，可以实现快速插入以及查找

RB_TREE

Paste_Image.png

Paste_Image.png

Paste_Image.png

G2.9

G4.9

G4.9

Paste_Image.png

Paste_Image.png

Paste_Image.png

map

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

hashtable