技術文章 » C++迭代器適配器:反向迭代器、插入迭代器、iostream迭代器

C++迭代器適配器:反向迭代器、插入迭代器、iostream迭代器

2020-08-13 21:06:29

適配器是標準庫中的一個通用概念。容器、迭代器和函數都有適配器(C++11出現了lambda函數、function類別範本、bind函數，幾乎取代了函數適配器)。本質上，適配器是一種機制 機製，能使某種事物的行爲看起來像另外一種一樣。棧、佇列、優先佇列都屬於容器適配器。本文主要介紹迭代器適配器。

迭代器適配器主要有三類：反向迭代器，插入迭代器，iostream迭代器。

插入迭代器

插入迭代器有三種類型，差異在於元素插入的位置：

  • back_inserter( Container& c )，在容器尾部插入，只能對有push_back()的容器使用
  • inserter( Container& c, Container::iterator i )，在容器內部指定迭代器前插入,只能對有insert()的容器使用。
  • front_inserter( Container& c )，在容器頭部插入，只能對有push_front()的容器使用。

假如你不能確定容器的大小，使用這三種迭代器，可以保證了不會造成越界的情況。

vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
fill_n(inserter(v, v.begin() + 1), 3, -2);  // v:1 -2 -2 -2 2 3 4 5 6 7 8 9 10 

vector<int> v2;
copy(v.begin(),v.end(),back_inserter(v2));  // v2:1 -2 -2 -2 2 3 4 5 6 7 8 9 10 

deque<int> d;
copy(v.begin(),v.end(),front_inserter(d));  //逆序插入 d:10 9 8 7 6 5 4 3 2 -2 -2 -2 1

原理分析

每一個insert iterators 內部都維護有一個容器（必須由使用者指定）；容器當然有自己的迭代器，於是，當用戶端對insert iterators做賦值（assign）操作時，就在insert iterators中被轉爲對該容器的選代器做插入操作，也就是說，在insert iterators的operator=操作符中呼叫底層容器的push_front（）或push_back（）或insert（）操作函數。至於其它的迭代器慣常行爲如operator++，operator++（int），operator*都被關閉功能，更沒有提供operator--（int）或operator--或operator->等功能。換句話說，insert iterators的前進、後退、取值、成員取用等操作都是沒有意義的，甚至是不允許的。
下面 下麪是back_inserter原始碼：

template <class Container>
class back_insert_iterator
{
protected:
  Container* container;
public:
  typedef output_iterator_tag iterator_category;
  typedef void                value_type;
  typedef void                difference_type;
  typedef void                pointer;
  typedef void                reference;
 
  explicit back_insert_iterator(Container& x) : container(&x) {}
 
  // 只有提供了push_back()操作的容器才能 纔能使用back_insert_iterator
  back_insert_iterator<Container>&
  operator=(const typename Container::value_type& value)
  {
    container->push_back(value);
    return *this;
  }
 
  back_insert_iterator<Container>& operator*() { return *this; }
  back_insert_iterator<Container>& operator++() { return *this; }
  back_insert_iterator<Container>& operator++(int) { return *this; }
};

反向迭代器

反向迭代器就是將迭代器的移動行爲倒轉。如果STL演算法接受的不是一般正常的迭代器，而是這種逆向迭代器，它就會以從尾到頭的方向來處理序列中的元素。例如：

//將所有元素逆向拷貝到ite所指位置上
//rbegin()和rend()返回的就是反向迭代器
copy(id.rbegin(),id.rend(),ite);

id.rbegin().base()返回反向迭代器對應的正向迭代器id.end()。

rbegin()雖然對應於原迭代器的end()，但是逆向迭代器的operator* 被過載爲將"對應的正向迭代器後退一格而後取值"，因此*id.rbegin()返回容器尾部元素值。這麼做是爲了配合迭代器區間左閉右開的習慣，使其不用額外修改就能搭配原有的STL函數。

在这里插入图片描述
實線表示取值*時對應的迭代器，虛線表示實際對應的迭代器。

