迭代器

引言ConcurrentModificationException这个异常大家都很熟悉，当在forEach进行删除时都会出现该异常。 如果你还不了解，请参考澍澍的博客：关于在list循环的过程中进行删除的处理 - 晨澍的博客 ConcurrentModificationException的解决方案之一是使用迭代器，但是不代表迭代器就一劳永逸了。 使用的时候还需斟酌数组的索引。 描述问题场景如下图所示： 原来的同步方法获取的节点是节点的父节点，根据父节点进行对应。 然而在同步更新文件的时候，发现这样并不好处理，在不改动原代码的情况下，设计了将列表转为树型结构的方法，这样可以从根节点向下开始遍历，便于操作。 也是在牛客网身经百战，实现这个难度不大。但在编写相关实现的时候，遇到了一个小问题。 迭代器智能吗？第一步，将列表中的根节点找出来。 @Overridepublic ClusterNode listToTree(List<ClusterNode> clusterNodes) { logger.debug("声明根节点名称"); final String ROOT_NAME = "ROOT"; logger.debug("声明根节点"); ClusterNode rootNode = null; logger.debug("获取迭代器，遍历节点列表"); Iterator<ClusterNode> iterator = clusterNodes.iterator(); while (iterator.hasNext()) { logger.debug("向后遍历"); ClusterNode clusterNode = iterator.next(); if (ROOT_NAME.equals(clusterNode.getName())) { logger.debug("获取到根节点，赋值，并从原列表中移除"); rootNode = clusterNode; iterator.remove(); break; } } logger.debug("设置子节点"); assert rootNode != null; setChildrenNode(rootNode, clusterNodes); return rootNode;}第二步，再从根节点开始，递归设置子节点。 /** * 为节点设置符合条件的子节点，同时递归，设置子节点的子节点 * @param parentNode 父节点 * @param clusterNodes 子节点列表 */private void setChildrenNode(ClusterNode parentNode, List<ClusterNode> clusterNodes) { logger.debug("清空原集合"); parentNode.getClusterNodes().clear(); logger.debug("遍历列表"); Iterator<ClusterNode> iterator = clusterNodes.iterator(); while (iterator.hasNext()) { ClusterNode clusterNode = iterator.next(); logger.debug("如果父节点匹配"); if (clusterNode.getParentClusterNode().getName().equals(parentNode.getName())) { logger.debug("将当前节点添加到父节点的子列表中"); parentNode.getClusterNodes().add(clusterNode); logger.debug("移除该节点"); iterator.remove(); logger.debug("递归设置子节点"); setChildrenNode(clusterNode, clusterNodes); } }}思想肯定是没问题的。 ...

