本文预览：
- 迭代器的分类
- 不同迭代器对算法的影响
- 算法举例及源码剖析
- 仿函数
- 适配器
概览
前面说的都是关于容器的东西，容器占到了STL大概百分之八十的内容，数据结构的地位是如此重要，程序只有数据结构还是不够的，这次来说说算法。STL提供了大概八九十个算法，包含在<algrithms>头文件里，数据结构是算法的底层基础，数据结构提供了算法操作的对象，而算法怎么去操作数据结构，这个是由迭代器来完成的。也就是说迭代器在算法和容易之间起到了一个粘合剂的作用。
迭代器的分类
迭代器分为五个类型：
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {}; //单向迭代器，单向列表
struct bidirectional_iterator_tag : public forward_iterator_tag {}; //双向迭代器，红黑树和双向链表用到的类型
struct random_access_iterator_tag : public bidirectional_iterator_tag {}; //随机访问型，连续内存vector、array等
每一种迭代器都是一个class
迭代器关系图
我们可以通过代码来测试每一种容器对应迭代器的类型：
void _display_category(random_access_iterator_tag)
{
cout<<"random_access_iterator_tag"<<endl;
}
void _display_category(bidirectional_iterator_tag)
{
cout<<"bidirectional_iterator_tag"<<endl;
}
void _display_category(forward_iterator_tag)
{
cout<<"forward_iterator_tag"<<endl;
}
void _display_category(output_iterator_tag)
{
cout<<"output_iterator_tag"<<endl;
}
void _display_category(input_iterator_tag)
{
cout<<"input_iterator_tag"<<endl;
}
template <typename T>
void display_category(T ite) {
typename iterator_traits<T>::iterator_category cagy;
_display_category(cagy);
cout<<"typeid(ite).name() = "<<typeid(ite).name()<<endl;
};
int main(int argc, const char * argv[]) {
display_category(array<int, 1>::iterator());
display_category(vector<int>::iterator());
display_category(list<int>::iterator());
display_category(map<int, int>::iterator());
display_category(set<int>::iterator());
display_category(istream_iterator<int>());
display_category(ostream_iterator<int>(cout, ""));
return 0;
}
不同迭代器对算法的影响
举一个简单的例子：
迭代器对算法的影响
算法distance计算迭代器的距离，如果是random_acess_iterator_tag类型的，我们看到，直接一次计算，时间复杂度O(1)，可忽略不计；但是如果是input_iterator_tag类型的，那么时间复杂度是O(n)，也就是说，迭代器对算法实现复杂度是有影响的。
再举一个例子advance：
advance对迭代器做移动操作
算法advance对迭代器执行迁建或者后退操作。都是根据迭代器类型，来决定进行那种类型的操作。
算法举例及源码剖析
1、 count_if()
返回满足条件的元素个数
vector<int> a = {1,3,2,8,7,4,6};
cout<<count_if(a.begin(), a.end(), bind2nd(less<int>(), 4));
可能需要对bind2nd做出解释一下，这一句的意思是对仿函数less的第二个参数绑定为40，整句的意思是：输出vector a中小于4的元素个数。
刚刚接触bind2nd不是很懂什么意思，这个刚开始我也不太懂，那就分心下源码：
//第一步：开始找源代码
template <class __Operation, class _Tp>
binder2nd<__Operation> //返回类型
bind2nd(const __Operation& __op, const _Tp& __x)
{return binder2nd<__Operation>(__op, __x);} //临时对象binder2nd，俩参数传进去，构造对象初始值
//第二步，找到binder2nd
template <class __Operation>
class _LIBCPP_TYPE_VIS_ONLY binder2nd
: public unary_function<typename __Operation::first_argument_type,
typename __Operation::result_type>
{
protected:
__Operation op; //定义了操作类型，这里是less<int>
typename __Operation::second_argument_type value; //定义了操作的第二参数，这里是 4
public:
_LIBCPP_INLINE_VISIBILITY
binder2nd(const __Operation& __x, const typename __Operation::second_argument_type __y)
: op(__x), value(__y) {} //构造函数啊，在这里给上面定义的俩变量赋值
_LIBCPP_INLINE_VISIBILITY typename __Operation::result_type operator() //重载了()，一定是在哪里调到了
( typename __Operation::first_argument_type& __x) const
{return op(__x, value);} //这里就很明了了，调用的时候传入了第一参数，我们去看看在哪调用的。
_LIBCPP_INLINE_VISIBILITY typename __Operation::result_type operator()
(const typename __Operation::first_argument_type& __x) const
{return op(__x, value);}
};
//第三步，找在哪里调用了__Operation(typename __Operation::first_argument_type& __x)
template <class _InputIterator, class _Predicate>
typename iterator_traits<_InputIterator>::difference_type
count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
typename iterator_traits<_InputIterator>::difference_type __r(0);
for (; __first != __last; ++__first)
if (__pred(*__first)) //这一句就是了，仿函数调用，我们看到传入第一参数。
++__r;
return __r;
}
在STL里面的源码我都加了注释，一步一步找到调用的地方，简单来说就是，bind2nd通过binder2nd返回它的临时对象，这个临时对象记录了操作(less<int>())和参数4，并重载了()，看到了没，这个就是仿函数了，在count_if源代码调用了()，传入一个参数。这就是整个调用过程。我们这里实际上有两处是仿函数，一次是less<int>一次是binder2nd<less<int>>。这里我们并没有看less的源代码，有兴趣可以看看，虽然很简单。
在C++11中bind2nd这个已经被有了更好了用法，那就是bind和lamda表达式。是因为这个太难理解了吗？或许吧。
2、 accumulate()
累加计算
#include <iostream>
#include <algorithm>
#include <numeric>
#include "Measurement.h"
using namespace std;
struct myClass{
int operator()(int x, int y){
return 2*x+y;
}
} myobj;
int main(int argc, const char * argv[]) {
int init = 0;
int arr[] = {10,20,30};
cout<<accumulate(arr, arr+2, init)<<endl;
cout<<accumulate(arr, arr+3, init, myobj);
return 0;
}
3、 count()
count本身是一个算法，不是每一种容器都提供count，其中线性容器没有count算法，而关联容器由于本身的特性，它是已经排好序的红黑树，所以本身提供count接口。
count
4、 find()
find需要注意的是一个问题是，在算法里提供了find算法，它的内部实现是全遍历，时间复杂度是O(n)，那么在所有的线性容器find都可以使用algorithms提供的算法，不需自己再写，但是set和map等关联容器就不行了，由于红黑树是一个高度平衡二叉树，它自己内部实现了更加效率的find算法，其时间复杂度是O(log(n))，这也是为什么线性容器没有find，而关联容器有find的原因。
find()
5、 sort()
sort方法有个特例，就是list，list内部实现了自己的sort，而其他的容器没有自己的sort，关联容器本身不需要实现sort，因其本身就是按顺序排列的，其他的线性容器可以统一使用算法提供的sort，而list由于自身的特殊性，不需要移动每一个元素，因此自身做了优化。
sort()
仿函数
仿函数的已经提过很多了，STL里面到处都是仿函数，这也是我们唯一可以修改的地方了吧，仿函数写起来还是比较简单的，一是小，二是比较容易扩容，但是想要和标准库兼容还是需要继承通用的父类，负责是不能和标准库兼容的。
STL仿函数使用举例
仿函数的适配条件：
每种仿函数都有对应的适配条件
这个跟函数适配器是有关系的。
适配器
适配器分很多类型：
- 容器适配器
- 函数适配器
- 迭代器适配器
容器适配器
stack和queue是容器，但是他们在本质上是适配器，他们本身并没有实现什么结构和算法，而是把deque拿过来，接口改造一下，实现了自己需要的功能。
容器适配器
函数适配器
我们前面分析的bind2nd就是一个函数适配器，我们使用一下C++11提供的bind适配器。
bind返回一个函数对象ret，调用ret，相当于调用function
int main(int argc, const char * argv[]) {
using namespace std::placeholders;
//绑定函数
auto fn_five = bind(my_divide, 10, 2);
cout<<fn_five()<<endl;
auto fn_half = bind(my_divide, _1, 2);
cout<<fn_half(10)<<endl;
auto fn_invert = bind(my_divide, _2, _1);
cout<<fn_invert(2, 10)<<endl;
auto fn_rounding = bind<int>(my_divide, _1, _2);
cout<<fn_rounding(10, 3)<<endl;
//绑定成员函数和成员变量
myPair ten_two {10,2};
auto bound_memfn = bind(&myPair::multiply, _1);
cout<<bound_memfn(ten_two)<<endl;
auto bound_memdata = bind(&myPair::a, _1);
cout<<bound_memdata(ten_two)<<endl;
//举例
vector<int> v {1,2,3,4,5,6,7};
auto fn = bind(less<int>(), _1, 5);
cout<<count_if(v.begin(), v.end(), fn);
cout<<count_if(v.begin(), v.end(), not1(bind2nd(less<int>(), 5)));
return 0;
}
迭代器适配器
list<int> foo, bar;
for (int i = 1; i <= 5; i++) {
foo.push_back(i);
bar.push_back(i*10);
}
list<int>::iterator it = foo.begin();
advance(it, 3);
copy(bar.begin(), bar.end(), inserter(foo, it));
for (auto x: foo) {
cout<<x<<' ';
}
输出结果：
1 2 3 10 20 30 40 50 4 5
inserter迭代器适配器，在copy的代码写的很清楚，但是怎么执行插入操作的？迭代器适配器重载了=操作符，使得每次赋值的时候都会执行插入操作。
ostream_iterator
向控制台输出
std::ostream_iterator<int> out_it(std::cout, ",");
copy(foo.begin(), foo.end(), out_it);
网友评论