简介

算法是STL的重要内容，前面部分讲完了容器，在容器和算法之间存在一个纽带那便是迭代器。下图是侯老师课件中展示的算法、容器、迭代器以及仿函数之间的关系。
Algorithm
可以看到算法和容器本身是分开的，但是算法通过迭代器实现对容器中的元素进行操作。仿函数一般用在算法的实现中，举个例子如下：

template<typename Iterator, typename Cmp>
Algorithm(Iterator itr1, Iterator itr2, Cmp comp)
{
    ...
}

其中的函数comp就是在算法中需要定义的比较函数，可以自己定义也可以直接使用模板中的函数。

iterator分类

迭代器的内容在前面的文章已经有些介绍。迭代器分为五类，分别是随机迭代器、双向迭代器、前向迭代器、输出和输入迭代器。对容器的内容了解完后，我们对各个容器的迭代器类型就能很好掌握。array，vector，deque：随机访问、list：双向迭代器、forward_list：前向迭代器、map，set：双向迭代器，unordered_set，unordered_map：前向迭代器。迭代器之间存在一种概念与强化的关系，而不是C++中的继承关系。随机迭代器==>双向迭代器==>前向迭代器==>输入迭代器，箭头代表左边的迭代器满足右边迭代器需要的条件，是其扩张集。正是由于这种关系使得调用时存在着便利，例如对于要求输入迭代器类型的参数，其余四个都可以。

iterator_category对算法的影响

下面这段代码是用来求两个迭代器之间的距离。我们知道对于连续存储的迭代器只需要尾首相减就可以得到两者的距离，但是对于非连续存储的，就需要移动迭代器直到首尾相等，从而得到距离，显然前者要比后者快很多。前面已经说过，对于Input_iterator_tag是可以接受后面的四种迭代器作为参数的，因此除了random_access_iterator使用第二种方式计算距离，其余都是通过第一种方法计算距离。

// 第一种
template <class 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;
}
// 第二种
template <class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag)
{
    return last - first;
}
template <class 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());
}

iterator_category和type traits对算法的影响

侯捷老师对于这个知识点举了很多例子，下面就说说其中的一个例子，针对迭代器的拷贝函数。对于拷贝可以使用memmove()函数和通过for循环来完成元素的逐个拷贝，显然前者速度更快，因为后者可能需要调用拷贝复制函数。后面还有一个条件判断has trivial op=()和has non-trivial op=()是对拷贝复制重要性的判断。例如侯老师上课中举的例子，对于一个我们自己创建的复数类，它的拷贝复制函数就很简单，而对于我们自己定义的其他类型，拷贝复制函数比较重要，这时就要选用不同的拷贝方式了。至于trivial和non-trivial的判断就要根据Type Traits来选择。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。