Контейнеры

   
На этом шаге мы приведем общие сведения о контейнерах.

   
Контейнерные классы (контейнеры) управляют коллекциями элементов. Для разных потребностей
программиста в STL предусмотрены разные типы контейнеров (рисунок 1).


Рис.1. Типы контейнеров STL

   
Контейнеры делятся на две категории.

  • Последовательные контейнеры представляют собой упорядоченные коллекции, в которых
    каждый элемент занимает определенную позицию. Позиция зависит от времени и места вставки, но не связана со
    значением элемента. Например, если последовательно присоединить шесть элементов к концу существующей
    коллекции, эти элементы будут следовать в порядке их занесения. STL содержит три стандартных класса
    последовательных контейнеров: vector (вектор), deque (дек) и
    list (список).
  • Ассоциативные контейнеры представляют собой отсортированные коллекции, в которых позиция
    элемента зависит от его значения по определенному критерию сортировки. После занесения шести элементов в
    коллекцию порядок их следования будет определяться только их значениями. Последовательность вставки значения
    не имеет. STL содержит три стандартных класса ассоциативных контейнеров: set (множество),
    multiset (мультимножество), map (отображение) и multimap
    (мультиотображение).

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

   
Автоматическая сортировка элементов в ассоциативных контейнерах не означает, что эти контейнеры специально
предназначены для сортировки элементов. С таким же успехом можно отсортировать элементы последовательного
контейнера. Основным достоинством автоматической сортировки является более высокая эффективность поиска.
В частности, программист всегда может воспользоваться двоичным поиском, для которого характерна
логарифмическая, а не линейная сложность. Это означает, что для поиска в коллекции из 1000 элементов в
среднем понадобится всего 10 сравнений вместо 500. Таким образом, автоматическая сортировка является только
(полезным) "побочным эффектом" реализации ассоциативного контейнера, спроектированного с расчетом на
повышение эффективности.

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

   
На следующем шаге мы рассмотрим векторы.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий