株式会社エス・スリー・フォー

STL Samples : <iterator>

traits,tag

iterator_traits

- template<class Iterator>
  struct iterator_traits {
    typedef typename Iterator::difference_type   difference_type;
    typedef typename Iterator::value_type        value_type;
    typedef typename Iterator::pointer           pointer;
    typedef typename Iterator::reference         reference;
    typedef typename Iterator::iterator_category iterator_category;
  };

- template<class T>
  struct iterator_traits<T*> {
    typedef ptrdiff_t                  difference_type;
    typedef T                          value_type;
    typedef T*                         pointer;
    typedef T&                         reference;
    typedef random_access_iterator_tag iterator_category;
  };

- template<class T>
  struct iterator_traits<const T*> {
    typedef ptrdiff_t                  difference_type;
    typedef T                          value_type;
    typedef const T*                   pointer;
    typedef const T&                   reference;
    typedef random_access_iterator_tag iterator_category;
  };

input_iterator_tag output_iterator_tag forward_iterator_tag bidirectional_iterator_tag random_access_iterator_tag

#include <iostream>
#include <list>
#include <deque>
#include <vector>
#include <iterator>
#include <algorithm>
#include "to_string.h"

using namespace std;

template<class Iterator>
void sort_any_(Iterator first, Iterator last, random_access_iterator_tag) {
  sort(first, last);
}

template<class Iterator>
void sort_any_(Iterator first, Iterator last, forward_iterator_tag) {
  typedef iterator_traits<Iterator>::value_type value_type;
  vector<value_type> v;
  copy(first, last, back_inserter(v));
  sort(v.begin(), v.end());
  copy(v.begin(), v.end(), first);
}

template<class Iterator>
void sort_any(Iterator first, Iterator last) {
  sort_any_(first, last, iterator_traits<Iterator>::iterator_category());
}

void std_traits() {
  cout << "iterator_traits, input_iterator_tag, output_iterator_tag, "
       << "forward_iterator_tag, bidirectional_iterator_tag, random_access_iterator_tag" << endl;
  list<int> l;
  deque<int> d;
  int i;
  for ( i = 0; i < 10; ++i ) {
    l.push_back(i % 4);
    d.push_back(i % 4);
  }

  cout << "list:  " << to_string(l.begin(), l.end()) << " をソート: ";
  sort_any(l.begin(), l.end());
  cout << to_string(l.begin(), l.end()) << endl;

  cout << "deque: " << to_string(d.begin(), d.end()) << " をソート: ";
  sort_any(d.begin(), d.end());
  cout << to_string(d.begin(), d.end()) << endl;
}

iterator操作

advance

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

iをn個進めます。InputIteratorがRandomAccessIteratorあるいはBidirectionalIteratorであればn<0でもかまいません。そのときは-n個戻ることになります。

distance

- template<class InputIterator>
  typename iterator_traits<InputIterator>::difference_type
  distance(InputIterator first, InputIterator last);

firstからlastまでの距離、すなわち範囲[first,last)にある要素の個数を返します。

#include <list>
#include <iterator>
#include "to_string.h"

using namespace std;

void std_iter_op() {
  cout << "advance, distance" << endl;
  list<int> l;
  for ( int i = 0; i < 10; ++i )
    l.push_back(i);
  list<int>::iterator it = l.begin();
  advance(it,4);
  cout << to_string(l.begin(), l.end()) << " の4番目の位置: "
       << to_string(l.begin(), it, l.end()) << endl;
  cout << "4番目以降の要素数: " << distance(it, l.end()) << endl;
}

反転イテレータ

reverse_iterator

- template <class Iterator>
  class reverse_iterator : public
    iterator<typename iterator_traits<Iterator>::iterator_category,
             typename iterator_traits<Iterator>::value_type,
             typename iterator_traits<Iterator>::difference_type,
             typename iterator_traits<Iterator>::pointer,
             typename iterator_traits<Iterator>::reference> {
  protected:
    Iterator current;
  public:
    typedef Iterator iterator_type;
    typedef typename iterator_traits<Iterator>::difference_type
                                                      difference_type;
    typedef typename iterator_traits<Iterator>::reference reference;
    typedef typename iterator_traits<Iterator>::pointer pointer;
    reverse_iterator();
    explicit reverse_iterator(Iterator x);
    template <class U> reverse_iterator(const reverse_iterator<U>& u);
    Iterator base() const; // explicit
    reference operator*() const;
    pointer operator->() const;
    reverse_iterator& operator++();
    reverse_iterator operator++(int);
    reverse_iterator& operator--();
    reverse_iterator operator--(int);
    reverse_iterator operator+ (difference_type n) const;
    reverse_iterator& operator+=(difference_type n);
    reverse_iterator operator-(difference_type n) const;
    reverse_iterator& operator-=(difference_type n);
    reference operator[](difference_type n) const;
  };

BidirectionalIterator,RandomAccessIteratorから進行方向の逆転(operator++で後退/operator--で前進)したイテレータを作ります。

