КОНТЕЙНЕРЫ И ХРАНЕНИЕ ОБЪЕКТОВ

Ограниченное количество объектов с фиксированным временем жизни характерно разве что для относительно простых программ.
В основном ваши программы будут создавать новые объекты на основании критериев, которые станут известны лишь во время их работы. До начала выполнения программы вы не знаете ни количества, ни даже типов нужных вам объектов. Следовательно, использовать именованную ссылку для каждого из возможных объектов не удастся:

 МуТуре aReference;

так как заранее неизвестно, сколько таких ссылок реально потребуется.
В большинстве языков существуют некоторые пути решения этой крайне насущной задачи. В Java предусмотрено несколько способов хранения объектов (или, точнее, ссылок на объекты). Встроенным типом является массив, который мы уже рассмотрели. Библиотека утилит Java (java.util.*) также содержит достаточно полный набор классов контейнеров (также известных, как классы кол­лекций, но, поскольку имя Collection (коллекция) используется для обозначения определенного подмножества библиотеки Java, я буду употреблять общий термин «контейнер»). Контейнеры обладают весьма изощренными возможностями для хранения объектов и работы с ними, и с их помощью удается решить огромное количество задач.

Параметризованные и типизованные контейнеры

Одна из проблем, существовавших при работе с контейнерами до выхода Java SE5, заключалась в том, что компилятор позволял вставить в контейнер объект неверного типа. Для примера рассмотрим один из основных рабочих контейнеров
ArrayList, в котором мы собираемся хранить объекты Apple. Пока рассматривайте ArrayList как «автоматически расширяемый массив». Работать с ним несложно: создайте объект, вставляйте объекты методом add(), обращайтеcь к ним методом get(), используйте индексирование — так же, как для массивов, но без квадратных скобок. ArrayList также содержит метод size(), который возвращает текущее количество элементов в массиве.
В следующем примере в контейнере размещаются объекты Apple и Orange, которые затем извлекаются из него. Обычно компилятор Java выдает предупреждение, потому что в данном примере не используется параметризация, однако в Java SE5 существует специальная директива @SuppressWarnings для подавления предупреждений. Директивы начинаются со знака @ и могут получать аргументы; в данном случае аргумент означает, что подавляются только «непроверяемые» предупреждения:

//: holding/ApplesAndOrangesWithoutGenerics.java
// Простой пример работы с контейнером
// (компилятор выдает предупреждения).
import java.util.*;
 
class Apple {
  private static long counter;
  private final long id = counter++;
  public long id() { return id; }
}
 
class Orange {}	
 
public class ApplesAndOrangesWithoutGenerics {
  @SuppressWarnings("unchecked")
  public static void main(String[] args) {
    ArrayList apples = new ArrayList();
    for(int i = 0; i < 3; i++)
      apples.add(new Apple());
    // He препятствует добавлению объекта Orange:
    apples.add(new Orange());
    for(int i = 0; i < apples.size(); i++)
      ((Apple)apples.get(i)).id();
      // Объект Orange обнаруживается только во время выполнения
  }
}

Директивы Java SE5 будут рассмотрены позднее.
Apple и Orange — совершенно разные классы; они не имеют ничего общего, кроме происхождения от Object (напомню: если в программе явно не указан базовый класс, то в этом качестве используется Object). Так как в ArrayList хранятся объекты Object, метод add() может добавлять в контейнер не только объекты Apple, но и Orange, без ошибок компиляции или времени выполнения. Но при вызове метода get() класса ArrayList вы вместо объекта Apple получаете ссылку на Object, которую необходимо преобразовать в Apple. Все выражение должно быть заключено в круглые скобки, чтобы преобразование было выполнено перед вызовом метода id() класса Apple. Во время выполнения, при попытке преобразования объекта Orange в Apple, произойдет исключение.
В главе «параметризованные типы» вы узнаете, что создание классов, использующих механизм параметризации, может быть довольно сложной задачей. С другой стороны, с применением готовых параметризованных классов проблем обычно не бывает. Например, чтобы определить объект ArrayList, предназначенный для хранения объектов Apple, достаточно использовать вместо имени ArrayList запись АrrayList< Apple>. В угловых скобках перечисляются параметры типов (их может быть несколько), указывающие тип объектов, хранящихся в данном экземпляре контейнера.
Механизм параметризации предотвращает занесение объектов неверного типа в контейнер на стадии компиляции. Рассмотрим тот же пример, но с использованием параметризации:

//: holding/ApplesAndOrangesWithGenerics.java
import java.util.*;
 
public class ApplesAndOrangesWithGenerics {
  public static void main(String[] args) {
    ArrayList<Apple> apples = new ArrayList<Apple>();
    for(int i = 0; i < 3; i++)
      apples.add(new Apple());
    // Ошибка компиляции:
    // apples.add(new Orange());
    for(int i = 0; i < apples.size(); i++)
      System.out.println(apples.get(i).id());
    // Использование foreach:
    for(Apple c : apples)
      System.out.print(c.id() + " ");
  }
}

<spoiler text="Output:">

0 1 2 0 1 2

</spoiler>
На этот раз компилятор не разрешит поместить объекты Orange в контейнер apples, поэтому вы получите ошибку на стадии компиляции (а не на стадии выполнения).
Также обратите внимание на то, что выборка данных из List не требует преобразования типов. Поскольку контейнер знает тип хранящихся в нем элементов, он автоматически выполняет преобразование при вызове get(). Таким образом, параметризация не только позволяет компилятору проверять тип объектов, помещаемых в контейнеры, но и упрощает синтаксис работы с объектами в контейнере. Пример также показывает, что, если индексы элементов вам не нужны, для перебора можно воспользоваться синтаксисом foreach.
Вы не обязаны точно соблюдать тип объекта, указанный в качестве параметра типа. Восходящее преобразование работает с параметризованными контейнерами точно так же, как и с другими типами:

//: holding/GenericsAndUpcasting.java
import java.util.*;
 
class GrannySmith extends Apple {}
class Gala extends Apple {}
class Fuji extends Apple {}
class Braeburn extends Apple {}
 
public class GenericsAndUpcasting {
  public static void main(String[] args) {
    ArrayList<Apple> apples = new ArrayList<Apple>();
    apples.add(new GrannySmith());
    apples.add(new Gala());
    apples.add(new Fuji());
    apples.add(new Braeburn());
    for(Apple c : apples)
      System.out.println(c);
  }
}

<spoiler text="Output:"> (Sample)

GrannySmith@7d772e
Gala@11b86e7
Fuji@35ce36
Braeburn@757aef

</spoiler>
Мы видим, что в контейнер, рассчитанный на хранение объектов Apple, можно помещать объекты типов, производных от Apple.
В результатах, полученных с использованием метода toString() объекта Object, выводится имя класса с беззнаковым шестнадцатеричным представлением хеш-кода объекта (сгенерированного методом hashCode()).

Основные концепции

В библиотеке контейнеров Java проблема хранения объектов делится на две концепции, выраженные в виде базовых интерфейсов библиотеки:

• Коллекция: группа отдельных элементов, сформированная по некоторым правилам. Класс List (список) хранит элементы в порядке вставки, в классе Set (множество) нельзя хранить повторяющиеся элементы, а класс Queue (очередь) выдает элементы в порядке, определяемом спецификой очереди (обычно это порядок вставки элементов в очередь).

• Карта: набор пар объектов «ключ-значение», с возможностью выборки по ключу. ArrayList позволяет искать объекты по порядковым номерам, поэтому в каком-то смысле он связывает числа с объектами. Класс Map (карта — также встречаются термины ассоциативный массив и словарь) позволяет искать объекты по другим объектам — например, получить объект значения по объекту ключа, по аналогии с поиском определения по слову.

Хотя на практике это не всегда возможно, в идеале весь программный код должен писаться в расчете на взаимодействие с этими интерфейсами, а точный тип указывается только в точке создания. Следовательно, объект List может быть создан так:

List<Apple> apples = new ArrayList<Apple>();

Обратите внимание на восходящее преобразование ArrayList к List, в отличие от предыдущих примеров. Если позднее вы решите изменить реализацию, достаточно сделать это в точке создания:

List<Apple> apples = new LinkedList<Apple>();

Итак, в типичной ситуации вы создаете объект реального класса, повышаете его до соответствующего интерфейса, а затем используете интерфейс во всем остальном коде.
Такой подход работает не всегда, потому что некоторые классы обладают дополнительной функциональностью. Например, LinkedList содержит дополнительные методы, не входящие в интерфейс List, а ТrееМар — методы, не входящие в Map. Если такие методы используются в программе, восходящее преобразование к обобщенному интерфейсу невозможно.
Интерфейс Collection представляет концепцию последовательности как способа хранения группы объектов. В следующем простом примере интерфейс Collection (представленный контейнером ArrayList) заполняется объектами Integer, с последующим выводом всех элементов полученного контейнера:

