小言_互联网的博客

C++(STL源码):39---配接器之(迭代器配接器(iterator adapters))

234人阅读  评论(0)

一、配接器介绍

  • STL提供的各种配接器中:
    • 改变仿函数接口者:称为function adapter
    • 改变容器接口者:称为container adapter
    • 改变迭代器接口者:称为iterator adapter

二、迭代器配接器概述

  • STL提供了很多用于迭代器身上的配接器,包括insert iterator、reverse iterator、iostream iterator
  • 应用层使用应该包含<iterator>,SGI STL将它们实现于<stl_iterator.h>中
  • 不同于后面介绍的仿函数配接器总以仿函数为参数。这里介绍的迭代器配接器很少以迭代器作为直接参数。所谓迭代器的修饰,只是一种概念上的改变

三、Insert Iterators

  • 所谓insert iterators,可以将一般迭代器的赋值操作转换为插入操作
  • 大致介绍:
    • 每一个insert iterators内部都维护一个容器(必须由用户指定)
    • 容器当然有自己的迭代器,于是,当客户端对insert iterators做赋值操作时,就在insert iterators中被转换为对该容器的迭代器做插入操作
      • 也就是说,在insert iterators的operator=操作符中调用底层容器的push_front()、push_back()、或insert()操作函数
    • 至于其他的迭代器行为例如:operator++、operator*、operator--、operator->等都被关闭了
    • 也就是说insert itertators的前进、后退、取值、成员取用等操作都是没有意义的
  • 这样的迭代器类包括:
    • 专用于尾端插入操作的back_insert_iterator
    • 专用于头端插入操作的front_insert_iterator
    • 记忆任意位置插入操作的insert_iterator
  • 由于上面三个iterator adapters的使用接口不是很直观,于是STL提供了下图所示的三个函数,提升使用时的便利性:

back_insert_iterator类、back_inserter()函数


   
  1. //这是一个迭代器配接器,用来将某个迭代器的赋值操作改为插入操作——改为从容器的尾端插入
  2. template< class Container>
  3. class back_insert_iterator
  4. {
  5. protected:
  6. Container* container; //底层容器
  7. public:
  8. typedef out_iterator_tag iterator_category; //注意类型
  9. typedef void value_type;
  10. typedef void difference_type;
  11. typedef void pointer;
  12. typedef void reference;
  13. //构造函数使back_insert_iterator与容器绑定起来
  14. explicit back_insert_iterator(Container& x) :container(&x) {}
  15. back_insert_iterator<Container>& operator=( const typename Container::value_type& value)
  16. {
  17. container->push_back(value); //这里是关键,直接调用push_back()
  18. return * this;
  19. }
  20. //下面的操作符对back_insert_iterator不起作用(关闭功能)
  21. //因此都返回自己
  22. back_insert_iterator<Container>& operator*() { return * this; }
  23. back_insert_iterator<Container>& operator++() { return * this; }
  24. back_insert_iterator<Container>& operator++( int) { return * this; }
  25. };

   
  1. //这是一个辅助函数,方便我们使用back_insert_iterator
  2. template< class Container>
  3. inline back_insert_iterator<Container> back_inserter(Container& x)
  4. {
  5. return back_insert_iterator<Container>(x);
  6. }

演示案例


   
  1. #include <iostream>
  2. #include <iterator>
  3. #include <deque>
  4. #include <algorithm>
  5. using namespace std;
  6. int main()
  7. {
  8. ostream_iterator< int> outiter( cout, " ");
  9. int ia[] = { 0, 1, 2, 3, 4, 5 };
  10. deque< int> id(ia, ia + 6);
  11. //将3插入id的尾部
  12. copy(ia+ 3, ia + 4, back_inserter(id));
  13. //输出id的内容
  14. copy(id.begin(), id.end(), outiter);
  15. cout << endl;
  16. return 0;
  17. }

 

