侯捷STL学习（十一）

2017-07-24 | 阅读：次

第三讲标准库内核分析-算法

标准库算法形式

iterator分类

不同容器iterator类型不同
测试iterator类型 ```C++ #include // std::cout #include // std::iterator_traits #include // typeid namespace jj33 { void _display_category(random_access_iterator_tag) { cout << "random_access_iterator" << endl; } void _display_category(bidirectional_iterator_tag) { cout << "bidirectional_iterator" << endl; } void _display_category(forward_iterator_tag) { cout << "forward_iterator" << endl; } void _display_category(output_iterator_tag) { cout << "output_iterator" << endl; } void _display_category(input_iterator_tag) { cout << "input_iterator" << endl; }

template void display_category(I itr) { typename iterator_traits::iterator_category cagy; _display_category(cagy);

cout « “typeid(itr).name()= “ « typeid(itr).name() « endl « endl;
//The output depends on library implementation. //The particular representation pointed by the
//returned valueis implementation-defined, //and may or may not be different for different types.
}

void test_iterator_category() { cout « “\ntest_iterator_category()………. \n”;

display_category(array<int,10>::iterator()); display_category(vector::iterator()); display_category(list::iterator()); display_category(forward_list::iterator()); display_category(deque::iterator()); display_category(set::iterator()); display_category(map<int,int>::iterator()); display_category(multiset::iterator()); display_category(multimap<int,int>::iterator()); display_category(unordered_set::iterator()); display_category(unordered_map<int,int>::iterator()); display_category(unordered_multiset::iterator()); display_category(unordered_multimap<int,int>::iterator()); display_category(istream_iterator()); display_category(ostream_iterator(cout,""));

} }

```

istream_iterator,ostream_iterator的iterator_category

iterator_category对算法效率的影响

distance函数实现
对于连续空间直接相减，不连续空间需要重新计算
type traits对算法的影响
traits为萃取机，将iterator和type放进去，然后回答一些属性问题？
输入迭代器可读，输出迭代器可写。
算法模板参数输入名称，有时候暗示该算法输入的迭代器类型

算法源码剖析例子

sort算法，区分C函数和STL库函数
本身遍历容器iterator就是有序的
算法accumulate
算法for_each
算法replace,replace_if,replace_copy
算法count,count_if
全局函数和成员函数的区别
算法find,find_if
reverse iterator:rbegin(),rend()
算法binary_search
有序查找，红黑树是怎么查找的？

仿函数functions

仿函数只为算法服务
GNU C++独有的，非标准；identity在set容器中取data
没有继承就没有融入STL体系
仿函数可适配的条件：继承
STL规定每个adaptable function都挑选适当着继承
仿函数是个函数对象，用小括号创建临时对象，实现的是函数功能，但是封装为class;方便adater去修饰调整

适配器Adapter

改造器
A用B的方法，两种方式：继承B或者内涵B
adapter内涵仿函数，迭代器，容器实现
容器适配器
stack,queue严格的是adapter;改造就是将一些函数重新封装，换名称
函数适配器：binder2nd
要问函数内部的参数类型及其返回值类型，就需要函数本身继承的calss回答，Operation::second_agrument 就由less内部继承的父类回答 ![](http://i.imgur.com/XmuUMsY.png)
已经更新用bind替换binder2nd；
函数适配器not1