//: holding/SimpleCollection.java
import java.util.*;
 
public class SimpleCollection {
  public static void main(String[] args) {
    Collection<Integer> c = new ArrayList<Integer>();
    for(int i = 0; i < 10; i++)
      c.add(i); // Autoboxing
    for(Integer i : c)
      System.out.print(i + ", ");
  }
}

<spoiler text="Output:">

0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

</spoiler>
Поскольку в этом примере используются только методы Collection, подойдет объект любого класса, производного от Collection, но ArrayList является самым простейшим типом последовательности.

Все коллекции поддерживают перебор в синтаксисе foreach, как в приведенном примере. Позднее в этой главе будет рассмотрена другая, более гибкая концепция итераторов.

Добавление групп элементов

Семейства Arrays и Collections в java.util содержат вспомогательные методы для включения групп элементов в коллекции. Метод Arrays.asList() получает либо массив, либо список элементов, разделенных запятыми, и преобразует его в объект List. Метод Collections.addAll() получает объект Collection и либо массив, либо список, разделенный запятыми, и добавляет элементы в Collection. Пример:

//: holding/AddingGroups.java
// Добавление групп элементов в объекты Collection
import java.util.*;
 
public class AddingGroups {
  public static void main(String[] args) {
    Collection<Integer> collection =
      new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5));
    Integer[] moreInts = { 6, 7, 8, 9, 10 };
    collection.addAll(Arrays.asList(moreInts));
    // Работает намного быстрее, но таким способом 
    // невозможно сконструировать Collection:
    Collections.addAll(collection, 11, 12, 13, 14, 15);
    Collections.addAll(collection, moreInts);
    // Produces a list "backed by" an array:
    List<Integer> list = Arrays.asList(16, 17, 18, 19, 20);
    list.set(1, 99);// Можно - изменение элемента 
    // list.add(21); // Ошибка времени выполнения - нижележащий 
                    // массив не должен изменяться в размерах
  }
}

Конструктор Collection может получать другой объект Collection, используемый для его инициализации, поэтому для передачи исходных данных можно воспользоваться методом Arrays.asList(). Однако метод Collections.addAll() работает намного быстрее, и вы с таким же успехом можете сконструировать Collection без элементов, а затем вызвать Collections.addAll — этот способ считается предпочтительным.
Методу Collection.addAll() в аргументе может передаваться только другой объект Collection, поэтому он уступает в гибкости методам Arrays.asList() и Collections.addAll(), использующим переменные списки аргументов.
Также можно использовать вывод Arrays.asList() напрямую, в виде List, но в этом случае нижележащим представлением будет массив, не допускающий изменения размеров. Вызов add() или delete() для такого списка приведет к попытке изменения размера массива, а это приведет к ошибке во время выполнения.
Недостаток Arrays.asList() заключается в том, что он пытается «вычислить» итоговый тип List, не обращая внимания на то, что ему присваивается. Иногда это создает проблемы:

//: holding/AsListInference.java
// Arrays.asList() makes its best guess about type.
import java.util.*;
 
class Snow {}
class Powder extends Snow {}
class Light extends Powder {}
class Heavy extends Powder {}
class Crusty extends Snow {}
class Slush extends Snow {}
 
public class AsListInference {
  public static void main(String[] args) {
    List<Snow> snow1 = Arrays.asList(
      new Crusty(), new Slush(), new Powder());
 
    // He компилируется-
    // List<Snow> snow2 = Arrays.asList(
    //   new Light(), new Heavy());
    // Сообщение компилятора:
    // found   : java.util.List<Powder>
    // required: java.util.List<Snow>
 
    // Collections.addAll()  работает нормально:
    List<Snow> snow3 = new ArrayList<Snow>();
    Collections.addAll(snow3, new Light(), new Heavy());
 
    // Передача информации посредством уточнения 
    // типа аргумента
    List<Snow> snow4 = Arrays.<Snow>asList(
       new Light(), new Heavy());
  }
}

При попытке создания snow2, Arrays.asList() создает List<Powder> вместо List <Snow>, тогда как Collections.addAll() работает нормально, потому что целевой тип определяется первым аргументом. Как видно из создания snow4, в вызов Arrays.asList() можно вставить «подсказку», которая сообщает компилятору фактический тип объекта List, производимого Arrays.asList().
С контейнерами Map дело обстоит сложнее, и стандартная библиотека Java не предоставляет средств их автоматической инициализации, кроме как по содержимому другого объекта Map.

Source(s): Java 4th edition

Вывод содержимого контейнеров

Для получения печатного представления массива необходимо использовать метод Arrays.toString, но контейнеры отлично выводятся и без посторонней помощи. Следующий пример демонстрирует использование основных типов контейнеров:

//: holding/PrintingContainers.java
// Вывод контейнеров по умолчанию 
import java.util.*;
import static net.mindview.util.Print.*;
 
public class PrintingContainers {
  static Collection fill(Collection<String> collection) {
    collection.add("rat");
    collection.add("cat");
    collection.add("dog");
    collection.add("dog");
    return collection;
  }
  static Map fill(Map<String,String> map) {
    map.put("rat", "Fuzzy");
    map.put("cat", "Rags");
    map.put("dog", "Bosco");
    map.put("dog", "Spot");
    return map;
  }	
  public static void main(String[] args) {
    print(fill(new ArrayList<String>()));
    print(fill(new LinkedList<String>()));
    print(fill(new HashSet<String>()));
    print(fill(new TreeSet<String>()));
    print(fill(new LinkedHashSet<String>()));
    print(fill(new HashMap<String,String>()));
    print(fill(new TreeMap<String,String>()));
    print(fill(new LinkedHashMap<String,String>()));
  }
}

<spoiler text="Output:">

[rat, cat, dog, dog]
[rat, cat, dog, dog]
[dog, cat, rat]
[cat, dog, rat]
[rat, cat, dog]
{dog=Spot, cat=Rags, rat=Fuzzy}
{cat=Rags, dog=Spot, rat=Fuzzy}
{rat=Fuzzy, cat=Rags, dog=Spot}

</spoiler>
Как уже было упомянуто, в библиотеке контейнеров Java существует две основные категории, различающиеся прежде всего тем, сколько в одной ячейке контейнера «помещается» элементов. Коллекции (Collection) содержат только один элемент в каждой ячейке. К этой категории относятся список (List), где в определенной последовательности хранится группа элементов, множество (Set), в которое можно добавлять только по одному элементу определенного типа, и очередь (Queue). В контейнерах Map (карта) хранятся два объекта: ключ и связанное с ним значение.
Из выходных данных программы видно, что вывод по умолчанию (обеспечиваемый методом toString() каждого контейнера) дает вполне приличные результаты. Содержимое Collection выводится в квадратных скобках, с разделением элементов запятыми. Содержимое Map заключается в фигурные скобки, ключи и значения разделяются знаком равенства (ключи слева, значения справа).
Контейнеры ArrayList и LinkedList принадлежат к семейству List, и из выходных данных видно, что элементы в них хранятся в порядке вставки. Они различаются не только скоростью выполнения тех или иных операций, но и тем, что LinkedList содержит больше операций, чем ArrayList.
HashSet, TreeSet и LinkedHashSet относятся к семейству Set. Из выходных данных видно, что в множествах Set каждый элемент хранится только в одном экземпляре, а разные реализации Set используют разный порядок хранения элементов. В HashSet порядок элементов определяется по довольно сложному алгоритму — пока достаточно знать, что этот алгоритм обеспечивает минимальное время выборки элементов, но порядок следования элементов на первый взгляд выглядит хаотично. Если порядок хранения для вас важен, используйте контейнер TreeSet, в котором объекты хранятся отсортированными по возрастанию в порядке сравнения, или LinkedHashSet с хранением элементов в порядке добавления.
Карта (Map) позволяет искать объекты по ключу, как несложная база данных. Объект, ассоциированный с ключом, называется значением. (Карты также называют ассоциативными массивами.)
В нашем примере используются три основные разновидности Map: HashMap, TreeMap и LinkedHashMap. Как и HashSet, HashMap обеспечивает максимальную скорость выборки, а порядок хранения его элементов не очевиден. TreeMap хра­нит ключи отсортированными по возрастанию, a LinkedHashMap хранит ключи в порядке вставки, но обеспечивает скорость поиска HashMap.

List

Контейнеры List гарантируют определенный порядок следования элементов. Интерфейс List дополняет Collection несколькими методами, обеспечивающими вставку и удаление элементов в середине списка. Существует две основные разновидности List:

• Базовый контейнер ArrayList, оптимизированный для произвольного доступа к элементам, но с относительно медленнными операциями вставки (удаления) элементов в середине списка.