front_insert_iterator类、front_inserter()函数


   
  1. //这是一个迭代器配接器,用来将某个迭代器的赋值操作改为插入操作——改为从容器的头部插入
  2. //注意,该容器不支持vector,因为vector没有提供push_front()函数
  3. template< class Container>
  4. class front_insert_iterator
  5. {
  6. protected:
  7. Container* container; //底层容器
  8. public:
  9. typedef out_iterator_tag iterator_category; //注意类型
  10. typedef void value_type;
  11. typedef void difference_type;
  12. typedef void pointer;
  13. typedef void reference;
  14. //构造函数使back_insert_iterator与容器绑定起来
  15. explicit front_insert_iterator(Container& x) :container(&x) {}
  16. front_insert_iterator<Container>& operator=( const typename Container::value_type& value)
  17. {
  18. container->push_front(value); //这里是关键,直接调用push_front()
  19. return * this;
  20. }
  21. //下面的操作符对front_insert_iterator不起作用(关闭功能)
  22. //因此都返回自己
  23. front_insert_iterator<Container>& operator*() { return * this; }
  24. front_insert_iterator<Container>& operator++() { return * this; }
  25. front_insert_iterator<Container>& operator++( int) { return * this; }
  26. };

   
  1. //这是一个辅助函数,方便我们使用front_insert_iterator
  2. template< class Container>
  3. inline front_insert_iterator<Container> front_inserter(Container& x)
  4. {
  5. return front_insert_iterator<Container>(x);
  6. }

演示案例


   
  1. #include <iostream>
  2. #include <iterator>
  3. #include <deque>
  4. #include <algorithm>
  5. using namespace std;
  6. int main()
  7. {
  8. ostream_iterator< int> outiter( cout, " ");
  9. int ia[] = { 0, 1, 2, 3, 4, 5 };
  10. deque< int> id(ia, ia + 6);
  11. //将1插入头部
  12. copy(ia + 1, ia + 2, front_inserter(id));
  13. //输出容器中的内容
  14. copy(id.begin(), id.end(), outiter);
  15. cout << endl;
  16. return 0;
  17. }

insert_iterator类、inserter()函数


   
  1. //这是一个迭代器配接器,用来将某个迭代器的赋值操作改为插入操作——在任意位置上插入
  2. //并将迭代器右移一个位置——如此便可以方便地连续插入
  3. //表面上是赋值操作,实际上是插入操作
  4. template< class Container>
  5. class insert_iterator
  6. {
  7. protected:
  8. Container* container; //底层容器
  9. typename Container::iterator iter;
  10. public:
  11. typedef out_iterator_tag iterator_category; //注意类型
  12. typedef void value_type;
  13. typedef void difference_type;
  14. typedef void pointer;
  15. typedef void reference;
  16. insert_iterator(Container& x, typename Container::iterator i)
  17. :container(&x), iter(i) {}
  18. insert_iterator<Container>& operator=( const typename Container::value_type& value)
  19. {
  20. iter = container->inserter(iter, value); //关键,直接调用insert()
  21. ++iter; //使insert iterator永远随其目标而移动
  22. return * this;
  23. }
  24. //下面的操作符对insert_iterator不起作用(关闭功能)
  25. //因此都返回自己
  26. insert_iterator<Container>& operator*() { return * this; }
  27. insert_iterator<Container>& operator++() { return * this; }
  28. insert_iterator<Container>& operator++( int) { return * this; }
  29. };

   
  1. //这是一个辅助函数,方便我们使用insert_iterator
  2. template< class Container>
  3. inline insert_iterator<Container> inserter(Container& x, Iterator i)
  4. {
  5. return insert_iterator<Container>(x, iter(i));
  6. }

演示案例


   
  1. #include <iostream>
  2. #include <iterator>
  3. #include <deque>
  4. #include <algorithm>
  5. using namespace std;
  6. int main()
  7. {
  8. ostream_iterator< int> outiter( cout, " ");
  9. int ia[] = { 0, 1, 2, 3, 4, 5 };
  10. deque< int> id(ia, ia + 6);
  11. //找出元素5所在的迭代器位置
  12. deque< int>::iterator iter = find(id.begin(), id.end(), 5);
  13. //将0、1、2插入在5的前面
  14. copy(ia + 0, ia + 3, inserter(id, iter));
  15. //于是输出0 1 2 3 4 0 1 2 5
  16. copy(id.begin(), id.end(), outiter);
  17. cout << endl;
  18. return 0;
  19. }

