标准库算法
- 从语言层面来看
- 容器Container是class template
- 算法Alogorithm是function template
- 迭代器Iterator是class template
- 仿函数Functor是class template
- 适配器Adapter是class template
- 分配器Allocator是class template
- 算法看不到迭代器，它所需要的一切信息都必需从Iterstor取得，而迭代器必需能够回答算法的所有问题，才能搭配算法的所有操作
template <typename Iterator>
Algorithm(Iterator itr1, Iterator itr2)
{
...
}
template<typename Iterator, typename Cmp>
Algorithm(Iterator itr1, Iterator itr2, Cmp comp)
{
...
}
迭代器的分类
- array、vector、deque都是连续空间，迭代器允许跳跃前进，都是random_access_iterator_tag
- list的迭代器可以双向移动，是bidirectional_iterator_tag
- forward_list是单向链表，是farward_iterator_tag
- 红黑树为底层实现的容器，迭代器都可以双向移动，是bidirectional_iterator_tag
- 哈希表为底层实现的容器，根据bucket中的链表是单向链表还是双向链表，判断迭代器是bidirectional_iterator_tag还是farward_iterator_tag
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{ };
- 标准库的五种迭代器，为什么采取继承关系实现
- 判断迭代器类型时可以使用函数重载，只要传入的是不同类型的参数，就会自动调用不同的函数
- 采取继承关系实现，对于该类型的迭代器，如果没有它特定版本的算法，它会调用符合它父类版本的算法（如后例）
- 如何打印迭代器的类型
- 方法一：自定义版
-----------------------五种类型的函数重载---------------------------
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 _diaplay_category(output_iterator_tag)
{ cout<< "output_iterator" << endl;}
voif _display_category(input_iterator_tag)
{ cout<< "input_iterator" << endl;}
template<typename T>
void display_category(I itr)
{
typename iterator_traits<I>::iterator_category cagy;
_display_category(cagy);
}
-----------------------测试函数-------------------------------
display_category(array<int, 10>::iterator());
display_category(set<int>::iterator());
...
display_category(istream_iterator<int>());
diaplay_category(ostream_iterator<int>(cout, ""));
#include<typeinfo>
template<typename I>
void display_category(I itr)
{
typename iterator_traits<I>::iterator_category cagy;
_display_category(cagy);
cout<<"typeid(ite).name()=" << typeid(itr).name()<<endl;
}
istream_iterator
- 不同版本的实现不同，但是不能影响接口。即虽然模板参数的数量不一样，但是一些模板参数有默认值
- 一个继承关系，父类只是一些typedef，没有数据也没有函数，这样子类继承父类，等同于子类拥有了这些typedef（相当于少打几个字hhh）
-----------------------G4.9----------------------------------
template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t, typename _Pointer = _Tp*, typename _Reference = _Tp&>
struct iterator
{
typedef _Category iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Pointer pointer;
typedef _Reference reference;
};
template<typename _Tp, typename _CharT = char, typename _Traits = char_traits<_CharT>,typename _Dist = ptrdiff_t>
class istream_iterator : public iterator<input_iterator_tag, _Tp, _Dist, const _Tp*, const _Tp&>
{
...
}
--------------------------G2.9----------------------------------
template<class T, class Distance = ptrdiff_t>
class istream_iterator{
public:
typedef input_iterator_tag iterator_category;
....
}
---------------------------G3.3-------------------------------------
template<class _Tp, class _CharT = char, class _Traits = char_traits<_ChatT>, class _Dist = ptrdiff_t>
class istream_iterator{
public:
typedef input_iterator_tag iterator_category;
...
}
迭代器的类型对算法效率的影响
- 示例一：distance
- distance接受两个参数，求二者之间的距离
- 这个函数会调用一个辅助函数，它有两个版本。一个是两个迭代器直接相减，仅适合于random_access_iterator，另一个是由first逐个数到last，适合于其余的迭代器
- 这个函数的返回类型是difference_type，是迭代器的五种typedef中专门用来表示距离
- 示例二：advance
- advance传入两个参数，表示迭代器从当前位置前进n步
- 这个函数调用一个辅助函数，它有三个版本。random_access_iterator可以直接到达新的位置。bidirectional_iterator_tag可以向前走也可以向后走，input_iterator_tag只能向前走
- 辅助函数有三个参数，分别是迭代器，前进步数n，迭代器类型的临时对象
- 示例三：copy
- copy传入三个参数，前两个是表示待拷贝序列的区间，第三个是目的地址
- copy先检查传进来的迭代器是哪种类型的，此处分了三种情况，两个特化版本直接调用memmove()，这是一种十分接近系统调用的函数。泛化版本又分了三种情况，具体如下图
- trivial op=()是type traits，把类型放进去，问它一些问题，此处是问拷贝赋值是否重要，默认版本是不重要的，如复数，它没有指针，不需要自己写拷贝赋值函数。
- 算法不会对迭代器类型强加限制，但是它会暗示算法需要的迭代器类型
|