На этом шаге мы приведем общие сведения о контейнерах.
Контейнерные классы (контейнеры) управляют коллекциями элементов. Для разных потребностей программиста в STL предусмотрены разные типы контейнеров (рисунок 1).
Рис.1. Типы контейнеров STL
Контейнеры делятся на две категории.
- Последовательные контейнеры представляют собой упорядоченные коллекции, в которых каждый элемент занимает определенную позицию. Позиция зависит от времени и места вставки, но не связана со значением элемента. Например, если последовательно присоединить шесть элементов к концу существующей коллекции, эти элементы будут следовать в порядке их занесения. STL содержит три стандартных класса последовательных контейнеров: vector (вектор), deque (дек) и list (список).
- Ассоциативные контейнеры представляют собой отсортированные коллекции, в которых позиция элемента зависит от его значения по определенному критерию сортировки. После занесения шести элементов в коллекцию порядок их следования будет определяться только их значениями. Последовательность вставки значения не имеет. STL содержит три стандартных класса ассоциативных контейнеров: set (множество), multiset (мультимножество), map (отображение) и multimap (мультиотображение).
Ассоциативный контейнер можно рассматривать как особую разновидность последовательного контейнера, поскольку сортированные коллекции упорядочиваются в соответствии с критерием сортировки. Такой подход вполне естествен для тех, кто работал с другими библиотеками классов коллекций, в которых сортированные коллекции были производными от упорядоченных коллекций. Однако не следует забывать, что типы коллекций STL полностью независимы друг от друга. Они имеют разные реализации и не являются производными друг от друга.
Автоматическая сортировка элементов в ассоциативных контейнерах не означает, что эти контейнеры специально предназначены для сортировки элементов. С таким же успехом можно отсортировать элементы последовательного контейнера. Основным достоинством автоматической сортировки является более высокая эффективность поиска. В частности, программист всегда может воспользоваться двоичным поиском, для которого характерна логарифмическая, а не линейная сложность. Это означает, что для поиска в коллекции из 1000 элементов в среднем понадобится всего 10 сравнений вместо 500. Таким образом, автоматическая сортировка является только (полезным) "побочным эффектом" реализации ассоциативного контейнера, спроектированного с расчетом на повышение эффективности.
В нескольких следующих шагах подробно рассматриваются разновидности контейнерных классов, и в частности их типичные реализации. Строго говоря, стандартная библиотека C++ не определяет реализацию контейнеров, однако указанные в стандарте поведение и требования к сложности операций не оставляют места для вариаций, поэтому на практике реализации отличаются только во второстепенных деталях.
На следующем шаге мы рассмотрим векторы.