文章内容分两部分： 前半部分为 “迭代器模式” 概念；后半部分为 ES6 中 Iterator (迭代器）上半部分开始... 迭代器模式：提供一种方法顺序访问一个聚合对象中的各个元素，而又不需要暴露该对象的内部表示。简单理解（白话理解）：统一 “集合” 型数据结构的遍历接口，实现可循环遍历获取集合中各数据项（不关心数据项中的数据结构）。 生活小栗子：清单 TodoList。每日清单有学习类、生活类、工作类、运动类等项目，清单列表只管罗列，不管类别。 模式特点为遍历不同数据结构的 “集合” 提供统一的接口；能遍历访问 “集合” 数据中的项，不关心项的数据结构模式实现// 统一遍历接口实现var each = function(arr, callBack) { for (let i = 0, len = arr.length; i < len; i++) { // 将值，索引返回给回调函数callBack处理 if (callBack(i, arr[i]) === false) { break; // 中止迭代器，跳出循环 } }}// 外部调用each([1, 2, 3, 4, 5], function(index, value) { if (value > 3) { return false; // 返回false中止each } console.log([index, value]);})// 输出：[0, 1] [1, 2] [2, 3]“迭代器模式的核心，就是实现统一遍历接口。” ...

起源何为迭代器？迭代器是被设计专用于迭代的对象，带有特定接口。所有的迭代器对象都拥有 next() 方法，会返回一个结果对象。该结果对象有两个属性：对应下一个值的 value ，以及一个布尔类型的 done ，其值为 true 时表示没有更多值可供使用。迭代器持有一个指向集合位置的内部指针，每当调用了 next() 方法，迭代器就会返回相应的下一个值。记住这些后，在 ES5 中创建一个迭代器就相当简单了:function ceateIterator(items) { var i = 0; return { next: function() { var done = (i >= items.length); var value = !done ? items[i++]: undefined; return { done: done, value: value }; } };}var iterator = createIterator([1, 2, 3]);console.log(iterator.next()); // “{ value: 1, done: false }“console.log(iterator.next()); // “{ value: 2, done: false }“console.log(iterator.next()); // “{ value: 3, done: false }“console.log(iterator.next()); // “{ value: undefined, done: true }”// 之后的所有调用console.log(iterator.next()); // “{ value: undefined, done: true }“可迭代对象 与 for-of循环与迭代器紧密相关的是，可迭代对象（ iterable ）是包含 Symbol.iterator 属性的对象。这个 Symbol.iterator 知名符号定义了为指定对象返回迭代器的函数。在 ES6 中，所有的集合对象（数组、 Set 与 Map ）以及字符串都是可迭代对象，因此它们都被指定了默认的迭代器。可迭代对象被设计用于与 ES 新增的 for-of 循环配合使用。for-of在循环每次执行时会调用可迭代对象next()方法，并将结果value值保存在一个变量上，循环过程到done变成true时停止。let values = [1, 2, 3];for (let num of values) {console.log(num);}此代码输出如下123这个 for-of 循环首先调用了 values 数组的 Symbol.iterator 方法，获取了一个迭代器（对 Symbol.iterator 的调用发生在 JS 引擎后台）。接下来 iterator.next() 被调用，迭代器结果对象的 value 属性被读出并放入了 num 变量。 num 变量的值开始为 1 ，接下来是 2 ，最后变成 3 。当结果对象的 done 变成 true ，循环就退出了，因此 num 绝不会被赋值为 undefined 。访问默认迭代器你可以使用 Symbol.iterator 来访问对象上的默认迭代器，就像这样：let values = [1, 2, 3];let iterator = valuesSymbol.iterator;console.log(iterator.next()); // “{ value: 1, done: false }“console.log(iterator.next()); // “{ value: 2, done: false }“console.log(iterator.next()); // “{ value: 3, done: false }“console.log(iterator.next()); // “{ value: undefined, done: true }“既然 Symbol.iterator 指定了默认迭代器，你就可以使用它来检测一个对象是否能进行迭代，正如下例：function isIterable(object) {return typeof object[Symbol.iterator] === “function”;}console.log(isIterable([1, 2, 3])); // trueconsole.log(isIterable(“Hello”)); // trueconsole.log(isIterable(new Map())); // trueconsole.log(isIterable(new Set())); // trueconsole.log(isIterable(new WeakMap())); // falseconsole.log(isIterable(new WeakSet())); // false集合的迭代器ES6 具有三种集合对象类型：数组、 Map 与 Set 。这三种类型都拥有如下的迭代器，有助于探索它们的内容：entries() ：返回一个包含键值对的迭代器；values() ：返回一个包含集合中的值的迭代器；keys() ：返回一个包含集合中的键的迭代器;entries()迭代器entries() 迭代器会在每次 next() 被调用时返回一个双项数组，此数组代表了集合中每个元素的键与值：对于数组来说，第一项是数值索引；对于 Set ，第一项也是值（因为它的值也会被视为键）；对于 Map ，第一项就就是键。let colors = [ “red”, “green”, “blue” ];let tracking = new Set([1234, 5678, 9012]);let data = new Map();data.set(“title”, “Understanding ES6”);data.set(“format”, “ebook”);for (let entry of colors.entries()) {console.log(entry);}for (let entry of tracking.entries()) {console.log(entry);}for (let entry of data.entries()) {console.log(entry);}输出内容如下:[0, “red”][1, “green”][2, “blue”][1234, 1234][5678, 5678][9012, 9012][“title”, “Understanding ES6”][“format”, “ebook”]values() 迭代器values() 迭代器仅仅能返回存储在集合内的值，例如：let colors = [ “red”, “green”, “blue” ];let tracking = new Set([1234, 5678, 9012]);let data = new Map();data.set(“title”, “Understanding ES6”);data.set(“format”, “ebook”);for (let value of colors.values()) {console.log(value);}for (let value of tracking.values()) {console.log(value);}for (let value of data.values()) {console.log(value);}此代码输出了如下内容：“red"“green"“blue"123456789012"Understanding ES6"“ebook"keys() 迭代器keys() 迭代器能返回集合中的每一个键。对于数组来说，它只返回了数值类型的键，永不返回数组的其他自有属性； Set 的键与值是相同的，因此它的 keys() 与 values() 返回了相同的迭代器；对于 Map ， keys() 迭代器返回了每个不重复的键。这里有个例子演示了这三种情况：let colors = [ “red”, “green”, “blue” ];let tracking = new Set([1234, 5678, 9012]);let data = new Map();data.set(“title”, “Understanding ES6”);data.set(“format”, “ebook”);for (let key of colors.keys()) {console.log(key);}for (let key of tracking.keys()) {console.log(key);}for (let key of data.keys()) {console.log(key);}本例输出了如下内容：012123456789012"title"“format” ...

前言上一篇：算法分析下一篇：基本排序本篇内容主要是栈，队列 (和包)的基本数据类型和数据结构在很多应用中，我们需要维护多个对象的集合，而对这个集合的操作也很简单基本数据类型对象的集合操作：insert – 向集合中添加新的对象remove – 去掉集合中的某个元素iterate – 遍历集合中的元素并对他们执行某种操作test if empty – 检查集合是否为空做插入和删除操作时我们要明确以什么样的形式去添加元素，或我们要删除集合中的哪个元素。处理这类问题有两个经典的基础数据结构：栈(stack) 和队列(queue)两者的区别在于去除元素的方式：栈：去除最近加入的元素，遵循后进先出原则(LIFO: last in first out)。插入元素对应的术语是入栈 – push；去掉最近加入的元素叫出栈 – pop队列：去除最开始加入的元素，遵循先进先出原则(FIFO: first in first out)。关注最开始加入队列的元素，为了和栈的操作区分，队列加入元素的操作叫做入队 – enqueue；去除元素的操作叫出队 – dequeue此篇隐含的主题是模块式编程，也是平时开发需要遵守的原则模块化编程这一原则的思想是将接口与实现完全分离。比如我们精确定义了一些数据类型和数据结构(如栈，队列等)，我们想要的是把实现这些数据结构的细节完全与客户端分离。客户端可以选择数据结构不同的实现方式，但是客户端代码只能执行基本操作。实现的部分无法知道客户端需求的细节，它所要做的只是实现这些操作，这样，很多不同的客户端都可以使用同一个实现，这使得我们能够用模块式可复用的算法与数据结构库来构建更复杂的算法和数据结构，并在必要的时候更关注算法的效率。Separate client and implementation via API.API：描述数据类型特征的操作Client：使用API操作的客户端程序。Implementation：实现API操作的代码。下面具体看下这两种数据结构的实现栈栈 API假设我们有一个字符串集合，我们想要实现字符串集合的储存，定期取出并且返回最后加入的字符串，并检查集合是否为空。我们需要先写一个客户端然后再看它的实现。字符串数据类型的栈性能要求：所有操作都花费常数时间客户端：从标准输入读取逆序的字符串序列测试客户端import edu.princeton.cs.algs4.StdIn;import edu.princeton.cs.algs4.StdOut;public static void main(String[] args){ StackOfStrings stack = new StackOfStrings(); while (!StdIn.isEmpty()) { //从标准输入获取一些字符串 String s = StdIn.readString(); //如果字符串为"-",则客户端将栈顶的字符串出栈，并打印出栈的字符串 if (s.equals("-")) StdOut.print(stack.pop()); //否则将字符串入栈到栈顶 else stack.push(s); }}客户端输入输出：栈的实现：链表链表(linked-list)连接待添加…我们想保存一个有节点组成的，用来储存字符串的链表。节点包含指向链表中下一个元素的引用(first).维持指针 first 指向链表中的第一个节点Push：入栈，在链表头插入一个新的节点Pop：出栈，去掉链表头处第一个节点Java 实现public class LinkedStackOfStrings{ //栈中唯一的实例变量是链表中的第一个节点的引用 private Node first = null; //内部类，节点对象，构成链表中的元素，由一个字符串和指向另一个节点的引用组成 private class Node { private String item; private Node next; } public boolean isEmpty() { return first == null; } // public void push(String item) { //将指向链表头的指针先保存 Node oldfirst = first; //创建新节点：我们将要插入表头的节点 first = new Node(); first.item = item; //实例变量的next指针指向链表oldfirst元素，现在变成链表的第二个元素 first.next = oldfirst; } //出栈 public String pop() { //将链表中的第一个元素储存在标量 item 中 String item = first.item; //去掉第一个节点：将原先指向第一个元素的指针指向下一个元素，然后第一个节点就等着被垃圾回收处理 first = first.next; //返回链表中原先保存的元素 return item; }}图示：出栈：入栈：性能分析通过分析提供给客户算法和数据结构的性能信息，评估这个实现对以不同客户端程序的资源使用量Proposition 在最坏的情况下，每个操作只需要消耗常数时间(没有循环)。Proposition 具有n个元素的栈使用 ~40n 个字节内存(没有考虑字符串本身的内存，因为这些空间的开销在客户端上)栈的实现：数组栈用链表是实现花费常数的时间，但是栈还有更快的实现另一种实现栈的 natural way 是使用数组储存栈上的元素将栈中的N个元素保存在数组中，索引为 n，n 对应的数组位置即为栈顶的位置，即下一个元素加入的地方使用数组 s[] 在栈上存储n个元素。push()：在 s[n] 处添加新元素。pop()：从 s[n-1] 中删除元素。在改进前使用数组的一个缺点是必须声明数组的大小，所以栈有确定的容量。如果栈上的元素个数比栈的容量多，我们就必须处理这个问题(调整数组)Java 实现public class FixedCapacityStackOfStrings{ private String[] s; //n 为栈的大小，栈中下一个开放位置，也为下一个元素的索引 private int n = 0; //int capacity：看以下说明 public FixedCapacityStackOfStrings(int capacity) { s = new String[capacity]; } public boolean isEmpty() { return n == 0; } public void push(String item) { //将元素放在 n 索引的位置，然后 n+1 s[n++] = item; } public String pop() { //然后返回数组n-1的元素 return s[–n]; }}int capacity： 在构造函数中加入了容量的参数，破坏了API，需要客户端提供栈的容量。不过实际上我们不会这么做，因为大多数情况下，客户端也无法确定需要多大栈，而且客户端也可能需要同时维护很多栈，这些栈又不同时间到达最大容量，同时还有其他因素的影响。这里只是为了简化。在调整数组中会处理可变容量的问题，避免溢出对于两种实现的思考上述的实现中我们暂时没有处理的问题：Overflow and underflowUnderflow ：客户端从空栈中出栈我们没有抛出异常Overflow ：使用数组实现，当客户端入栈超过容量发生栈溢出的问题Null item：客户端是否能像数据结构中插入空元素Loitering 对象游离：即在栈的数组中，我们有一个对象的引用，可是我们已经不再使用这个引用了数组中当我们减小 n 时，在数组中仍然有我们已经出栈的对象的指针，尽管我们不再使用它，但是Java系统并不知道。所以为了避免这个问题，有效地利用内存，最好将去除元素对应的项设为 null，这样就不会剩下旧元素的引用指针，接下来就等着垃圾回收机制去回收这些内存。这个问题比较细节化，但是却很重要。public String pop(){ String item = s[–n]; s[n] = null; return item;} 调整数组队列泛型迭代器栈与队列的应用附录 ...