template <class Iterator>
class reverse_iterator
{
protected:
  Iterator current;
public:
  typedef typename iterator_traits<Iterator>::iterator_category
          iterator_category;
  typedef typename iterator_traits<Iterator>::value_type
          value_type;
  typedef typename iterator_traits<Iterator>::difference_type
          difference_type;
  typedef typename iterator_traits<Iterator>::pointer
          pointer;
  typedef typename iterator_traits<Iterator>::reference
          reference;
 
  typedef Iterator iterator_type;
  typedef reverse_iterator<Iterator> self;
 
public:
  reverse_iterator() {}
  explicit reverse_iterator(iterator_type x) : current(x) {}
 
  reverse_iterator(const self& x) : current(x.current) {}
#ifdef __STL_MEMBER_TEMPLATES
  template <class Iter>
  reverse_iterator(const reverse_iterator<Iter>& x) : current(x.current) {}
#endif /* __STL_MEMBER_TEMPLATES */
 
  iterator_type base() const { return current; }
  reference operator*() const {
    Iterator tmp = current;
    return *--tmp;
  }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
 
  self& operator++() {
    --current;
    return *this;
  }
  self operator++(int) {
    self tmp = *this;
    --current;
    return tmp;
  }
  self& operator--() {
    ++current;
    return *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;
  }
  reference operator[](difference_type n) const { return *(*this + n); }
};

iostream迭代器

  • istream_iterator()，輸入迭代器，可以對istream物件進行操作
  • ostream_iterator()，輸出迭代器，可以對ostream物件進行操作

所謂iostream迭代器，可以將迭代器系結到一個stream（數據流）物件身上。系結istream物件（例如cin）者，稱爲istream_iterator，擁有輸入能力；系結到ostream物件（例如cout）者，稱爲ostream_iterator，擁有輸出能力。

cout<<accumulate(istream_iterator<int>(cin),istream_iterator<int>(),0);//輸出從標準輸入讀取的值得和

vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
ostream_iterator<int> out_iter(cout," ");//第一位參數爲系結輸出流；第二位參數爲輸出分隔符，預設爲空字串
copy(v.begin(),v.end(),out_iter);//標準輸出1 2 3 4 5 6 7 8 9 10

原理分析

  • istream迭代器

所謂系結一個istream object，其實就是在istream_iterator內部維護一個istream member，用戶端對於這個迭代器所做的operator++操作，會被導引呼叫迭代器內部所含的那個istream member的輸入操作（operator>>）。這個迭代器是個Input iterator，不具備operator- -。如下是可讀性比較強的一種原始碼版本。

template <class T, class Distance = ptrdiff_t>
class istream_iterator
{
  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;//是否繼續輸入，結束爲false，繼續爲true
  void read() {//讀取輸入流
    end_marker = (*stream) ? true : false;
    if (end_marker) *stream >> value;
    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;
  istream_iterator() : stream(&cin), end_marker(false) {}//使用預設構造時，讀取標記關閉，不再讀取，相當於eof
  istream_iterator(istream& s) : stream(&s) { read(); }//系結時已開始讀取
  reference operator*() const { return value; }        //返回輸入的數據
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
  istream_iterator<T, Distance>& operator++() {
    read();
    return *this;
  }
  istream_iterator<T, Distance> operator++(int)  {
    istream_iterator<T, Distance> tmp = *this;
    read();
    return tmp;
  }
};

在这里插入图片描述

  • ostream迭代器

所謂系結一個ostream object，就是在其內部維護一個ostream member，用戶端對於這個迭代器所做的 operator=操作，會被導引呼叫對應的（迭代器內部所含的）那個ostream member的輸出操作（operator<<）.這個迭代器是個Oufputterator.下面 下麪的原始碼和註釋說明了一切。

至於ostream iterator，所謂系結一個ostream object，就是在其內部維護一個ostream member，用戶端對於這個迭代器所做的 operator=操作，會被導引呼叫對應的（迭代器內部所含的）那個ostream member的輸出操作（operator<<）。這個迭代器是個Output iterator。

template <class T>
class ostream_iterator
{
protected:
  ostream* stream;
  const char* 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(c)  {}
  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; }
};


參考：
《STL原始碼剖析》