3.2 Контейнеры

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

При организации контейнера требуется решить следующие принципиальные вопросы.

1. Каким образом осуществляется хранение элементов контейнера? Т.е. каким образом элементы должны быть расположены в памяти: последовательно, непрерывным блоком, или они могут быть разбросаны по всей памяти.
2. Каким образом осуществляется доступ к элементам контейнера? По индексу или достаточно последовательного перебора.

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

Стандартная библиотека С++ предоставляет все возможные контейнеры, кроме деревьев. Это связано с тем, что при решении разных задач к деревьям предъявляются разнообразные требования и выработать обобщенный шаблон этой структуры данных достаточно сложно.