JavaScript中实现对象属性的yield迭代器

Question

我需要一个像这样工作的真正的迭代器：

var haystackObj = {
        'needle': 'abc',
        'prop2': {
                'prop1': 'def',
                'prop2': {
                        'needle': 'ghi',
                },
                'needle': 'jkl',
        },
};
var needleKey = 'needle';
var iterator = {
    next: function () {
            /* 
             * WHAT CODE GOES HERE? 
             * 
             * Should return the next property, recursively, with the name 
             * equal to needleKey, of haystackObj.
             *
             */
    }
};

var value = iterator.next();
console.log(value); // -> 'abc'
value = iterator.next();
console.log(value); // -> 'ghi'
value = iterator.next();
console.log(value); // -> 'jkl'

我认为使用for(k in o)和一级续延将很容易解决这个问题，但JS没有这些功能。

编辑：我只能扫描haystackObj一次。

编辑2：我不是在寻找“遍历对象属性的方法”。我正在寻找一个对象属性的迭代器。这是一个巨大的区别。这个问题并不像乍一看那么简单。

- Nick Zalutskiy

---

"def"发生了什么？为什么“ghi”在“jkl”之前输出？ - Bergi

你有尝试过什么吗？看起来你只是想让 Stack Overflow 为你编写代码... - Florian Margaine

顺便提一下：JavaScript 中未经认证的属性顺序。你的要求无法满足。 - Florian Margaine

JS 什么时候失去了 for( var key in obj ) 这个语法？ - rlemon

你们大多数人都没理解问题的要点，是吧。他想在JS中使用“yield”语义。他想迭代一个类似于树形结构的东西，并在找到“key”的位置时将控制权返回给调用者，然后继续迭代。 - Stan R.

Answer 1

JS中不保证属性的顺序。不同的引擎行为不同。（一些引擎基于字母顺序，其他基于最后添加的顺序。）

因此，您的要求是不可能实现的。

如果您只想要一个迭代器而不关心顺序，您可以查看这个问题/答案：如何模拟JavaScript yield？ 这就是规范对属性顺序的说明：

“枚举属性的机制和顺序（第一个算法中的步骤6.a，第二个算法中的步骤7.a）未指定。在枚举期间，正在枚举的对象的属性可能会被删除。如果在枚举期间尚未访问过的属性被删除，则不会访问该属性。如果在枚举期间向正在枚举的对象添加新属性，则不能保证在活动枚举中访问新添加的属性。任何枚举中都不得多次访问属性名。”

实际上，大多数浏览器会按照特定的顺序遍历元素：在“for(…in…)”循环中的元素顺序

根据实际情况来看，我所能想到的实现虚拟生成器的唯一方法就是复制对象，并在需要时删除副本的扫描属性。这意味着您不会重复扫描相同的属性。以下是一些代码示例：

var Iterator = function() {
    var copy = $.extend(haystackObj, true);
    // ^ using jQuery's extend for a quick function, but use w/e you want.
    // Anyway keep it in a closure. This copy will have its properties deleted
    // after each iteration.

    return {
        next: function next() {
            var found = false,
                needle;
            for (var prop in copy) {
                if (typeof copy[prop] === 'object') {
                    // Since next() doesn't take any argument...
                    // That's a bad solution. You should use an inner function
                    // to recurse. But I'm going to bed right now!
                    var copyCopy = $.extend(copy, true);
                    copy = copy[prop];
                    found = next();
                    copy = copyCopy;
                }

                else {
                    if (prop === needleKey) {
                        found = true;
                    }
                }

                if (found) {
                    needle = copy[prop];
                }

                // Delete the current property to simulate a real generator.
                delete copy[prop];

                if (found) {
                    return needle;
                }
            }
        }
    };
};

// Usage:
var iterator = Iterator();
iterator.next(); // "abc"

这段代码不起作用（请参见jsfiddle），我要去睡觉了。但是您可以看到它的方向，以及如何制作一些东西。

- Florian Margaine

---

你赢得了游戏。恭喜！ - Naftali

很好的答案。这在规范的12.6.4中有说明。 - Benjamin Gruenbaum

这是迄今为止唯一有效的答案，我为什么因一个完全合理的问题而受到负面评价，我不知道。 - Nick Zalutskiy

