Итерация върху колекции в Java

Всеки път, когато имате колекция от неща, ще ви е необходим някакъв механизъм за систематично стъпване през елементите в тази колекция. Като ежедневен пример, разгледайте дистанционното управление на телевизора, което ни позволява да прелистваме през различни телевизионни канали. По подобен начин в света на програмирането се нуждаем от механизъм за систематично итерация чрез колекция от софтуерни обекти. Java включва различни механизми за итерация, включително индекс (за итерация над масив), курсор (за итерация върху резултатите от заявка към база данни), изброяване (в ранните версии на Java) и итератор (в по-новите версии на Java).

Моделът на Итератора

Един итератор е механизъм, който позволява на всички елементи на една колекция, за да бъдат достъпни последователно, като някои от експлоатация, която се извършва на всеки елемент. По същество итераторът осигурява средство за „циклиране“ върху капсулирана колекция от обекти. Примерите за използване на итератори включват

  • Посетете всеки файл в директория ( известна още като папка) и покажете името му.
  • Посетете всеки възел в графика и определете дали той е достъпен от даден възел.
  • Посетете всеки клиент на опашка (например, симулиране на линия в банка) и разберете колко време той или тя чака.
  • Посетете всеки възел в абстрактното дърво на синтаксиса на компилатора (което се създава от анализатора) и извършете семантична проверка или генериране на код. (Можете също да използвате шаблона на посетителя в този контекст.)

Прилагат се определени принципи за използването на итератори: Като цяло трябва да имате възможност да имате няколко хода едновременно; т.е. итератор трябва да позволява концепцията за вложен цикъл. Итераторът също трябва да бъде неразрушителен в смисъл, че актът на итерация сам по себе си не трябва да променя колекцията. Разбира се, операцията, която се извършва върху елементите в колекция, може да промени някои от елементите. Може да е възможно итераторът да поддържа премахване на елемент от колекция или вмъкване на нов елемент в определена точка от колекцията, но такива промени трябва да са изрични в рамките на програмата, а не страничен продукт от итерацията. В някои случаи ще трябва да имате итератори с различни методи за обхождане; например обхождане на дърво преди или след поръчка на дърво или обхождане на графика първо и по дълбочина.

Итерация на сложни структури от данни

За първи път се научих да програмирам в ранна версия на FORTRAN, където единствената възможност за структуриране на данни беше масив. Бързо се научих как да преглеждам масив, използвайки индекс и DO-цикъл. Оттам беше само кратък умствен скок към идеята да се използва общ индекс в множество масиви, за да се симулира масив от записи. Повечето езици за програмиране имат функции, подобни на масивите, и те поддържат пряк цикъл по масивите. Но съвременните езици за програмиране поддържат и по-сложни структури от данни като списъци, набори, карти и дървета, където възможностите се предоставят чрез публични методи, но вътрешните детайли са скрити в частни части на класа. Програмистите трябва да могат да преминават през елементите на тези структури от данни, без да излагат вътрешната си структура, което е целта на итераторите.

Итератори и бандата на четири дизайнерски модела

Според Gang of Four (виж по-долу), моделът за дизайн на Iterator е поведенчески модел, чиято ключова идея е „да поеме отговорността за достъп и обръщане от списъка [ обект на колекция на мисли ] и да го постави в итератор обект. " Тази статия не е толкова за модела на Итератор, колкото за това как итераторите се използват на практика. За да обхване изцяло модела, ще е необходимо да се обсъди как ще бъде проектиран итератор, участници (обекти и класове) в дизайна, възможни алтернативни проекти и компромиси на различни алтернативи на дизайна. Предпочитам да се съсредоточа върху начина, по който итераторите се използват на практика, но ще ви насоча към няколко източника за изследване на шаблона на Iterator и моделите на проектиране като цяло:

  • Дизайнерски модели: Елементи на многократно използвания обектно-ориентиран софтуер (Addison-Wesley Professional, 1994), написан от Erich Gamma, Richard Helm, Ralph Johnson и John Vlissides (известен също като Gang of Four или просто GoF) е окончателният ресурс за обучение за дизайнерските модели. Въпреки че книгата е публикувана за първи път през 1994 г., тя остава класика, за което свидетелства фактът, че има над 40 отпечатъка.
  • Боб Тар, преподавател в Университета на Мериленд, окръг Балтимор, има отличен набор от слайдове за своя курс по дизайнерски модели, включително въведението му в модела на Итератор.
  • Java Design Patterns от серията JavaWorld на David Geary представя много от моделите на Gang of Four, включително модели на Singleton, Observer и Composite. Също така на JavaWorld, по-новият тридесетен преглед на дизайнерските модели на Джеф Фризън включва ръководство за моделите на GoF.

