STL算法、迭代器和映射总结
迭代器
迭代器的提出
算法函数独立于数据结构无疑是一种很好的思路，它高度体现了OOP的核心思想。
但很快，我们就会发现因各数据结构的访问形式不同，困难显而易见。比如：
int sum( vector<int> &v )
{
int s = 0;
for ( int i = 0; i < v.size(); ++i ) s += v[i];
return s;
}
int sum( List<int>& l )
{
int s = 0;
Link<int> *first = l.first;
while ( first != l.last ) {
s += first ->elem;
first = first ->next;
}
return s;
}
从而我们设想必须有一种通用的访问工具。这就是迭代器。将算法和容器隔离开的过程叫做解耦。
迭代器的分类
| 类型 | 支持的操作 | 容器举例 |
|---|
| 前向迭代器 | 向前移动；读取；相等比较 | 单向list |
| 双向迭代器 | 前向操作；向后移动 | 双向list |
| 随机访问迭代器 | 双向操作；自由移动；任意读取；大小比较；相减 | vector |
使用模型
在定义数据序列的功能上说，迭代器是一种可以表示数据序列中元素的对象。
数据序列：
begin()开始，end()结束- 每个元素可以通过
* 进行解引用，取出对应位置的元素。 - 迭代器可以支持基本运算，实现在数据序列中的遍历。
常用算法
查找函数
find(begin(),end())函数，遍历查找。
find_if(begin(), end(), pred())，为查找添加条件。
谓词predicates
其中 pred() 就称为谓词。
谓词的形式：
bool odd(int i) return i%2;
struct Odd
{
bool operator(int i) const { return i%2;}
} odd;
if (odd(n))
{ ... }
vector<int>::iterator p = find_if(v.begin(), v.end, odd);
vector<int>::iterator p = find_if(v.begin(), v.end, Odd());
从上面的例子可以看出，在调用过程当中，二者实际上并无太大差异。
那为什么要舍近求远用函数对象呢？
思考： C++的类，相比函数，优势在于结合了结构体变量携带状态的特点。从而可以在运行时改变函数的非入口特征值。这是仅有一个入口的普通函数谓词所不能比拟的。
例如以下这个门限值的判定
template<class T>
struct Less_than
{
T val;
Less_than(T& x) : val(x) { }
bool operator()(const T& x) const { return x < val; }
};
p = find_if(v.begin(), v.end(), Less_than(43));
q = find_if(ls.begin(), ls.end(), Less_than("perfection"));
函数对象的优点再论
- 可以抽象成一类函数的判别，并可以在运行过程中改动。
- 易于内联：现有编译器支持性好
- STL中已有一类成熟的函数对象模板
plus<T>
minus<T>
multiplies<T>
divides<T>
modulus<T>
multiplies<double> m;
m( x, y );
累加算法
定义在可泛化为累乘、累除、累减。
#include <numeric>
#include <functional>
void f(list<double>& ld)
{
double product = accumulate(ld.begin(), ld.end(), 1.0, multiplies<double>());
}
内积算法
向量内积的计算方式，给出两个数据序列，第一个给出头尾，第二个给出头。结果为一个数。
#include <vector>
#include <numeric> >
int main()
{
vector<double> score { 92, 77, 85, …. };
vector<double> weight { 4, 2, 3, … };
double average = inner_product(score.begin(), score.end(),weight.begin(), 0.0) /
accumulate(weight.begin(), weight.end());
return;
}
内积算法也可以进行泛化。
其他常用标准库算法
| 算法 | 用法 |
|---|
| for_each(b,e,op) | 对区间 [b,e) 的每一个元素执行 op |
| r=find(b,e,v) | 在区间 [b,e) 查找给定值 v 的元素 |
| r=find_if(b,e,p) | 在区间 [b,e) 查找符合条件 p(x) 的元素 |
| x=count(b,e,v) | 在区间 [b,e) 计算值为给定值 v 的元素的个数 |
| x=count_if(b,e,p) | 在区间 [b,e) 计算符合条件 p(x) 的元素的个数 |
| r=remove(b,e,v) | 删除区间 [b,e) 中值为给定值 v 的元素 |
| r=remove_if(b,e,p) | 删除区间 [b,e) 中符合条件 p(x) 的元素 |
| fill(b,e,v) | 用给定值 v 填充区间 [b,e) 的元素 |
| sort(b,e) | 对区间 [b,e) 的元素进行排序，排序条件： < |
| sort(b,e,p) | 对区间 [b,e) 的元素进行排序，排序条件： p |
| copy(b,e,b2) | 复制区间 [b,e)中的元素至另一区间（b2 起始）*dest++ = *src++; |
| unique_copy(b,e,b2) | 复制区间 [b,e)中的元素至另一区间，剔除相邻相同元素 |
| merge(b,e,b2,e2,r) | 合并两个区间 [b,e)， [b2,e2) 的元素至第三个区间（r 起始） |
| equal(b,e,b2) | 区间 [b,e) 与区间 [b2,b2+(e-b)) 的所有元素是否相等? |
算法小结
- 面向一个或更多的序列进行处理
- 支持一个或多个类型的操作
- 一般通过返回指向序列尾部的迭代器报告“错误或操作失败”
关联容器与映射
map是仅次于 vector 的STL容器。- 基于平衡二叉树实现
- 支持通过下标访问元素
映射的常见操作
标准操作：begin(), end(), size(), empty(), clear()
插入操作：
age.insert( pair<string,int>{ “Andy”, 10 } );
age.insert( make_pair(“Andy”, 10 ) ) ;
下标操作：
int n = age.[“Jack”];
age[“Andy”] = 12;
删除操作：
age.erase(“Andy”);
查找操作：map的查找非常高效
map<string,int>::iterator it = age.find(“Andy”);
if( it != age.end() ) cout<<it->first<<it->second<<endl;
集合set
去除了映射中的值维，无下标操作。键不重复，同样利用平衡二叉树高度有序。
例 利用set实现字典
int main()
{
set<string> words{ istream_iterator<string>{ cin },
istream_iterator<string>{ } } );
copy( words.begin(), words.end(),
ostream_iterator<string>{cout, "\n"} );
}
字典如果使用vector实现，则需要先读入，后排序，再 unique_copy。使用set极大减少了因顺序和判断重复造成的开销。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