@Nick 我更新了答案并添加了相关链接。你可以看一下，看看是否符合你的要求。 - Florian Margaine

@FlorianMargaine 一个聪明的解决方案。我一定会考虑它。谢谢。 - Nick Zalutskiy

Answer 2

尽管Florian Margaine的回答指出属性顺序取决于js引擎，但这个解决方案在chrome中有效。需要稍微调整一下，但是这里有一个链接http://jsfiddle.net/6zCkJ/3/。已编辑（此解决方案是在OP说树只能处理一次之前完成的）。

var needleKey = 'needle';
var currIndex = 0;
var runningIndex = 0;
var getValueByIndex = function (obj) {
    var objToSearch = obj || haystackObj;
    for (var x in objToSearch) {
        if (x == needleKey) {

            if (runningIndex == currIndex)  {
                currIndex += 1;
                return objToSearch[x];
            }
            runningIndex += 1;
        } else if (typeof objToSearch[x] == 'object') {
            var found = getValueByIndex(objToSearch[x]);
            if (found) return found;
        }

    }
}

var iterator = {
    next: function () {
        runningIndex = 0;
        return getValueByIndex(0);
    }
};

另一种仅遍历树一次的方法如下http://jsfiddle.net/6zCkJ/6/。但需要注意的是，每当更新针（needle）时，必须加载值数组（values array）。

var currIndex = 0;
var valuesArray = [];

var loadValues = function (obj) {
    var objToSearch = obj || haystackObj;
    for (var x in objToSearch) {
        if (x == needleKey) {
            valuesArray.push(objToSearch[x])
        } else if (typeof objToSearch[x] == 'object') {
            loadValues(objToSearch[x]);
        }
    }
}

loadValues();
console.log(valuesArray);
var iterator = {
    next: function () {
        return valuesArray[currIndex++];
    }
};

编辑：到目前为止，所有在此处发布的答案都涉及至少一次导航整个树的操作或更多，这不是楼主所寻求的，包括必须复制对象并在遍历过程中移除属性的解决方案。然而，有一种解决方案可以标记对象为已遍历，使用元数据使你可以跳过下一次遇到这些对象时的遍历。使用我的第一种方法，添加这些优化应该相当容易，并希望能够满足OP的要求。

好了，我忍不住想试着让它工作。http://jsfiddle.net/6zCkJ/12/ 这里是我的做法。你可以看到，我将找到的对象存储在foundObjects对象中，其中键由到该对象的路径组成，因此你可以快速查找以查看是否已经遍历过。numFound用于正确增加运行索引。我没有对这进行大量测试，但这应该是一个良好的起点。

var Iterator = function () {
    var needleKey = 'needle';
    var currIndex = 0;
    var runningIndex = 0;
    var foundObjects = {};

    var getValueByIndex = function (obj,currentPath) {
        var objToSearch = obj || haystackObj;
        for (var x in objToSearch) {
            currentPath += x + '_';
            if (x == needleKey) {

                if (runningIndex == currIndex) {
                    currIndex += 1;
                    if (!foundObjects[currentPath]) {
                        foundObjects[currentPath] = {
                            numFound: 0,
                            finished: false
                        };
                    }
                    foundObjects[currentPath].numFound += 1;
                    return objToSearch[x];
                }
                runningIndex += 1;
            } else if (typeof objToSearch[x] == 'object') {
                if (foundObjects[currentPath] && foundObjects[currentPath].finished) {
                    runningIndex += foundObjects[currentPath].numFound;
                } else {
                    var found = getValueByIndex(objToSearch[x],currentPath);
                    if (found) {
                        return found;
                    }
                }
            }
            if (!foundObjects[currentPath]) {
                foundObjects[currentPath] = {
                    numFound: 0,
                    finished: true
                };
            }
            foundObjects[currentPath].finished = true;
        }
    }

    this.next = function () {
        runningIndex = 0;

        return getValueByIndex(0,'');
    }
};
var iterator = new Iterator();
var value = iterator.next();

- Justin Bicknell

---

不错。它也适用于Firefox和Opera。不幸的是无法在IE上测试...然而，你正在每次迭代中扫描objToSearch。这并不完全是OP想要的。 - Florian Margaine

