一、配接器介绍
- 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()函数
//这是一个迭代器配接器,用来将某个迭代器的赋值操作改为插入操作——改为从容器的尾端插入 template< class Container> class back_insert_iterator { protected: Container* container; //底层容器 public: typedef out_iterator_tag iterator_category; //注意类型 typedef void value_type; typedef void difference_type; typedef void pointer; typedef void reference; //构造函数使back_insert_iterator与容器绑定起来 explicit back_insert_iterator(Container& x) :container(&x) {} back_insert_iterator<Container>& operator=( const typename Container::value_type& value) { container->push_back(value); //这里是关键,直接调用push_back() return * this; } //下面的操作符对back_insert_iterator不起作用(关闭功能) //因此都返回自己 back_insert_iterator<Container>& operator*() { return * this; } back_insert_iterator<Container>& operator++() { return * this; } back_insert_iterator<Container>& operator++( int) { return * this; } };
//这是一个辅助函数,方便我们使用back_insert_iterator template< class Container> inline back_insert_iterator<Container> back_inserter(Container& x) { return back_insert_iterator<Container>(x); }演示案例
#include <iostream> #include <iterator> #include <deque> #include <algorithm> using namespace std; int main() { ostream_iterator< int> outiter( cout, " "); int ia[] = { 0, 1, 2, 3, 4, 5 }; deque< int> id(ia, ia + 6); //将3插入id的尾部 copy(ia+ 3, ia + 4, back_inserter(id)); //输出id的内容 copy(id.begin(), id.end(), outiter); cout << endl; return 0; }
front_insert_iterator类、front_inserter()函数
//这是一个迭代器配接器,用来将某个迭代器的赋值操作改为插入操作——改为从容器的头部插入 //注意,该容器不支持vector,因为vector没有提供push_front()函数 template< class Container> class front_insert_iterator { protected: Container* container; //底层容器 public: typedef out_iterator_tag iterator_category; //注意类型 typedef void value_type; typedef void difference_type; typedef void pointer; typedef void reference; //构造函数使back_insert_iterator与容器绑定起来 explicit front_insert_iterator(Container& x) :container(&x) {} front_insert_iterator<Container>& operator=( const typename Container::value_type& value) { container->push_front(value); //这里是关键,直接调用push_front() return * this; } //下面的操作符对front_insert_iterator不起作用(关闭功能) //因此都返回自己 front_insert_iterator<Container>& operator*() { return * this; } front_insert_iterator<Container>& operator++() { return * this; } front_insert_iterator<Container>& operator++( int) { return * this; } };
//这是一个辅助函数,方便我们使用front_insert_iterator template< class Container> inline front_insert_iterator<Container> front_inserter(Container& x) { return front_insert_iterator<Container>(x); }演示案例
#include <iostream> #include <iterator> #include <deque> #include <algorithm> using namespace std; int main() { ostream_iterator< int> outiter( cout, " "); int ia[] = { 0, 1, 2, 3, 4, 5 }; deque< int> id(ia, ia + 6); //将1插入头部 copy(ia + 1, ia + 2, front_inserter(id)); //输出容器中的内容 copy(id.begin(), id.end(), outiter); cout << endl; return 0; }
insert_iterator类、inserter()函数
//这是一个迭代器配接器,用来将某个迭代器的赋值操作改为插入操作——在任意位置上插入 //并将迭代器右移一个位置——如此便可以方便地连续插入 //表面上是赋值操作,实际上是插入操作 template< class Container> class insert_iterator { protected: Container* container; //底层容器 typename Container::iterator iter; public: typedef out_iterator_tag iterator_category; //注意类型 typedef void value_type; typedef void difference_type; typedef void pointer; typedef void reference; insert_iterator(Container& x, typename Container::iterator i) :container(&x), iter(i) {} insert_iterator<Container>& operator=( const typename Container::value_type& value) { iter = container->inserter(iter, value); //关键,直接调用insert() ++iter; //使insert iterator永远随其目标而移动 return * this; } //下面的操作符对insert_iterator不起作用(关闭功能) //因此都返回自己 insert_iterator<Container>& operator*() { return * this; } insert_iterator<Container>& operator++() { return * this; } insert_iterator<Container>& operator++( int) { return * this; } };
//这是一个辅助函数,方便我们使用insert_iterator template< class Container> inline insert_iterator<Container> inserter(Container& x, Iterator i) { return insert_iterator<Container>(x, iter(i)); }演示案例
#include <iostream> #include <iterator> #include <deque> #include <algorithm> using namespace std; int main() { ostream_iterator< int> outiter( cout, " "); int ia[] = { 0, 1, 2, 3, 4, 5 }; deque< int> id(ia, ia + 6); //找出元素5所在的迭代器位置 deque< int>::iterator iter = find(id.begin(), id.end(), 5); //将0、1、2插入在5的前面 copy(ia + 0, ia + 3, inserter(id, iter)); //于是输出0 1 2 3 4 0 1 2 5 copy(id.begin(), id.end(), outiter); cout << endl; return 0; }
四、Reverse Iterators
- Reverse Iterators,就是将一般迭代器的前进方向逆转:
- 使原本应该前进的operator++变为后退操作
- 使原本应该后退的operator--编程前进操作
- 如果STL算法接受的不是一般的迭代器,而是这种逆向迭代器,它就会从尾到头的方向来处理序列中的元素。例如:
-
//将所哟普元素你想拷贝到iter迭代器所在的位置
-
//rbegin、rend与reverse_iterator有关
-
copy(id.rbegin(), id.rend(), iter);
rbegin()、rend()
- 大部分STL容器实现了这两个操作
- 单向序列容器如slist不可以使用rever iterators,有些容器如stack、queue、priority_queue并不提供begin()、end(),当然也就没有rbegin()、rend()
- 例如下面是vector的源码:
template< class T,class Alloc=alloc> class vector { public: typedef T value_type; typedef value_type* iterator; typedef reverse_iterator<iterator> reverse_iterator; reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } };
- 例如下面是list的源码:
template< class T, class Alloc = alloc> class list { public: typedef __list_iterator<T, T&, T*> iterator; typedef reverse_iterator<iterator> reverse_iterator; reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } };
- 例如下面是deque的源码:
template< class T, class Alloc = alloc,size_t BufSiz=0> class deque { public: typedef __deque_iterator<T, T&, T*,BufSiz> iterator; typedef reverse_iterator<iterator> reverse_iterator; iterator begin() { return start; } iterator end() { return finish; } reverse_iterator rbegin() { return reverse_iterator(finish()); } reverse_iterator rend() { return reverse_iterator(start()); } };演示案例
#include <iostream> #include <iterator> #include <deque> #include <algorithm> using namespace std; int main() { int ia[] = { 32, 26, 99, 1, 0, 1, 2, 3, 4, 0, 1, 2, 5, 3 }; deque< int> id(ia, ia + 14); std:: cout << *(id.begin()) << std:: endl; //32 std:: cout << *(id.rbegin()) << std:: endl; //3 //*(id.end()) //0 //*(id.rend()) //0 std:: cout << std:: endl; auto iter = find(id.begin(), id.end(), 99); reverse_iterator< deque< int>::iterator > riter(iter); std:: cout << *iter << std:: endl; //99 std:: cout << *riter << std:: endl; //26 return 0; }
- 为什么上面“正向迭代器”和“逆向迭代器”取出不同的元素呢?因为begin()、end()与rbegin()、rend()的逻辑位置变了
- 当我们将一个正向迭代器区间转换为一个逆向迭代器区间后,不必再有任何额外处理,就可以让接受这个逆向迭代器区间的算法,以相反的元素依次来处理区间中的每一个元素,例如:
#include <iostream> #include <iterator> #include <deque> #include <algorithm> using namespace std; int main() { ostream_iterator< int> outiter( cout, " "); int ia[] = { 0, 1, 2, 3, 4, 5 }; deque< int> id(ia, ia + 6); //0 1 2 3 4 5 copy(id.begin(), id.end(), outiter); cout << endl; //5 4 3 2 1 0 copy(id.rbegin(), id.rend(), outiter); cout << endl; return 0; }
- 注意,上述的id.rbegin()是个暂时对象,相当于:
reverse_iterator< deque< int>::iterator >(id.end()); //指向本例的最后元素 deque< int>::reverse_iterator(id.end()); //指向本例的最后元素
- 其中的deque<int>::reverse_iterator是一种类型定义
reverse_iterator源码
//迭代器配接器,用来将某个迭代器逆反前进方向 template< class Iterator> class reverse_iterator { protected: Iterator current; /记录对应的正向迭代器 public: //5中与迭代器相关的类型 typedef typname iterator_traits<Iterator>::iterator_category iterator_category; typedef typname iterator_traits<Iterator>::value_type value_type; typedef typname iterator_traits<Iterator>::difference_type difference_type; typedef typname iterator_traits<Iterator>::pointer pointer; typedef typname iterator_traits<Iterator>::reference reference; typedef Iterator iterator_type; //正向迭代器 typedef reverse_iterator<Iterator> self; //逆向迭代器 public: reverse_iterator() {} //将reverse_iterator与某个迭代器x关联起来 explicit reverse_iterator(iterator_type x) :current(x) {} reverse_iterator( const self& x) :current(x.current) {} iterator_type base()const { return current; } //取出对应的正向迭代器 reference operator*() const { Iterator tmp = current; return *--tmp; //以上关键在于。对逆向迭代器取值,“对应的正向迭代器”后退一位取值 } pointer operator->() const { return &( operator*()); } //意义同上 //前进变后退 self& operator++() { --current; ++* this; } self operator++( int) { self tmp = * this; --current; return tmp; } //后退变前进 self& operator--() { ++current; ++* this; } self operator--( int) { self tmp = * this; ++current; return tmp; } //前进与后退方向逆转 self operator+(difference_type n) const { return self(current - n); } self& operator+=(difference_type n) { current -= n; return * this; } self operator-(difference_type n) const { return self(current + n); } self& operator-=(difference_type n) { current += n; return * this; } //下面第一个*和唯一一个+都会调用本类的operator*和operator+ //第二个*则不会 reference operator[](difference_type n) const { return*(* this + n); } };
- 下面是另一些测试:
#include <iostream> #include <iterator> #include <deque> #include <algorithm> using namespace std; int main() { int ia[] = { 1, 0, 1, 2, 3, 4, 0, 1, 2, 5, 3 }; deque< int> id(ia, ia + 11); deque< int>:: reverse_iterator riter(id.end()); std:: cout << *(riter) << std:: endl; //3 std:: cout << *(++++++riter) << std:: endl; //1(前进3个位置后取值) std:: cout << *(--riter) << std:: endl; //2(后退1个位置后取值) std:: cout << *(riter.base()) << std:: endl; //5(恢复正向迭代器后,取值) std:: cout << riter[ 3] << std:: endl; //4(前进3个位置后取值) return 0; }
- 图片说明: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--
- 源码如下:
//这是一个input iterator,能够为“来自某一basic_istream”的对象执行格式化输入操作 //注意:此版本为旧的HP规则,未符合标准接口:istream_iterator<T,charT,traits,Distance> //然而一般使用input iterators时都只使用template参数,此时以下仍使用 //注:SGI STL 3.3已实现出符合标准接口的istream_iterator。做法与此版本大同小异 template< class T,class Distance=ptrdiff_t> class istream_iterator { //在<stl_config.h>中,__STL_NULL_TMPL_ARGS被定义为<> friend bool operator==__STL_NULL_TMPL_ARGS( const istream_iterator<T, Distance>& x, const istream_iterator<T, Distance>& y); protected: istream* stream; T value; bool end_marker; void read() { end_marker = (*stream) ? true : false; if (end_marker)*stream >> value; //关键 //以上,输入之后,stream的状态可能改变,所以下面再判断一次以决定end_marker //当读到eof或读到类型不符的数据时,stream处于false状态 end_marker = (*stream) ? true : false; } public: typedef input_iterator_tag iterator_category; typedef T value_type; typedef Distance difference_type; typedef const T* pointer; typedef const T& reference; //因为input iterator,所以采用const istream_iterator() :stream(& cin), end_marker( false) {} istream_iterator(istream& s) :stream(&s) { read(); } /*以上两行的用法 istream_iterator<int> eos; 造成end_marker为false istream_iterator<int> initer(cin); 引发read(),程序会等待输入 因此,下面这两行客户端程序: istream_iterator<int> initer(cin); //A cout<<"please ..."<<endl; //B 会停留在A等待一个输入,然后才执行B的消息。这是不合理的现象 建议:永远在最必要的时候,才定义一个istream_iterator */ reference operator*() const { return value; } pointer operator->() const { return &( operator*()); } //迭代器前进一个位置,就代表要读取一次数据 istream_iterator<T, Distance>& operator++() { read(); return * this; } istream_iterator<T, Distance> operator++( int) { istream_iterator<T, Distance> tmp = * this; read(); return tmp; } };
- 源码告诉我们,只要客户端定义一个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标记,在各个系统上可能都不相同
演示案例
#include <iostream> #include <iterator> #include <deque> #include <algorithm> using namespace std; int main() { ostream_iterator< int> outiter( cout, " "); int ia[] = { 0, 1, 2, 3, 4, 5 }; deque< int> id(ia, ia + 6); copy(id.begin(), id.end(), outiter); cout << endl; //输入数据。接收到eof结束 istream_iterator< int> initer( cin), eos; //将输入的数据插入在id最前面 copy(initer, eos, inserter(id, id.begin())); //打印id中的元素 copy(id.begin(), id.end(), outiter); return 0; }
ostream_iterator源码
//这是一个output iterator,能够将对象格式化输出到某个basic_ostream上 //注意:此版本为旧的HP规则,未符合标准接口:ostream_iterator<T,charT,traits> //然而一般使用output iterators时都只使用template参数,此时以下仍使用 //注:SGI STL 3.3已实现出符合标准接口的ostream_iterator。做法与此版本大同小异 template< class T, class Distance = ptrdiff_t> class ostream_iterator { protected: ostream* stream; const char* string; //每次输出后的间隔符号,变量名称为string public: typedef output_iterator_tag iterator_category; typedef void value_type; typedef void difference_type; typedef void pointer; typedef void reference; ostream_iterator(ostream& s) :stream(&s), string( 0) {} ostream_iterator(ostream& s, const char* c) :stream(&s), string( 0) {} /*上面构造函数的用法: ostream_iterator<int> outiter(cout,' '); 输出至cout,每次间隔一空格 */ //对迭代器做赋值操作,就代表要输出一次数据 ostream_iterator<T>& operator=( const T& value) { *stream << value; //关键,输出值 if ( string)*stream << string; //如果输出状态没错,输出间隔符号 return * this; } ostream_iterator<T>& operator*() { return * this; } ostream_iterator<T>& operator++() { return * this; } ostream_iterator<T>& operator++( int) { return * this; } };演示案例
- 下面给出了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
查看评论