四、Reverse Iterators

  • Reverse Iterators,就是将一般迭代器的前进方向逆转:
    • 使原本应该前进的operator++变为后退操作
    • 使原本应该后退的operator--编程前进操作
  • 如果STL算法接受的不是一般的迭代器,而是这种逆向迭代器,它就会从尾到头的方向来处理序列中的元素。例如:

  
  1. //将所哟普元素你想拷贝到iter迭代器所在的位置
  2. //rbegin、rend与reverse_iterator有关
  3. copy(id.rbegin(), id.rend(), iter);

rbegin()、rend()

  • 大部分STL容器实现了这两个操作
  • 单向序列容器如slist不可以使用rever iterators,有些容器如stack、queue、priority_queue并不提供begin()、end(),当然也就没有rbegin()、rend()
  • 例如下面是vector的源码:

   
  1. template< class T,class Alloc=alloc>
  2. class vector
  3. {
  4. public:
  5. typedef T value_type;
  6. typedef value_type* iterator;
  7. typedef reverse_iterator<iterator> reverse_iterator;
  8. reverse_iterator rbegin() { return reverse_iterator(end()); }
  9. reverse_iterator rend() { return reverse_iterator(begin()); }
  10. };
  • 例如下面是list的源码:

   
  1. template< class T, class Alloc = alloc>
  2. class list
  3. {
  4. public:
  5. typedef __list_iterator<T, T&, T*> iterator;
  6. typedef reverse_iterator<iterator> reverse_iterator;
  7. reverse_iterator rbegin() { return reverse_iterator(end()); }
  8. reverse_iterator rend() { return reverse_iterator(begin()); }
  9. };
  • 例如下面是deque的源码:

   
  1. template< class T, class Alloc = alloc,size_t BufSiz=0>
  2. class deque
  3. {
  4. public:
  5. typedef __deque_iterator<T, T&, T*,BufSiz> iterator;
  6. typedef reverse_iterator<iterator> reverse_iterator;
  7. iterator begin() { return start; }
  8. iterator end() { return finish; }
  9. reverse_iterator rbegin() { return reverse_iterator(finish()); }
  10. reverse_iterator rend() { return reverse_iterator(start()); }
  11. };

演示案例


   
  1. #include <iostream>
  2. #include <iterator>
  3. #include <deque>
  4. #include <algorithm>
  5. using namespace std;
  6. int main()
  7. {
  8. int ia[] = { 32, 26, 99, 1, 0, 1, 2, 3, 4, 0, 1, 2, 5, 3 };
  9. deque< int> id(ia, ia + 14);
  10. std:: cout << *(id.begin()) << std:: endl; //32
  11. std:: cout << *(id.rbegin()) << std:: endl; //3
  12. //*(id.end()) //0
  13. //*(id.rend()) //0
  14. std:: cout << std:: endl;
  15. auto iter = find(id.begin(), id.end(), 99);
  16. reverse_iterator< deque< int>::iterator > riter(iter);
  17. std:: cout << *iter << std:: endl; //99
  18. std:: cout << *riter << std:: endl; //26
  19. return 0;
  20. }

  • 为什么上面“正向迭代器”和“逆向迭代器”取出不同的元素呢?因为begin()、end()与rbegin()、rend()的逻辑位置变了

  • 当我们将一个正向迭代器区间转换为一个逆向迭代器区间后,不必再有任何额外处理,就可以让接受这个逆向迭代器区间的算法,以相反的元素依次来处理区间中的每一个元素,例如:

   
  1. #include <iostream>
  2. #include <iterator>
  3. #include <deque>
  4. #include <algorithm>
  5. using namespace std;
  6. int main()
  7. {
  8. ostream_iterator< int> outiter( cout, " ");
  9. int ia[] = { 0, 1, 2, 3, 4, 5 };
  10. deque< int> id(ia, ia + 6);
  11. //0 1 2 3 4 5
  12. copy(id.begin(), id.end(), outiter);
  13. cout << endl;
  14. //5 4 3 2 1 0
  15. copy(id.rbegin(), id.rend(), outiter);
  16. cout << endl;
  17. return 0;
  18. }

  • 注意,上述的id.rbegin()是个暂时对象,相当于:

   
  1. reverse_iterator< deque< int>::iterator >(id.end()); //指向本例的最后元素
  2. deque< int>::reverse_iterator(id.end()); //指向本例的最后元素
  • 其中的deque<int>::reverse_iterator是一种类型定义