是的，我考虑过类似的解决方案。但正如Florian所说，我只能扫描对象一次，因为这可能经常发生。我需要写一篇关于为什么我有这样特定要求的文章，但它们就是它们。 - Nick Zalutskiy

@Nick - 只是一个想法，但我不会实现这个功能，你可以采用我的第一种方法并添加已遍历对象的列表，下次扫描时可以跳过这些对象（不完全等同于删除）。这样你就不需要提前“复制”整个 obj。 - Justin Bicknell

@JustinBicknell 我认为这可能是迄今为止最好的两全其美之举。一种类似于“快进”到最后一个属性的方法。由于您正在进行深度搜索，因此需要保持这些链，但仍然可以实现。我需要测量的是对于我实际感兴趣的第一个键，从 o 中的 k 开始的成本。我怀疑复制对象无论如何都更昂贵... - Nick Zalutskiy

好的，在聊过之后，看起来这确实是最高效的解决方案。如果我的解决方案最终成为瓶颈，我会选择直接采用它，因为设置起来相当麻烦。 - Florian Margaine

Answer 3

假设我理解您的意思，记住这不是“真正的收益率”，并将所有代码放在您想要的位置。

var iterator = {
    next: function () {
        /* 
        * WHAT CODE GOES HERE? 
        * 
        * Should return the next property, recursively, with the name 
        * equal to needleKey, of haystackObj.
        *
        */
        var values=[], findneedles;
        findneedles = function(o){
            var k;
            for(k in o){
                if(k === needleKey){
                    values.push(o[k]);
                }else if(typeof o[k] === 'object'){
                    findneedles(o[k]);
                }
            }
        };
        findneedles(haystackObj);
        this.next = function(){
            return values.shift();
        };
        return values.shift();
    }
};

- 1983

---

是的，我已经说过了。你最好还是对该结构进行递归，并传入一个回调函数。但在没有任何解释说明为什么这不可行的情况下... - 1983

是的，这与Justin Bicknell的解决方案完全相同，但您将结果移位，他索引到数组中。请查看我的评论以获取他的答案。对象可能非常大，迭代器的整个目的是不要提前支付搜索价格。 - Nick Zalutskiy

然后只需递归并在完成时抛出异常。(是的，当我写我的答案时，我还没有看到他的第二个答案。) - 1983

@Nick 或者进行广度优先搜索，并存储对未搜索的子对象的引用，以便您可以恢复迭代。 - 1983

@xtal 迭代器不知道何时完成，这就是迭代器的本质。 =）至于存储对未搜索对象的引用，请查看Florian答案的第二部分。我可能会这样做。 - Nick Zalutskiy

Answer 4

我将为后人回答这个问题。

在ECMAScript 6中，我们有一个yield语句。但是假设你很疯狂，想要立即使用这个功能。使用traceur-compiler编译成普通的JavaScript，我们得到了以下结果。

输入：

var iterator = function* (object) {

        for(var key in object) {
                yield key;
                for( k of iterator(object[key]) ) {
                        yield k;
                }
        }
};

var o = {
        a: 10,
        b: 11,
        c: {
                ca: 12,
                cb: 13,
        },
        d: 14,
};

var res = [];
for( key of iterator(o) ) {
        res.push(key);
}

res;

输出