Активни итератори срещу пасивни итератори

Има два основни подхода за прилагане на итератор в зависимост от това кой контролира итерацията. За активен итератор (известен също като изричен итератор или външен итератор ), клиентът контролира итерацията в смисъл, че клиентът създава итератора, казва му кога да премине към следващия елемент, тества дали всеки елемент е бил посетен, и така нататък. Този подход е често срещан в езици като C ++ и именно подходът получава най-голямо внимание в книгата GoF. Въпреки че итераторите в Java са приемали различни форми, използването на активен итератор по същество е единствената жизнеспособна опция преди Java 8.

За пасивен итератор (известен също като имплицитен итератор , вътрешен итератор или итератор за обратно извикване ), самият итератор контролира итерацията. Клиентът по същество казва на итератора: „извършете тази операция върху елементите в колекцията“. Този подход е често срещан в езици като LISP, които предоставят анонимни функции или затваряне. С пускането на Java 8, този подход към итерацията вече е разумна алтернатива за програмистите на Java.

Схеми за именуване на Java 8

Въпреки че не е чак толкова зле като Windows (NT, 2000, XP, VISTA, 7, 8, ...), историята на версиите на Java включва няколко схеми за именуване. За начало трябва ли да се позоваваме на стандартното издание на Java като „JDK“, „J2SE“ или „Java SE“? Номерата на версиите на Java започнаха доста лесно - 1.0, 1.1 и т.н. - но всичко се промени с версия 1.5, която беше с марка Java (или JDK) 5. Когато се позовавам на ранните версии на Java, използвам фрази като "Java 1.0" или "Java 1.1, "но след петата версия на Java използвам фрази като" Java 5 "или" Java 8. "

За да илюстрирам различните подходи за итерация в Java, имам нужда от пример за колекция и нещо, което трябва да се направи с нейните елементи. За началната част на тази статия ще използвам колекция от низове, представляващи имена на неща. За всяко име в колекцията просто ще отпечатам стойността му на стандартен изход. Тези основни идеи лесно се разширяват до колекции от по-сложни обекти (като служители) и където обработката за всеки обект е малко по-ангажирана (като даване на повишен 4,5% на всеки високо оценен служител).

Други форми на итерация в Java 8

Фокусирам се върху итерация върху колекции, но има и други, по-специализирани форми на итерация в Java. Например можете да използвате JDBC, за ResultSetда прегледате редовете, върнати от заявка SELECT в релационна база данни, или да използвате Scannerитерация над входен източник.

Итерация с класа Enumeration

В Java 1.0 и 1.1 двата основни класа на колекция бяха Vectorи Hashtable, а моделът за проектиране на Iterator беше реализиран в клас, наречен Enumeration. В ретроспекция това беше лошо име за класа. Не бъркайте класа Enumerationс концепцията за вида ENUM , които не се появи, докато Java 5. Днес и двете Vectorи Hashtableса генерични класове, но тогава генеричните лекарства не са част от езика Java. Кодът, който да обработва вектор от низове, Enumerationще изглежда нещо като Листинг 1.

Листинг 1. Използване на изброяване за итерация над вектор от низове

 Vector names = new Vector(); // ... add some names to the collection Enumeration e = names.elements(); while (e.hasMoreElements()) { String name = (String) e.nextElement(); System.out.println(name); } 

