迭代器---STL源码剖析

约定不等于承诺〃 2022-05-18 06:49 338阅读 0赞

写在前面

关于STL源码剖析当中对于迭代器这一章内容的一些重点技巧的理解。
STL设计的一些启发性思维是值得学习的。重在总结,以备后用。

迭代器

迭代器是一种智能指针。最重要的工作就是对opperator* 和 operator->的重载。

对于operator->的重载需要注意:p->size()会被编译器自动绑定其成员,会被翻译成:p->operztor->()->size();
所以重载operator->操作符的时候应该返回的是指针。

如果设计迭代器的人和设计容器的人是分离的,那么设计迭代器的人就必须知道关于容器的一些内部实现,比如++操作是通过容器的什么成员函数实现的等等。所以既然无可避免,就干脆把迭代器的开发工作交给各个容器的开发者,这样所有的实现都可以被封装不被外界得知。所以每个容器都有自己的专属迭代器。

迭代器相应型别

需求:需要获得迭代器所指对象的型别为型别使用。
难点:c++本身不支持类型的获取,RTTI当中的typeid()只能获得类型的别名用来做判断并不能拿来声明变量。
解决:traits技巧。

1 . 使用traits萃取类型的某些特定的特性(比如迭代器对象所指的类型)。

  1. template<class IterT>
  2. struct my_iterator_traits {
  3. typedef typename IterT::value_type value_type;
  4. };

my_iterator_traits就获取IterT的内嵌 类型value_type。在IterT的内部定义了所指向的类型T的别名为value_type.所以我这里只需要萃取这个value_type就相当于萃取出T而T是IterT的模板参数是变化的而value_type是不变的。这样就成功的封装了变化点,用不变的value_type表示了变化的T。这是这个技巧的成功之处。所以我们只需要在每个迭代器模板当中typedef T value_type,就可以用上面的萃取模板萃取出IterT所指向的类型。

对于原生指针非类类型采用模板的偏特化的方式解决:

  1. template<class T>
  2. struct my_iterator_traits<T*> {
  3. typedef T value_type;
  4. };

偏特化:如果拥有一个或者多个模板参数,我们可以针对其中某个或者数个非全部进行特化。
但是如果是指向常数对象的指针我们得到的value_type是const T并不是我们想要的T,我们可以提供下面的偏特化版本:

  1. template<class T>
  2. struct my_iterator_traits<const T*> {
  3. typedef T value_type;
  4. };

现在无论是类类型还是原生指针,或者是指向常数对象的指针都可以使用iterator_traits模板萃取出来正确的value_type.

所以为了此项工作可以正确完成,每一个迭代器必须遵守约定,自行以内嵌型别定义的方式定义出相应型别的value_type。iterator_traits再次封装了变化点将变化迭代器类型,原生指针全部封装到使用iterator_traits就可以解决。

最常用到的迭代器相应的型别有5种:value_type,difference_type,pointer,reference,iterator_catagoly。

迭代器相应型别1
value_type是指迭代器所指对象的类型。
迭代器相应类型2
difference_type:
用来表示两个迭代器之间的距离。
迭代器相应型别3
*p的型别就是reference_type。从迭代器所指之对象的内容是否允许改变的角度将迭代器分为2类。
迭代器相应型别4
传回一个指针指向迭代器所指之物。
迭代器相应型别5

迭代器的分类:input_iterator:只读只支持++操作。output_iterator:只写,只支持++操作。Forward_iterator:允许写入,在迭代器所形成的区间上进行读写操作,只支持++操作。Bidirectional_iterator:支持双向移动,支持++,–操作。Random Access iterator:支持所有的指针操作,随机访问,功能最强大。
问题:执行期间才决定使用哪一个版本的函数。影响程序效率。
解决:编译器就选择正确的版本,函数重载机制。