var $__generatorWrap = function(generator) {
        return $traceurRuntime.addIterator({
                next: function(x) {
                        switch (generator.GState) {
                                case 1:
                                        throw new Error('"next" on executing generator');
                                case 3:
                                        throw new Error('"next" on closed generator');
                                case 0:
                                        if (x !== undefined) {
                                        throw new TypeError('Sent value to newborn generator');
                                }
                                case 2:
                                        generator.GState = 1;
                                if (generator.moveNext(x, 0)) {
                                        generator.GState = 2;
                                        return {
                                                value: generator.current,
                                                done: false
                                        };
                                }
                                generator.GState = 3;
                                return {
                                        value: generator.yieldReturn,
                                        done: true
                                };
                        }
                },
                'throw': function(x) {
                        switch (generator.GState) {
                                case 1:
                                        throw new Error('"throw" on executing generator');
                                case 3:
                                        throw new Error('"throw" on closed generator');
                                case 0:
                                        generator.GState = 3;
                                throw x;
                                case 2:
                                        generator.GState = 1;
                                if (generator.moveNext(x, 1)) {
                                        generator.GState = 2;
                                        return {
                                                value: generator.current,
                                                done: false
                                        };
                                }
                                generator.GState = 3;
                                return {
                                        value: generator.yieldReturn,
                                        done: true
                                };
                        }
                }
        });
};
var iterator = function(object) {
        var $that = this;
        var $arguments = arguments;
        var $state = 20;
        var $storedException;
        var $finallyFallThrough;
        var $__0;
        var $__1;
        var $__2;
        var $__3;
        var $__4;
        var $__5;
        var key;
        var $G = {
                GState: 0,
                current: undefined,
                yieldReturn: undefined,
                innerFunction: function($yieldSent, $yieldAction) {
                        while (true) switch ($state) {
                                case 20:
                                        $__2 = [];
                                $state = 21;
                                break;
                                case 21:
                                        $__3 = object;
                                $state = 23;
                                break;
                                case 23:
                                        for (var $__4 in $__3) $__2.push($__4);
                                $state = 25;
                                break;
                                case 25:
                                        $__5 = 0;
                                $state = 17;
                                break;
                                case 17:
                                        if ($__5 < $__2.length) {
                                        $state = 12;
                                        break;
                                } else {
                                        $state = 19;
                                        break;
                                }
                                case 11:
                                        $__5++;
                                $state = 17;
                                break;
                                case 12:
                                        key = $__2[$__5];
                                $state = 13;
                                break;
                                case 13:
                                        if (!(key in $__3)) {
                                        $state = 11;
                                        break;
                                } else {
                                        $state = 15;
                                        break;
                                }
                                case 15:
                                        this.current = key;
                                $state = 1;
                                return true;
                                case 1:
                                        if ($yieldAction == 1) {
                                        $yieldAction = 0;
                                        throw $yieldSent;
                                }
                                $state = 3;
                                break;
                                case 3:
                                        $__0 = $traceurRuntime.getIterator(iterator(object[key]));
                                $state = 7;
                                break;
                                case 7:
                                        if (!($__1 = $__0.next()).done) {
                                        $state = 8;
                                        break;
                                } else {
                                        $state = 11;
                                        break;
                                }
                                case 8:
                                        k = $__1.value;
                                $state = 9;
                                break;
                                case 9:
                                        this.current = k;
                                $state = 5;
                                return true;
                                case 5:
                                        if ($yieldAction == 1) {
                                        $yieldAction = 0;
                                        throw $yieldSent;
                                }
                                $state = 7;
                                break;
                                case 19:
                                        $state = -2;
                                case -2:
                                        return false;
                                case -3:
                                        throw $storedException;
                                default:
                                        throw "traceur compiler bug: invalid state in state machine: " + $state;
                        }
                },
                moveNext: function($yieldSent, $yieldAction) {
                        while (true) try {
                                return this.innerFunction($yieldSent, $yieldAction);
                        } catch ($caughtException) {
                                $storedException = $caughtException;
                                switch ($state) {
                                        default:
                                                this.GState = 3;
                                        $state = -2;
                                        throw $storedException;
                                }
                        }
                }
        };
        return $__generatorWrap($G);
};
var o = {
        a: 10,
        b: 11,
        c: {
                ca: 12,
                cb: 13
        },
        d: 14
};
var res = [];
for (var $__1 = $traceurRuntime.getIterator(iterator(o)), $__0; !($__0 = $__1.next()).done;) {
        key = $__0.value;
        {
                res.push(key);
        }
}
res;

在 JavaScript 中使用 yield 语句是可能的，但非常不实际。

我最终使用的方法

用法示例：

var object = {...};
var callback = function (key, value) {

        // Do stuff...

        return traverse.CONTINUE; 
        // or return traverse.STOP if you want the iteration to stop
};

traverse(object, callback);

实现：

var traverse = (function () {

        var _traverse = function (object, callback) {

                var key, value, command;
                for( key in object ) {
                        value = object[key];

                        command = callback(key, value);
                        if( command === _traverse.STOP ) {
                                return _traverse.STOP;
                        }

                        command = _traverse(value, callback);
                        if( command === _traverse.STOP ) {
                                return _traverse.STOP;
                        }
                }
        };
        _traverse.CONTINUE = 1;
        _traverse.STOP = 2;

        return _traverse;
})();

- Nick Zalutskiy