Итерация с клас Iterator

Java 1.2 introduced the collection classes that we all know and love, and the Iterator design pattern was implemented in a class appropriately named Iterator. Because we didn't yet have generics in Java 1.2, casting an object returned from an Iterator was still necessary. For Java versions 1.2 through 1.4, iterating over a list of strings might resemble Listing 2.

Listing 2. Using an Iterator to iterate over a list of strings

 List names = new LinkedList(); // ... add some names to the collection Iterator i = names.iterator(); while (i.hasNext()) { String name = (String) i.next(); System.out.println(name); } 

Iteration with generics and the enhanced for-loop

Java 5 gave us generics, the interface Iterable, and the enhanced for-loop. The enhanced for-loop is one of my all-time-favorite small additions to Java. The creation of the iterator and calls to its hasNext() and next() methods are not expressed explicitly in the code, but they still take place behind the scenes. Thus, even though the code is more compact, we are still using an active iterator. Using Java 5, our example would look something like what you see in Listing 3.

Listing 3. Using generics and the enhanced for-loop to iterate over a list of strings

 List names = new LinkedList(); // ... add some names to the collection for (String name : names) System.out.println(name); 

Java 7 gave us the diamond operator, which reduces the verbosity of generics. Gone were the days of having to repeat the type used to instantiate the generic class after invoking the new operator! In Java 7 we could simplify the first line in Listing 3 above to the following:

 List names = new LinkedList(); 

A mild rant against generics

The design of a programming language involves tradeoffs between the benefits of language features versus the complexity they impose on the syntax and semantics of the language. For generics, I am not convinced that the benefits outweigh the complexity. Generics solved a problem that I did not have with Java. I generally agree with Ken Arnold's opinion when he states: "Generics are a mistake. This is not a problem based on technical disagreements. It's a fundamental language design problem [...] The complexity of Java has been turbocharged to what seems to me relatively small benefit."

Fortunately, while designing and implementing generic classes can sometimes be overly complicated, I have found that using generic classes in practice is usually straightforward.

Iteration with the forEach() method

Before delving into Java 8 iteration features, let's reflect on what's wrong with the code shown in the previous listings–which is, well, nothing really. There are millions of lines of Java code in currently deployed applications that use active iterators similar to those shown in my listings. Java 8 simply provides additional capabilities and new ways of performing iteration. For some scenarios, the new ways can be better.

The major new features in Java 8 center on lambda expressions, along with related features such as streams, method references, and functional interfaces. These new features in Java 8 allow us to seriously consider using passive iterators instead of the more conventional active iterators. In particular, the Iterable interface provides a passive iterator in the form of a default method called forEach().

A default method, another new feature in Java 8, is a method in an interface with a default implementation. In this case, the forEach() method is actually implemented using an active iterator in a manner similar to what you saw in Listing 3.

Collection classes that implement Iterable (for example, all list and set classes) now have a forEach() method. This method takes a single parameter that is a functional interface. Therefore the actual parameter passed to the forEach() method is a candidate for a lambda expression. Using the features of Java 8, our running example would evolve to the form shown in Listing 4.

Listing 4. Iteration in Java 8 using the forEach() method

 List names = new LinkedList(); // ... add some names to the collection names.forEach(name -> System.out.println(name)); 

Note the difference between the passive iterator in Listing 4 and the active iterator in the previous three listings. In the first three listings, the loop structure controls the iteration, and during each pass through the loop, an object is retrieved from the list and then printed. In Listing 4, there is no explicit loop. We simply tell the forEach() method what to do with the objects in the list — in this case we simply print the object. Control of the iteration resides within the forEach() method.

Iteration with Java streams

Сега нека помислим да направим нещо малко по-ангажирано, отколкото просто да отпечатаме имената в нашия списък. Да предположим, например, че искаме да се преброят на имена, които започват с буквата А . Можем да внедрим по-сложната логика като част от ламбда израза или да използваме новия API на Stream Java 8. Нека възприемем последния подход.