reverse_iterator源码


   
  1. //迭代器配接器,用来将某个迭代器逆反前进方向
  2. template< class Iterator>
  3. class reverse_iterator
  4. {
  5. protected:
  6. Iterator current; /记录对应的正向迭代器
  7. public:
  8. //5中与迭代器相关的类型
  9. typedef typname iterator_traits<Iterator>::iterator_category iterator_category;
  10. typedef typname iterator_traits<Iterator>::value_type value_type;
  11. typedef typname iterator_traits<Iterator>::difference_type difference_type;
  12. typedef typname iterator_traits<Iterator>::pointer pointer;
  13. typedef typname iterator_traits<Iterator>::reference reference;
  14. typedef Iterator iterator_type; //正向迭代器
  15. typedef reverse_iterator<Iterator> self; //逆向迭代器
  16. public:
  17. reverse_iterator() {}
  18. //将reverse_iterator与某个迭代器x关联起来
  19. explicit reverse_iterator(iterator_type x) :current(x) {}
  20. reverse_iterator( const self& x) :current(x.current) {}
  21. iterator_type base()const { return current; } //取出对应的正向迭代器
  22. reference operator*() const {
  23. Iterator tmp = current;
  24. return *--tmp;
  25. //以上关键在于。对逆向迭代器取值,“对应的正向迭代器”后退一位取值
  26. }
  27. pointer operator->() const { return &( operator*()); } //意义同上
  28. //前进变后退
  29. self& operator++() {
  30. --current;
  31. ++* this;
  32. }
  33. self operator++( int) {
  34. self tmp = * this;
  35. --current;
  36. return tmp;
  37. }
  38. //后退变前进
  39. self& operator--() {
  40. ++current;
  41. ++* this;
  42. }
  43. self operator--( int) {
  44. self tmp = * this;
  45. ++current;
  46. return tmp;
  47. }
  48. //前进与后退方向逆转
  49. self operator+(difference_type n) const {
  50. return self(current - n);
  51. }
  52. self& operator+=(difference_type n) {
  53. current -= n;
  54. return * this;
  55. }
  56. self operator-(difference_type n) const {
  57. return self(current + n);
  58. }
  59. self& operator-=(difference_type n) {
  60. current += n;
  61. return * this;
  62. }
  63. //下面第一个*和唯一一个+都会调用本类的operator*和operator+
  64. //第二个*则不会
  65. reference operator[](difference_type n) const { return*(* this + n); }
  66. };
  • 下面是另一些测试:

   
  1. #include <iostream>
  2. #include <iterator>
  3. #include <deque>
  4. #include <algorithm>
  5. using namespace std;
  6. int main()
  7. {
  8. int ia[] = { 1, 0, 1, 2, 3, 4, 0, 1, 2, 5, 3 };
  9. deque< int> id(ia, ia + 11);
  10. deque< int>:: reverse_iterator riter(id.end());
  11. std:: cout << *(riter) << std:: endl; //3
  12. std:: cout << *(++++++riter) << std:: endl; //1(前进3个位置后取值)
  13. std:: cout << *(--riter) << std:: endl; //2(后退1个位置后取值)
  14. std:: cout << *(riter.base()) << std:: endl; //5(恢复正向迭代器后,取值)
  15. std:: cout << riter[ 3] << std:: endl; //4(前进3个位置后取值)
  16. return 0;
  17. }

  • 图片说明:rbegin()连续三次累加后,退后一格,然后再以标注表示法[3]前进三格。由于是逆向迭代器,所以方向与一般的正向迭代器恰恰相反

