1.C++标准库的算法，是什么东西？
从语言的层面讲，STL的算法都长下面两个样子：
template
Algorithm(Iterator itr1, Iterator itr2)
{
//...
}
template
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
inline iterator_traits::difference_type
distance(InputIterator first, InputIterator last)
{
typedef typename iterator_traits::iterator_category category;
return __distance(first, last, category);
}
当传入vector.begin()和vector.end()函数，通过萃取机iterator_traits得到他的iterator_category类型，然后去调用：
template
inline iterator_traits::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last, input_iterator_tag)
{
return last - first;
}
因为连续空间的容器，所以直接首尾相减，就能得到距离，速度非常快
当传入的是list.begin()和list.end()函数，通过萃取机iterator_traits得到他的iterator_category类型，然后去调用：
template
inline iterator_traits::difference_type
__distance(InputIterator first, InputIterator last, input_iterator_tag)
{
iterator_traits::difference_type n = 0;
while(first != last)
{
++first;
++n;
}
return n;
}
因为是非连续空间容器，所以只能通过迭代的方式，一个一个向后偏移得到距离。 速度很慢。
由此可以想象，不同的iterator_category对算法的影响是非常大的。 在算法中，会做非常多的检查，让算法使用正确的最快的迭代器分类去操作容器，使用STL其实是一件非常幸福的事情（想想c程序员。。。 ）
2.仿函数
仿函数其实是一个类重载了()运算符，在STL中如下：
template
struct plus: public binary_function
{
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
struct less: public binary_function
{
bool operator () (const T& x, const T& y) const
{
return x < y;
}
}
sort(myvec.begin(), myvec.end(), less());
less()是一个临时对象，将其传入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
struct binary_ function
{
typedef Arg1 fist_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
};
STL规定每一个Adaptable Function都要挑选适当的来继承，因为Function Adapter将会提问问题，例如：
template
class binder2nd: public unary_function
{
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为例：
模板 < 类 InputIterator, 类谓词 > 类型 iterator_traits < InputIterator >::d ifference_type count_if (InputIterator 第一, InputIterator 最后, 谓词 pred) {类型
iterator_traits < InputIterator >::d ifference_type n = 0;for (; 首先是最后一个; + + 第一个) {if (pred (* 第一)) {+ n;}
} 返回 n;
} 在使用count_if时如下:
count_if (vi. 开始 (), vi. 结束 (), bind2nd (较少 < int > (), 40));bind2nd就是一个适配器,用于将仿函数less的第二参数绑定为40.
bind2nd源码如下:
模板 < 类操作, 类 T > 内联 binder2nd < 操作 > bind2nd (const 操作 & op, 常量 T & x) {typedef 类型操作:: second_argument_type arg2_type; 返回
binder2nd < 操作 > (op, arg2_type (x));}
在bind2nd中返回的是一个binder2nd类型的临时对象，bind2nd函数其实是一个中间层，因为binder2nd类模板不可以自动推导类型参数，只有模板函数可以，所以使用中间层给类模板指定模板参数Operation。
class binder2nd源码如下：
模板 < 类操作 > 类 binder2nd: 公共 unary_function < 类型操作:: first_argument_type, 类型操作:: result_type > {保护:
操作 op;类型操作:: second_argument_type 值;
public: binder2nd (const 操作 & x, 常量类型操作:: second_argument_type & y): op (x), 值 (y) {} 类型操作:: result_type 运算符 () (const
类型操作:: first_argument_type & x) 常量 {返回 op (x, 值);}
} 当在count_if中传入第三参数bind2nd (较少 < int > (), 40) 后, 先会调用bind2nd函数, 函数确定Operation 和 T的类型函数变成如下:
内嵌 binder2nd < 更少 < int > > bind2nd (恒少 < 国际 > & op, const int & x) {typedef 更少的 < int >:: second_argument_type arg2_type; 返回 binder2nd < 少 < 国际 > > (op, arg2 _
类型 (x));} 然后先让class binder2nd确定模板参数
类 binder2nd: 公共 unary_function < 较少 < int >:: fist_argument_type, 更少 < 国际 >:: result_type > {保护: 更少的 < 国际 > op; 更少的 < 国际 >:: second_argument_
类型值;公共: binder2nd (常量较少 < int > & x, 常量较少 < int >:: second_argument_type & y): op (x)、值 (y) {} 更少 < int >:: result_type 运算符 () (不小于 < int >:
: first_argument_type & x) 常量 {返回 op (x, 值);}
}
再在函数内部调用class binder2nd的构造函数，实例化一个binder2nd类型的临时对象，将less()和40分别记录在op和value里头。
最后count_if的第三个参数就得到一个binder2nd类型的临时对象，其中包涵了less和40，count_if函数变成如下：
加上vi是容器list的实例化 ptrdiff_t count_if (列表 < int >:: 迭代器第一, 列表 < int >:: 迭代最后, binder2nd pred) {ptrdiff_t n = 0; for (; 首先! = 尾页; + + 第一个) {if (pred (*
第一)) {+ + n;}
} 返回 n;
}
在count_if中调用pred这个仿函数时（pred就是binder2nd类型的临时对象的别名），会触发class binder2nd中的 operator()，在operator()中
op(x, 40)；
40就被绑定到less()的第二参数上
这就是仿函数适配器的工作原理（真的非常的巧妙）。
3.2 inserter
当我们想用copy函数进行容器间的拷贝动作时，一种是提前将空间预留
int myints[] = {10, 20, 30, 40, 50, 60, 70};
vector myvec(7);
copy(myints, myints+7, myvec.begin());
提前预留空间是因为copy函数只是单纯的移动迭代器，向迭代器所指的地方插入数据，源码如下：
模板 < 类 InputIterator, 类 OutputIterator > OutputIterator 复制 (InputIterator 首先, InputIterator 最后, OutputIterator 结果) {而 (第一个! 最后一个) {结果 = * 第一;
++ 结果;首先为 ++;
} 返回结果;
}
假设我们的容器其中本来就有数据，没有预留空间，那么直接使用copy函数会造成一颗定时炸弹（越界访问），在这种时候就需要使用适配器来改造拷贝动作。
将copy的第三参数改写成迭代适配器：
copy(myints, myints+7, inserter(myvec, iter)); //iter为迭代器，指向容器内任意地方
inserter源码如下：
模板 < 类容器, 类迭代器 > 内联 insert_iterator < 容器 > 插入 (容器 & x, 迭代器 i) {类型容器: 迭代器 iter; 返回 insert_
迭代器 < 容器 > (x, iter (i));} inserter与bind2nd一样,也是一个辅助函数,帮助class insert_iterator确定模板参数.
类 insert_iterator源码如下:
模板 < 类容器 > 类 insert_iterator {保护: 容器 * 容器; 类型容器:: 迭代器 iter; public: typedef output_iterator_tag
iterator_category;
insert_iterator(Container& x, typename Container::iterator i)
:container(&x), iter(i)
{ }
insert_iterator&
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
4.1 ostream_iterator
ostream_iterator的使用方法如下：
将out_it绑定到cout输出设备 ostream_iterator < int > out_it (cout);
//将out_it绑定到cout输出设备, 并且在输出元素后加上一个字符串 ostream_iterator < int > out_it (cout, ",");
包括 < iostream >
包括 < 向量 >
包括 < 算法 >
包括 < 迭代器 >
使用命名空间性病;
int main () {向量 < int > vec; (int i = 0; 我 < 10; + + i) {vec. push_back (i);}
ostream_iterator < int > outit (cout, ",");
复制 (vec, 开始 (), vec. end (), outit);
返回 0;
}
4.2 istream_iterator
使用方法如下：
// 定义一个指向输入流结束位置的迭代器
istream_iterator eos;
// 定义一个指向标准输入的迭代器
istream_iterator iit(cin)
当 iit = eos时，说明流中的数据已经全部读取结束，操作iit让其加一，可以让迭代器指向下一个流中的数据
包括 < iostream >
包括 < 迭代器 >
using namespace std;
int main()
{
double value1, value2;
cout << "please insert two value: ";
istream_iterator eos;
istream_iterator 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 iit(cin);
后面
在执行程序的时候，我们发现，当输入第一个数字之后，cout这句输出才会被打印出来，造成这样的原因是，当定义了iit之后，其构造函数已经对iit加一，读取已经开始，所以cout的输出被放在后面。
注：
ifstream infile("./test/01.cpp");
istream_iterator eos;
istream_iterator iit(infile);
ofstream outfile("./2.cpp");
ostream_iterator out_it(outfile, " ")
网友评论