36. Контейнеры. Итераторы

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

К наиболее популярным типам классов относятся классы, контейнеры (называемые также классы совокупностей), т.е. классы, спроектированные для хранения в них совокупностей объектов.

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

Одним из важных понятий библиотеки наряду с контейнером и родовым алгоритмом является итератор – класс, объекты которого обеспечивают доступ к компонентам контейнера. Итератор обобщает понятие указателя, позволяет перебирать компоненты контейнера. Итератор может указывать на конкретный компонент.

Контейнеры подразделяются на два основных семейства:

1. последовательные (векторы, списки, двусторонние очереди – их элементы упорядочиваются операциями вставки и удаления;

2. множества, мультимножества, отображения, мультиотображения.

Контейнер отображения является ассоциативным классом, ему необходимо, чтобы была определена операция сравнения элементов.

Интерфейсы типичных контейнеров включают

1) конструкторы;

2) доступ к элементу;

3) вставка элемента;

4) удаление элемента;

5) деструкторы;

6) итераторы.

double sum(const deque <double>& dq) //dq – контейнер

{

deque<double>::const _iterator p;

double s=0.0;

for(p=dq, begin(); p!=dq.end(); ++p)

…

return s;

}

Проход по контейнеру dq происходит с помощью константного итератора p. Для получения очередного элемента контейнера операторы разыменовываются, итератор begin() указывает на первый элемент контейнера, end() – на конец последнего элемента.

Контейнерные функции:

CAN :: value_type

CAN :: reference //тип ссылки на элемент

CAN :: const_reference //тип константной ссылки

CAN :: pointer //тип указателя на элемент

CAN :: iterator //тип итератора

CAN :: const_iterator //тип константного итератора

CAN :: reverse_iterator //тип обратного итератора

CAN :: differnce_type //тип расстояния между элементами

CAN :: size_type //тип размера контейнера

Эти определения доступны во всех контейнерных классах, например, vector <char> :: value_type – т. обр. будут сообщаться символьные значения, а проход по такому контейнеру будет выполнен посредством итератора.

vector <char> :: iterator

Список стандартных методов любого контейнерного класса:

CAN() – конструктор по умолчанию;

CAN(c) – конструктор копирования;

c.begin() – начальная позиция контейнера;

c.end() – конечная позиция контейнера;

c.rend() – конечная позиция обратного контейнера;

c.rbegin() – начальная позиция обратного контейнера;

c.size() – число элементов;

c.max_size() – максимально возможный размер;

c.empty() – истина, если c пуст;

c.swap(d) – обмен элементами между c и d.

Существует 5 категорий итераторов: для записи / для чтения, однонаправленные, двунаправленные, произвольного доступа.

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

Итераторы для чтения поддерживают операции равенства, константного разыменования, автоинкременты (специальным типом такого итератора является istream_iterator). Итератор для записи поддерживает операции равенства, константного разыменования, автоинкременты (специальный тип такого итератора – ostream_iterator).

Однонаправленные поддерживают все операции итераторов чтения и записи, позволяют применять присваивание, т.е. сохранить позицию внутри контейнера при многократных подходах.

Двунаправленные поддерживают все операции однонаправленных итераторов и автодекременту.