47. Структуры данных: множества, мультимножества, дерево.

Дерево как структура данных. Каждый элемент имеет родителя и потомков. В общем случае дерево начинается с корня, каждый элемент можно отнести к какому-то уровню, связи внутри дерева не пересекаются.

Бинарное дерево — количество потомков не более 2. Это имеет свои преимущества. Например в данном случае дерево отсортировано и можно простыми операциями сравнения найти нужный элемент, ища из корня.

Сбалансированное дерево — такое дерево, в котором все кроме одного последнего уровня обязательно заполнены. Такое дерево позволяет осуществить гарантированный поиск за log2(N) операций.

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

Виды проходов деревьев (pre-order, in-order, post-order, level-order).

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

48. Алгоритмы, контейнеры и итераторы.

Алгоритмы основной части стандартной библиотеки шаблонов. Алгоритмы не работают с контейнерами, а сами с итераторами. Следовательно, один и тот же алгоритм может использоваться, если не все большинством контейнеров STL. В этом подразделе содержатся соглашения и терминология алгоритмов STL.

Библиотека стандартных шаблонов (STL) ISO предоставляет контейнеры для хранения коллекций связанных объектов. Контейнеры — это классы шаблонов, которые содержат спецификацию объектов, разрешенных в контейнерах.

Средства STL, широко распространённое использование итераторов посредничать в разных алгоритмов и последовательностей, на которых они являются. Имя типа итераторов (или ее префикса) указывает категорию итераторов. для этого типа. Категории перечислены в порядке возрастания мощности:

• Выходные данные. Итератор X выходных данных может иметь только косвенно хранящиеся значения V, Входные данные. Итератор X ввода может представлять исключительное значение,

• Поиск. Передний итератор X может использоваться вместо итератора вывода для записи или итератора ввода для чтения. 

• Двунаправленный. Двунаправленный итератор X может использоваться вместо переднего итератора. 

• Прямой доступ. Произвольно-доступный итератор X может использоваться вместо двунаправленного итератора. 

49. Контейнер как структура данных.

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

Контейнеры — это фактически те структуры данных, которые мы рассматривали ранее, но на языке С++, и они уже готовы к применению. Итераторы — специальные объекты для доступа к элементам структуры данных, близкая аналогия — указатели. Алгоритмы — готовый набор функциональных действий, позволяющий получить что-то полезное.

Каждый контейнер представляет собой упорядоченную последовательность элементов. Т.е. все элементы можно выстроить в одну цепочку друг за другом. Если мы хотим перебрать все элементы контейнера (распечатать их, найти какой-то и др.), что является типичной операцией, то это делается через итерационный перебор. Пример перебора. Понятие end-of-sequence (элемент за последним, но не последний).