#include <iostream>
#include <iterator>
#include "to_string.h"

using namespace std;

void std_reverse_iter() {
  cout << "reverse_iterator" << endl;
  const int N = 6;
  int array[N] = { 0, 1, 2, 3, 4, 5 };
  cout << to_string(array,array+N) << " を逆順に出力: ";
  reverse_iterator<int*,int> first(array+N);
  reverse_iterator<int*,int> last(array);
  while ( first != last ) {
    cout << *first << ' ';
    ++first;
  }
  cout << endl;
}

挿入イテレータ

back_insert_iterator back_inserter

- template <class Container>
  class back_insert_iterator :
    public iterator<output_iterator_tag,void,void,void,void> {
  protected:
    Container* container;
  public:
    typedef Container container_type;
    explicit back_insert_iterator(Container& x);
    back_insert_iterator<Container>&
    operator=(typename Container::const_reference value);
    back_insert_iterator<Container>& operator*();
    back_insert_iterator<Container>& operator++();
    back_insert_iterator<Container> operator++(int);
  };

コンストラクト時にメンバ関数push_backの定義されたコンテナcを与えておけば、operator=(x)されるたびにc.push_back(x)します。

- template <class Container>
  back_insert_iterator<Container>
  back_inserter(Container& x);

back_insert_iterator<Container>(x) を返します。

front_insert_iterator front_inserter

- template <class Container>
  class front_insert_iterator :
    public iterator<output_iterator_tag,void,void,void,void> {
  protected:
    Container* container;
  public:
    typedef Container container_type;
    explicit front_insert_iterator(Container& x);
    front_insert_iterator<Container>&
    operator=(typename Container::const_reference value);
    front_insert_iterator<Container>& operator*();
    front_insert_iterator<Container>& operator++();
    front_insert_iterator<Container> operator++(int);
  };

コンストラクト時にメンバ関数push_frontの定義されたコンテナcを与えておけば、operator=(x)されるたびにc.push_front(x)します。

- template <class Container>
  front_insert_iterator<Container>
  front_inserter(Container& x);

front_insert_iterator<Container>(x) を返します。

insert_iterator inserter

- template <class Container>
  class insert_iterator :
    public iterator<output_iterator_tag,void,void,void,void> {
  protected:
    Container* container;
    typename Container::iterator iter;
  public:
    typedef Container container_type;
    insert_iterator(Container& x, typename Container::iterator i);
    insert_iterator<Container>&
    operator=(typename Container::const_reference value);
    insert_iterator<Container>& operator*();
    insert_iterator<Container>& operator++();
    insert_iterator<Container>& operator++(int);
  };

コンストラクト時にメンバ関数insertの定義されたコンテナcとイテレータiを与えておけば、operator=(x)されるたびにc.insert(i++,x)します。

- template <class Container, class Iterator>
  insert_iterator<Container>
  inserter(Container& x, Iterator i);

insert_iterator<Container>(x,i)を返します。

#include <iostream>
#include <list>
#include "to_string.h"

using namespace std;

void std_insert_iter() {
  cout << "back_insert_iterator, front_insert_iterator, insert_iterator" << endl;
  list<char> l;
  for ( int i = 0; i < 4; ++i )
    l.push_back(i+'0');
  const int N = 3;
  const char front[] = "ABC";
  const char mid[]   = "DEF";
  const char back[]  = "GHI";

  list<char>::iterator it = l.begin();
  advance(it,2);
  cout << to_string(l.begin(), it, l.end()) << " に " << to_string(mid,mid+N) << " を挿入: ";
  insert_iterator< list<char> > m(l,it);
  copy(mid, mid+N, m);
  cout << to_string(l.begin(), l.end()) << endl;

  cout << to_string(l.begin(), l.end()) << " に " << to_string(front,front+N) << " をpush_front: ";
  front_insert_iterator< list<char> > f(l);
  copy(front, front+N, f);
  cout << to_string(l.begin(), l.end()) << endl;

  cout << to_string(l.begin(), l.end()) << " に " << to_string(back,back+N) << " をpush_back: ";
  back_insert_iterator< list<char> > b(l);
  copy(back, back+N, b);
  cout << to_string(l.begin(), l.end()) << endl;
}

void std_inserter() {
  cout << "back_inserter, front_inserter, inserter" << endl;
  list<char> l;
  for ( int i = 0; i < 4; ++i )
    l.push_back(i+'0');
  const int N = 3;
  const char front[] = "ABC";
  const char mid[]   = "DEF";
  const char back[]  = "GHI";

  list<char>::iterator it = l.begin();
  advance(it,2);
  cout << to_string(l.begin(), it, l.end()) << " に " << to_string(mid,mid+N) << " を挿入: ";
  copy(mid, mid+N, inserter(l,it));
  cout << to_string(l.begin(), l.end()) << endl;

  cout << to_string(l.begin(), l.end()) << " に " << to_string(front,front+N) << " をpush_front: ";
  copy(front, front+N, front_inserter(l));
  cout << to_string(l.begin(), l.end()) << endl;

  cout << to_string(l.begin(), l.end()) << " に " << to_string(back,back+N) << " をpush_back: ";
  copy(back, back+N, back_inserter(l));
  cout << to_string(l.begin(), l.end()) << endl;
}