五、IOStream Iterators

  • IOStream Iterators,就是将迭代器绑定到某个iostream对象身上
  • 这样的迭代器类包括:
    • 绑定istream(例如std::cin)身上,称为istream_iterator,拥有输入能力
    • 绑定ostream(例如std::cout)身上,称为ostream_iterator,拥有输出能力,这种迭代器运用于屏幕输出,十分方便
  • 以它们为蓝图,稍加修改,便可适用于任何输出或输入装置上。例如,你可以在了解iostream iterator之后,完成一个绑定到Internet Explorer cache身上的迭代器,或是完成一个系结到磁盘目录上的一个迭代器

istream_iterator源码

  • 所谓绑定一个istream,其实就是在istream iterator内部维护 一个istream member,客户端对于这个迭代器所做的operator++操作,会被引导调用迭代器内部所含的那个istream member的输入操作(operator>>)
  • 这个迭代器是个Input Iterator,不具备operator--
  • 源码如下:

   
  1. //这是一个input iterator,能够为“来自某一basic_istream”的对象执行格式化输入操作
  2. //注意:此版本为旧的HP规则,未符合标准接口:istream_iterator<T,charT,traits,Distance>
  3. //然而一般使用input iterators时都只使用template参数,此时以下仍使用
  4. //注:SGI STL 3.3已实现出符合标准接口的istream_iterator。做法与此版本大同小异
  5. template< class T,class Distance=ptrdiff_t>
  6. class istream_iterator
  7. {
  8. //在<stl_config.h>中,__STL_NULL_TMPL_ARGS被定义为<>
  9. friend bool operator==__STL_NULL_TMPL_ARGS( const istream_iterator<T, Distance>& x,
  10. const istream_iterator<T, Distance>& y);
  11. protected:
  12. istream* stream;
  13. T value;
  14. bool end_marker;
  15. void read() {
  16. end_marker = (*stream) ? true : false;
  17. if (end_marker)*stream >> value; //关键
  18. //以上,输入之后,stream的状态可能改变,所以下面再判断一次以决定end_marker
  19. //当读到eof或读到类型不符的数据时,stream处于false状态
  20. end_marker = (*stream) ? true : false;
  21. }
  22. public:
  23. typedef input_iterator_tag iterator_category;
  24. typedef T value_type;
  25. typedef Distance difference_type;
  26. typedef const T* pointer;
  27. typedef const T& reference;
  28. //因为input iterator,所以采用const
  29. istream_iterator() :stream(& cin), end_marker( false) {}
  30. istream_iterator(istream& s) :stream(&s) { read(); }
  31. /*以上两行的用法
  32. istream_iterator<int> eos; 造成end_marker为false
  33. istream_iterator<int> initer(cin); 引发read(),程序会等待输入
  34. 因此,下面这两行客户端程序:
  35. istream_iterator<int> initer(cin); //A
  36. cout<<"please ..."<<endl; //B
  37. 会停留在A等待一个输入,然后才执行B的消息。这是不合理的现象
  38. 建议:永远在最必要的时候,才定义一个istream_iterator
  39. */
  40. reference operator*() const { return value; }
  41. pointer operator->() const { return &( operator*()); }
  42. //迭代器前进一个位置,就代表要读取一次数据
  43. istream_iterator<T, Distance>& operator++() {
  44. read();
  45. return * this;
  46. }
  47. istream_iterator<T, Distance> operator++( int) {
  48. istream_iterator<T, Distance> tmp = * this;
  49. read();
  50. return tmp;
  51. }
  52. };
  • 源码告诉我们,只要客户端定义一个istream iterator并绑定到某个istream对象上,程序便会停在istream_iterator<T>::read()函数等待输入。这并不是我们预期的行为,因此,请在绝对必要的时候才定义你锁需要的istream iterator

