Гарантирано ли е итерирането на опашка‹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
Мисля, че повечето хора пропускат смисъла на вашия въпрос. Опашката се определя от това как работят натисканията и пуканията. Итерирането в този метод не е дефинирано в нормалната дефиниция на опашка   -  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 на следващия елемент.

Това обаче не засяга какъв ще бъде първият елемент в колекцията. За да отговорим на този въпрос, трябва да отидем на описанието на самата опашка:

Представлява колекция от обекти първи влязъл, първи излязъл.

Комбинирайки двете горни твърдения, имаме официалния кодов договор, че първият обект, върнат от Enumerator, ще бъде първият елемент в колекцията и факта, че първият елемент в колекцията ще бъде първият обект, добавен към колекцията, което ни дава окончателния изход, че итерацията над 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 за Queue. В обобщение (както казаха и други) сте готови. 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