• Контейнер LinkedList, оптимизированный для последовательного доступа, с быстрыми операциями вставки (удаления) в середине списка; Произвольный доступ к элементам LinkedList выполняется относительно медленно, но по широте возможностей он превосходит ArrayList.

В следующем примере используется библиотека typenfo.pets из главы «Информация о типе». Она содержит иерархию классов домашних животных Pet, а также ряд вспомогательных средств для случайного построения объектов Pet. Пока достаточно знать, что (1) библиотека содержит класс Pet и производные типы, и (2) статический метод Pets.arrayList() возвращает контейнер ArrayList, заполненный случайно выбранными объектами Pet.

//: holding/ListFeatures.java
import typeinfo.pets.*;
import java.util.*;
import static net.mindview.util.Print.*;
 
public class ListFeatures {
  public static void main(String[] args) {
    Random rand = new Random(47);
    List<Pet> pets = Pets.arrayList(7);
    print("1: " + pets);
    Hamster h = new Hamster();
    pets.add(h); // Автоматическое изменение размера 
    print("2: " + pets);
    print("3: " + pets.contains(h));
    pets.remove(h); // Удаление объекта
    Pet p = pets.get(2);
    print("4: " +  p + " " + pets.indexOf(p));
    Pet cymric = new Cymric();
    print("5: " + pets.indexOf(cymric));
    print("6: " + pets.remove(cymric));
    // Точно заданный объект:
    print("7: " + pets.remove(p));
    print("8: " + pets);
    pets.add(3, new Mouse()); // Вставка no индексу 
    print("9: " + pets);
    List<Pet> sub = pets.subList(1, 4);
    print("subList: " + sub);
    print("10: " + pets.containsAll(sub));
    Collections.sort(sub); // Сортировка "на месте"
    print("sorted subList: " + sub);
    // Для containsAll() порядок неважен:
    print("11: " + pets.containsAll(sub));
    Collections.shuffle(sub, rand); // Случайная перестановка
    print("shuffled subList: " + sub);
    print("12: " + pets.containsAll(sub));
    List<Pet> copy = new ArrayList<Pet>(pets);
    sub = Arrays.asList(pets.get(1), pets.get(4));
    print("sub: " + sub);
    copy.retainAll(sub);
    print("13: " + copy);
    copy = new ArrayList<Pet>(pets); // Получение новой копии 
    copy.remove(2); // Удаление по индексу
    print("14: " + copy);
    copy.removeAll(sub); // Удаление заданных элементов print("15: " + copy);
    print("15: " + copy);
    copy.set(1, new Mouse()); // Замена элемента
    print("16: " + copy);
    copy.addAll(2, sub); // Вставка в середину списка
    print("17: " + copy);
    print("18: " + pets.isEmpty());
    pets.clear(); // Удаление всех элементов
    print("19: " + pets);
    print("20: " + pets.isEmpty());
    pets.addAll(Pets.arrayList(4));
    print("21: " + pets);
    Object[] o = pets.toArray();
    print("22: " + o[3]);
    Pet[] pa = pets.toArray(new Pet[0]);
    print("23: " + pa[3].id());
  }
}

<spoiler text="Output:">

1: [Rat, Manx, Cymric, Mutt, Pug, Cymric, Pug]
2: [Rat, Manx, Cymric, Mutt, Pug, Cymric, Pug, Hamster]
3: true
4: Cymric 2
5: -1
6: false
7: true
8: [Rat, Manx, Mutt, Pug, Cymric, Pug]
9: [Rat, Manx, Mutt, Mouse, Pug, Cymric, Pug]
subList: [Manx, Mutt, Mouse]
10: true
sorted subList: [Manx, Mouse, Mutt]
11: true
shuffled subList: [Mouse, Manx, Mutt]
12: true
sub: [Mouse, Pug]
13: [Mouse, Pug]
14: [Rat, Mouse, Mutt, Pug, Cymric, Pug]
15: [Rat, Mutt, Cymric, Pug]
16: [Rat, Mouse, Cymric, Pug]
17: [Rat, Mouse, Mouse, Pug, Cymric, Pug]
18: false
19: []
20: true
21: [Manx, Cymric, Rat, EgyptianMau]
22: EgyptianMau
23: 14

</spoiler>
Строки вывода пронумерованы, чтобы вам было удобнее связывать результат с исходным кодом.
В первой строке выводится исходный контейнер List с объектами Pets. В отличие от массивов, List поддерживает добавление и удаление элементов с изменением размеров списка. Результат добавления Hamster виден в строке 2: объект появляется в конце списка.

Метод contains() проверяет, присутствует ли объект в списке. Чтобы удалить объект, передайте ссылку на него методу remove(). Кроме того, при наличии ссылки на объект можно узнать его индекс в списке при помощи метода indexOf(), как показано в строке 4.

При проверке вхождения элемента в List, проверке индекса элемента и удаления элемента из List по ссылке используется метод equals() (из корневого класса Object). Все объекты Pet считаются уникальными, поэтому несмотря на присутствие двух объектов Cymric в списке, если я создам новый объект Cymric и передам его indexOf(), результат будет равен -1 (элемент не найден), а вызов remove() вернет false. Для других классов метод equals() может быть определен иначе — например, объекты String считаются равными в случае совпадения содержимого.

В строках 7 и 8 из List успешно удаляется заданный объект. Строка 9 и предшествующий ей код демонстрируют вставку элемента в середину списка. Метод subList() позволяет легко создать «срез» из подмножества элементов списка; естественно, при передаче его методу containsAll() большего списка будет получен истинный результат. Вызовы Collections.sort() и Collections.shuffle() для sub не влияют на результат вызова containsAll().

Метод retainAll() фактически выполняет операцию «пересечения множеств», то есть определения всех элементов сору, которые также присутствуют в sub. И снова поведение метода зависит от реализации equals().

В строке 14 представлен результат удаления элемента по индексу — это проще, чем удаление по ссылке на объект, потому что вам не придется беспокоиться о поведении equals().
Работа метода removeAll() также зависит от equals(). Как подсказывает название, метод удаляет из List все объекты, входящие в List-аргумент.

Название метода set() выбрано неудачно, потому что оно совпадает с именем класса Set — возможно, лучше было бы назвать метод «replace», потому что он заменяет элемент с заданным индексом (первый аргумент) вторым аргументом.

В строке вывода 17 показано, что для List существует перегруженный метод addAll(), вставляющий новый список в середину исходного списка (вместо простого добавления в конец методом addAll(), унаследованным от Collection).

В строках 18-20 представлен результат вызова методов isEmpty() и clear(). Строки 22 и 23 демонстрируют, что любой объект Collection можно преобразовать в массив с использованием toArray().

Итераторы

У любого контейнера должен существовать механизм вставки и выборки элементов. В конце концов, контейнер предназначен именно для хранения объектов. При работе с List для вставки может использоваться метод add(), а для выборки — метод get() (впрочем, существуют и другие способы).

Если взглянуть на ситуацию с более высокого уровня, обнаруживается проблема: чтобы использовать контейнер в программе, необходимо знать его точный тип. Что, если вы начали использовать в программе контейнер List, а затем обнаружили, что в вашем случае будет удобнее применить тот же код к множеству (Set)? Или если вы хотите написать универсальный код, который не зависит от типа контейнера и может применяться к любому контейнеру?

С данной абстракцией хорошо согласуется концепция итератора (iterator). Итератор — это объект, обеспечивающий перемещение по последовательности объектов с выбором каждого объекта этой последовательности, при этом про­граммисту-клиенту не надо знать или заботиться о лежащей в ее основе структуре. Вдобавок, итератор обычно является так называемым «легковесным» (lightweight) объектом: его создание должно обходиться без заметных затрат ресурсов. Из-за этого итераторы часто имеют ограничения; например, Iterator в Java поддерживает перемещение только в одном направлении. Его возможности не так уж широки, но с его помощью можно сделать следующее:

• Запросить у контейнера итератор вызовом метода iterator(). Полученный итератор готов вернуть начальный элемент последовательности при первом вызове своего метода next().

• Получить следующий элемент последовательности вызовом метода next().

• Проверить, остались ли еще объекты в последовательности (метод hasNext()).

• Удалить из последовательности последний элемент, возвращенный итератором, методом remove().

Чтобы увидеть итератор в действии, мы снова воспользуемся иерархией Pets:

//: holding/SimpleIteration.java
import typeinfo.pets.*;
import java.util.*;
 
public class SimpleIteration {
  public static void main(String[] args) {
    List<Pet> pets = Pets.arrayList(12);
    Iterator<Pet> it = pets.iterator();
    while(it.hasNext()) {
      Pet p = it.next();
      System.out.print(p.id() + ":" + p + " ");
    }
    System.out.println();
    // Более простой способ (если подходит):
    for(Pet p : pets)
      System.out.print(p.id() + ":" + p + " ");
    System.out.println();	
    // Итератор также способен удалять элементы:
    it = pets.iterator();
    for(int i = 0; i < 6; i++) {
      it.next();
      it.remove();
    }
    System.out.println(pets);
  }
}

