堆栈和队列枚举顺序 [英] Stack and Queue enumeration order

问题描述

我知道 List 枚举数可保证枚举顺序并尊重最后的排序操作，我知道 Dictionary 和 HashSet 不会您可以不确保

  Dictionary< string，string>字典= ...;foreach(字典中的变量对){} 

将按其附加顺序处理对.

堆栈和 Queue 怎么样?他们的枚举员保证任何命令吗?

解决方案

对于 Stack ，枚举当前由称为 StackEnumerator 的嵌套私有类完成(这是从参考源):

 私有类StackEnumerator:IEnumerator，ICloneable{专用Stack _stack;private int _index;private int _version;私有对象currentElement;内部StackEnumerator(堆栈堆栈){_stack =堆栈;_version = _stack._version;_index = -2;currentElement = null;}公共对象克隆(){返回MemberwiseClone();}公共虚拟布尔MoveNext(){布尔·雷特瓦尔如果(_version！= _stack._version)抛出新的InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));if(_index == -2){//首次调用枚举器._index = _stack._size-1;retval =(_index> = 0);如果(retval)currentElement = _stack._array [_index];返回retval;}if(_index == -1){//枚举结束.返回false；}retval =(--_ index> = 0);如果(retval)currentElement = _stack._array [_index];别的currentElement = null;返回retval;}当前的公共虚拟对象{得到 {如果(_index == -2)抛出新的InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted));如果(_index == -1)抛出新的InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded));返回currentElement;}}公共虚拟无效Reset(){如果(_version！= _stack._version)抛出新的InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));_index = -2;currentElement = null;}} 

请注意，它是如何从设置为 _stack._size-1 的索引开始枚举并减少索引以按LIFO顺序返回每个元素的.

但是，因为没有记录，所以不能保证一定会一直如此(尽管Microsoft更改枚举器现在的工作方式是很疯狂的！)

您可以检查嵌套的 QueueEnumerator 类的实现，并类似地确定枚举是以将项目出队的顺序进行的.

Stack.GetEnumerator()强烈暗示使用了LIFO订单.

如果您查看 Stack< T> .GetEnumerator() 并检查声明的输出，您可以看到它是按照LIFO顺序排列的.

这强烈表明Microsoft完全打算按照LIFO顺序枚举Stack-但他们忘记了(或不花心思)对此进行明确记录！

I know that List enumerator guarantees the enumeration order and respects last sort operation, I know that the Dictionary and HashSet ones do not i.e. you can NOT be sure that

Dictionary<string, string> dictionary = ...;

foreach(var pair in dictionary)
{

}

will process pairs in the order they were appended.

What about the Stack and the Queue? Do their enumerators guarantee any order?

解决方案

For Stack, the enumeration is currently done by a nested private class called StackEnumerator (this is from the Reference Source):

private class StackEnumerator : IEnumerator, ICloneable
{
    private Stack _stack;
    private int _index;
    private int _version;
    private Object currentElement;

    internal StackEnumerator(Stack stack) {
        _stack = stack;
        _version = _stack._version;
        _index = -2;
        currentElement = null;
    }

    public Object Clone()
    {
        return MemberwiseClone();
    }

    public virtual bool MoveNext() {
        bool retval;
        if (_version != _stack._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
        if (_index == -2) {  // First call to enumerator.
            _index = _stack._size-1;
            retval = ( _index >= 0);
            if (retval)
                currentElement = _stack._array[_index];
            return retval;
        }
        if (_index == -1) {  // End of enumeration.
            return false;
        }

        retval = (--_index >= 0);
        if (retval)
            currentElement = _stack._array[_index];
        else
            currentElement = null;
        return retval;
    }

    public virtual Object Current {
        get {
            if (_index == -2) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted));
            if (_index == -1) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded));
            return currentElement;
        }
    }

    public virtual void Reset() {
        if (_version != _stack._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
        _index = -2;
        currentElement = null;
    }
}    

Note how it enumerates starting with the index set to _stack._size-1 and decrements the index to return each element in LIFO order.

However, because this is not documented you can't guarantee that it will always be this way (although it would be insane for Microsoft to change the way that the enumerator works now!)

You can inspect the implementation of the nested QueueEnumerator class and similarly determine that the enumeration is done in the order in which items would be dequeued.

The Stack.GetEnumerator() strongly implies that LIFO order is used.

If you look at the example for Stack<T>.GetEnumerator() in Microsoft's documentation and inspect the stated output, you can see that it is in LIFO order.

This strongly suggests that Microsoft fully intend a Stack to be enumerated in LIFO order - but they forgot (or didn't bother to) to explicitly document this!

这篇关于堆栈和队列枚举顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！