Обобщенные контейнеры

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

Контейнерный класс описывает объект, предназначенный для хранения других объектов. Контейнеры играют настолько важную роль, что в ранних объектно-ориентированных языках они считались фундаментальными структурами данных. Например, в Smalltalk язык с точки зрения программиста представляет собой совокупность транслятора и библиотеки классов, а набор контейнерных классов является важнейшей частью этой библиотеки. Вполне естественно, что разработчики компиляторов С++ также прилагают к своим продуктам библиотеку контейнерных классов. Кстати, весьма удобный класс vector в простейшей форме был представлен в начале первого тома книги.

Первые библиотеки контейнерных классов, как и многие другие ранние библиотеки С++, были основаны на объектно-базированной иерархии Smalltalk. Для Smalltalk такое решение работало хорошо, но в С++ оно оказалось громоздким и неудобным. Требовался другой подход.

Контейнеры С++ реализуются в виде шаблонов. Контейнеры стандартной библиотеки С++ предоставляют широкий ассортимент структур данных, хорошо работают со стандартными алгоритмами и подходят для решения многих типовых задач из области программирования.

Контейнеры и итераторы

Если вы не знаете, сколько объектов потребуется для решения той или иной задачи и как долго они будут существовать, вам не удастся заранее выяснить, как хранить эти объекты. Как узнать, сколько памяти для них выделить? Ответ на этот вопрос становится известным лишь на стадии выполнения.

Большинство задач в объектно-ориентированных архитектурах решается просто - определением нового типа объекта. Для нашей задачи этот новый тип объекта должен содержать другие объекты или указатели на них. В С++ этот объект, обычно называемый контейнером (в других языках также используется термин коллекция ), автоматически расширяется по мере необходимости для хранения всех содержащихся в нем объектов. Вам не нужно заранее знать, сколько объектов будет помещено в контейнер, достаточно создать объект контейнерного класса, а об остальном он позаботится сам.

К счастью, хорошие объектно-ориентированные языки поставляются со своей библиотекой контейнеров. В С++ это стандартная библиотека шаблонов (STL). Разработчики некоторых библиотек сочли, что на все случаи жизни достаточно одного обобщенного контейнера; разработчики других (и особенно это касается библиотек С++) предусмотрели разные типы контейнеров для разных целей: вектор (vector) обеспечивает эффективный доступ к любому элементу, связанный список (list) - эффективную вставку в произвольной позиции, и т. д. Программист выбирает ту разновидность контейнера, которая лучше всего отвечает его требованиям.

Во всех контейнерах предусмотрены средства для записи и удаления элементов. С записью элементов все достаточно очевидно - задача решается при помощи функции с именем push, add или что-нибудь в этом роде. С выборкой элементов дело обстоит сложнее; для контейнеров, являющихся аналогами массивов (например, для векторов) выборка может производиться оператором индексирования или функцией, но во многих ситуациях это не имеет смысла. Кроме того, одиночная выборка устанавливает слишком жесткие ограничения. Что, если потребуется сравнить или обработать группу элементов контейнера?

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

С точки зрения архитектуры все, что вам действительно нужно, - это интервал, с которым можно выполнять необходимые операции. Если бы существовала одна разновидность интервалов, подходящая для любой ситуации, создавать разные типы было бы незачем. Разные контейнеры необходимы по двум причинам. Во-первых, контейнеры предоставляют разные интерфейсы и обладают.разным поведением. Так, стек по своему поведению и интерфейсу отличается от очереди, которая, естественно, отличается от списка. Одна разновидность контейнера может лучше подойти для решения вашей конкретной задачи, или предоставляемая ей абстракция может лучше выражать ваши намерения при проектировании. Контейнеры различаются по эффективности выполнения некоторых операций. Для примера сравним вектор со списком. Оба являются простыми последовательными

Первое знакомство

в следующем примере используется множество (шаблон класса set) - контейнер, построенный по образцу классических математических множеств, которые не могут содержать одинаковые значения. В данном примере множество предназначено для работы со значениями типа int:

: C07:Intset.cpp

Простой пример использования множеств STL linclude <cassert> linclude <set> using namespace std:

int mainO { set<int> intset; forCint i = 0: i < 25: i++) forCint j = 0: j < 10:

Попытка вставить дубликат: intset.insertcj): assertCintset.sizeC) - 10): } /:-

Частный случай эталона Состояние, описанного в главе 10.

См. http: www.dinkumware.com, http: ww.sgi.com/tech/stl и http: ww.stlport.org.

контейнерами, обладающими практически одинаковыми интерфейсами и внешним поведением, но некоторые операции выполняются с принципиально разной сложностью. Например, произвольный доступ к элементам вектора требует постоянной сложности, то есть занимает одинаковое время независимо от элемента. Тогда как в связанных списках обращение к элементу требует перемещения по списку и обходится дороже для элементов, расположенных дальше от начала списка. Однако вставка элемента в середину списка выполняется быстрее, чем в середину вектора. Эффективность этих и других операций зависит от базовой структуры данных контейнера. На стадии проектирования можно начать со списка, а в процессе оптимизации быстродействия переключиться на вектор, или наоборот. Благодаря итераторам код перебора изолируется от изменений в реализации базовой структуры данных.

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

Эта глава, как и предыдущая, не содержит полной документации по всем функциям всех контейнеров STL. Хотя в книге приводятся описания функций, используемых в примерах, за полной информацией следует обращаться к другим источникам. Мы рекомендуем электронную документацию реализаций STL от Dinkumware, Silicon Graphics и STLPort.