任何一个迭代器(包括原生指针)都应该永远落在该迭代器所隶属的各个类型当中最强化的那个。这样才能够达到最佳的效率。
STL算法的一个命名规则:以算法所能够接受的最低阶的迭代器类型来为其迭代器型别参数命名。

给每个迭代器定义一个型别iterator_category。通过萃取模板萃取出来这个型别,使用函数重载的机制,使得迭代器被最大化的使用达到最大的访问效率。由于采用了标记型别的类作为型别,所以可以采用继承关系,当没有完全参数匹配的重载函数时,可以调用相应参数为基类类型的重载函数。

问题:为了符合规范,任何迭代器都需要提供以上5个内嵌的型别。一旦遗漏将无法与其他的STL组件搭配。
解决:提供一个模板基类iterator每个新设计的迭代器继承自这个基类他包含了所有的所需规范。

STL < stl_iterator.h>源码

  1. #ifndef __SGI_STL_INTERNAL_ITERATOR_H
  2. #define __SGI_STL_INTERNAL_ITERATOR_H
  3. __STL_BEGIN_NAMESPACE
  4. struct input_iterator_tag {};
  5. struct output_iterator_tag {};
  6. struct forward_iterator_tag : public input_iterator_tag {};
  7. struct bidirectional_iterator_tag : public forward_iterator_tag {};
  8. struct random_access_iterator_tag : public bidirectional_iterator_tag {};
  9. template <class T, class Distance> struct input_iterator {
  10. typedef input_iterator_tag iterator_category;
  11. typedef T value_type;
  12. typedef Distance difference_type;
  13. typedef T* pointer;
  14. typedef T& reference;
  15. };
  16. struct output_iterator {
  17. typedef output_iterator_tag iterator_category;
  18. typedef void value_type;
  19. typedef void difference_type;
  20. typedef void pointer;
  21. typedef void reference;
  22. };
  23. template <class T, class Distance> struct forward_iterator {
  24. typedef forward_iterator_tag iterator_category;
  25. typedef T value_type;
  26. typedef Distance difference_type;
  27. typedef T* pointer;
  28. typedef T& reference;
  29. };
  30. template <class T, class Distance> struct bidirectional_iterator {
  31. typedef bidirectional_iterator_tag iterator_category;
  32. typedef T value_type;
  33. typedef Distance difference_type;
  34. typedef T* pointer;
  35. typedef T& reference;
  36. };
  37. template <class T, class Distance> struct random_access_iterator {
  38. typedef random_access_iterator_tag iterator_category;
  39. typedef T value_type;
  40. typedef Distance difference_type;
  41. typedef T* pointer;
  42. typedef T& reference;
  43. };
  44. #ifdef __STL_USE_NAMESPACES
  45. template <class Category, class T, class Distance = ptrdiff_t,
  46. class Pointer = T*, class Reference = T&>
  47. struct iterator {
  48. typedef Category iterator_category;
  49. typedef T value_type;
  50. typedef Distance difference_type;
  51. typedef Pointer pointer;
  52. typedef Reference reference;
  53. };
  54. #endif /* __STL_USE_NAMESPACES */
  55. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  56. template <class Iterator>
  57. struct iterator_traits {
  58. typedef typename Iterator::iterator_category iterator_category;
  59. typedef typename Iterator::value_type value_type;
  60. typedef typename Iterator::difference_type difference_type;
  61. typedef typename Iterator::pointer pointer;
  62. typedef typename Iterator::reference reference;
  63. };
  64. template <class T>
  65. struct iterator_traits<T*> {
  66. typedef random_access_iterator_tag iterator_category;
  67. typedef T value_type;
  68. typedef ptrdiff_t difference_type;
  69. typedef T* pointer;
  70. typedef T& reference;
  71. };
  72. template <class T>
  73. struct iterator_traits<const T*> {
  74. typedef random_access_iterator_tag iterator_category;
  75. typedef T value_type;
  76. typedef ptrdiff_t difference_type;
  77. typedef const T* pointer;
  78. typedef const T& reference;
  79. };
  80. template <class Iterator>
  81. inline typename iterator_traits<Iterator>::iterator_category
  82. iterator_category(const Iterator&) {
  83. typedef typename iterator_traits<Iterator>::iterator_category category;
  84. return category();
  85. }
  86. template <class Iterator>
  87. inline typename iterator_traits<Iterator>::difference_type*
  88. distance_type(const Iterator&) {
  89. return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
  90. }
  91. template <class Iterator>
  92. inline typename iterator_traits<Iterator>::value_type*
  93. value_type(const Iterator&) {
  94. return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
  95. }
  96. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  97. template <class T, class Distance>
  98. inline input_iterator_tag
  99. iterator_category(const input_iterator<T, Distance>&) {
  100. return input_iterator_tag();
  101. }
  102. inline output_iterator_tag iterator_category(const output_iterator&) {
  103. return output_iterator_tag();
  104. }
  105. template <class T, class Distance>
  106. inline forward_iterator_tag
  107. iterator_category(const forward_iterator<T, Distance>&) {
  108. return forward_iterator_tag();
  109. }
  110. template <class T, class Distance>
  111. inline bidirectional_iterator_tag
  112. iterator_category(const bidirectional_iterator<T, Distance>&) {
  113. return bidirectional_iterator_tag();
  114. }
  115. template <class T, class Distance>
  116. inline random_access_iterator_tag
  117. iterator_category(const random_access_iterator<T, Distance>&) {
  118. return random_access_iterator_tag();
  119. }
  120. template <class T>
  121. inline random_access_iterator_tag iterator_category(const T*) {
  122. return random_access_iterator_tag();
  123. }
  124. template <class T, class Distance>
  125. inline T* value_type(const input_iterator<T, Distance>&) {
  126. return (T*)(0);
  127. }
  128. template <class T, class Distance>
  129. inline T* value_type(const forward_iterator<T, Distance>&) {
  130. return (T*)(0);
  131. }
  132. template <class T, class Distance>
  133. inline T* value_type(const bidirectional_iterator<T, Distance>&) {
  134. return (T*)(0);
  135. }
  136. template <class T, class Distance>
  137. inline T* value_type(const random_access_iterator<T, Distance>&) {
  138. return (T*)(0);
  139. }
  140. template <class T>
  141. inline T* value_type(const T*) { return (T*)(0); }
  142. template <class T, class Distance>
  143. inline Distance* distance_type(const input_iterator<T, Distance>&) {
  144. return (Distance*)(0);
  145. }
  146. template <class T, class Distance>
  147. inline Distance* distance_type(const forward_iterator<T, Distance>&) {
  148. return (Distance*)(0);
  149. }
  150. template <class T, class Distance>
  151. inline Distance*
  152. distance_type(const bidirectional_iterator<T, Distance>&) {
  153. return (Distance*)(0);
  154. }
  155. template <class T, class Distance>
  156. inline Distance*
  157. distance_type(const random_access_iterator<T, Distance>&) {
  158. return (Distance*)(0);
  159. }
  160. template <class T>
  161. inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*)(0); }
  162. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  163. template <class InputIterator, class Distance>
  164. inline void __distance(InputIterator first, InputIterator last, Distance& n,
  165. input_iterator_tag) {
  166. while (first != last) { ++first; ++n; }
  167. }
  168. template <class RandomAccessIterator, class Distance>
  169. inline void __distance(RandomAccessIterator first, RandomAccessIterator last,
  170. Distance& n, random_access_iterator_tag) {
  171. n += last - first;
  172. }
  173. template <class InputIterator, class Distance>
  174. inline void distance(InputIterator first, InputIterator last, Distance& n) {
  175. __distance(first, last, n, iterator_category(first));
  176. }
  177. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  178. template <class InputIterator>
  179. inline iterator_traits<InputIterator>::difference_type
  180. __distance(InputIterator first, InputIterator last, input_iterator_tag) {
  181. iterator_traits<InputIterator>::difference_type n = 0;
  182. while (first != last) {
  183. ++first; ++n;
  184. }
  185. return n;
  186. }
  187. template <class RandomAccessIterator>
  188. inline iterator_traits<RandomAccessIterator>::difference_type
  189. __distance(RandomAccessIterator first, RandomAccessIterator last,
  190. random_access_iterator_tag) {
  191. return last - first;
  192. }
  193. template <class InputIterator>
  194. inline iterator_traits<InputIterator>::difference_type
  195. distance(InputIterator first, InputIterator last) {
  196. typedef typename iterator_traits<InputIterator>::iterator_category category;
  197. return __distance(first, last, category());
  198. }
  199. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  200. template <class InputIterator, class Distance>
  201. inline void __advance(InputIterator& i, Distance n, input_iterator_tag) {
  202. while (n--) ++i;
  203. }
  204. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  205. #pragma set woff 1183
  206. #endif
  207. template <class BidirectionalIterator, class Distance>
  208. inline void __advance(BidirectionalIterator& i, Distance n,
  209. bidirectional_iterator_tag) {
  210. if (n >= 0)
  211. while (n--) ++i;
  212. else
  213. while (n++) --i;
  214. }
  215. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  216. #pragma reset woff 1183
  217. #endif
  218. template <class RandomAccessIterator, class Distance>
  219. inline void __advance(RandomAccessIterator& i, Distance n,
  220. random_access_iterator_tag) {
  221. i += n;
  222. }
  223. template <class InputIterator, class Distance>
  224. inline void advance(InputIterator& i, Distance n) {
  225. __advance(i, n, iterator_category(i));
  226. }
  227. template <class Container>
  228. class back_insert_iterator {
  229. protected:
  230. Container* container;
  231. public:
  232. typedef output_iterator_tag iterator_category;
  233. typedef void value_type;
  234. typedef void difference_type;
  235. typedef void pointer;
  236. typedef void reference;
  237. explicit back_insert_iterator(Container& x) : container(&x) {}
  238. back_insert_iterator<Container>&
  239. operator=(const typename Container::value_type& value) {
  240. container->push_back(value);
  241. return *this;
  242. }
  243. back_insert_iterator<Container>& operator*() { return *this; }
  244. back_insert_iterator<Container>& operator++() { return *this; }
  245. back_insert_iterator<Container>& operator++(int) { return *this; }
  246. };
  247. #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  248. template <class Container>
  249. inline output_iterator_tag
  250. iterator_category(const back_insert_iterator<Container>&)
  251. {
  252. return output_iterator_tag();
  253. }
  254. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  255. template <class Container>
  256. inline back_insert_iterator<Container> back_inserter(Container& x) {
  257. return back_insert_iterator<Container>(x);
  258. }
  259. template <class Container>
  260. class front_insert_iterator {
  261. protected:
  262. Container* container;
  263. public:
  264. typedef output_iterator_tag iterator_category;
  265. typedef void value_type;
  266. typedef void difference_type;
  267. typedef void pointer;
  268. typedef void reference;
  269. explicit front_insert_iterator(Container& x) : container(&x) {}
  270. front_insert_iterator<Container>&
  271. operator=(const typename Container::value_type& value) {
  272. container->push_front(value);
  273. return *this;
  274. }
  275. front_insert_iterator<Container>& operator*() { return *this; }
  276. front_insert_iterator<Container>& operator++() { return *this; }
  277. front_insert_iterator<Container>& operator++(int) { return *this; }
  278. };
  279. #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  280. template <class Container>
  281. inline output_iterator_tag
  282. iterator_category(const front_insert_iterator<Container>&)
  283. {
  284. return output_iterator_tag();
  285. }
  286. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  287. template <class Container>
  288. inline front_insert_iterator<Container> front_inserter(Container& x) {
  289. return front_insert_iterator<Container>(x);
  290. }
  291. template <class Container>
  292. class insert_iterator {
  293. protected:
  294. Container* container;
  295. typename Container::iterator iter;
  296. public:
  297. typedef output_iterator_tag iterator_category;
  298. typedef void value_type;
  299. typedef void difference_type;
  300. typedef void pointer;
  301. typedef void reference;
  302. insert_iterator(Container& x, typename Container::iterator i)
  303. : container(&x), iter(i) {}
  304. insert_iterator<Container>&
  305. operator=(const typename Container::value_type& value) {
  306. iter = container->insert(iter, value);
  307. ++iter;
  308. return *this;
  309. }
  310. insert_iterator<Container>& operator*() { return *this; }
  311. insert_iterator<Container>& operator++() { return *this; }
  312. insert_iterator<Container>& operator++(int) { return *this; }
  313. };
  314. #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  315. template <class Container>
  316. inline output_iterator_tag
  317. iterator_category(const insert_iterator<Container>&)
  318. {
  319. return output_iterator_tag();
  320. }
  321. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  322. template <class Container, class Iterator>
  323. inline insert_iterator<Container> inserter(Container& x, Iterator i) {
  324. typedef typename Container::iterator iter;
  325. return insert_iterator<Container>(x, iter(i));
  326. }
  327. #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
  328. template <class BidirectionalIterator, class T, class Reference = T&,
  329. class Distance = ptrdiff_t>
  330. #else
  331. template <class BidirectionalIterator, class T, class Reference,
  332. class Distance>
  333. #endif
  334. class reverse_bidirectional_iterator {
  335. typedef reverse_bidirectional_iterator<BidirectionalIterator, T, Reference,
  336. Distance> self;
  337. protected:
  338. BidirectionalIterator current;
  339. public:
  340. typedef bidirectional_iterator_tag iterator_category;
  341. typedef T value_type;
  342. typedef Distance difference_type;
  343. typedef T* pointer;
  344. typedef Reference reference;
  345. reverse_bidirectional_iterator() {}
  346. explicit reverse_bidirectional_iterator(BidirectionalIterator x)
  347. : current(x) {}
  348. BidirectionalIterator base() const { return current; }
  349. Reference operator*() const {
  350. BidirectionalIterator tmp = current;
  351. return *--tmp;
  352. }
  353. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  354. pointer operator->() const { return &(operator*()); }
  355. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  356. self& operator++() {
  357. --current;
  358. return *this;
  359. }
  360. self operator++(int) {
  361. self tmp = *this;
  362. --current;
  363. return tmp;
  364. }
  365. self& operator--() {
  366. ++current;
  367. return *this;
  368. }
  369. self operator--(int) {
  370. self tmp = *this;
  371. ++current;
  372. return tmp;
  373. }
  374. };
  375. #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  376. template <class BidirectionalIterator, class T, class Reference,
  377. class Distance>
  378. inline bidirectional_iterator_tag
  379. iterator_category(const reverse_bidirectional_iterator<BidirectionalIterator,
  380. T,
  381. Reference, Distance>&) {
  382. return bidirectional_iterator_tag();
  383. }
  384. template <class BidirectionalIterator, class T, class Reference,
  385. class Distance>
  386. inline T*
  387. value_type(const reverse_bidirectional_iterator<BidirectionalIterator, T,
  388. Reference, Distance>&) {
  389. return (T*) 0;
  390. }
  391. template <class BidirectionalIterator, class T, class Reference,
  392. class Distance>
  393. inline Distance*
  394. distance_type(const reverse_bidirectional_iterator<BidirectionalIterator, T,
  395. Reference, Distance>&) {
  396. return (Distance*) 0;
  397. }
  398. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  399. template <class BidirectionalIterator, class T, class Reference,
  400. class Distance>
  401. inline bool operator==(
  402. const reverse_bidirectional_iterator<BidirectionalIterator, T, Reference,
  403. Distance>& x,
  404. const reverse_bidirectional_iterator<BidirectionalIterator, T, Reference,
  405. Distance>& y) {
  406. return x.base() == y.base();
  407. }
  408. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  409. // This is the new version of reverse_iterator, as defined in the
  410. // draft C++ standard. It relies on the iterator_traits template,
  411. // which in turn relies on partial specialization. The class
  412. // reverse_bidirectional_iterator is no longer part of the draft
  413. // standard, but it is retained for backward compatibility.
  414. template <class Iterator>
  415. class reverse_iterator
  416. {
  417. protected:
  418. Iterator current;
  419. public:
  420. typedef typename iterator_traits<Iterator>::iterator_category
  421. iterator_category;
  422. typedef typename iterator_traits<Iterator>::value_type
  423. value_type;
  424. typedef typename iterator_traits<Iterator>::difference_type
  425. difference_type;
  426. typedef typename iterator_traits<Iterator>::pointer
  427. pointer;
  428. typedef typename iterator_traits<Iterator>::reference
  429. reference;
  430. typedef Iterator iterator_type;
  431. typedef reverse_iterator<Iterator> self;
  432. public:
  433. reverse_iterator() {}
  434. explicit reverse_iterator(iterator_type x) : current(x) {}
  435. reverse_iterator(const self& x) : current(x.current) {}
  436. #ifdef __STL_MEMBER_TEMPLATES
  437. template <class Iter>
  438. reverse_iterator(const reverse_iterator<Iter>& x) : current(x.current) {}
  439. #endif /* __STL_MEMBER_TEMPLATES */
  440. iterator_type base() const { return current; }
  441. reference operator*() const {
  442. Iterator tmp = current;
  443. return *--tmp;
  444. }
  445. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  446. pointer operator->() const { return &(operator*()); }
  447. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  448. self& operator++() {
  449. --current;
  450. return *this;
  451. }
  452. self operator++(int) {
  453. self tmp = *this;
  454. --current;
  455. return tmp;
  456. }
  457. self& operator--() {
  458. ++current;
  459. return *this;
  460. }
  461. self operator--(int) {
  462. self tmp = *this;
  463. ++current;
  464. return tmp;
  465. }
  466. self operator+(difference_type n) const {
  467. return self(current - n);
  468. }
  469. self& operator+=(difference_type n) {
  470. current -= n;
  471. return *this;
  472. }
  473. self operator-(difference_type n) const {
  474. return self(current + n);
  475. }
  476. self& operator-=(difference_type n) {
  477. current += n;
  478. return *this;
  479. }
  480. reference operator[](difference_type n) const { return *(*this + n); }
  481. };
  482. template <class Iterator>
  483. inline bool operator==(const reverse_iterator<Iterator>& x,
  484. const reverse_iterator<Iterator>& y) {
  485. return x.base() == y.base();
  486. }
  487. template <class Iterator>
  488. inline bool operator<(const reverse_iterator<Iterator>& x,
  489. const reverse_iterator<Iterator>& y) {
  490. return y.base() < x.base();
  491. }
  492. template <class Iterator>
  493. inline typename reverse_iterator<Iterator>::difference_type
  494. operator-(const reverse_iterator<Iterator>& x,
  495. const reverse_iterator<Iterator>& y) {
  496. return y.base() - x.base();
  497. }
  498. template <class Iterator>
  499. inline reverse_iterator<Iterator>
  500. operator+(reverse_iterator<Iterator>::difference_type n,
  501. const reverse_iterator<Iterator>& x) {
  502. return reverse_iterator<Iterator>(x.base() - n);
  503. }
  504. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  505. // This is the old version of reverse_iterator, as found in the original
  506. // HP STL. It does not use partial specialization.
  507. #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
  508. template <class RandomAccessIterator, class T, class Reference = T&,
  509. class Distance = ptrdiff_t>
  510. #else
  511. template <class RandomAccessIterator, class T, class Reference,
  512. class Distance>
  513. #endif
  514. class reverse_iterator {
  515. typedef reverse_iterator<RandomAccessIterator, T, Reference, Distance>
  516. self;
  517. protected:
  518. RandomAccessIterator current;
  519. public:
  520. typedef random_access_iterator_tag iterator_category;
  521. typedef T value_type;
  522. typedef Distance difference_type;
  523. typedef T* pointer;
  524. typedef Reference reference;
  525. reverse_iterator() {}
  526. explicit reverse_iterator(RandomAccessIterator x) : current(x) {}
  527. RandomAccessIterator base() const { return current; }
  528. Reference operator*() const { return *(current - 1); }
  529. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  530. pointer operator->() const { return &(operator*()); }
  531. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  532. self& operator++() {
  533. --current;
  534. return *this;
  535. }
  536. self operator++(int) {
  537. self tmp = *this;
  538. --current;
  539. return tmp;
  540. }
  541. self& operator--() {
  542. ++current;
  543. return *this;
  544. }
  545. self operator--(int) {
  546. self tmp = *this;
  547. ++current;
  548. return tmp;
  549. }
  550. self operator+(Distance n) const {
  551. return self(current - n);
  552. }
  553. self& operator+=(Distance n) {
  554. current -= n;
  555. return *this;
  556. }
  557. self operator-(Distance n) const {
  558. return self(current + n);
  559. }
  560. self& operator-=(Distance n) {
  561. current += n;
  562. return *this;
  563. }
  564. Reference operator[](Distance n) const { return *(*this + n); }
  565. };
  566. template <class RandomAccessIterator, class T, class Reference, class Distance>
  567. inline random_access_iterator_tag
  568. iterator_category(const reverse_iterator<RandomAccessIterator, T,
  569. Reference, Distance>&) {
  570. return random_access_iterator_tag();
  571. }
  572. template <class RandomAccessIterator, class T, class Reference, class Distance>
  573. inline T* value_type(const reverse_iterator<RandomAccessIterator, T,
  574. Reference, Distance>&) {
  575. return (T*) 0;
  576. }
  577. template <class RandomAccessIterator, class T, class Reference, class Distance>
  578. inline Distance* distance_type(const reverse_iterator<RandomAccessIterator, T,
  579. Reference, Distance>&) {
  580. return (Distance*) 0;
  581. }
  582. template <class RandomAccessIterator, class T, class Reference, class Distance>
  583. inline bool operator==(const reverse_iterator<RandomAccessIterator, T,
  584. Reference, Distance>& x,
  585. const reverse_iterator<RandomAccessIterator, T,
  586. Reference, Distance>& y) {
  587. return x.base() == y.base();
  588. }
  589. template <class RandomAccessIterator, class T, class Reference, class Distance>
  590. inline bool operator<(const reverse_iterator<RandomAccessIterator, T,
  591. Reference, Distance>& x,
  592. const reverse_iterator<RandomAccessIterator, T,
  593. Reference, Distance>& y) {
  594. return y.base() < x.base();
  595. }
  596. template <class RandomAccessIterator, class T, class Reference, class Distance>
  597. inline Distance operator-(const reverse_iterator<RandomAccessIterator, T,
  598. Reference, Distance>& x,
  599. const reverse_iterator<RandomAccessIterator, T,
  600. Reference, Distance>& y) {
  601. return y.base() - x.base();
  602. }
  603. template <class RandomAccessIter, class T, class Ref, class Dist>
  604. inline reverse_iterator<RandomAccessIter, T, Ref, Dist>
  605. operator+(Dist n, const reverse_iterator<RandomAccessIter, T, Ref, Dist>& x) {
  606. return reverse_iterator<RandomAccessIter, T, Ref, Dist>(x.base() - n);
  607. }
  608. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  609. template <class T, class Distance = ptrdiff_t>
  610. class istream_iterator {
  611. friend bool
  612. operator== __STL_NULL_TMPL_ARGS (const istream_iterator<T, Distance>& x,
  613. const istream_iterator<T, Distance>& y);
  614. protected:
  615. istream* stream;
  616. T value;
  617. bool end_marker;
  618. void read() {
  619. end_marker = (*stream) ? true : false;
  620. if (end_marker) *stream >> value;
  621. end_marker = (*stream) ? true : false;
  622. }
  623. public:
  624. typedef input_iterator_tag iterator_category;
  625. typedef T value_type;
  626. typedef Distance difference_type;
  627. typedef const T* pointer;
  628. typedef const T& reference;
  629. istream_iterator() : stream(&cin), end_marker(false) {}
  630. istream_iterator(istream& s) : stream(&s) { read(); }
  631. reference operator*() const { return value; }
  632. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  633. pointer operator->() const { return &(operator*()); }
  634. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  635. istream_iterator<T, Distance>& operator++() {
  636. read();
  637. return *this;
  638. }
  639. istream_iterator<T, Distance> operator++(int) {
  640. istream_iterator<T, Distance> tmp = *this;
  641. read();
  642. return tmp;
  643. }
  644. };
  645. #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  646. template <class T, class Distance>
  647. inline input_iterator_tag
  648. iterator_category(const istream_iterator<T, Distance>&) {
  649. return input_iterator_tag();
  650. }
  651. template <class T, class Distance>
  652. inline T* value_type(const istream_iterator<T, Distance>&) { return (T*) 0; }
  653. template <class T, class Distance>
  654. inline Distance* distance_type(const istream_iterator<T, Distance>&) {
  655. return (Distance*) 0;
  656. }
  657. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  658. template <class T, class Distance>
  659. inline bool operator==(const istream_iterator<T, Distance>& x,
  660. const istream_iterator<T, Distance>& y) {
  661. return x.stream == y.stream && x.end_marker == y.end_marker ||
  662. x.end_marker == false && y.end_marker == false;
  663. }
  664. template <class T>
  665. class ostream_iterator {
  666. protected:
  667. ostream* stream;
  668. const char* string;
  669. public:
  670. typedef output_iterator_tag iterator_category;
  671. typedef void value_type;
  672. typedef void difference_type;
  673. typedef void pointer;
  674. typedef void reference;
  675. ostream_iterator(ostream& s) : stream(&s), string(0) {}
  676. ostream_iterator(ostream& s, const char* c) : stream(&s), string(c) {}
  677. ostream_iterator<T>& operator=(const T& value) {
  678. *stream << value;
  679. if (string) *stream << string;
  680. return *this;
  681. }
  682. ostream_iterator<T>& operator*() { return *this; }
  683. ostream_iterator<T>& operator++() { return *this; }
  684. ostream_iterator<T>& operator++(int) { return *this; }
  685. };
  686. #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  687. template <class T>
  688. inline output_iterator_tag
  689. iterator_category(const ostream_iterator<T>&) {
  690. return output_iterator_tag();
  691. }
  692. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  693. __STL_END_NAMESPACE
  694. #endif /* __SGI_STL_INTERNAL_ITERATOR_H */
  695. // Local Variables:
  696. // mode:C++
  697. // End:

发表评论

表情:
评论列表 (有 0 条评论,338人围观)

还没有评论,来说两句吧...

相关阅读

    相关 STL剖析——

    前言 在STL的思想中,容器和算法是彼此独立设计的,再通过某种方式使它们连接;而迭代器是使算法独立于使用的容器类型,即迭代器是连接算法和容器的方法。由于迭代器是一种行为

    相关 STL

    什么是迭代器 迭代器是STL中行为类似指针的设计模式,它可以提供了一种对容器中的对象的访问方法;并且它没有暴露容器中内部的表述方式。 例如STL中的map和set,它

    相关 STL&&失效

    1.说说设计模式?(迭代器模式)         迭代器模式作为STL的六大组件之一,通俗来讲,它就是用来遍历容器的,对容器进行一定的操作。我们通常使用的容器vector