1.C++标准库的算法，是什么东西？
从语言的层面讲，STL的算法都长下面两个样子：
template<typename Iterator>
Algorithm(Iterator itr1, Iterator itr2)
{
//...
}
template<typename Iterator, typename Cmp>
Algorithm(Iterator itr1, Iterator itr2, Cmp comp)
{
//...
}
上面这两个东西是Function template（函数模板），一般情况算法都有两个版本，一个是两个参数的，一个是有三个参数的版本。前面两个参数是两个迭代器，用来让算法知道需要操作的对象的范围，第三个参数是为了增加算法的弹性，用户可以在其中加上自己的准则，比如：sort函数，默认是从小到大排序，如果加上第三个参数（指定从大到小），那么sort就会将数据按照指定的方式操作。
算法是看不见容器的，对其一无所知，一切信息都是从iterator中得到。iterator就是算法和容器之间的桥梁。
1.1各种容器的iterators的iterator_category
STL中有五中iterator_category分别是：
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{};
Array，Vector，Deque这三种容器支持随机访问，是连续空间（deque模仿出连续的假象），使用的是random_access_iterator_tag
list，set，map，multiset，multimap，都是关联性容器，不支持随机访问，使用的是bidirectional_iterator_tag
forward_list，unordered_set，unordered_map，unordered_multiset，unordered_multimap是单向连续性空间，不支持随机访问，使用的是forward_iterator_tag
istream，ostream分别使用的是input_iterator_tag，output_inerator_tag
注：typeid(iter).name()，可以直接得到对象的类型名称
1.2iterator_category对算法的影响
使用distance函数求得一个容器begin和end之间的距离
template<typename InputIterator>
inline iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last)
{
typedef typename iterator_traits<InputIterator>::iterator_category category;
return __distance(first, last, category);
}
当传入vector.begin()和vector.end()函数，通过萃取机iterator_traits得到他的iterator_category类型，然后去调用：
template<typename RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last, input_iterator_tag)
{
return last - first;
}
因为连续空间的容器，所以直接首尾相减，就能得到距离，速度非常快
当传入的是list.begin()和list.end()函数，通过萃取机iterator_traits得到他的iterator_category类型，然后去调用：
template<typename InputIterator>
inline iterator_traits<InputIterator>::difference_type
__distance(InputIterator first, InputIterator last, input_iterator_tag)
{
iterator_traits<InputIterator>::difference_type n = 0;
while(first != last)
{
++first;
++n;
}
return n;
}
因为是非连续空间容器，所以只能通过迭代的方式，一个一个向后偏移得到距离。速度很慢。
由此可以想象，不同的iterator_category对算法的影响是非常大的。在算法中，会做非常多的检查，让算法使用正确的最快的迭代器分类去操作容器，使用STL其实是一件非常幸福的事情（想想c程序员。。。）
2.仿函数
仿函数其实是一个类重载了()运算符，在STL中如下：
template <typename T>
struct plus: public binary_function<T,T,T>
{
T operator () (const T& x, const T& y)
{
return x+y;
}
}
在使用STL的算法时，可以使用函数来指定第三参数，也可以用仿函数指定，例如：
// 使用函数指定
bool myfunc(int i, int j)
{
return i < j;
}
sort(myvec.begin(), myvec.end(), myfunc);
// 使用仿函数指定
template <typename T>
struct less: public binary_function<T, T, bool>
{
bool operator () (const T& x, const T& y) const
{
return x < y;
}
}
sort(myvec.begin(), myvec.end(), less<int>());
less<int>()是一个临时对象，将其传入sort之后，sort会自动调用class less里头的operator ()，就像调用函数一样（仿函数比函数更有弹性），因为仿函数可以被适配器修改。
如果我们自己写了一个仿函数，需要继承STL的两个类：
// 一个操作数继承
unary_functiontemplate <class Arg, class Result>
struct unary_function
{
typedef Arg argument_type;
typedef Result result_type;
};
// 两个操作数继承
binary_functiontemplate <class Arg1, class Arg2, class Result>
struct binary_function
{
typedef Arg1 fist_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
};
STL规定每一个Adaptable Function都要挑选适当的来继承，因为Function Adapter将会提问问题，例如：
template <class Operation>
class binder2nd: public unary_function<typename Operation::fist_argument_type,typename Operation::result_type>
{
protected: Operation op;
// 这里就是function adapter在问问题
typename Operation::second_argument_type value;
public:
// ....
};
typename Operation::second_argument_type value;
这一句就是在问仿函数问题，你的第二个参数类型是什么，如果这一句可以编译通过，那么函数适配器就得到了仿函数的第二个参数类型，仿函数就可以被改造。
一个仿函数想要能被STL中的适配器改造，就需要继承适当的类融入STL。
3. Adapter
STL的算法可以让用户提供第三参数，用于给用户自定义算法处理数据的方式，上面讲述了可以使用仿函数作为第三参数，仿函数可以被适配器改造，下面就来看一下适配器是如何改造仿函数的。
3.1 bind2nd
以泛型算法count_if为例：
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 n = 0;
for(; first != last; ++first)
{
if(pred(*first))
{
++n;
}
} return n;
}
在使用count_if时如下：
count_if(vi.begin(), vi.end(), bind2nd(less<int>(), 40));
bind2nd就是一个适配器，用于将仿函数less的第二参数绑定为40。
bind2nd源码如下：
template <class Operation, class T>
inline binder2nd<Operation> bind2nd(const Operation& op, const T& x)
{
typedef typename Operation::second_argument_type arg2_type;
return binder2nd<Operation>(op, arg2_type(x));
}
在bind2nd中返回的是一个binder2nd类型的临时对象，bind2nd函数其实是一个中间层，因为binder2nd类模板不可以自动推导类型参数，只有模板函数可以，所以使用中间层给类模板指定模板参数Operation。
class binder2nd源码如下：
template <class Operation>
class binder2nd
: public unary_function<typename Operation::first_argument_type,
typename Operation::result_type>
{
protected:
Operation op;
typename Operation::second_argument_type value;
public:
binder2nd(const Operation& x, const typename Operation::second_argument_type& y)
:op(x), value(y)
{ }
typename Operation::result_type
operator () (const typename Operation::first_argument_type& x) const
{
return op(x, value);
}
}
当在count_if中传入第三参数bind2nd(less<int>(), 40)后，先会调用bind2nd函数，函数确定Operation 和 T的类型函数变成如下：
inline binder2nd<less<int>> bind2nd(const less<int>& op, const int& x)
{
typedef less<int>::second_argument_type arg2_type;
return binder2nd<less<int>>(op, arg2_type(x));
}
然后先让class binder2nd确定模板参数
class binder2nd
: public unary_function<less<int>::fist_argument_type, less<int>::result_type>
{
protected:
less<int> op;
less<int>::second_argument_type value;
public:
binder2nd(const less<int>& x, const less<int>::second_argument_type& y)
:op(x), value(y)
{ }
less<int>::result_type operator () (const less<int>::first_argument_type& x) const
{
return op(x, value);
}
}
再在函数内部调用class binder2nd的构造函数，实例化一个binder2nd类型的临时对象，将less<int>()和40分别记录在op和value里头。
最后count_if的第三个参数就得到一个binder2nd类型的临时对象，其中包涵了less<int>和40，count_if函数变成如下：
// 加上vi是容器list的实例化
ptrdiff_t count_if(list<int>::iterator first, list<int>::iterator last, binder2nd pred)
{
ptrdiff_t n = 0;
for(; first != last; ++first)
{
if(pred(*first))
{
++n;
}
}
return n;
}
在count_if中调用pred这个仿函数时（pred就是binder2nd类型的临时对象的别名），会触发class binder2nd中的 operator()，在operator()中
op(x, 40)；
40就被绑定到less<int>()的第二参数上
这就是仿函数适配器的工作原理（真的非常的巧妙）。
3.2 inserter
当我们想用copy函数进行容器间的拷贝动作时，一种是提前将空间预留
int myints[] = {10, 20, 30, 40, 50, 60, 70};
vector<int> myvec(7);
copy(myints, myints+7, myvec.begin());
提前预留空间是因为copy函数只是单纯的移动迭代器，向迭代器所指的地方插入数据，源码如下：
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
{
while(first != last)
{
result = *first;
++result;
++first;
}
return result;
}
假设我们的容器其中本来就有数据，没有预留空间，那么直接使用copy函数会造成一颗定时炸弹（越界访问），在这种时候就需要使用适配器来改造拷贝动作。
将copy的第三参数改写成迭代适配器：
copy(myints, myints+7, inserter(myvec, iter)); //iter为迭代器，指向容器内任意地方
inserter源码如下：
template <class Container, class iterator>
inline insert_iterator<Container>
insert(Container& x, Iterator i)
{
typedef typename Container::iterator iter;
return insert_iterator<Container>(x, iter(i));
}
inserter与bind2nd一样，也是一个辅助函数，帮助class insert_iterator确定模板参数。
class insert_iterator源码如下：
template <class Container>
class insert_iterator
{
protected:
Container* container;
typename Container::iterator iter;
public:
typedef output_iterator_tag iterator_category;
insert_iterator(Container& x, typename Container::iterator i)
:container(&x), iter(i)
{ }
insert_iterator<Container>&
operator = (const typename Container::value_type& value)
{
iter = container->insert(iter, value);
return *this;
}
typename Container::iterator& operator ++ ()
{
return ++iter;
}
};
inserter函数返回一个insert_iterator类型的临时对象，在这个临时对象中，容器myvec被记录到了容器指针container中，myvec的迭代器iter被记录到了临时对象中的的iter里，当copy函数在执行：
result = *first;
++result;
以上两个操作的时候，会触发class insert_iterator里的两个操作符重载函数。
这样copy函数从原来一个傻傻的，只会一个一个拷贝的底层函数，摇身一变成了一个智能的插入拷贝函数（C++技术相当奇妙，这就是操作符重载的好处）。
4. iostream iterator
标准库定义有提供给输入输出使用的 iostream iterator，称为istream_iterator 和 ostream_iterator，他们分别支持单个元素的读取和写入。
使用这两个迭代器需要包涵#include <iterator>
4.1 ostream_iterator
ostream_iterator的使用方法如下：
// 将out_it绑定到cout输出设备
ostream_iterator<int> out_it(cout);
// 将out_it绑定到cout输出设备，并且在输出元素后加上一个字符串
ostream_iterator<int> out_it(cout, ",");
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
int main()
{
vector<int> vec;
for(int i = 0; i < 10; ++i)
{
vec.push_back(i);
}
ostream_iterator<int> outit(cout, ",");
copy(vec.begin(), vec.end(), outit);
return 0;
}
4.2 istream_iterator
使用方法如下：
// 定义一个指向输入流结束位置的迭代器
istream_iterator<double> eos;
// 定义一个指向标准输入的迭代器
istream_iterator<double> iit(cin)
当 iit = eos时，说明流中的数据已经全部读取结束，操作iit让其加一，可以让迭代器指向下一个流中的数据
#include <iostream>
#include <iterator>
using namespace std;
int main()
{
double value1, value2;
cout << "please insert two value: ";
istream_iterator<double> eos;
istream_iterator<double> iit(cin);
if(iit != eos)
{
value1 = *iit;
}
++iit;
if(iit != eos)
{
value2 = *iit;
}
cout << value1 << ' ' << value2 << endl;
return 0;
}
这里值得注意的是，当我们把
cout << "please insert two value: ";
写到
istream_iterator<double> iit(cin);
后面
在执行程序的时候，我们发现，当输入第一个数字之后，cout这句输出才会被打印出来，造成这样的原因是，当定义了iit之后，其构造函数已经对iit加一，读取已经开始，所以cout的输出被放在后面。
注：
ifstream infile("./test/01.cpp");
istream_iterator<string> eos;
istream_iterator<string> iit(infile);
ofstream outfile("./2.cpp");
ostream_iterator<string> out_it(outfile, " ")
这周先参考一篇知乎专栏
网友评论