演示案例

  • 下图是copy()和istream iterator使用的例子:
    • copy()有能力判断各种迭代器的类型,由于istream_iterator是个InputIterator,所以copy()最后会进入下图中的copy()源码中
  • 我们发现,当客户端初次定义了一个istream_iterator<T>对象并绑定到标准输入设备cin时,便调用istream_iterator<T>::read()读取cin的值,此值被放置于data member value中。然后进入循环,最这样的事情:

  • 根据istream_iterator的定义,对first取值就是返回data member value,也就是从cin获得的值。此值被赋值给*result。当copy()中的for循环进入下一次迭代时,会引发++first,而根据istream_iterator的定义,对first累加,就是再从cin中读值...如此持续下去,直到first==last为止。last代表的是一个end-of-stream标记,在各个系统上可能都不相同

演示案例


   
  1. #include <iostream>
  2. #include <iterator>
  3. #include <deque>
  4. #include <algorithm>
  5. using namespace std;
  6. int main()
  7. {
  8. ostream_iterator< int> outiter( cout, " ");
  9. int ia[] = { 0, 1, 2, 3, 4, 5 };
  10. deque< int> id(ia, ia + 6);
  11. copy(id.begin(), id.end(), outiter);
  12. cout << endl;
  13. //输入数据。接收到eof结束
  14. istream_iterator< int> initer( cin), eos;
  15. //将输入的数据插入在id最前面
  16. copy(initer, eos, inserter(id, id.begin()));
  17. //打印id中的元素
  18. copy(id.begin(), id.end(), outiter);
  19. return 0;
  20. }

ostream_iterator源码


   
  1. //这是一个output iterator,能够将对象格式化输出到某个basic_ostream上
  2. //注意:此版本为旧的HP规则,未符合标准接口:ostream_iterator<T,charT,traits>
  3. //然而一般使用output iterators时都只使用template参数,此时以下仍使用
  4. //注:SGI STL 3.3已实现出符合标准接口的ostream_iterator。做法与此版本大同小异
  5. template< class T, class Distance = ptrdiff_t>
  6. class ostream_iterator
  7. {
  8. protected:
  9. ostream* stream;
  10. const char* string; //每次输出后的间隔符号,变量名称为string
  11. public:
  12. typedef output_iterator_tag iterator_category;
  13. typedef void value_type;
  14. typedef void difference_type;
  15. typedef void pointer;
  16. typedef void reference;
  17. ostream_iterator(ostream& s) :stream(&s), string( 0) {}
  18. ostream_iterator(ostream& s, const char* c) :stream(&s), string( 0) {}
  19. /*上面构造函数的用法:
  20. ostream_iterator<int> outiter(cout,' '); 输出至cout,每次间隔一空格
  21. */
  22. //对迭代器做赋值操作,就代表要输出一次数据
  23. ostream_iterator<T>& operator=( const T& value) {
  24. *stream << value; //关键,输出值
  25. if ( string)*stream << string; //如果输出状态没错,输出间隔符号
  26. return * this;
  27. }
  28. ostream_iterator<T>& operator*() { return * this; }
  29. ostream_iterator<T>& operator++() { return * this; }
  30. ostream_iterator<T>& operator++( int) { return * this; }
  31. };

演示案例

  •  下面给出了copy()和ostream_iterator使用的例子。本例将ostream_iterator绑定到标准输出设备cout上
  • copy()能判断出迭代器的类型,采用最佳处理方法
  • 由于deque<int>::iterator是个RandomAccessIterator,所以copy()最后会进入下图所示的摘录的代码中。我们发现迭代器都做下面的事情:

  • 根据ostream_iterator的定义,对result取值,返回的是自己。对result执行赋值操作,则是将operator=右边的东西输出到cout去。当copy()算法进入for循环的下一次迭代时,会引发++result,而根据ostream_iterator的定义,对result的累加,返回的是自己...如此持续下去,知道数据来源结束(first==last)位置


转载:https://blog.csdn.net/qq_41453285/article/details/104375418
查看评论
* 以上用户言论只代表其个人观点,不代表本网站的观点或立场