 |
Общее понятие о контейнере
|
|
|
|
Стандартная библиотека шаблонов (Standard Template Library, STL) входит в стандартную библиотеку языка C++. В неё включены реализации наиболее часто используемых контейнеров и алгоритмов, что избавляет программистов от рутинного переписывания их снова и снова. При разработке контейнеров и применяемых к ним алгоритмов (таких как удаление одинаковых элементов, сортировка, поиск и т. д.) часто приходится приносить в жертву либо универсальность, либо быстродействие. Однако разработчики STL поставили перед собой задачу: сделать библиотеку одновременно эффективной и универсальной. Для ее решения были использованы такие универсальные средства языка C++, как шаблоны и перегрузка операторов. В последующем изложении будем опираться на реализацию STL, поставляемую фирмой Microsoft вместе с компилятором Visual C++ 6.0. Тем не менее большая часть сказанного будет справедлива и для реализаций STL другими компиляторами.
Основными понятиями в STL являются понятия контейнера (container), алгоритма (algorithm) и итератора (iterator).
Контейнер - это хранилище объектов (как встроенных, так и определённых пользователем типов). Как правило, контейнеры реализуются в виде шаблонов классов. Простейшие виды контейнеров (статические и динамические массивы) встроены непосредственно в язык C++. Кроме того, стандартная библиотека включает в себя реализации таких контейнеров, как вектор (vector), список (list), очередь (deque), ассоциативный массив (map), множество (set) и некоторых других.
Алгоритм - это функция для манипулирования объектами, содержащимися в контейнере. Типичные примеры алгоритмов - сортировка и поиск. В STL реализовано порядка 60 алгоритмов, которые можно применять к различным контейнерам, в том числе к массивам, встроенным в язык C++.
|
|
|
Итератор - это абстракция указателя, то есть объект, который может ссылаться на другие объекты, содержащиеся в контейнере. Основные функции итератора - обеспечение доступа к объекту, на который он ссылается (разыменование), и переход от одного элемента контейнера к другому (итерация, отсюда и название итератора). Для встроенных контейнеров в качестве итераторов используются обычные указатели. В случае с более сложными контейнерами итераторы реализуются в виде классов с набором перегруженных операторов.
Помимо отмеченных элементов в STL есть ряд вспомогательных понятий; с некоторыми из них следует также познакомиться.
Аллокатор (allocator) - это объект, отвечающий за распределение памяти для элементов контейнера. С каждым стандартным контейнером связывается аллокатор (его тип передаётся как один из параметров шаблона). Если какому-то алгоритму требуется распределять память для элементов, он обязан делать это через аллокатор. В этом случае можно быть уверенным, что распределённые объекты будут уничтожены правильно.
В состав STL входит стандартный класс allocator (описан в файле xmemory). Именно его по умолчанию используют все контейнеры, реализованные в STL. Однако пользователь может реализовать собственный класс. Необходимость в этом возникает очень редко, но иногда это можно сделать из соображений эффективности или в отладочных целях.
Остановимся более подробно на рассмотрении введенных понятий.
Контейнеры. Каждый контейнер предоставляет строго определённый интерфейс, через который с ним будут взаимодействовать алгоритмы. Этот интерфейс обеспечивают соответствующие контейнеру итераторы. Важно подчеркнуть, что никакие дополнительные функции-члены для взаимодействия алгоритмов и контейнеров не используются. Это сделано потому, что стандартные алгоритмы должны работать, в том числе со встроенными контейнерами языка C++, у которых есть итераторы (указатели), но нет ничего, кроме них. Таким образом, при создании собственного контейнера реализация итератора - необходимый минимум.
|
|
|
Каждый контейнер реализует определённый тип итераторов. При этом выбирается наиболее функциональный тип итератора, который может быть эффективно реализован для данного контейнера. "Эффективно" означает, что скорость выполнения операций над итератором не должна зависеть от количества элементов в контейнере. Например, для вектора реализуется итератор с произвольным доступом, а для списка - двунаправленный. Поскольку скорость выполнения операции [] для списка линейно зависит от его длины, итератор с произвольным доступом для списка не реализуется.
Вне зависимости от фактической организации контейнера (вектор, список, дерево) хранящиеся в нём элементы можно рассматривать как последовательность. Итератор первого элемента в этой последовательности возвращает функция begin(), а итератор элемента, следующего за последним, - функция end(). Это очень важно, так как все алгоритмы в STL работают именно с последовательностями, заданными итераторами начала и конца.
Кроме обычных итераторов в STL существуют обратные итераторы (reverse iterator). Обратный итератор отличается тем, что просматривает последовательность элементов в контейнере в обратном порядке. Другими словами, операции + и - у него меняются местами. Это позволяет применять алгоритмы как к прямой, так и к обратной последовательности элементов. Например, с помощью функции find можно искать элементы как "с начала", так и "с конца" контейнера.
В STL контейнеры делятся на три основные группы (табл. 2): контейнеры последовательностей, ассоциативные контейнеры и адаптеры контейнеров. Первые две группы объединяются в контейнеры первого класса.
Таблица 2
| Контейнерный класс STL | Описание |
| Контейнеры последовательностей | |
| vector | Динамический массив |
| deque | Двунаправленная очередь |
| list | Двунаправленный линейный список |
| Ассоциативные контейнеры | |
| set | Ассоциативный контейнер с уникальными ключами |
| multiset | Ассоциативный контейнер, допускающий дублирование ключей |
| map | Ассоциативный контейнер для наборов уникальных элементов |
| multimap | Ассоциативный контейнер для наборов с дублированием элементов |
| Адаптеры контейнеров | |
| stack | Стандартный стек |
| queue | Стандартная очередь |
| priority_queue | Очередь с приоритетами |
Каждый класс контейнера, реализованный в STL, описывает набор типов, связанных с контейнером. При написании собственных контейнеров следует придерживаться этой же практики. Вот список наиболее важных типов:
|
|
|
value_type - тип элемента;
size_type - тип для хранения числа элементов (обычно size_t);
iterator - итератор для элементов контейнера;
key_type - тип ключа (в ассоциативном контейнере).
Помимо типов можно выделить набор функций, которые реализует почти каждый контейнер в STL (табл. 3). Они не требуются для взаимодействия с алгоритмами, но их реализация улучшает взаимозаменяемость контейнеров в программе. STL разработана с тем расчетом, чтобы контейнеры обеспечивали аналогичные функциональные возможности.
Таблица 3
| Общие методы всех STL-контейнеров | Описание |
| default constructor | Конструктор по умолчанию. Обычно контейнер имеет несколько конструкторов |
| copy constructor | Копирующий конструктор |
| destructor | Деструктор |
| empty | Возвращает true, если в контейнере нет элементов, иначе false |
| max_size | Возвращает максимальное число элементов для контейнера |
| size | Возвращает число элементов в контейнере в текущее время |
| operator = | Присваивает один контейнер другому |
| operator < | Возвращает true, если первый контейнер меньше второго, иначе false |
| operator <= | Возвращает true, если первый контейнер не больше второго, иначе false |
| operator > | Возвращает true, если первый контейнер больше второго, иначе false |
| operator >= | Возвращает true, если первый контейнер не меньше второго, иначе false |
| operator == | Возвращает true, если сравниваемые контейнеры равны, иначе false |
| operator!= | Возвращает true, если сравниваемые контейнеры не равны, иначе false |
| swap | Меняет местами элементы двух контейнеров |
| Функции, имеющиеся только в контейнерах первого класса | |
| begin | Две версии этой функции возвращают либо iterator, либо const_iterator, который ссылается на первый элемент контейнера |
| end | Две версии этой функции возвращают либо iterator, либо const_iterator, который ссылается на следующую позицию после конца контейнера |
| rbegin | Две версии этой функции возвращают либо reverse_iterator, либо reverse_const_iterator, который ссылается на последний элемент контейнера |
| rend | Две версии этой функции возвращают либо reverse_iterator, либо reverse_const_iterator, который ссылается на позицию перед первым элементом контейнера |
| insert, erase, | Позволяют вставить или удалить элемент(ы) в середине последовательности |
| Окончание табл. 3 | |
| clear | Удаляет из контейнера все элементы |
| front, back | Возвращают ссылки на первый и последний элемент, хранящийся в контейнере |
| push_back, pop_back | Позволяют добавить или удалить последний элемент в последовательности |
| push_front, pop_front | Позволяют добавить или удалить первый элемент в последовательности |
Итераторы обычно создаются как друзья классов, с которыми они работают, что позволяет выполнить прямой доступ к частным данным этих классов. С одним контейнером может быть связано несколько итераторов, каждый из которых поддерживает свою собственную «позиционную информацию» (табл. 4).
|
|
|
Таблица 4
| Тип итератора | Доступ | Разыменование | Итерация | Сравнение |
| Итератор вывода (output iterator) | Только запись | * | ++ | |
| Итератор ввода (input iterator) | Только чтение | *, -> | ++ | ==,!= |
| Прямой итератор (forward iterator) | Чтение и запись | *, -> | ++ | ==,!= |
| Двунаправленный итератор (bidirectional iterator) | Чтение и запись | *, -> | ++, -- | ==,!= |
| Итератор с произвольным доступом (random-access iterator) | Чтение и запись | *, ->, [] | ++, --, +, -, +=, -= | ==,!=, <, <=, >, >= |
|
|
|
