Гарантируется ли итерация по Queue‹T› в порядке очереди?

Гарантированно ли это всегда печатать 123?

Queue<string> theQueue = new Queue<string>();
theQueue.Enqueue("1");
theQueue.Enqueue("2");
theQueue.Enqueue("3");
foreach(var str in theQueue)
{
    Console.Write(str);
}
Console.WriteLine();

Редактировать: я полностью согласен с тем, что очередь, перечисляемая в любом другом порядке, будет явно неправильной. Вот почему я задал вопрос. Однако абстрактный тип данных queue гарантирует только свои операции enqueue и dequeue.

Я ищу ответ, который ссылается на документацию, гарантирующую такой порядок в .NET BCL.


.net collections base-class-library
person Jacob Krall    schedule 26.08.2013    source источник
comment
Я думаю, что большинство людей упускают суть вашего вопроса. Очередь определяется тем, как работают push и pops. Итерация в этом методе не определена в обычном определении очереди.   -  person bengoesboom    schedule 26.08.2013
comment
@bengoesboom да, он определен, Queue<T>.GetEnumerator() имеет собственную страницу MSDN, включая пример кода, в котором говорится, что IEnumerable, который использует вызов foreach, будет вести себя так же, как Peek() и Pop().   -  person Scott Chamberlain    schedule 26.08.2013
comment
Вы читали страницу MSDN для Queue<T>? Мне кажется, это хорошая отсылка (а как еще будет работать Queue<T> b = new Queue<T>(a)?).   -  person user7116    schedule 26.08.2013
comment
@ScottChamberlain Я имел в виду абстрактный тип данных Queue, а не конкретную реализацию.   -  person bengoesboom    schedule 27.08.2013
comment
@bengoesboom, что это за абстрактный тип данных, о котором вы говорите? вот что такое Queue‹T›, и его функция GetEnumerator очень хорошо документирована.   -  person Robert Levy    schedule 27.08.2013
comment
@ScottChamberlain: на этой странице показан пример, в котором все получилось. Но в документации прямо не сказано, что перечисление очереди вернет элементы в том же порядке, как если бы вы вызвали Dequeue для очистки очереди. Насколько я понимаю, в договоре этого нет.   -  person Jim Mischel    schedule 27.08.2013
comment
@ user7116: Если предположить, что Queue<T> реализовано как циклический буфер, Queue<T> b = new Queue<T>(a) можно реализовать путем копирования резервного массива и индексов Head и Tail. Не было бы необходимости повторять элементы.   -  person Jim Mischel    schedule 27.08.2013
comment
При этом реализация делает то, что мы и ожидали. Но я не вижу никакой явной документации.   -  person Jim Mischel    schedule 27.08.2013
comment
@JimMischel Я выделяю явную документацию в своем ответе.   -  person Scott Chamberlain    schedule 27.08.2013

Ответы (4)


arrow_upward
3
arrow_downward

Да. Это. Очередь — это коллекция в порядке очереди, и она будет перечисляться по порядку.

person Ant P    schedule 26.08.2013
comment
Мне это кажется интуитивно правильным, но есть ли документация, подтверждающая вас? - person Jacob Krall; 26.08.2013
comment
На странице Queue‹T›.GetEnumerator() есть гораздо лучший пример. код. - person Scott Chamberlain; 26.08.2013

arrow_upward
2
arrow_downward

Подтверждение документации:

Да, из Документация MSDN GetEnumerator, выделено мной

Изначально перечислитель располагается перед первым элементом в коллекции. В этой позиции Current не определено. Таким образом, вы должны вызвать MoveNext, чтобы переместить перечислитель к первому элементу коллекции перед чтением значения Current.

Current возвращает один и тот же объект, пока не будет вызван MoveNext. MoveNext устанавливает Current в следующий элемент.

Однако это не касается того, каким будет первый элемент в коллекции. Чтобы ответить на этот вопрос, нам нужно перейти к описанию самой очереди:

Представляет коллекцию объектов в порядке поступления.

Объединив два приведенных выше утверждения, мы получаем официальное соглашение кода о том, что первый объект, возвращенный перечислителем, будет первым элементом в коллекции, и тот факт, что первый элемент в коллекции будет первым в объектом, добавленным в коллекцию, что даст нам окончательный вывод о том, что итерация по Queue<T> всегда будет в порядке.

Кстати, сравните это с Dictionary, определением для GetEnumerator() указывает ту же строку о получении первого элемента первым. Однако описание словаря включает явное упорядочивание объектов в коллекции:

Представляет набор ключей и значений.

И именно поэтому для Dictionary законно не возвращаться в порядке вставки.

person Scott Chamberlain    schedule 26.08.2013
comment
Документация для Dictionary‹TKey,TValue› говорит точно то же самое, и было показано, что вы не можете рассчитывать на словарь, перечисляющий элементы в порядке их добавления. Я допускаю, что реализация Queue<T> работает так, как и следовало ожидать (т. е. повторяется в порядке удаления), но я утверждаю, что поведение — это просто деталь реализации: ничего в контракте не сказано, что оно должно выполнять так. - person Jim Mischel; 27.08.2013
comment
@JimMischel Я обновил свой ответ, включив в него свой предыдущий (удаленный) комментарий. Если вы все еще считаете, что в документации не указан контракт кода, сообщите мне, что я пропустил. - person Scott Chamberlain; 27.08.2013
comment
Я понимаю ваши рассуждения и считаю вероятным (как и всегда), что они на самом деле имели в виду документацию для определения контракта кода. На мой взгляд, документация оставляет место для маневра. Я думаю, что следует явно указать, что элементы повторяются в порядке удаления. Но это вопрос, который я должен обсудить с командой документации. - person Jim Mischel; 27.08.2013

arrow_upward
1
arrow_downward

Вот страница MSDN, которая описывает GetEnumerator для очереди. В общем (как говорили другие) вы готовы к работе. http://msdn.microsoft.com/en-us/library/4a9449ty.aspx

Обратите внимание, что перечисление очереди таким образом не изменяет ее содержимое так, как это произошло бы при циклическом вызове Dequeue().

person Robert Levy    schedule 26.08.2013

arrow_upward
1
arrow_downward

Да, итерация по Queue<T> гарантированно будет происходить в том порядке, в котором к нему были добавлены элементы. Это определение очереди FIFO. Из документов MSDN:

Очереди удобны для хранения сообщений в том порядке, в котором они были получены для последовательной обработки. Объекты, хранящиеся в очереди, вставляются с одного конца и удаляются с другого.

person Seth Flowers    schedule 26.08.2013