Cборщики и итераторы
Если вы не знаете, сколько объектов вам будет необходимо для решения проблемы, или сколько долго они будут существовать, то вы также не знаете, как хранить эти объекты. Откуда вы можете знать, сколько пространства необходимо для этих объектов? Вы не можете, так как эта информация не известна, пока не настанет время выполнения.
Решения большинства проблем в объектно-ориентированном дизайне выглядит дерзко: вы создаете типы других объектов. Новый тип объектов, который решает эту обычную проблему хранения ссылок на другие объекты. Конечно, вы можете сделать то же самое с помощью массива, который поддерживают многие языки. Но это гораздо большее. Этот новый объект, обычно называемый контейнер (также называется коллекцией, но библиотека Java использует этот термин в другом смысле, так что эта книга будет использовать “контейнер”), будет расширять себя при необходимости, чтобы аккомодировать все, что вы поместите внутрь него. Так что вы не должны знать, сколько объектов вы положили храниться в контейнер. Просто создайте объект контейнера и дайте ему заботится о деталях.
К счастью, хорошие языки ООП пришли с набором контейнеров, как часть пакета. В C++ это часть Стандартной Библиотеки C++, часто называемой Библиотекой Стандартных Шаблонов [Standard Template Library (STL)]. Object Pascal имеет контейнеры в Библиотеке Визуальных Компонент [Visual Component Library (VCL)]. Smalltalk имеет более полный набор контейнеров. Java также имеет контейнеры в своей стандартной библиотеке. В некоторых библиотеках общие контейнеры достаточно хороши для всех надобностей, а в других (например, в Java) библиотека имеет различные типы контейнеров для разных надобностей: вектор (называемый ArrayList в Java) для последовательного доступа ко всем элементам, и связанный список для последовательной вставки в любое место, например, вы можете выбрать обычный тип, который удовлетворяет вашим требованиям. Библиотеки контейнеров могут также включать наборы, очереди, хэш-таблицы, деревья, стеки и т.п.
Все контейнеры имеют определенный способ для помещения вещей внутрь и получения вещей назад. Обычно это функции для добавления элемента в контейнер, а другая - для извлечения этого элемента. Но получение элемента может стать более пробламетично, поскольку функция простого выбора ограничена. Что если вы захотите манипулировать или сравнивать набор элементов в контейнере не по одному?
Решением этого является итератор, который является объектом, чья работа - это выбор элементов из контейнера и представление их пользователю итератора. Как класс, он также обеспечивает уровень абстракции. Эта абстракция может быть использована для разделения деталей контейнера от кода, который имеет доступ к контейнеру. Контейнер через итератор абстрагируется до простой последовательности. Итератор позволяет вам обработать эту последовательность, не заботясь о лежащей в основе структуре — является ли она ArrayList, LinkedList, Stack или чем-то еще. Это дает вам гибкость для легкой смены лежащей в основе структуры данных без переделки кода вашей программы. Java началась (в версиях 1.0 и 1.1) со стандартного итератора, называемого Enumeration, для всех контейнерных классов. В Java 2 добавлено много более сложных библиотек контейнеров, которые содержат итераторы, называемые Iterator, который делает много больше, чем старый Enumeration.
С точки зрения разработки, все что вам нужно - это последовательность, которой можно манипулировать для решения вашей проблемы. Если последовательность простых типов удовлетворяет всем вашим требованиям, то нет смысла иметь другие типы. Есть два довода, почему вам необходимы контейнеры. Во-первых, контейнеры обеспечивают различные типы интерфейсов и внешних воздействий. Стек имеет различные интерфейсы и поведение, в отличие от очереди, которая отличается от набора или списка. Один из них может обеспечивать более гибкое решение вашей проблемы, чем другие. Во-вторых, различные контейнеры имеют различную эффективность для определенных операций. Лучший пример - это ArrayList и LinkedList. Оба контейнера - это простая последовательность, которые могут иметь одинаковые интерфейсы и внешнее поведение. Но определенные операции могут иметь радикальное отличие в стоимости. Случайный доступ к элементам в ArrayList - это операция постоянная по времени. Она занимает примерно одно и то же время не зависимо от выбираемого вами элемента. Однако в LinkedList очень дорого перемещаться по списку элементов в случайном порядке, и занимает больше времени при нахождении элемента, чем при переборе их вниз по списку. С другой стороны, если вы хотите вставить элемент в середину последовательности, это дешевле в LinkedList, чем в ArrayList. Есть и другие операции, имеющие различия в эффективности, в зависимости от лежащей в основе структуры последовательности. В фазе разработки вы можете начать с LinkedList и, когда будете настраивать производительность, сменить на ArrayList. Поскольку есть абстракция через итераторы, вы можете сменить один на другой с минимальной переработкой вашего кода.
В завершение, помните, что контейнеры только хранилище для помещения объектов. Если такое хранилище решает все ваши проблемы, не имеет значение как оно реализовано (основная концепция для большинства типов объектов). Если вы работаете со средой программирования, имеющей встроенную возможность, обусловленную другими факторами, то стоимость различается для ArrayList и LinkedList может не иметь значения. Вам может понадобиться только один из типов последовательности. Вы можете вообразить “совершенный” абстрактный контейнер, который может автоматически изменять лежащую в основе реализацию в зависимости от способа его использования.