ストリームイテレータ

istream_iterator

- template <class T, class charT = char,
            class traits = char_traits<charT>,
            class Distance = ptrdiff_t>
  class istream_iterator:
    public iterator<input_iterator_tag,T,Distance,const T*,const T&> {
  public:
    typedef charT char_type
    typedef traits traits_type;
    typedef basic_istream<charT,traits> istream_type;
    istream_iterator();
    istream_iterator(istream_type& s);
    istream_iterator(const istream_iterator<T,charT,traits,Distance>& x);
    ~istream_iterator();
    const T& operator*() const;
    const T* operator->() const;
    istream_iterator<T,charT,traits,Distance>& operator++();
    istream_iterator<T,charT,traits,Distance> operator++(int);
  };

入力ストリームをInputIterator化します。

ostream_iterator

- template <class T, class charT = char,
            class traits = char_traits<charT> >
  class ostream_iterator:
    public iterator<output_iterator_tag, void, void, void, void> {
  public:
    typedef charT char_type;
    typedef traits traits_type;
    typedef basic_ostream<charT,traits> ostream_type;
    ostream_iterator(ostream_type& s);
    ostream_iterator(ostream_type& s, const charT* delimiter);
    ostream_iterator(const ostream_iterator<T,charT,traits>& x);
    ~ostream_iterator();
    ostream_iterator<T,charT,traits>& operator=(const T& value);
    ostream_iterator<T,charT,traits>& operator*();
    ostream_iterator<T,charT,traits>& operator++();
    ostream_iterator<T,charT,traits>& operator++(int);
  private:
    // basic_ostream<charT,traits>* out_stream; exposition only
    // const char* delim; exposition only
  };

出力ストリームをOutputiterator化します。

istreambuf_iterator

- template<class charT, class traits = char_traits<charT> >
  class istreambuf_iterator
    : public iterator<input_iterator_tag, charT,
                      typename traits::off_type, charT*, charT&> {
  public:
    typedef charT char_type;
    typedef traits traits_type;
    typedef typename traits::int_type int_type;
    typedef basic_streambuf<charT,traits> streambuf_type;
    typedef basic_istream<charT,traits> istream_type;
    class proxy; // exposition only
  public:
    istreambuf_iterator() throw();
    istreambuf_iterator(istream_type& s) throw();
    istreambuf_iterator(streambuf_type* s) throw();
    istreambuf_iterator(const proxy& p) throw();
    charT operator*() const;
    istreambuf_iterator<charT,traits>& operator++();
    proxy operator++(int);
    bool equal(istreambuf_iterator& b);
  private:
    streambuf_type* sbuf_; exposition only
  };

入力ストリームバッファをInputIterator化します。

ostreambuf_iterator

- template <class charT, class traits = char_traits<charT> >
  class ostreambuf_iterator:
    public iterator<output_iterator_tag, void, void, void, void> {
  public:
    typedef charT char_type;
    typedef traits traits_type;
    typedef basic_streambuf<charT,traits> streambuf_type;
    typedef basic_ostream<charT,traits> ostream_type;
  public:
    ostreambuf_iterator(ostream_type& s) throw();
    ostreambuf_iterator(streambuf_type* s) throw();
    ostreambuf_iterator& operator=(charT c);
    ostreambuf_iterator& operator*();
    ostreambuf_iterator& operator++();
    ostreambuf_iterator& operator++(int);
    bool failed() const throw();
  private:
    streambuf_type* sbuf_; exposition only
  };

出力入力ストリームバッファをOutputIterator化します。

#include <iostream>
#include <sstream>
#include <string>
#include <iterator>
#include <cctype>

using namespace std;

void std_stream_iter() {
  cout << "istream_iterator, ostream_iterator" << endl;
  istringstream is("this string is on istringstream");
  istream_iterator<string> first(is);
  istream_iterator<string> last;
  ostream_iterator<int>    result(cout," ");
  cout << '"' << is.str() << "\" の各単語の長さ :";
  while ( first != last ) {
    *result = first->size();
    ++result;
    ++first;
  }
  cout << endl;
}

void std_streambuf_iter() {
  cout << "istreambuf_iterator, ostreambuf_iterator" << endl;
  istringstream is("this string is on istringstream");
  istreambuf_iterator<char> first(is);
  istreambuf_iterator<char> last;
  ostreambuf_iterator<char> result(cout);
  cout << '"' << is.str() << "\" の各文字を大文字に :";
  ctype<char> ct;
  while ( first != last ) {
    *result = ct.toupper(*first);
    ++result;
    ++first;
  }
  cout << endl;
}