面试之快速学习STL-迭代适配器

先放一张大图

参考：http://c.biancheng.net/view/7255.html

1. 反向迭代器

例子：

    std::list<int> values{1,2,3,4,5};auto start_it = values.rbegin();const auto end_it = values.rend();//start_it end_it std::reverse_iterator<std::list<int>>::iteratorwhile (start_it != end_it) {std::cout << *start_it << std::endl;++start_it;}/*54321*/

1. 想使用反向迭代器实现逆序遍历容器，则该容器的迭代器类型必须是双向迭代器或者随机访问迭代器。
   
2. 常见操作
   

    std::vector<int> values{1,2,3,4,5};auto r_start_it = values.rbegin();const auto end_it = values.rend();//r_start_it end_it std::reverse_iterator<std::list<int>>::iteratorwhile (r_start_it != end_it) {std::cout << *r_start_it << std::endl;++r_start_it;}/*54321*/r_start_it = values.rbegin();std::cout << "r_start_it + 3 = " << *(r_start_it + 3)<< std::endl;std::cout << "r_start_it[3] = " << r_start_it[3] << std::endl;

3. 注意这里不能用std::list，因为它是双向迭代器， +3的操作需要随机访问迭代器。故联想到std::list排序只能使用list提供的 sort 接口，而不能使用algorithm 提供的 sort 接口，因为链表的物理地址不连续，迭代器为双向迭代器，不支持 + - 操作，而算法库中的 sort 接口需要支撑 + - 的随机迭代器；

2. 插入迭代器适配器

感觉没啥好讲的，看看代码：

#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
int main() {//创建一个 vector 容器std::vector<int> foo;//创建一个可向 foo 容器尾部添加新元素的迭代器std::back_insert_iterator< std::vector<int> > back_it(foo);//将 5 插入到 foo 的末尾back_it = 5;//将 4 插入到当前 foo 的末尾back_it = 4;//将 3 插入到当前 foo 的末尾back_it = 3;//将 6 插入到当前 foo 的末尾back_it = 6;//输出 foo 容器中的元素for (std::vector<int>::iterator it = foo.begin(); it != foo.end(); ++it)std::cout << *it << ' ';return 0;/*5 4 3 6*/
}

1. 每次插入新元素时，该元素都会插入到当前 foo 容器的末尾。换句话说，程序中 11-17 行的每个赋值语句，都可以分解为以下这 2 行代码：

//pos表示指向容器尾部的迭代器，value 表示要插入的元素
pos = foo.insert(pos,value);
++pos;

3. istream_iterator和ostream_iterator

原理源码：原理

1. 自己理解：istream_iterator是重载了++操作符然后调用的是read(); ostream_iterator重载 = 操作符，做输出操作。

#include <iostream>
#include <thread>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstring>
#include <deque>
#include <iterator>
using namespace std;int main()
{deque<int> id;istream_iterator<int> intie(cin),eos;                     //开始触发一次输入   copy(intie, eos, inserter(id, id.begin()));               //迭代器类型为InputIterator，所以这里调用copy的时候采用*result = *first;版本，会使用重载类型 ,那么就会转换为插入操作      //其中++first会继续调用下一个，然后重载为新的输入ostream_iterator<int> outie(cout, " ");                  //deque的迭代器类型为random_access_iterator,也会是 *result = *first;调用赋值操作  result++操作，返回本身，不影响后面的输出操作copy(id.begin(), id.end(), outie);                       //将=操作，转换为输出操作cout << endl;system("pause");
}

3. 移动迭代器

std::vector<std::string> v1{ "haha", "xixi" };//调用移动构造函数std::vector<std::string> v2(make_move_iterator(v1.begin()), make_move_iterator(v1.end()));std::cout << "v1 : " << std::endl;for (auto record : v1)std::cout << record << std::endl;std::cout << "v2 : " << std::endl;for (auto record : v2)std::cout << record << std::endl;/*v1 :v2 : hahaxixi*/

没啥好说的，就是每个值调用移动构造函数make_move_iterator

4. advance()函数用法详解

template <class InputIterator, class Distance>
void advance (InputIterator& it, Distance n);

1. 根据 it 类型是否为随机访问迭代器，advance() 函数底层采用了不同的实现机制：
   当 it 为随机访问迭代器时，由于该类型迭代器支持 p+n 或者 p-n（其中 p 就是一个随机访问迭代器）运算，advance() 函数底层采用的就是 it+n 操作实现的；
   当 it 为其他类型迭代器时，它们仅支持进行 ++ 或者 – 运算，这种情况下，advance() 函数底层是通过重复执行 n 个 ++ 或者 – 操作实现的。

#include <iostream>     // std::cout
#include <iterator>     // std::advance
#include <forward_list>
using namespace std;
int main() {//创建一个 forward_list 容器forward_list<int> mylist{1,2,3,4};//it为前向迭代器，其指向 mylist 容器中第一个元素forward_list<int>::iterator it = mylist.begin();//借助 advance() 函数将 it 迭代器前进 2 个位置advance(it, 2);cout << "*it = " << *it;return 0;
}

注意： 此程序中，由于 it 为前向迭代器，其只能进行 ++ 操作，即只能前进（右移），所以 advance() 函数的第 2 个参数只能为正数。

5. distance()函数用法详解

template
typename iterator_traits::difference_type distance (InputIterator first, InputIterator last);

1. first 和 last 的迭代器类型，直接决定了 distance() 函数底层的实现机制：
   当 first 和 last 为随机访问迭代器时，distance() 底层直接采用 last - first 求得 [first, last) 范围内包含元素的个数，其时间复杂度为O(1)常数阶；
   当 first 和 last 为非随机访问迭代器时，**distance() 底层通过不断执行 ++first（或者 first++）直到 first==last，**由此来获取 [first, last) 范围内包含元素的个数，其时间复杂度为O(n)线性阶。

#include <iostream>     // std::cout
#include <iterator>     // std::distance
#include <list>         // std::list
using namespace std;int main() {//创建一个空 list 容器list<int> mylist;//向空 list 容器中添加元素 0~9for (int i = 0; i < 10; i++) {mylist.push_back(i);}//指定 2 个双向迭代器，用于执行某个区间list<int>::iterator first = mylist.begin();//指向元素 0list<int>::iterator last = mylist.end();//指向元素 9 之后的位置//获取 [first,last) 范围内包含元素的个数cout << "distance() = " << distance(first, last);return 0;
}