本文共 2185 字,大约阅读时间需要 7 分钟。
目录
一、C++标准库算法的本质
- 容器 Container 是一个 class template
- 算法 Algorithm 是一个 function template
- 迭代器 Iterator 是一个 class template
- 仿函数 Functor 是一个 class template
- 适配器 Adaptor 是一个 class template
- 分配器 Allocator 是一个 class template
算法通常的两种形式:
- 两个迭代器参数,控制算法的作用范围。迭代器由容器提供,体现了算法通过迭代器控制容器的关系。而 Iterator 必须能够回答 Algorithm 提出的所有提问,才能搭配该 Algorithm 的所有操作。
- 迭代器加上自定义的函数准则(仿函数)
二、各种容器的迭代器
2.1迭代器的分类
输入迭代器、输出迭代器、正向迭代器、双向迭代器、随机访问迭代器(描述了移动方式)
由每种容器的内存分布特性可推断其迭代器类型:
- Array Vector Deque: 随机访问迭代器
- List Set Map(rb_tree):双向迭代器(红黑树节点之间是双向链接)
- Forward List:正向迭代器
- Unordered Set Map:由其底部实现的哈希表中的链表决定,可能为正向或者双向迭代器
不同类型的迭代器是不同的类,上例可以通过函数重载写成不同的函数。
类型名 后面直接加小括号 表示创建一个临时对象。
2.2迭代器分类对算法的影响
distance:
- distance 函数一般不是由用户调用的,而是由其他算法调用的,用来得到两个迭代器之间元素个数。
- 在 iterator 是 随机存取迭代器的情况下,实现方法就是尾减头。
- 在 iterator 是 input 迭代器的情况下,实现方法是从头开始 ++ 计数。
- distance 函数的返回类型就是 traits 中的 difference_type(5个相关类型之一)。
这种由一个主函数调用不同情况下的 iterator 重载次函数的形式,广泛存在与 STL 算法中。
因为 iterator_tag 是具有继承关系的类,所以所有的类型情况都可以 只提供几种方案并利用多态来实现。
advance:
advance 函数为 iterator 向前操作,参数为 iterator 引用,分3种情况利用多态实现了所有迭代器类型的操作。
copy:
- 一般 iterator 时,每复制过一个元素都要检查是否到头,效率较低。
- random_acess_iterator 时,根据黄字,可直接判断循环次数,效率较高。(随机访问表示连续内存分布)。
- trival op = 与 non_trival op= 如何判断:例如,复数类,只有两个元素 im 和 re ,没有指针,这样的类不需要写析构、拷贝构造、拷贝赋值函数,编译器默认生成的这些函数就是 non_trival 的。(第四讲 STL 之外,标准库之内的东西)
特化与偏特化是对于 模板参数来说的,函数参数类型的不同是函数重载 。
2.3算法中对要求的 iterator 类型的暗示
语法上传入任何类型的 iterator 都能通过编译,编译器做不到限制,但是调用时就会出错。
只能在模板函数与函数参数列表中暗示出所希望的类型。
三、算法的源代码剖析
accumulate:
- accumlate 算法有两种重载的形式默认为累加,,其中第二种接收一个自定义操作对数据做累计。
- myfunc() 表示自定义函数
- myobj() 表示函数对象(或称仿函数),实质是一个类或者结构体,重载了 operator() 。
for_each():
对迭代器范围内的所有元素做 f() 运算。
C++11 基于范围的 for
for ( decl:coll ) 对 coll (可能是个容器)中的所有元素做相同的 statement 操作。
replace(),replace_if(),replace_copy()
检查范围内所有元素,如果和原值相同,则取代为新值。
if() 表示要给出取代条件,返回 bool 。
copy() 范围内所有等同于 old_value 者都以 new_value 放置新区间,不符合的原值放入新区间。
全局与成员 count(),count_if()
找相等或符合条件的元素个数。
基本 所有关联式容器(底层实现为红黑树或哈希表) 8个自成一组,提供了一些独有的效率更高的类方法。
全局与成员 find(),find_if()
没有复杂的操作,就是简单的循序式查找。
全局与成员 sort()
要求必须是 random_acess_iterator。所以 list 不能调用全局 sort。
.rbegin() 与 .rend() 代表反向迭代器,使用 sort 后就变成了由大到小排序。
binary_search()
二分查找,必须先通过排序才能使用,返回bool,即在不在此区间内。
lower_bound() 返回查找到的较低可插入位置。
reverse iterator,rbegin(),rend()
rbegin() 通过 适配器reverse iterator 调整 end() 得到。
转载地址:http://pqxni.baihongyu.com/