Skip to content

Latest commit

 

History

History
146 lines (107 loc) · 13.7 KB

05_Collections_Lists.adoc

File metadata and controls

146 lines (107 loc) · 13.7 KB
Raw

Коллекции, итераторы, списки

Здесь мы начинаем рассматривать библиотеку коллекций Java.

Основные понятия

Библиотека коллекций строится на трёх видах кирпичей:

  • интерфейсы interface определяют, что именно умеет делать тот или иной объект, но обычно ничего не говорят о том, как он это делает

  • абстрактные классы abstract class содержат так называемую частичную реализацию объекта; в библиотеке коллекций они, как правило, реализуют все необходимые методы через несколько базовых

  • классы class отвечают на вопрос о том, какие именно данные хранит объект и как именно он осуществляет те или иные операции

В прикладном коде интерфейсы обычно используются для определения типов переменных, параметров, полей, результатов методов; классы — для создания объектов при вызове их конструкторов. Абстрактные классы в прикладном коде используются сравнительно редко, они позволяют за короткое время написать свою реализацию коллекции, если это потребовалось.

Для описания отношений вида подтип, подвид используется концепция наследования. В объектно-ориентированном программировании ситуация, когда класс (интерфейс) Б является наследником класса (интерфейса) А, означает, что:

  • по смыслу объект типа Б является разновидностью объекта типа А

  • объект типа Б можно употреблять везде, где нужен тип А

  • объект типа Б содержит все данные, которые есть в объекте типа А (и, возможно, какие-либо другие)

  • на объекте типа Б можно вызывать все методы, которые можно вызывать на объекте типа А (и, возможно, какие-либо другие)

Сокращённо говорят, что "public inheritance means IS A", или "открытое наследование означает ЭТО ЕСТЬ". В Java любое наследование считается открытым (в отличие от, например, C++). Кроме этого, с наследованием связано ещё два специальных слова:

  • про класс Б можно сказать, что он расширяет класс А или реализует интерфейс А (в обоих случаях он является наследником А)

  • про интерфейс Б можно сказать, что он расширяет интерфейс А (и опять-таки это синоним слова "наследник")

  • интерфейс Б никогда не может являться наследником класса А (запрещено правилами Java).

Иерархия коллекций

Коллекции Java образуют иерархию наследования. С ней можно ознакомиться, например, здесь: https://en.wikipedia.org/wiki/Java_collections_framework. Подобное изображение иерархий распространено среди программистов; в них наследник всегда рисуется ниже своего базового класса (интерфейса) и соединяется с ним стрелкой, ведущей в сторону базового класса (интерфейса).

Вершиной иерархии коллекций, а следовательно, самым общим типом, является интерфейс Iterable. Его свойства наследуют все коллекции библиотеки. Благодаря этому интерфейсу нам доступен в Java код следующего вида

    public static void foo(Iterable<String> container) {
        for (String element: container) {
            bar(element);
        }
    }

На месте Iterable здесь может стоять Collection, List, Set, Queue и цикл for-each всё равно будет для них доступен. Интерфейс Iterable тесно связан с интерфейсом-помощником Iterator (так говорят в ситуации, когда помощник является бессмысленным без основного интерфейса, и наоборот). Его формальное описание выглядит так:

public interface Iterable<E> {
    Iterator<E> iterator(); // то есть Iterable даёт возможность получить Iterator
}

Iterator является чем-то вроде указателя, путешествующего по коллекции. В момент создания он "смотрит" перед нулевым элементом коллекции. Итератор содержит три метода:

public interface Iterator<E> {
    boolean hasNext(); // Возвращает true, если за итератором есть ещё элементы
    E next(); // Возвращает следующий элемент за итератором И передвигает итератор за него
    void remove(); // Удаляет из коллекции элемент, который вернул последний вызов next
}

Порядок ручного использования итератора в общем случае выглядит так:

  1. Создать итератор с помощью вызова iterator().

  2. Проверить, есть ли следующий элемент hasNext(). Если его нет — перебор закончен.

  3. Достать следующий элемент next().

  4. Сделать необходимую его обработку. Если для данного элемента это требуется, его можно удалить вызовом метода remove().

  5. Вернуться к пункту 2.