<spoiler text="Output:">

0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx 8:Cymric 9:Rat 10:EgyptianMau 11:Hamster
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx 8:Cymric 9:Rat 10:EgyptianMau 11:Hamster
[Pug, Manx, Cymric, Rat, EgyptianMau, Hamster]

</spoiler>
Мы видим, что с Iterator можно не беспокоиться о количестве элементов в последовательности. Проверка осуществляется методами hasNext() и next().
Если вы просто перебираете элементы списка в одном направлении, не пытаясь модифицировать его содержимое, «синтаксис foreach» обеспечивает более компактную запись.
Iterator удаляет последний элемент, полученный при помощи next(), поэтому перед вызовом remove() необходимо вызвать next().
Теперь рассмотрим задачу создания метода display(), не зависящего от типа контейнера:

//: holding/CrossContainerIteration.java
import typeinfo.pets.*;
import java.util.*;
 
public class CrossContainerIteration {
  public static void display(Iterator<Pet> it) {
    while(it.hasNext()) {
      Pet p = it.next();
      System.out.print(p.id() + ":" + p + " ");
    }
    System.out.println();
  }	
  public static void main(String[] args) {
    ArrayList<Pet> pets = Pets.arrayList(8);
    LinkedList<Pet> petsLL = new LinkedList<Pet>(pets);
    HashSet<Pet> petsHS = new HashSet<Pet>(pets);
    TreeSet<Pet> petsTS = new TreeSet<Pet>(pets);
    display(pets.iterator());
    display(petsLL.iterator());
    display(petsHS.iterator());
    display(petsTS.iterator());
  }
}

<spoiler text="Output:">

0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx
4:Pug 6:Pug 3:Mutt 1:Manx 5:Cymric 7:Manx 2:Cymric 0:Rat
5:Cymric 2:Cymric 7:Manx 1:Manx 3:Mutt 6:Pug 4:Pug 0:Rat

</spoiler>
В методе display() отсутствует информация о типе последовательности, и в этом проявляется истинная мощь итераторов: операция перемещения по последовательности отделяется от фактической структуры этой последовательности. Иногда говорят, что итераторы унифицируют доступ к контейнерам.

Listlterator

Listlterator — более мощная разновидность Iterator, поддерживаемая только классами List. Если Iterator поддерживает перемещение только вперед, ListIterator является двусторонним. Кроме того, он может выдавать индексы следующего и предыдущего элементов по отношению к текущей позиции итератора в списке и заменять последний посещенный элемент методом set(). Вызов listIterator() возвращает ListIterator, указывающий в начало List, а для создания итератора ListIterator, изначально установленного на элемент с индексом n, используется вызов listIterator(n). Все перечисленные возможности продемонстрированы в следующем примере:

//: holding/ListIteration.java
import typeinfo.pets.*;
import java.util.*;
 
public class ListIteration {
  public static void main(String[] args) {
    List<Pet> pets = Pets.arrayList(8);
    ListIterator<Pet> it = pets.listIterator();
    while(it.hasNext())
      System.out.print(it.next() + ", " + it.nextIndex() +
        ", " + it.previousIndex() + "; ");
    System.out.println();
    // В обратном направлении
    while(it.hasPrevious())
      System.out.print(it.previous().id() + " ");
    System.out.println();
    System.out.println(pets);	
    it = pets.listIterator(3);
    while(it.hasNext()) {
      it.next();
      it.set(Pets.randomPet());
    }
    System.out.println(pets);
  }
}

<spoiler text="Output:">

Rat, 1, 0; Manx, 2, 1; Cymric, 3, 2; Mutt, 4, 3; Pug, 5, 4; Cymric, 6, 5; Pug, 7, 6; Manx, 8, 7;
7 6 5 4 3 2 1 0
[Rat, Manx, Cymric, Mutt, Pug, Cymric, Pug, Manx]
[Rat, Manx, Cymric, Cymric, Rat, EgyptianMau, Hamster, EgyptianMau]

</spoiler>
Метод Pets.randomPet() используется для замены всех объектов Pet в списке, начиная с позиции 3 и далее.

LinkedList

LinkedList тоже реализует базовый интерфейс List, как и ArrayList, но выполняет некоторые операции (например, вставку и удаление в середине списка) более эффективно, чем ArrayList. И наоборот, операции произвольного доступа выпол­няются им с меньшей эффективностью.
Класс LinkedList также содержит методы, позволяющие использовать его в качестве стека, очереди (Queue) или двусторонней очереди (дека).
Некоторые из этих методов являются псевдонимами или модификациями для получения имен, более знакомых в контексте некоторого использования. Например, методы getFirst() и element() идентичны — они возвращают начало (первый элемент) списка без его удаления и выдают исключение NoSuchElementException для пустого списка. Метод peek() представляет собой небольшую модификацию этих двух методов: он возвращает null для пустого списка.
Метод addFirst() вставляет элемент в начало списка. Метод offer() делает то же, что add() и addLast() — он добавляет элемент в конец списка. Метод removeLast() удаляет и возвращает последний элемент списка.
Следующий пример демонстрирует схожие и различающиеся аспекты этих методов:

//: holding/LinkedListFeatures.java
import typeinfo.pets.*;
import java.util.*;
import static net.mindview.util.Print.*;
 
public class LinkedListFeatures {
  public static void main(String[] args) {
    LinkedList<Pet> pets =
      new LinkedList<Pet>(Pets.arrayList(5));
    print(pets);
    // Идентично
    print("pets.getFirst(): " + pets.getFirst());
    print("pets.element(): " + pets.element());
    // Различие проявляется только для пустых списков:
    print("pets.peek(): " + pets.peek());
    // Идентично, удаление и возврат первого элемента.
    print("pets.remove(): " + pets.remove());
    print("pets.removeFirst(): " + pets.removeFirst());
    // Различие проявляется только для пустых списков:
    print("pets.poll(): " + pets.poll());
    print(pets);
    pets.addFirst(new Rat());
    print("After addFirst(): " + pets);
    pets.offer(Pets.randomPet());
    print("After offer(): " + pets);
    pets.add(Pets.randomPet());
    print("After add(): " + pets);
    pets.addLast(new Hamster());
    print("After addLast(): " + pets);
    print("pets.removeLast(): " + pets.removeLast());
  }
}

<spoiler text="Output:">

[Rat, Manx, Cymric, Mutt, Pug]
pets.getFirst(): Rat
pets.element(): Rat
pets.peek(): Rat
pets.remove(): Rat
pets.removeFirst(): Manx
pets.poll(): Cymric
[Mutt, Pug]
After addFirst(): [Rat, Mutt, Pug]
After offer(): [Rat, Mutt, Pug, Cymric]
After add(): [Rat, Mutt, Pug, Cymric, Pug]
After addLast(): [Rat, Mutt, Pug, Cymric, Pug, Hamster]
pets.removeLast(): Hamster

</spoiler>
Результат Pets.arrayList() передается конструктору LinkedList для заполнения. Присмотревшись к интерфейсу Queue, вы найдете в нем методы element(), offer(), peek(), poll() и remove(), добавленные в LinkedList для использования в реализации очереди (см. далее).

Стек

Стек часто называют контейнером, работающим по принципу «первым вошел, последним вышел» (LIFO). То есть элемент, последним занесенный в стек, будет первым, полученным при извлечении из стека.
В классе LinkedList имеются методы, напрямую реализующие функциональность стека, поэтому вы просто используете LinkedList, не создавая для стека новый класс. Впрочем, иногда отдельный класс для контейнера-стека лучше справляется с задачей:

//: net/mindview/util/Stack.java
// Making a stack from a LinkedList.
package net.mindview.util;
import java.util.LinkedList;
 
public class Stack<T> {
  private LinkedList<T> storage = new LinkedList<T>();
  public void push(T v) { storage.addFirst(v); }
  public T peek() { return storage.getFirst(); }
  public T pop() { return storage.removeFirst(); }
  public boolean empty() { return storage.isEmpty(); }
  public String toString() { return storage.toString(); }
}

Это простейший пример определения класса с использованием параметризации. Суффикс <Т> после имени класса сообщает компилятору, что тип является параметризованным по типу Т — при использовании класса на место Т будет подставлен фактический тип. Фактически такое определение означает: «Мы определяем класс Stack для хранения объектов типа Т». Stack реализуется на базе LinkedList, также предназначенного для хранения типа Т. Обратите внимание: метод push() получает объект типа Т, а методы реек() и рор() возвращают объект типа Т. Метод реек() возвращает верхний элемент без извлечения из стека, а метод рор() удаляет и возвращает верхний элемент. Простой пример использования нового класса Stack:

//: holding/StackTest.java
import net.mindview.util.*;
 
