iterators.h 7.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251
  1. #ifndef ITERATORS_H
  2. #define ITERATORS_H
  3. #include <iterator>
  4. template <class It>
  5. class input_iterator
  6. {
  7. It it_;
  8. template <class U> friend class input_iterator;
  9. public:
  10. typedef std::input_iterator_tag iterator_category;
  11. typedef typename std::iterator_traits<It>::value_type value_type;
  12. typedef typename std::iterator_traits<It>::difference_type difference_type;
  13. typedef It pointer;
  14. typedef typename std::iterator_traits<It>::reference reference;
  15. It base() const {return it_;}
  16. input_iterator() : it_() {}
  17. explicit input_iterator(It it) : it_(it) {}
  18. template <class U>
  19. input_iterator(const input_iterator<U>& u) :it_(u.it_) {}
  20. reference operator*() const {return *it_;}
  21. pointer operator->() const {return it_;}
  22. input_iterator& operator++() {++it_; return *this;}
  23. input_iterator operator++(int)
  24. {input_iterator tmp(*this); ++(*this); return tmp;}
  25. friend bool operator==(const input_iterator& x, const input_iterator& y)
  26. {return x.it_ == y.it_;}
  27. friend bool operator!=(const input_iterator& x, const input_iterator& y)
  28. {return !(x == y);}
  29. };
  30. template <class T, class U>
  31. inline
  32. bool
  33. operator==(const input_iterator<T>& x, const input_iterator<U>& y)
  34. {
  35. return x.base() == y.base();
  36. }
  37. template <class T, class U>
  38. inline
  39. bool
  40. operator!=(const input_iterator<T>& x, const input_iterator<U>& y)
  41. {
  42. return !(x == y);
  43. }
  44. template <class It>
  45. class forward_iterator
  46. {
  47. It it_;
  48. template <class U> friend class forward_iterator;
  49. public:
  50. typedef std::forward_iterator_tag iterator_category;
  51. typedef typename std::iterator_traits<It>::value_type value_type;
  52. typedef typename std::iterator_traits<It>::difference_type difference_type;
  53. typedef It pointer;
  54. typedef typename std::iterator_traits<It>::reference reference;
  55. It base() const {return it_;}
  56. forward_iterator() : it_() {}
  57. explicit forward_iterator(It it) : it_(it) {}
  58. template <class U>
  59. forward_iterator(const forward_iterator<U>& u) :it_(u.it_) {}
  60. reference operator*() const {return *it_;}
  61. pointer operator->() const {return it_;}
  62. forward_iterator& operator++() {++it_; return *this;}
  63. forward_iterator operator++(int)
  64. {forward_iterator tmp(*this); ++(*this); return tmp;}
  65. friend bool operator==(const forward_iterator& x, const forward_iterator& y)
  66. {return x.it_ == y.it_;}
  67. friend bool operator!=(const forward_iterator& x, const forward_iterator& y)
  68. {return !(x == y);}
  69. };
  70. template <class T, class U>
  71. inline
  72. bool
  73. operator==(const forward_iterator<T>& x, const forward_iterator<U>& y)
  74. {
  75. return x.base() == y.base();
  76. }
  77. template <class T, class U>
  78. inline
  79. bool
  80. operator!=(const forward_iterator<T>& x, const forward_iterator<U>& y)
  81. {
  82. return !(x == y);
  83. }
  84. template <class It>
  85. class bidirectional_iterator
  86. {
  87. It it_;
  88. template <class U> friend class bidirectional_iterator;
  89. public:
  90. typedef std::bidirectional_iterator_tag iterator_category;
  91. typedef typename std::iterator_traits<It>::value_type value_type;
  92. typedef typename std::iterator_traits<It>::difference_type difference_type;
  93. typedef It pointer;
  94. typedef typename std::iterator_traits<It>::reference reference;
  95. It base() const {return it_;}
  96. bidirectional_iterator() : it_() {}
  97. explicit bidirectional_iterator(It it) : it_(it) {}
  98. template <class U>
  99. bidirectional_iterator(const bidirectional_iterator<U>& u) :it_(u.it_) {}
  100. reference operator*() const {return *it_;}
  101. pointer operator->() const {return it_;}
  102. bidirectional_iterator& operator++() {++it_; return *this;}
  103. bidirectional_iterator operator++(int)
  104. {bidirectional_iterator tmp(*this); ++(*this); return tmp;}
  105. bidirectional_iterator& operator--() {--it_; return *this;}
  106. bidirectional_iterator operator--(int)
  107. {bidirectional_iterator tmp(*this); --(*this); return tmp;}
  108. };
  109. template <class T, class U>
  110. inline
  111. bool
  112. operator==(const bidirectional_iterator<T>& x, const bidirectional_iterator<U>& y)
  113. {
  114. return x.base() == y.base();
  115. }
  116. template <class T, class U>
  117. inline
  118. bool
  119. operator!=(const bidirectional_iterator<T>& x, const bidirectional_iterator<U>& y)
  120. {
  121. return !(x == y);
  122. }
  123. template <class It>
  124. class random_access_iterator
  125. {
  126. It it_;
  127. template <class U> friend class random_access_iterator;
  128. public:
  129. typedef std::random_access_iterator_tag iterator_category;
  130. typedef typename std::iterator_traits<It>::value_type value_type;
  131. typedef typename std::iterator_traits<It>::difference_type difference_type;
  132. typedef It pointer;
  133. typedef typename std::iterator_traits<It>::reference reference;
  134. It base() const {return it_;}
  135. random_access_iterator() : it_() {}
  136. explicit random_access_iterator(It it) : it_(it) {}
  137. template <class U>
  138. random_access_iterator(const random_access_iterator<U>& u) :it_(u.it_) {}
  139. reference operator*() const {return *it_;}
  140. pointer operator->() const {return it_;}
  141. random_access_iterator& operator++() {++it_; return *this;}
  142. random_access_iterator operator++(int)
  143. {random_access_iterator tmp(*this); ++(*this); return tmp;}
  144. random_access_iterator& operator--() {--it_; return *this;}
  145. random_access_iterator operator--(int)
  146. {random_access_iterator tmp(*this); --(*this); return tmp;}
  147. random_access_iterator& operator+=(difference_type n) {it_ += n; return *this;}
  148. random_access_iterator operator+(difference_type n) const
  149. {random_access_iterator tmp(*this); tmp += n; return tmp;}
  150. friend random_access_iterator operator+(difference_type n, random_access_iterator x)
  151. {x += n; return x;}
  152. random_access_iterator& operator-=(difference_type n) {return *this += -n;}
  153. random_access_iterator operator-(difference_type n) const
  154. {random_access_iterator tmp(*this); tmp -= n; return tmp;}
  155. reference operator[](difference_type n) const {return it_[n];}
  156. };
  157. template <class T, class U>
  158. inline
  159. bool
  160. operator==(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
  161. {
  162. return x.base() == y.base();
  163. }
  164. template <class T, class U>
  165. inline
  166. bool
  167. operator!=(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
  168. {
  169. return !(x == y);
  170. }
  171. template <class T, class U>
  172. inline
  173. bool
  174. operator<(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
  175. {
  176. return x.base() < y.base();
  177. }
  178. template <class T, class U>
  179. inline
  180. bool
  181. operator<=(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
  182. {
  183. return !(y < x);
  184. }
  185. template <class T, class U>
  186. inline
  187. bool
  188. operator>(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
  189. {
  190. return y < x;
  191. }
  192. template <class T, class U>
  193. inline
  194. bool
  195. operator>=(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
  196. {
  197. return !(x < y);
  198. }
  199. template <class T, class U>
  200. inline
  201. typename std::iterator_traits<T>::difference_type
  202. operator-(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
  203. {
  204. return x.base() - y.base();
  205. }
  206. #endif // ITERATORS_H