设计模式之美：Iterator（迭代器）
本文共 20697 字，大约阅读时间需要 68 分钟。
索引
意图
提供一种方法顺序访问一个聚合对象中各个元素，而又不需暴露该对象的内部表示。
Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.
结构
参与者
Iterator
- 迭代器定义访问和遍历元素的接口。
ConcreteIterator
- 具体迭代器实现迭代器接口。
- 对该聚合遍历时跟踪当前位置。
Aggregate
- 聚合定义创建相应迭代器对象的接口。
ConcreteAggregate
- 具体聚合实现创建相应迭代器的接口，该操作返回 ConreteIterator 的实例。
适用性
在以下情况下可以使用 Iterator 模式：
- 访问一个聚合对象的内容而无需暴露它的内部表示。
- 支持对聚合对象的多种遍历。
- 为遍历不同的聚合结构提供一个统一的接口。
效果
- 它支持以不同的方式遍历一个聚合。
- 迭代器简化了聚合的接口。
- 在同一个聚合上可以有多个遍历。
相关模式
- Iterator 常被应用到 Composite 这样的递归结构上。
- 可以使用 Factory Method 模式来实例化多态迭代器。
- Iterator 可以使用 Memento 来捕获一个迭代的状态，在内部存储 Memento。
实现
实现方式（一）：Iterator 模式结构样式代码。
1 namespace IteratorPattern.Implementation1 2 { 3 public abstract class Iterator 4 { 5 public abstract object First(); 6 public abstract object MoveNext(); 7 public abstract object Current(); 8 public abstract bool IsDone(); 9 public abstract void Reset(); 10 } 11 12 public abstract class Aggregate 13 { 14 public abstract Iterator CreateIterator(); 15 } 16 17 public class ConcreteAggregate : Aggregate 18 { 19 private readonly ArrayList _items = new ArrayList(); 20 21 public int Count 22 { 23 get { return _items.Count; } 24 } 25 26 public object this[int index] 27 { 28 get { return _items[index]; } 29 set { _items.Insert(index, value); } 30 } 31 32 public override Iterator CreateIterator() 33 { 34 return new ConcreteIterator(this); 35 } 36 } 37 38 public class ConcreteIterator : Iterator 39 { 40 private readonly ConcreteAggregate _aggregate; 41 private int _currentIndex = 0; 42 43 public ConcreteIterator(ConcreteAggregate aggregate) 44 { 45 _aggregate = aggregate; 46 } 47 48 public override object First() 49 { 50 if (_aggregate.Count > 0) 51 return _aggregate[0]; 52 else 53 return null; 54 } 55 56 public override object MoveNext() 57 { 58 object item = null; 59 if (_currentIndex < _aggregate.Count - 1) 60 { 61 item = _aggregate[++_currentIndex]; 62 } 63 64 return item; 65 } 66 67 public override object Current() 68 { 69 return _aggregate[_currentIndex]; 70 } 71 72 public override bool IsDone() 73 { 74 return _currentIndex >= _aggregate.Count; 75 } 76 77 public override void Reset() 78 { 79 _currentIndex = 0; 80 } 81 } 82 83 public class Client 84 { 85 public void TestCase1() 86 { 87 var aggregate = new ConcreteAggregate(); 88 aggregate[0] = "Apple"; 89 aggregate[1] = "Orange"; 90 aggregate[2] = "Strawberry"; 91 92 var iterator = new ConcreteIterator(aggregate); 93 94 object item = iterator.First(); 95 while (!iterator.IsDone()) 96 { 97 Console.WriteLine(item); 98 item = iterator.MoveNext(); 99 }100 }101 }102 } 实现方式（二）：实现 IEnumerable 中序遍历二叉树。
1 ///2 /// 二叉树节点 3 /// 4 ///The item type 5 public class BinaryTreeNode6 { 7 #region Constructors 8 9 /// 10 /// 二叉树节点 11 /// 12 public BinaryTreeNode() 13 { 14 } 15 16 ///17 /// 二叉树节点 18 /// 19 /// 节点中的值 20 public BinaryTreeNode(T value) 21 { 22 this.Value = value; 23 } 24 25 ///26 /// 二叉树节点 27 /// 28 /// 节点中的值 29 /// 节点的父节点 30 public BinaryTreeNode(T value, BinaryTreeNodeparent) 31 { 32 this.Value = value; 33 this.Parent = parent; 34 } 35 36 /// 37 /// 二叉树节点 38 /// 39 /// 节点中的值 40 /// 节点的父节点 41 /// 节点的左节点 42 /// 节点的右节点 43 public BinaryTreeNode(T value, 44 BinaryTreeNodeparent, 45 BinaryTreeNode left, 46 BinaryTreeNode right) 47 { 48 this.Value = value; 49 this.Right = right; 50 this.Left = left; 51 this.Parent = parent; 52 } 53 54 #endregion 55 56 #region Properties 57 58 /// 59 /// 节点值 60 /// 61 public T Value { get; set; } 62 63 ///64 /// 父节点 65 /// 66 public BinaryTreeNodeParent { get; set; } 67 68 /// 69 /// 左节点 70 /// 71 public BinaryTreeNodeLeft { get; set; } 72 73 /// 74 /// 右节点 75 /// 76 public BinaryTreeNodeRight { get; set; } 77 78 /// 79 /// 是否为根节点 80 /// 81 public bool IsRoot { get { return Parent == null; } } 82 83 ///84 /// 是否为叶子节点 85 /// 86 public bool IsLeaf { get { return Left == null && Right == null; } } 87 88 ///89 /// 是否为可访问的 90 /// 91 internal bool Visited { get; set; } 92 93 #endregion 94 95 #region Public Overridden Functions 96 97 ///98 /// Returns a 100 ///that represents this instance. 99 /// 101 /// A 103 public override string ToString()104 {105 return Value.ToString();106 }107 108 #endregion109 }that represents this instance.102 ///
1 ///2 /// 二叉树 3 /// 4 ///二叉树中节点内容类型 5 [SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")] 6 public class BinaryTree: ICollection , IEnumerable where T : IComparable 7 { 8 #region Constructor 9 10 /// 11 /// 二叉树 12 /// 13 public BinaryTree() 14 { 15 NumberOfNodes = 0; 16 } 17 18 ///19 /// 二叉树 20 /// 21 /// 二叉树根节点 22 public BinaryTree(BinaryTreeNoderoot) 23 : this() 24 { 25 this.Root = root; 26 } 27 28 #endregion 29 30 #region Properties 31 32 /// 33 /// 树的根节点 34 /// 35 public BinaryTreeNodeRoot { get; set; } 36 37 /// 38 /// 树中节点的数量 39 /// 40 protected int NumberOfNodes { get; set; } 41 42 ///43 /// 树是否为空 44 /// 45 public bool IsEmpty { get { return Root == null; } } 46 47 ///48 /// 获取树中节点的最小值 49 /// 50 public T MinValue 51 { 52 get 53 { 54 if (IsEmpty) 55 return default(T); 56 57 BinaryTreeNodeminNode = Root; 58 while (minNode.Left != null) 59 minNode = minNode.Left; 60 61 return minNode.Value; 62 } 63 } 64 65 /// 66 /// 获取树中节点的最大值 67 /// 68 public T MaxValue 69 { 70 get 71 { 72 if (IsEmpty) 73 return default(T); 74 75 BinaryTreeNodemaxNode = Root; 76 while (maxNode.Right != null) 77 maxNode = maxNode.Right; 78 79 return maxNode.Value; 80 } 81 } 82 83 #endregion 84 85 #region IEnumerable Members 86 87 /// 88 /// Returns an enumerator that iterates through the collection. 89 /// 90 ///91 /// A 94 public IEnumerator92 /// that can be used to iterate through the collection. 93 /// GetEnumerator() 95 { 96 foreach (BinaryTreeNode node in Traverse(Root)) 97 { 98 yield return node.Value; 99 }100 }101 102 #endregion103 104 #region IEnumerable Members105 106 /// 107 /// Returns an enumerator that iterates through a collection.108 /// 109 ///110 /// An 113 IEnumerator IEnumerable.GetEnumerator()114 {115 foreach (BinaryTreeNode111 /// object that can be used to iterate through the collection.112 /// node in Traverse(Root))116 {117 yield return node.Value;118 }119 }120 121 #endregion122 123 #region ICollection Members124 125 /// 126 /// 新增节点127 /// 128 /// The object to add to the 129 ///.130 /// The 131 /// 133 public void Add(T item)134 {135 if (Root == null)136 {137 Root = new BinaryTreeNode132 /// is read-only. (item);138 ++NumberOfNodes;139 }140 else141 {142 Insert(item);143 }144 }145 146 /// 147 /// 清除树148 /// 149 public void Clear()150 {151 Root = null;152 }153 154 ///155 /// 树中是否包含此节点156 /// 157 /// The object to locate in the 158 ///.159 /// 160 /// true if item is found in the 161 /// 163 public bool Contains(T item)164 {165 if (IsEmpty)166 return false;167 168 BinaryTreeNode; otherwise, false.162 /// currentNode = Root;169 while (currentNode != null)170 {171 int comparedValue = currentNode.Value.CompareTo(item);172 if (comparedValue == 0)173 return true;174 else if (comparedValue < 0)175 currentNode = currentNode.Left;176 else177 currentNode = currentNode.Right;178 }179 180 return false;181 }182 183 /// 184 /// 将树中节点拷贝至目标数组185 /// 186 /// The array.187 /// Index of the array.188 public void CopyTo(T[] array, int arrayIndex)189 {190 T[] tempArray = new T[NumberOfNodes];191 int counter = 0;192 foreach (T value in this)193 {194 tempArray[counter] = value;195 ++counter;196 }197 Array.Copy(tempArray, 0, array, arrayIndex, Count);198 }199 200 ///201 /// 树中节点的数量202 /// 203 public int Count204 {205 get { return NumberOfNodes; }206 }207 208 ///209 /// 树是否为只读210 /// 211 public bool IsReadOnly212 {213 get { return false; }214 }215 216 ///217 /// 移除节点218 /// 219 /// 节点值220 ///是否移除成功 221 public bool Remove(T item)222 {223 BinaryTreeNodenode = Find(item);224 if (node == null)225 return false;226 227 List values = new List ();228 foreach (BinaryTreeNode l in Traverse(node.Left))229 {230 values.Add(l.Value);231 }232 foreach (BinaryTreeNode r in Traverse(node.Right))233 {234 values.Add(r.Value);235 }236 237 if (node.Parent.Left == node)238 {239 node.Parent.Left = null;240 }241 else242 {243 node.Parent.Right = null;244 }245 246 node.Parent = null;247 248 foreach (T v in values)249 {250 this.Add(v);251 }252 253 return true;254 }255 256 #endregion257 258 #region Private Functions259 260 /// 261 /// 查找指定值的节点262 /// 263 /// 指定值264 ///265 /// 指定值的节点266 /// 267 protected BinaryTreeNodeFind(T value)268 {269 foreach (BinaryTreeNode node in Traverse(Root))270 if (node.Value.Equals(value))271 return node;272 return null;273 }274 275 /// 276 /// 遍历树277 /// 278 /// 遍历搜索的起始节点279 ///280 /// The individual items from the tree281 /// 282 [SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures")]283 protected IEnumerable> Traverse(BinaryTreeNode node)284 {285 // 遍历左子树286 if (node.Left != null)287 {288 foreach (BinaryTreeNode left in Traverse(node.Left))289 yield return left;290 }291 292 // 中序遍历二叉树, 顺序是 左子树，根，右子树293 yield return node;294 295 // 遍历右子树296 if (node.Right != null)297 {298 foreach (BinaryTreeNode right in Traverse(node.Right))299 yield return right;300 }301 }302 303 /// 304 /// 插入节点305 /// 306 /// 插入的节点值307 protected void Insert(T value)308 {309 // 从根节点开始比较310 BinaryTreeNodecurrentNode = Root;311 312 while (true)313 {314 if (currentNode == null)315 throw new InvalidProgramException("The current tree node cannot be null.");316 317 // 比较当前节点与新节点的值318 int comparedValue = currentNode.Value.CompareTo(value);319 if (comparedValue < 0)320 {321 // 当前节点值小于新节点值322 if (currentNode.Left == null)323 {324 currentNode.Left = new BinaryTreeNode (value, currentNode);325 ++NumberOfNodes;326 return;327 }328 else329 {330 currentNode = currentNode.Left;331 }332 }333 else if (comparedValue > 0)334 {335 // 当前节点值大于新节点值336 if (currentNode.Right == null)337 {338 currentNode.Right = new BinaryTreeNode (value, currentNode);339 ++NumberOfNodes;340 return;341 }342 else343 {344 currentNode = currentNode.Right;345 }346 }347 else348 {349 // 当前节点值等于新节点值350 currentNode = currentNode.Right;351 }352 }353 }354 355 #endregion356 }
实现方式（三）：实现 BidirectionalConcurrentDictionary 双向并发字典。
1 namespace IteratorPattern.Implementation3 2 { 3 /// 4 /// 双值对 5 /// 6 /// 第一个值的类型 7 /// 第二个值的类型 8 [Serializable] 9 public struct FirstSecondPair 10 { 11 private TFirst first; 12 private TSecond second; 13 14 /// 15 /// 第一个值 16 /// 17 public TFirst First 18 { 19 get 20 { 21 return this.first; 22 } 23 } 24 25 /// 26 /// 第二个值 27 /// 28 public TSecond Second 29 { 30 get 31 { 32 return this.second; 33 } 34 } 35 36 /// 37 /// 双值对 38 /// 39 /// 第一个值 40 /// 第二个值 41 public FirstSecondPair(TFirst first, TSecond second) 42 { 43 if (first == null) 44 throw new ArgumentNullException("first"); 45 if (second == null) 46 throw new ArgumentNullException("second"); 47 48 this.first = first; 49 this.second = second; 50 } 51 52 /// 53 /// Determines whether the specified 55 /// The 57 /// true if the specified false . 58 /// 59 public override bool Equals(object obj) 60 { 61 if (obj == null) 62 return false; 63 64 FirstSecondPair target = (FirstSecondPair )obj; 65 return this.First.Equals(target.First) && this.Second.Equals(target.Second); 66 } 67 68 /// 69 /// Returns a hash code for this instance. 70 /// 71 /// 72 /// A hash code for this instance, suitable for use in hashing algorithms and data structures like a hash table. 73 /// 74 public override int GetHashCode() 75 { 76 return base.GetHashCode(); 77 } 78 79 /// 80 /// Returns a 82 /// 83 /// A 85 public override string ToString() 86 { 87 StringBuilder sb = new StringBuilder(); 88 sb.Append('['); 89 90 if (this.First != null) 91 { 92 sb.Append(this.First.ToString()); 93 } 94 95 sb.Append(", "); 96 97 if (this.Second != null) 98 { 99 sb.Append(this.Second.ToString());100 }101 102 sb.Append(']');103 104 return sb.ToString();105 }106 107 /// 108 /// Implements the operator ==.109 /// 110 /// The left.111 /// The right.112 /// 113 /// The result of the operator.114 /// 115 public static bool operator ==(FirstSecondPair left, FirstSecondPair right)116 {117 if (((object)left == null) || ((object)right == null))118 {119 return false;120 }121 122 return left.Equals(right);123 }124 125 /// 126 /// Implements the operator !=.127 /// 128 /// The left.129 /// The right.130 /// 131 /// The result of the operator.132 /// 133 public static bool operator !=(FirstSecondPair left, FirstSecondPair right)134 {135 return !(left == right);136 }137 }138 139 public class BidirectionalConcurrentDictionary : IEnumerable >140 {141 #region Fields142 143 private ConcurrentDictionary firstToSecond = new ConcurrentDictionary ();144 private ConcurrentDictionary secondToFirst = new ConcurrentDictionary ();145 146 #endregion147 148 #region Public Methods149 150 public void Add(TFirst first, TSecond second)151 {152 if (firstToSecond.ContainsKey(first) || secondToFirst.ContainsKey(second))153 throw new ArgumentException("Duplicate first or second");154 155 firstToSecond.Add(first, second);156 secondToFirst.Add(second, first);157 }158 159 public bool ContainsFirst(TFirst first)160 {161 return firstToSecond.ContainsKey(first);162 }163 164 public bool ContainsSecond(TSecond second)165 {166 return secondToFirst.ContainsKey(second);167 }168 169 public TSecond GetByFirst(TFirst first)170 {171 TSecond second;172 if (!firstToSecond.TryGetValue(first, out second))173 throw new KeyNotFoundException("Cannot find second by first.");174 175 return second;176 }177 178 public TFirst GetBySecond(TSecond second)179 {180 TFirst first;181 if (!secondToFirst.TryGetValue(second, out first))182 throw new KeyNotFoundException("Cannot find first by second.");183 184 return first;185 }186 187 public void RemoveByFirst(TFirst first)188 {189 TSecond second;190 if (!firstToSecond.TryGetValue(first, out second))191 throw new KeyNotFoundException("Cannot find second by first.");192 193 firstToSecond.Remove(first);194 secondToFirst.Remove(second);195 }196 197 public void RemoveBySecond(TSecond second)198 {199 TFirst first;200 if (!secondToFirst.TryGetValue(second, out first))201 throw new KeyNotFoundException("Cannot find first by second.");202 203 secondToFirst.Remove(second);204 firstToSecond.Remove(first);205 }206 207 public bool TryAdd(TFirst first, TSecond second)208 {209 if (firstToSecond.ContainsKey(first) || secondToFirst.ContainsKey(second))210 return false;211 212 firstToSecond.Add(first, second);213 secondToFirst.Add(second, first);214 return true;215 }216 217 public bool TryGetByFirst(TFirst first, out TSecond second)218 {219 return firstToSecond.TryGetValue(first, out second);220 }221 222 public bool TryGetBySecond(TSecond second, out TFirst first)223 {224 return secondToFirst.TryGetValue(second, out first);225 }226 227 public bool TryRemoveByFirst(TFirst first)228 {229 TSecond second;230 if (!firstToSecond.TryGetValue(first, out second))231 return false;232 233 firstToSecond.Remove(first);234 secondToFirst.Remove(second);235 return true;236 }237 238 public bool TryRemoveBySecond(TSecond second)239 {240 TFirst first;241 if (!secondToFirst.TryGetValue(second, out first))242 return false;243 244 secondToFirst.Remove(second);245 firstToSecond.Remove(first);246 return true;247 }248 249 public int Count250 {251 get { return firstToSecond.Count; }252 }253 254 public void Clear()255 {256 firstToSecond.Clear();257 secondToFirst.Clear();258 }259 260 #endregion261 262 #region IEnumerable > Members263 264 IEnumerator > IEnumerable >.GetEnumerator()265 {266 foreach (var item in firstToSecond)267 {268 yield return new FirstSecondPair (item.Key, item.Value);269 }270 }271 272 #endregion273 274 #region IEnumerable Members275 276 IEnumerator IEnumerable.GetEnumerator()277 {278 foreach (var item in firstToSecond)279 {280 yield return new FirstSecondPair (item.Key, item.Value);281 }282 }283 284 #endregion285 }286 287 public static class ConcurrentDictionaryExtensions288 {289 public static TValue Add (this ConcurrentDictionary collection, TKey key, TValue @value)290 {291 TValue result = collection.AddOrUpdate(key, @value, (k, v) => { return @value; });292 return result;293 }294 295 public static TValue Update (this ConcurrentDictionary collection, TKey key, TValue @value)296 {297 TValue result = collection.AddOrUpdate(key, @value, (k, v) => { return @value; });298 return result;299 }300 301 public static TValue Get (this ConcurrentDictionary collection, TKey key)302 {303 TValue @value = default(TValue);304 collection.TryGetValue(key, out @value);305 return @value;306 }307 308 public static TValue Remove (this ConcurrentDictionary collection, TKey key)309 {310 TValue @value = default(TValue);311 collection.TryRemove(key, out @value);312 return @value;313 }314 }315 } 实现方式（四）：实现 RoundRobin 循环列表。
1 namespace IteratorPattern.Implementation4 2 { 3 /// 4 /// 循环列表 5 /// 6 /// : IEnumerable 8 { 9 private T[] _items;10 private int _head;11 12 /// 13 /// 循环列表14 /// 15 /// 供循环的列表项16 public RoundRobinCollection(IEnumerable items)17 {18 if (items == null || items.Count () == 0)19 {20 throw new ArgumentException(21 "One or more items must be provided", "items");22 }23 24 // copy the list to ensure it doesn't change on us 25 // (and so we can lock() on our private copy) 26 _items = items.ToArray();27 }28 29 /// 30 /// 获取循环器31 /// 32 /// GetEnumerator()34 {35 int currentHead;36 37 lock (_items)38 {39 currentHead = _head++;40 41 if (_head == _items.Length)42 {43 // wrap back to the start 44 _head = 0;45 }46 }47 48 // return results [current] ... [last] 49 for (int i = currentHead; i < _items.Length; i++)50 {51 yield return _items[i];52 }53 54 // return wrap-around (if any) [0] ... [current-1] 55 for (int i = 0; i < currentHead; i++)56 {57 yield return _items[i];58 }59 }60 61 /// 62 /// 获取循环器63 /// 64 /// 转载地址：http://baxkm.baihongyu.com/
你可能感兴趣的文章
javascript深入理解js闭包
查看>>
SQL 分布式查询、插入递增列示例
查看>>
单例模式
查看>>
Codeforces 600 E - Lomsat gelral
查看>>
HDU 3949 XOR
查看>>
移动端开发复习
查看>>
JsDoc脚本注释文档生成
查看>>
基于人脸识别的考试系统16
查看>>
Android -- Annotation（注解）原理详解及常见框架应用
查看>>
webpack
查看>>
如何在eclipse模拟器上运行下载好的apk程序
查看>>
Hibernate 错题分析
查看>>
Django+Uwsgi+Nginx部署
查看>>
js获得一月中天数
查看>>
DTCMS插件的制作实例电子资源管理（一）插件目录结构
查看>>
《领域模型》——第四部分-战略设计
查看>>
微信开发之调起摄像头、本地展示图片、上传下载图片
查看>>
对于使用了SSH造成的中文乱码问题，4大解决方法
查看>>
PAT Advanced 1023 Have Fun with Numbers
查看>>
python多线程threading下载示例
查看>>