public class StackTest {
  public static void main(String[] args) {
    Stack<String> stack = new Stack<String>();
    for(String s : "My dog has fleas".split(" "))
      stack.push(s);
    while(!stack.empty())
      System.out.print(stack.pop() + " ");
  }
}

<spoiler text="Output:">

fleas has dog My

</spoiler>
Если вы хотите использовать класс Stack в своем коде, вам придется либо полностью указать пакет, либо изменить имя класса при создании объекта; в противном случае, скорее всего, возникнет конфликт с классом Stack из пакета java.util. Пример использования имен пакетов при импортировании java.util.* в предыдущем примере:

//: holding/StackCollision.java
import net.mindview.util.*;
 
public class StackCollision {
  public static void main(String[] args) {
    net.mindview.util.Stack<String> stack =
      new net.mindview.util.Stack<String>();
    for(String s : "My dog has fleas".split(" "))
      stack.push(s);
    while(!stack.empty())
      System.out.print(stack.pop() + " ");
    System.out.println();
    java.util.Stack<String> stack2 =
      new java.util.Stack<String>();
    for(String s : "My dog has fleas".split(" "))
      stack2.push(s);
    while(!stack2.empty())
      System.out.print(stack2.pop() + " ");
  }
}

<spoiler text="Output:">
fleas has dog My
fleas has dog My
</spoiler>
В java.util нет общего интерфейса Stack — вероятно, из-за того, что имя было задействовано в исходной, неудачно спроектированной версии java.util.Stack для Java 1.0. Хотя класс java.util.Stack существует, LinkedList обеспечивает более качественную реализацию стека, и решение net.mindview.util.Stack является предпочтительным.

Множество

В множествах (Set) каждое значение может храниться только в одном экземпляре. Попытки добавить новый экземпляр эквивалентного объекта блокируются. Множества часто используются для проверки принадлежности, чтобы вы могли легко проверить, принадлежит ли объект заданному множеству. Следовательно, важнейшей операцией Set является операция поиска, поэтому на практике обычно выбирается реализация HashSet, оптимизированная для быстрого поиска.

Set имеет такой же интерфейс, что и Collection. В сущности, Set и является Collection, но обладает несколько иным поведением (кстати, идеальный пример использования наследования и полиморфизма: выражение разных концепций поведения). Пример использования HashSet с объектами Integer:

//: holding/SetOfInteger.java
import java.util.*;
 
public class SetOfInteger {
  public static void main(String[] args) {
    Random rand = new Random(47);
    Set<Integer> intset = new HashSet<Integer>();
    for(int i = 0; i < 10000; i++)
      intset.add(rand.nextInt(30));
    System.out.println(intset);
  }
}

<spoiler text="Output:">
[15, 8, 23, 16, 7, 22, 9, 21, 6, 1, 29, 14, 24, 4, 19, 26, 11, 18, 3, 12, 27, 17, 2, 13, 
28, 20, 25, 10, 5, 0]

</spoiler>
В множество включаются десять тысяч случайных чисел от 0 до 29; естественно, числа должны многократно повторяться. Но при этом мы видим, что в результатах каждое число присутствует только в одном экземпляре.

Также обратите внимание на непредсказуемый порядок следования чисел в выводе. Это объясняется тем, что HashSet использует хеширование для ускорения выборки. Порядок, поддерживаемый HashSet, отличается от порядка TreeSet или LinkedHashSet, поскольку каждая реализация упорядочивает элементы по-своему. Если вы хотите, чтобы результат был отсортирован, воспользуйтесь TreeSet вместо HashSet:

//: holding/SortedSetOfInteger.java
import java.util.*;
 
public class SortedSetOfInteger {
  public static void main(String[] args) {
    Random rand = new Random(47);
    SortedSet<Integer> intset = new TreeSet<Integer>();
    for(int i = 0; i < 10000; i++)
      intset.add(rand.nextInt(30));
    System.out.println(intset);
  }
}

<spoiler text="Output:">

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 
23, 24, 25, 26, 27, 28, 29]

</spoiler>
Одной из наиболее распространенных операций со множествами является проверка принадлежности методом contains(), но существуют и другие операции, которые напомнят вам диаграммы Венна из школьного курса:

//: holding/SetOperations.java
import java.util.*;
import static net.mindview.util.Print.*;
 
public class SetOperations {
  public static void main(String[] args) {
    Set<String> set1 = new HashSet<String>();
    Collections.addAll(set1,
      "A B C D E F G H I J K L".split(" "));
    set1.add("M");
    print("H: " + set1.contains("H"));
    print("N: " + set1.contains("N"));
    Set<String> set2 = new HashSet<String>();
    Collections.addAll(set2, "H I J K L".split(" "));
    print("set2 in set1: " + set1.containsAll(set2));
    set1.remove("H");
    print("set1: " + set1);
    print("set2 in set1: " + set1.containsAll(set2));
    set1.removeAll(set2);
    print("set2 removed from set1: " + set1);
    Collections.addAll(set1, "X Y Z".split(" "));
    print("'X Y Z' added to set1: " + set1);
  }
}

<spoiler text="Output:">

H: true
N: false
set2 in set1: true
set1: [D, K, C, B, L, G, I, M, A, F, J, E]
set2 in set1: false
set2 removed from set1: [D, C, B, G, M, A, F, E]
'X Y Z' added to set1: [Z, D, C, B, G, M, A, F, Y, X, E]

</spoiler>
Имена методов говорят за себя. Информацию о других методах Set можно найти в документации JDK.

Карта

Возможность отображения одних объектов на другие (ассоциация) чрезвычайно полезна при решении широкого класса задач программирования. В качестве примера рассмотрим программу, анализирующую качество распределения класса Java Random. В идеале класс Random должен выдавать абсолютно равномерное распределение чисел, но чтобы убедиться в этом, необходимо сгенерировать большое количество случайных чисел и подсчитать их количество в разных интервалах. Множества упрощают эту задачу: ключом в данном случае является число, сгенерированное при помощи Random, а значением — количество его вхождений:

//: holding/Statistics.java
// Простой пример использования HashMap
import java.util.*;
 
public class Statistics {
  public static void main(String[] args) {
    Random rand = new Random(47);
    Map<Integer,Integer> m =
      new HashMap<Integer,Integer>();
    for(int i = 0; i < 10000; i++) {
      // Получение случайного числа от 0 до 20.
      int r = rand.nextInt(20);
      Integer freq = m.get(r);
      m.put(r, freq == null ? 1 : freq + 1);
    }
    System.out.println(m);
  }
}

<spoiler text="Output:">

{15=497. 4=481. 19=464. 8=468. 11=531. 16=533. 18=478. 3=508, 7=471. 12=521. 17=509. 2=489,  
13=506, 9=549, 6=519, 1=502, 14=477, 10=513, 5=503, 0=481}

</spoiler>
В main() механизм автоматической упаковки преобразует случайно сгенерированое целое число в ссылку на Integer, которая может использоваться с HashMap (контейнеры не могут использоваться для хранения примитивов).

