泛型和STL

泛型程序设计

泛型程序的思想:

程序尽可能通用
将算法从数据结构中抽象出来, 成为一种通用的算法

STL做了什么

它是泛型程序思想的体现

它包含了常用的数据结构
它包含了常用的基本算法
它提供了一套可扩展的泛型编程框架

STL的六大组件

容器组件(Container)

标准容器共有如下几个:

vector
deque
list
set
multiset
map
multimap

数组(定长)的特点:

随机访问(在有效范围内, 随意指定下标进行单独访问)的速度是最快的.
随机访问的时间复杂度为 O(1)
插入/删除中间的数据的时候, 时间复杂度为 O(n)
删除末尾元素, 时间复杂度 O(1)
末尾增加元素, 时间复杂度 O(1)

序列式容器:

vector (向量)
- 本质是一个数组, 但是是可变长(通过一定的技法让用户感知不到长度的变化)的.
- 它是一个一维数组
- 进行可变长操作是, 时间复杂度为 O(n)
- 如果要进行大量数据的存储, 可以初始化足够的空间避免变长操作
deque (双端队列)
- 本质也是一个数组, 也是可变长的.
- 它是一个map(非stl的map), 这个map指向一个一维数组
- 这个一维数组的每个元素都是一个指针, 分别指向别的数组的首地址.
- 所以, 它在进行前端或后端增加操作的时候, 都是O(1)
- 它的随机访问, 是 >= O(3) 的
list (链表)
- 有单向和双向两种.
- 随机访问非常慢.
- 进行数据插入和删除非常快, O(1)
他们都是有序的

总结:

在频繁的插入或删除, 不用在序列内部长距离跳转的时候, 应选择 list.
在vector的头部和中间插入或删除数据的时候效率低, 但是在尾部插入或删除效率很高.
deque在头部和尾部插入与删除效率都很高, 但是实际访问速度比vector低.

关联式容器

set/multiset (集合)/(多重集合)
- 通过序号随机访问其中的元素
- multiset中序号可重复
map/multimap (映射)/(多重映射)
- 通过key-value随机访问其中的元素
- multimap中的key可重复
它们都是无序的, 是通过二叉树(红黑树)来实现的
在C11中新增了2个容器, 是通过哈希表实现的
一般我们都使用的是有序树, 用来进行搜索
红黑树是会将我们原来的顺序打乱的

适配器

它是改变了容器(Container)或者迭代器(Iterators)或函数对象(Function Object)接口的组件.

它分为以下三大类:

容器适配器
- 为现有类提供新的接口
- 包括 stack (栈)
- queue (队列)
- priority_queue (优先队列)
迭代器适配器
- 反向迭代器
- 插入迭代器
- IO迭代器
函数适配器
- 函数对象适配器
- 成员函数适配器
- 普通函数适配器

算法(Algorithm)

提供了各种算法, 比如 find, sort....
#include <algorithm> 就可以使用STL中的算法.
可作用于任何一个STL的容器上.

迭代器(Iterator)

迭代器的作用是连接容器(Containers)和算法(Algorithms).

迭代器可被称为一个 SMART POINT(小指针)
可以认为它是指针的一个类化.

它并没有实现指针的所有操作
它可以在一个容器的元素上进行遍历
它也可以是容器的一部分
它实现了++(累进)
- 使用++可以遍历下一个元素
它实现了*(提取值)
- 类似指针的解引用
它的遍历形式取决于容器内部的数据组织形式(数据结构)

函数对象(Function Object)

暂略...
一般来实现可扩展功能

分配器 (Allocator)

暂略...
一般来实现可扩展功能

六大组件的工作原理

Alt 工作原理
简而言之, 每个容器通过迭代器输入到算法中, 经过处理后, 算法在通过迭代器输出到容器内!

未完待续...

如有错误,请提出指正!谢谢.

本文由花心胡萝卜创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2017-03-16 at 07:59 am

PoEdu培训 STL班 第四课 STL的六大组件