Всё то же самое можно выполнить с помощью обычного цикла for-each, кроме удаления элемента.

    public static void foo(Iterable<String> container) {
        for (String element: container) {
            bar(element);
        }
        // Is equivalent to
        Iterator<String> it = container.iterator();
        while (it.hasNext()) {
            String element = it.next();
            bar(element);
        }
    }

Важно, однако, отметить, что удалить элемент в цикле for-each невозможно. Например:

public class SomeClass {
    private static boolean condition(String s) {
        return ...// Some condition
    }

    public static void foo(Collection<String> container) {
        Iterator<String> it = container.iterator();
        while (it.hasNext()) {
            String element = it.next();
            if (condition(element)) it.remove();
        }
        // Is NOT equivalent to
        for (String element: container) {
            if (condition(element)) {
                container.remove(element); // Produces ConcurrentModificationException
            }
        }
        // However, it's possible...
        container.removeIf(SomeClass::condition);
    }
}

Что такое ConcurrentModificationException? Это исключение, связанное с так называемым контрактом итератора. Согласно этому контракту, во время работы итератора (от момента, когда он был создан, и до момента, когда на нём был вызван последний метод), запрещается менять коллекцию любым способом, за исключением вызова remove на итераторе.

Про метод removeIf см. раздел "Потоки и функции высшего порядка".

Интерфейс Collection и его реализации

По смыслу интерфейс Collection описывает объект, содержащий некоторое количество однотипных объектов. По контракту коллекции, туда можно добавлять элементы и удалять их, а также перебирать их с помощью итератора. Коллекция "как есть" (т.е. без расширений) не нумерует свои элементы, и не запрещает добавлять в коллекцию равные элементы.

Содержимое интерфейса описано здесь: https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html. Повторять это описание вряд ли имеет смысл; здесь мы лишь подчеркнём, что отдельного внимания заслуживают методы stream(), parallelStream(), spliterator() и removeIf(predicate). Все они относятся к поддержке в Java функций высшего порядка, появившейся в версии 1.8 языка. Про неё см. раздел "Потоки и функции высшего порядка".

Коллекция "как есть" не имеет полных реализаций. Существует, однако, абстрактный класс AbstractCollection, обеспечивающий так называемый "скелет" реализации. Расширив этот абстрактный класс с помощью extends, мы можем создать собственную реализацию коллекции, добавив туда нужные для хранения данных поля и всего три метода:

  • iterator() и size(), если мы хотим создать неизменяемую коллекцию. Итератор при этом должен поддерживать next() и hasNext().

  • add(), если мы хотим создать изменяемую коллекцию. Следует добавить также реализацию remove() в итераторе.

Некоторые методы — в первую очередь clear() — абстрактный класс AbstractCollection реализует заведомо неэффективно.

Списки: интерфейс List и его реализации

Список List расширяет коллекцию Collection. В отличие от коллекции "вообще", список является пронумерованным — у каждого элемента есть свой номер (индекс), а по индексу можно достать или изменить элемент get, set. Индексы нумеруются от нуля до числа элементов size() минус один. Список, по-видимому, самая используемая структура данных в языках программирования.

Также список добавляет ряд методов, связанных с работой с индексами — например, вставка в список элемента по заданному индексу add(index, element) (данная операция "раздвигает" список в этом месте и вставляет туда новый элемент), или, наоборот, удаление по заданному индексу remove(index) (здесь список наоборот "схлопывается" в данном месте). Полный список методов можно посмотреть здесь: https://docs.oracle.com/javase/8/docs/api/java/util/List.html. У некоторых методов меняются контракты:

  • Метод add(element) в списке всегда вставляет элемент именно в его конец

  • Итератор iterator() перебирает список по возрастанию индексов

  • Сравнение на равенство equals() возвращает true, если размеры списков равны, и равны все пары элементов с одинаковыми индексами. При сравнении списка с не-списком всегда возвращается false.

К списку функций высшего порядка добавляются replaceAll(unaryOperator) и sort(comparator).

Потоки и функции высшего порядка

TODO