Mercurial > Algorithms__Sedgewick
changeset 25:3cdac4c29445
Refactored Queue's iterator and const_iterator into a template.
The generic_iterator can be instatiated as either a const or non-const iterator
as needed. It uses <type_traits> std::conditional<>::type create the
appropriate types as needed.
I learned this trick here:
http://www.sj-vs.net/c-implementing-const_iterator-and-non-const-iterator-without-code-duplication/
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Tue, 23 Jun 2015 15:27:26 -0500 |
parents | 028689700a47 |
children | 2cbfacd2a3e9 |
files | algs4-c++/src/Queue.hpp |
diffstat | 1 files changed, 37 insertions(+), 99 deletions(-) [+] |
line diff
1.1 --- a/algs4-c++/src/Queue.hpp Tue Jun 23 14:52:17 2015 -0500 1.2 +++ b/algs4-c++/src/Queue.hpp Tue Jun 23 15:27:26 2015 -0500 1.3 @@ -6,6 +6,7 @@ 1.4 #include <cstddef> 1.5 #include <cassert> 1.6 #include <iterator> 1.7 +#include <type_traits> 1.8 1.9 template <typename T> 1.10 class Queue { 1.11 @@ -22,43 +23,54 @@ 1.12 public: 1.13 1.14 //////////////////////////////////// 1.15 - class iterator : public std::iterator<std::forward_iterator_tag, T> { 1.16 + 1.17 + template <bool is_const = true> 1.18 + class generic_iterator : public std::iterator<std::forward_iterator_tag, T> { 1.19 + 1.20 + private: 1.21 + typedef typename std::conditional<is_const, const Node *, Node *>::type NodePtrType; 1.22 + typedef typename std::conditional<is_const, const T, T>::type ValueType; 1.23 1.24 public: 1.25 1.26 - iterator( Node *c ); 1.27 + generic_iterator( NodePtrType c ) : 1.28 + curr (c) 1.29 + { 1.30 + } 1.31 1.32 - iterator& operator++(); 1.33 - iterator operator++(int); 1.34 + generic_iterator & operator++() { 1.35 + if ( this->curr != nullptr ) { 1.36 + this->curr = this->curr->next; 1.37 + } 1.38 + return *this; 1.39 + } 1.40 1.41 - T operator*(); 1.42 - bool operator!=( typename Queue<T>::iterator ); 1.43 + generic_iterator operator++( int ) { 1.44 + auto t = generic_iterator( *this ); 1.45 + 1.46 + if ( this->curr != nullptr ) { 1.47 + this->curr = this->curr->next; 1.48 + } 1.49 + return t; 1.50 + } 1.51 + 1.52 + ValueType operator*() { 1.53 + return this->curr->item; 1.54 + } 1.55 + 1.56 + bool operator!=( generic_iterator other ) { 1.57 + return this->curr != other.curr; 1.58 + } 1.59 1.60 private: 1.61 1.62 - Node *curr; 1.63 + NodePtrType curr; 1.64 }; 1.65 1.66 //////////////////////////////////// 1.67 1.68 - class const_iterator : public std::iterator<std::forward_iterator_tag, T> { 1.69 - 1.70 - public: 1.71 - 1.72 - const_iterator( const Node *c ); 1.73 - 1.74 - const_iterator& operator++(); 1.75 - const_iterator operator++(int); 1.76 - 1.77 - const T operator*(); 1.78 - bool operator!=( typename Queue<T>::const_iterator ); 1.79 - 1.80 - private: 1.81 - 1.82 - const Node *curr; 1.83 - }; 1.84 - 1.85 - //////////////////////////////////// 1.86 + typedef generic_iterator<true> const_iterator; 1.87 + typedef generic_iterator<false> iterator; 1.88 1.89 Queue( void ); 1.90 ~Queue( void ); 1.91 @@ -182,79 +194,5 @@ 1.92 return Queue<T>::const_iterator( nullptr ); 1.93 } 1.94 1.95 - 1.96 -//////////////////////////////////////////////////////////////////////////////// 1.97 - 1.98 -template <typename T> 1.99 -Queue<T>::iterator::iterator( Node *c ) : 1.100 - curr (c) 1.101 - { 1.102 - } 1.103 - 1.104 -template <typename T> 1.105 -typename Queue<T>::iterator & Queue<T>::iterator::operator++() { 1.106 - if ( this->curr != nullptr ) { 1.107 - this->curr = this->curr->next; 1.108 - } 1.109 - return *this; 1.110 - } 1.111 - 1.112 -template <typename T> 1.113 -typename Queue<T>::iterator Queue<T>::iterator::operator++( int ) { 1.114 - auto t = Queue<T>::iterator( *this ); 1.115 - 1.116 - if ( this->curr != nullptr ) { 1.117 - this->curr = this->curr->next; 1.118 - } 1.119 - return t; 1.120 - } 1.121 - 1.122 -template <typename T> 1.123 -T Queue<T>::iterator::operator*() { 1.124 - return this->curr->item; 1.125 - } 1.126 - 1.127 -template <typename T> 1.128 -bool Queue<T>::iterator::operator!=( typename Queue<T>::iterator other ) { 1.129 - return this->curr != other.curr; 1.130 - } 1.131 - 1.132 -//////////////////////////////////////////////////////////////////////////////// 1.133 - 1.134 -template <typename T> 1.135 -Queue<T>::const_iterator::const_iterator( const Node *c ) : 1.136 - curr (c) 1.137 - { 1.138 - } 1.139 - 1.140 -template <typename T> 1.141 -typename Queue<T>::const_iterator & Queue<T>::const_iterator::operator++() { 1.142 - if ( this->curr != nullptr ) { 1.143 - this->curr = this->curr->next; 1.144 - } 1.145 - return *this; 1.146 - } 1.147 - 1.148 -template <typename T> 1.149 -typename Queue<T>::const_iterator Queue<T>::const_iterator::operator++( int ) { 1.150 - auto t = Queue<T>::const_iterator( *this ); 1.151 - 1.152 - if ( this->curr != nullptr ) { 1.153 - this->curr = this->curr->next; 1.154 - } 1.155 - return t; 1.156 - } 1.157 - 1.158 -template <typename T> 1.159 -const T Queue<T>::const_iterator::operator*() { 1.160 - return this->curr->item; 1.161 - } 1.162 - 1.163 -template <typename T> 1.164 -bool Queue<T>::const_iterator::operator!=( typename Queue<T>::const_iterator other ) { 1.165 - return this->curr != other.curr; 1.166 - } 1.167 - 1.168 - 1.169 #endif 1.170