Метод get() возвращает null, если элемент отсутствует в контейнере (то есть если число было сгенерировано впервые. В противном случае метод get() возвращает значение Integer, связанное с ключом, и последнее увеличивается на 1 (автоматическая упаковка снова упрощает вычисления, но в действительности при этом выполняются преобразования к Integer и обратно).

Следующий пример демонстрирует поиск объектов Pet по строковому описанию String. Он также показывает, как проверить присутствие некоторого ключа или значения в Map методами containsKey() и containsValue():

//: holding/PetMap.java
import typeinfo.pets.*;
import java.util.*;
import static net.mindview.util.Print.*;
 
public class PetMap {
  public static void main(String[] args) {
    Map<String,Pet> petMap = new HashMap<String,Pet>();
    petMap.put("My Cat", new Cat("Molly"));
    petMap.put("My Dog", new Dog("Ginger"));
    petMap.put("My Hamster", new Hamster("Bosco"));
    print(petMap);
    Pet dog = petMap.get("My Dog");
    print(dog);
    print(petMap.containsKey("My Dog"));
    print(petMap.containsValue(dog));
  }
}

<spoiler text="Output:">

{My Cat=Cat Molly, My Hamster=Hamster Bosco, My Dog=Dog Ginger}
Dog Ginger
true
true

</spoiler>
Map, по аналогии с массивами и Collection, легко расширяются до нескольких измерений; достаточно создать Map со значениями типа Map (причем значениями этих Map могут быть другие контейнеры, и даже другие Map). Контейнеры легко комбинируются друг с другом, что позволяет быстро создавать сложные структуры данных. Например, если нам потребуется сохранить информацию о владельцах сразу нескольких домашних животных, для этого будет достаточно создать контейнер Map<Person,List<Pet>>:

//: holding/MapOfList.java
package holding;
import typeinfo.pets.*;
import java.util.*;
import static net.mindview.util.Print.*;
 
public class MapOfList {
  public static Map<Person, List<? extends Pet>>
    petPeople = new HashMap<Person, List<? extends Pet>>();
  static {
    petPeople.put(new Person("Dawn"),
      Arrays.asList(new Cymric("Molly"),new Mutt("Spot")));
    petPeople.put(new Person("Kate"),
      Arrays.asList(new Cat("Shackleton"),
        new Cat("Elsie May"), new Dog("Margrett")));
    petPeople.put(new Person("Marilyn"),
      Arrays.asList(
       new Pug("Louie aka Louis Snorkelstein Dupree"),
       new Cat("Stanford aka Stinky el Negro"),
       new Cat("Pinkola")));	
    petPeople.put(new Person("Luke"),
      Arrays.asList(new Rat("Fuzzy"), new Rat("Fizzy")));
    petPeople.put(new Person("Isaac"),
      Arrays.asList(new Rat("Freckly")));
  }
  public static void main(String[] args) {
    print("People: " + petPeople.keySet());
    print("Pets: " + petPeople.values());
    for(Person person : petPeople.keySet()) {
      print(person + " has:");
      for(Pet pet : petPeople.get(person))
        print("    " + pet);
    }
  }
}

<spoiler text="Output:">

People: [Person Luke, Person Marilyn, Person Isaac, Person Dawn, Person Kate]
Pets: [[Rat Fuzzy, Rat Fizzy], [Pug Louie aka Louis Snorkelstein Dupree, Cat Stanford aka Stinky
el Negro, Cat Pinkola], [Rat Freckly], [Cymric Molly, Mutt Spot], [Cat Shackleton, Cat Elsie May,
Dog Margrett]]
Person Luke has:
   Rat Fuzzy
   Rat Fizzy
Person Marilyn has:
   Pug Louie aka Louis Snorkelstein Dupree
   Cat Stanford aka Stinky el Negro
   Cat Pinkola
Person Isaac has:
   Rat Freckly
Person Dawn has:
   Cymric Molly
   Mutt Spot
Person Kate has:
   Cat Shackleton
   Cat Elsie May
   Dog Margrett

</spoiler>
Map может вернуть множество (Set) своих ключей, коллекцию (Collection) значений или множество (Set) всех пар «ключ-значение». Метод keySet() создает множество всех ключей, которое затем используется в синтаксисе foreach для перебора Map.

Очередь

Очередь обычно представляет собой контейнер, работающий по принципу «первым вошел, первым вышел» (FIFO). Иначе говоря, элементы заносятся в очередь с одного «конца» и извлекаются с другого в порядке их поступления. Очереди часто применяются для реализации надежной передачи объектов между разными областями программы.
Класс LinkedList содержит методы, поддерживающие поведение очереди, и реализует интерфейс Queue, поэтому LinkedList может использоваться в качестве реализации Queue. В следующем примере LinkedList повышается восходящим преобразованием до Queue:

//: holding/QueueDemo.java
// Восходящее преобразование LinkedList в Queue
import java.util.*;
 
public class QueueDemo {
  public static void printQ(Queue queue) {
    while(queue.peek() != null)
      System.out.print(queue.remove() + " ");
    System.out.println();
  }
  public static void main(String[] args) {
    Queue<Integer> queue = new LinkedList<Integer>();
    Random rand = new Random(47);
    for(int i = 0; i < 10; i++)
      queue.offer(rand.nextInt(i + 10));
    printQ(queue);
    Queue<Character> qc = new LinkedList<Character>();
    for(char c : "Brontosaurus".toCharArray())
      qc.offer(c);
    printQ(qc);
  }
}

<spoiler text="Output:">

8 1 1 1 5 14 3 1 0 1
B r o n t o s a u r u s

</spoiler>
Метод offer(), один из методов Queue, вставляет элемент в конец очереди, а если вставка невозможна — возвращает false. Методы реек() и element() возвращают начальный элемент без его удаления из очереди, но реек() для пустой очереди возвращает null, a element() выдает исключение NoSuchElementException. Методы poll() и remove() удаляют и возвращают начальный элемент очереди, но poll() для пустой очереди возвращает null, a remove() выдает NoSuchElementException.
Автоматическая упаковка преобразует результат int вызова nextInt() в объект Integer, необходимый для queue, a char с — в объект Character, необходимый для qc. Интерфейс Queue сужает доступ к методам LinkedList так, что доступными остаются только соответствующие методы и у пользователя остается меньше возможностей для вызова методов LinkedList (конечно, queue можно преобразовать обратно в LinkedList, но это создает дополнительные затруднения).

PriorityQueue

Принцип FIFO описывает наиболее типичную организацию очереди. Именно организация очереди определяет, какой элемент будет следующим для заданного состояния очереди. Правило FIFO означает, что следующим элементом будет тот, который дольше всего находится в очереди.

В приоритетной очереди следующим элементом считается элемент, обладающий наивысшим приоритетом. Например, в аэропорту пассажира, самолет которого скоро улетит, могут пропустить без очереди. В системах обработки сообще­ний некоторые сообщения могут быть важнее других и должны обрабатываться как можно скорее, независимо от момента их поступления. Параметризованный класс PriorityQueue был добавлен в Java SE5 как механизм автоматической реали­зации этого поведения.

При помещении объекта в PriorityQueue вызовом offer() объект сортируется в очереди. По умолчанию используется естественный порядок помещения объектов в очередь, однако вы можете изменить его, предоставив собственную реа­лизацию Comparator. PriorityQueue гарантирует, что при вызове peek(), poll() или remove() вы получите элемент с наивысшим приоритетом.

Создание приоритетной очереди для встроенных типов — Integer, String, Character и т. д. — является делом тривиальным. В следующем примере используются те же значения, что и в предыдущем, но PriorityQueue выдает их в другом порядке:

//: holding/PriorityQueueDemo.java
import java.util.*;
 
public class PriorityQueueDemo {
  public static void main(String[] args) {
    PriorityQueue<Integer> priorityQueue =
      new PriorityQueue<Integer>();
    Random rand = new Random(47);
    for(int i = 0; i < 10; i++)
      priorityQueue.offer(rand.nextInt(i + 10));
    QueueDemo.printQ(priorityQueue);
 
    List<Integer> ints = Arrays.asList(25, 22, 20,
      18, 14, 9, 3, 1, 1, 2, 3, 9, 14, 18, 21, 23, 25);
    priorityQueue = new PriorityQueue<Integer>(ints);
    QueueDemo.printQ(priorityQueue);
    priorityQueue = new PriorityQueue<Integer>(
        ints.size(), Collections.reverseOrder());
    priorityQueue.addAll(ints);
    QueueDemo.printQ(priorityQueue);
 
    String fact = "EDUCATION SHOULD ESCHEW OBFUSCATION";
    List<String> strings = Arrays.asList(fact.split(""));
    PriorityQueue<String> stringPQ =
      new PriorityQueue<String>(strings);
    QueueDemo.printQ(stringPQ);
    stringPQ = new PriorityQueue<String>(
      strings.size(), Collections.reverseOrder());
    stringPQ.addAll(strings);
    QueueDemo.printQ(stringPQ);
 
    Set<Character> charSet = new HashSet<Character>();
    for(char c : fact.toCharArray())
      charSet.add(c); // Autoboxing
    PriorityQueue<Character> characterPQ =
      new PriorityQueue<Character>(charSet);
    QueueDemo.printQ(characterPQ);
  }
}

<spoiler text="Output:">

0 1 1 1 1 1 3 5 8 14
1 1 2 3 3 9 9 14 14 18 18 20 21 22 23 25 25
25 25 23 22 21 20 18 18 14 14 9 9 3 3 2 1 1
      A A B C C C D D E E E F H H I I L N N O O O O S S S T T U U U W
W U U U T T S S S O O O O N N L I I H H F E E E D D C C C B A A
 A B C D E F H I L N O S T U W

</spoiler>
Мы видим, что дубликаты разрешены, а меньшие значения обладают более высокими приоритетами. Чтобы показать, как изменить порядок элементов посредством передачи собственного объекта Comparator, при третьем вызове кон­структора PriorityQueue<Integer> и втором — PriorityQueue<String> используется
Comparator с обратной сортировкой, полученный вызовом Collections.reverseOrder() (одно из новшеств Java SE5).
В последней части добавляется HashSet для уничтожения дубликатов Character — просто для того, чтобы пример был чуть более интересным.
Integer, String и Character изначально работают с PriorityQueue, потому что они обладают «встроенным» естественным упорядочением. Если вы хотите использовать собственный класс с PriorityQueue, включите дополнительную реализацию естественного упорядочения или предоставьте собственный объект Comparator.

Collection и Iterator

Collection — корневой интерфейс, описывающий общую функциональность всех последовательных контейнеров. Его можно рассматривать как «вторичный интерфейс», появившийся вследствие сходства между другими интерфейсами. Кроме того, класс java.util.AbstractCollection предоставляет реализацию Collection по умолчанию, поэтому вы можете создать новый подтип AbstractCollection без избыточного дублирования кода.

Один из доводов в пользу интерфейсов заключается в том, что они позволяют создавать более универсальный код. Код, написанный для интерфейса, а не для его реализации, может быть применен к более широкому кругу объектов. Таким образом, если я пишу метод, которому при вызове передается Collection, этот метод будет работать с любым типом, реализующим Collection, — следовательно, если новый класс реализует Collection, он будет совместим с моим методом. Однако интересно заметить, что стандартная библиотека C++ не имеет общего базового класса для своих контейнеров — вся общность контейнеров обеспечивается итераторами. Казалось бы, в Java будет логично последовать примеру C++ и выражать сходство между контейнерами при помощи итераторов, а не Collection. Тем не менее эти два подхода взаимосвязаны, потому что реализация Collection также означает поддержку метода iterator():

//: holding/InterfaceVsIterator.java
import typeinfo.pets.*;
import java.util.*;
 
public class InterfaceVsIterator {
  public static void display(Iterator<Pet> it) {
    while(it.hasNext()) {
      Pet p = it.next();
      System.out.print(p.id() + ":" + p + " ");
    }
    System.out.println();
  }
  public static void display(Collection<Pet> pets) {
    for(Pet p : pets)
      System.out.print(p.id() + ":" + p + " ");
    System.out.println();
  }	
  public static void main(String[] args) {
    List<Pet> petList = Pets.arrayList(8);
    Set<Pet> petSet = new HashSet<Pet>(petList);
    Map<String,Pet> petMap =
      new LinkedHashMap<String,Pet>();
    String[] names = ("Ralph, Eric, Robin, Lacey, " +
      "Britney, Sam, Spot, Fluffy").split(", ");
    for(int i = 0; i < names.length; i++)
      petMap.put(names[i], petList.get(i));
    display(petList);
    display(petSet);
    display(petList.iterator());
    display(petSet.iterator());
    System.out.println(petMap);
    System.out.println(petMap.keySet());
    display(petMap.values());
    display(petMap.values().iterator());
  }	
}

<spoiler text="Output:">

0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx
4:Pug 6:Pug 3:Mutt 1:Manx 5:Cymric 7:Manx 2:Cymric 0:Rat
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx
4:Pug 6:Pug 3:Mutt 1:Manx 5:Cymric 7:Manx 2:Cymric 0:Rat
{Ralph=Rat, Eric=Manx, Robin=Cymric, Lacey=Mutt, Britney=Pug, Sam=Cymric, Spot=Pug, Fluffy=Manx}
[Ralph, Eric, Robin, Lacey, Britney, Sam, Spot, Fluffy]
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx

</spoiler>
Обе версии display() работают как с объектами Map, так и с подтипами Collection; при этом как Collection, так и Iterator изолируют методы display() от знания конкретной реализации используемого контейнера.
В данном случае два решения примерно равноценны. Использование Iterator становится предпочтительным при реализации постороннего класса, для которого реализация интерфейса Collection затруднена или нежелательна. Например, если мы создаем реализацию Collection наследованием от класса, содержащего объекты Pet, нам придется реализовать все методы Collection, даже если они не будут использоваться в методе display(). Хотя проблема легко решается наследованием от AbstractCollection, вам все равно придется реализовать iterator() вместе с size(), чтобы предоставить методы, не реализованные AbstractCollection, но используемые другими методами AbstractCollection:

//: holding/CollectionSequence.java
import typeinfo.pets.*;
import java.util.*;
 
public class CollectionSequence
extends AbstractCollection<Pet> {
  private Pet[] pets = Pets.createArray(8);
  public int size() { return pets.length; }
  public Iterator<Pet> iterator() {
    return new Iterator<Pet>() {
      private int index = 0;
      public boolean hasNext() {
        return index < pets.length;
      }
      public Pet next() { return pets[index++]; }
      public void remove() { // Not implemented
        throw new UnsupportedOperationException();
      }
    };
  }	
  public static void main(String[] args) {
    CollectionSequence c = new CollectionSequence();
    InterfaceVsIterator.display(c);
    InterfaceVsIterator.display(c.iterator());
  }
}

<spoiler text="Output:">

0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx

</spoiler>
Метод remove() является необязательной операцией. В нашем примере реализовывать его не нужно, и в случае вызова он выдает исключение.
Из приведенного примера видно, что при реализации Collection вы также реализуете iterator(), а простая отдельная реализация iterator() требует чуть меньших усилий, чем наследование от AbstractCollection. Но, если класс уже наследует от другого класса, наследование еще и от AbstractCollection невозможно. В этом случае для реализации Collection придется реализовать все методы интерфейса, и тогда гораздо проще ограничиться наследованием и добавить возможность создания итератора:

//: holding/NonCollectionSequence.java
import typeinfo.pets.*;
import java.util.*;
 
class PetSequence {
  protected Pet[] pets = Pets.createArray(8);
}
 
public class NonCollectionSequence extends PetSequence {
  public Iterator<Pet> iterator() {
    return new Iterator<Pet>() {
      private int index = 0;
      public boolean hasNext() {
        return index < pets.length;
      }
      public Pet next() { return pets[index++]; }
      public void remove() { // Not implemented
        throw new UnsupportedOperationException();
      }
    };
  }
  public static void main(String[] args) {
    NonCollectionSequence nc = new NonCollectionSequence();
    InterfaceVsIterator.display(nc.iterator());
  }
}

<spoiler text="Output:">

0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx

</spoiler>
Создание Iterator обеспечивает минимальную логическую привязку между последовательностью и методом, использующим эту последовательность, а также налагает гораздо меньше ограничений на класс последовательности, реализующий Collection.

Синтаксис foreach и итераторы

До настоящего момента «синтаксис foreach» использовался в основном с массивами, но он также будет работать с любым объектом Collection. Некоторые примеры уже встречались нам при работе с ArrayList, но можно привести и более об­щее подтверждение:

//: holding/ForEachCollections.java
// Синтаксис foreach работает с любыми коллекциями
import java.util.*;
 
public class ForEachCollections {
  public static void main(String[] args) {
    Collection<String> cs = new LinkedList<String>();
    Collections.addAll(cs,
      "Take the long way home".split(" "));
    for(String s : cs)
      System.out.print("'" + s + "' ");
  }
}

<spoiler text="Output:">

'Take' 'the' 'long' 'way' 'home' 

</spoiler>
Поскольку cs является Collection, этот пример показывает, что поддержка foreach является характеристикой всех объектов Collection.
Работа этой конструкции объясняется тем, что в Java SE5 появился новый интерфейс Iterable, который содержит метод iterator() для создания Iterator, и именно интерфейс Iterable используется при переборе последовательности в синтаксисе foreach. Следовательно, создав любой класс, реализующий Iterable, вы сможете использовать его в синтаксисе foreach:

//: holding/IterableClass.java
// Любой Iterable работает с foreach.
import java.util.*;
 
public class IterableClass implements Iterable<String> {
  protected String[] words = ("And that is how " +
    "we know the Earth to be banana-shaped.").split(" ");
  public Iterator<String> iterator() {
    return new Iterator<String>() {
      private int index = 0;
      public boolean hasNext() {
        return index < words.length;
      }
      public String next() { return words[index++]; }
      public void remove() { // Не реализован
        throw new UnsupportedOperationException();
      }
    };
  }	
  public static void main(String[] args) {
    for(String s : new IterableClass())
      System.out.print(s + " ");
  }
}

<spoiler text="Output:">

And that is how we know the Earth to be banana-shaped.

</spoiler>
Метод iterator() возвращает экземпляр анонимной внутренней реализации Iterator<String>, последовательно доставляющей каждое слово в массиве. В main() мы видим, что IterableClass действительно работает в синтаксисе foreach.
В Java SE5 многие классы реализуют Iterable, прежде всего все классы Collection (но не Map). Например, следующий код выводит все переменные окружения (environment) операционной системы:

//: holding/EnvironmentVariables.java
import java.util.*;
 
public class EnvironmentVariables {
  public static void main(String[] args) {
    for(Map.Entry entry: System.getenv().entrySet()) {
      System.out.println(entry.getKey() + ": " +
        entry.getValue());
    }
  }
} /* (Execute to see output) */

System.getenv() возвращает Map, entrySet() создает Set с элементами Map.Entry, a Set поддерживает Iterable и поэтому может использоваться в цикле foreach.
Синтаксис foreach работает с массивами и всем, что поддерживает Iterable, но это не означает, что массив автоматически поддерживает Iterable:

//: holding/ArrayIsNotIterable.java
import java.util.*;
 
public class ArrayIsNotIterable {
  static <T> void test(Iterable<T> ib) {
    for(T t : ib)
      System.out.print(t + " ");
  }
  public static void main(String[] args) {
    test(Arrays.asList(1, 2, 3));
    String[] strings = { "A", "B", "C" };
    // Массив работает в foreach. но не является Iterable:
    //! test(strings);
    // его необходимо явно преобразовать к Iterable:
    test(Arrays.asList(strings));
  }
}

<spoiler text="Output:">

1 2 3 A B C

</spoiler>
Попытка передачи массива в аргументе Iterable завершается неудачей. Автоматическое преобразование в Iterable не производится; его необходимо выполнять вручную.

Идиома «метод-адаптер»

Что делать, если у вас имеется существующий класс, реализующий Iterable, и вы хотите добавить новые способы использования этого класса в синтаксисе foreach? Допустим, вы хотите иметь возможность выбора между перебором списка слов в прямом или обратном направлении. Если просто воспользоваться наследованием от класса и переопределить метод iterator, то существующий метод будет заменен и никакого выбора не будет.
Одно из решений этой проблемы основано на использовании идиомы, которую я называю «методом-адаптером». Термин «адаптер» происходит от одноименного паттерна: вы должны предоставить интерфейс, необходимый для работы синтаксиса foreach. Если у вас имеется один интерфейс, а нужен другой, проблема решается написанием адаптера. В данном случае требуется добавить к стандартному «прямому» итератору обратный, так что переопределение исключено. Вместо этого мы добавим метод, создающий объект Iterable, который может использоваться в синтаксисе foreach. Как будет показано далее, это позволит нам предоставить несколько вариантов использования foreach:

//: holding/AdapterMethodIdiom.java
// Идиома "метод-адаптер" позволяет использовать foreach
// с дополнительными разновидностями Iterable.
import java.util.*;
 
class ReversibleArrayList<T> extends ArrayList<T> {
  public ReversibleArrayList(Collection<T> c) { super(c); }
  public Iterable<T> reversed() {
    return new Iterable<T>() {
      public Iterator<T> iterator() {
        return new Iterator<T>() {
          int current = size() - 1;
          public boolean hasNext() { return current > -1; }
          public T next() { return get(current--); }
          public void remove() { // // He реализован
            throw new UnsupportedOperationException();
          }
        };
      }
    };
  }
}	
 
public class AdapterMethodIdiom {
  public static void main(String[] args) {
    ReversibleArrayList<String> ral =
      new ReversibleArrayList<String>(
        Arrays.asList("To be or not to be".split(" ")));
    // Получаем обычный итератор, полученный при помощи iterator():
    for(String s : ral)
      System.out.print(s + " ");
    System.out.println();
    // Передаем выбранный нами Iterable
    for(String s : ral.reversed())
      System.out.print(s + " ");
  }
}

<spoiler text="Output:">

To be or not to be 
be to not or be To 

</spoiler>
Если просто поместить объект ral в синтаксис foreach, мы получим (стандартный) «прямой» итератор. Но если вызвать для объекта reversed(), поведение изменится.
Использовав этот прием, можно добавить в пример IterableClass.java два метода-адаптера:

//: holding/MultiIterableClass.java
// Adding several Adapter Methods.
import java.util.*;
 
public class MultiIterableClass extends IterableClass {
  public Iterable<String> reversed() {
    return new Iterable<String>() {
      public Iterator<String> iterator() {
        return new Iterator<String>() {
          int current = words.length - 1;
          public boolean hasNext() { return current > -1; }
          public String next() { return words[current--]; }
          public void remove() { He реализован
            throw new UnsupportedOperationException();
          }
        };
      }
    };
  }	
  public Iterable<String> randomized() {
    return new Iterable<String>() {
      public Iterator<String> iterator() {
        List<String> shuffled =
          new ArrayList<String>(Arrays.asList(words));
        Collections.shuffle(shuffled, new Random(47));
        return shuffled.iterator();
      }
    };
  }	
  public static void main(String[] args) {
    MultiIterableClass mic = new MultiIterableClass();
    for(String s : mic.reversed())
      System.out.print(s + " ");
    System.out.println();
    for(String s : mic.randomized())
      System.out.print(s + " ");
    System.out.println();
    for(String s : mic)
      System.out.print(s + " ");
  }
}

<spoiler text="Output:">

banana-shaped. be to Earth the know we how is that And
is banana-shaped. Earth that how the be And we know to
And that is how we know the Earth to be banana-shaped.

</spoiler>
Из выходных данных видно, что метод Collections.shuffle не изменяет исходный массив, а только переставляет ссылки в shuffled. Так происходит только потому, что метод randomized() создает для результата Arrays.asList() «обертку» в виде ArrayList. Если бы операция выполнялась непосредственно с объектом List, полученным от Arrays.asList(), то это привело бы к изменению нижележащего массива:

//: holding/ModifyingArraysAsList.java
import java.util.*;
 
public class ModifyingArraysAsList {
  public static void main(String[] args) {
    Random rand = new Random(47);
    Integer[] ia = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    List<Integer> list1 =
      new ArrayList<Integer>(Arrays.asList(ia));
    System.out.println("До перестановки : " + list1);
    Collections.shuffle(list1, rand);
    System.out.println("После перестановки : " + list1);
    System.out.println("Массив: " + Arrays.toString(ia));
 
    List<Integer> list2 = Arrays.asList(ia);
    System.out.println("До перестановки : " + list2);
    Collections.shuffle(list2, rand);
    System.out.println("После перестановки : " + list2);
    System.out.println("Массив: " + Arrays.toString(ia));
  }
}

<spoiler text="Output:">

До перестановки : [1, 2, 3. 4, 5. 6. 7. 8, 9, 10] 
После перестановки : [4. 6, 3, 1. 8. 7, 2, 5. 10. 9]
Массив: [1, 2. 3. 4. 5. 6. 7, 8. 9. 10]
До перестановки : [1, 2. 3, 4, 5. 6. 7. 8, 9, 10]
После перестановки : [9. 1. 6. 3. 7, 2. 5, 10, 4. 8]
Массив: [9. 1, 6. 3. 7, 2, 5. 10. 4. 8]

</spoiler>
В первом случае вывод Arrays.asList() передается конструктору ArrayList(), а последний создает объект ArrayList, ссылающийся на элементы ia. Перестановка этих ссылок не изменяет массива. Но, если мы используем результат Arrays.asList(ia) напрямую, перестановка изменит порядок ia. Важно учитывать, что Arrays.asList() создает объект List, который использует нижележащий массив в качестве своей физической реализации. Если с этим объектом List выполняются какие-либо изменяющие операции, но вы не хотите изменения исходного массива, создайте копию в другом контейнере.

Резюме

В Java существует несколько способов хранения объектов:

• В массивах объектам назначаются числовые индексы. Массив содержит объекты заранее известного типа, поэтому преобразование типа при выборке объекта не требуется. Массив может быть многомерным и может использоваться для хранения примитивных типов. Тем не менее изменить размер созданного массива невозможно.

• В Collection хранятся отдельные элементы, а в Map — пары ассоциированных элементов. Механизм параметризации позволяет задать тип объектов, хранимых в контейнере, поэтому поместить в контейнер объект неверного типа невозможно, и элементы не нуждаются в преобразовании типа при выборке. И Collection, и Map автоматически изменяются в размерах при добавлении новых элементов. В контейнерах не могут храниться примитивы, но механизм автоматической упаковки автоматически создает объектные «обертки», сохраняемые в контейнере.

• В контейнере List, как и в массиве, объектам назначаются числовые индексы — таким образом, массивы и List являются упорядоченными контейнерами.

• Используйте ArrayList при частом использовании произвольного доступа к элементам или LinkedList при частом выполнении операций вставки и удаления в середине списка.

• Поведение очередей и стеков обеспечивается контейнером LinkedList.

• Контейнер Map связывает с объектом не целочисленный индекс, а другой объект. Контейнеры HashMap оптимизированы для быстрого доступа, а контейнер TreeMap хранит ключи в отсортированном порядке, но уступает по скорости HashMap. В контейнере LinkedHashMap элементы хранятся в порядке вставки, но хеширование обеспечивает быстрый доступ.

• В контейнере Set каждый объект может храниться только в одном экземпляре. Контейнер HashSet обеспечивает максимальную скорость поиска, а в TreeSet элементы хранятся в отсортированном порядке. В контейнере LinkedHashSet элементы хранятся в порядке вставки.

• Использовать старые классы Vector, Hashtable и Stack в новом коде не нужно.

Контейнеры Java — необходимый инструмент, которым вы будете постоянно пользоваться в своей повседневной работе; благодаря им ваш код станет более простым, мощным и эффективным. Возможно, на освоение некоторых аспектов контейнеров потребуется время, но вы быстро привыкнете к классам этой библиотеки и начнете использовать их.