Последовательные контейнеры. Контейнеры вектор, список

Контейнеры

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

для хранения данных. При этом не имеет значения, какие именно данные хра-

нятся, будь то некоторые базовые типы, такие, как int, float и т. п., или же объекты

классов. STL включает в себя семь основных типов контейнеров и еще три

производных типа. Зачем же нам столько типов контейнеров? Почему нельзя использовать обычный массив во всех случаях, когда нужно хранить данные?

Ответ таков: неэффективно. Работать с массивом во многих ситуациях бывает неудобно — медленно и вообще затруднительно

Контейнеры STL подразделяются на две категории: последовательные и ассоциативные. Среди последовательных выделяют векторы, списки и очереди с двусторонним доступом. Среди ассоциативных — множества, мультимножества, отображения и мультиотображения. Кроме того, наследниками последователь-

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

Последовательные контейнеры

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

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

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

В STL для борьбы с такими трудностями существует контейнер vector.

Но с массивами есть еще одна проблема. Допустим, в массиве хранятся данные о работниках, и вы отсортировали их по алфавиту в соответствии с фамилиями. Теперь, если нужно будет добавить сотрудника, фамилия которого начиается с буквы Л, то придется сдвинуть всех работников с фамилиями на М — Я, чтобы освободить место для вставки нового значения. Все это может занимать довольно много времени. В STL имеется контейнер список, который основан на идее связного списка и который решает данный вопрос.

Третьим представителем последовательных контейнеров является очередь с двусторонним доступом. Это комбинация стека и обычной очереди. Стек, как вы помните, работает по принципу LIFO (последний вошел — первый вышел). То есть и ввод, и вывод данных в стеке производится «сверху». В очереди же,

напротив, используется принцип FIFO (первый вошел — первый вышел): данные поступают «сверху», а выходят «снизу». Очередь с двусторонним доступом, надо полагать, использует комбинированный порядок обмена данных. И вносить значения в очередь с двусторонним доступом, и выводить из нее можно с обеих сторон. Это довольно гибкий инструмент, он ценен не только сам по себе, но может служить базой для стеков очередей, в чем мы вскоре сможем убедиться.

Таблица 15.1. Основные последовательные контейнеры

Контейнер Характеристика Плюсы/минусы

Обычный массив

Фиксированный

размер

Скоростной случайный доступ (по индексу)

Медленная вставка или изъятие данных из середины

Размер не может быть изменен во время работы

программы

Вектор

Перераспределяемый,

расширяемый массив

Скоростной случайный доступ (по индексу)

Медленная вставка или изъятие данных из середины

Скоростная вставка или изъятие данных из хвоста

Список

Аналогичен связному списку

Скоростная вставка или изъятие данных из любого места

Быстрый доступ к обоим концам

Медленный случайный доступ

Очередь с двусторонним доступом

Как вектор, но доступ с обоих концов

Скоростной случайный доступ

Медленная вставка или изъятие данных из середины

Скоростная вставка и изъятие данных из хвоста или головы

Реализация на практике контейнера STL не представляет особого труда.

Во-первых, нужно включить в программу соответствующий заголовочный файл.

Передача информации о том, какие типы объектов будут храниться, производится в виде передачи параметра в шаблон. Например:

vector<int> aVect; //создать вектор целых чисел (типа int)

или

1ist<airtime> departure_list; //создать список типа airtime

Обратите внимание: в STL не нужно специфицировать размеры контейнеров. Они сами заботятся о размещении своих данных в памяти.

Ассоциативные контейнеры

Ассоциативный контейнер — это уже несколько иная организация данных. Данные располагаются не последовательно, доступ к ним осуществляется посредством ключей. Ключи — это просто номера строк, они обычно используются для выстраивания хранящихся элементов в определенном порядке и модифицируются контейнерами автоматически. Примером может служить обычный орфографический словарь, где слова сортируются по алфавиту. Вы просто вводите нужное слово (значение ключа), например «арбуз», а контейнер конвертирует

его в адрес этого элемента в памяти. Если известен ключ, доступ к данным осуществляется очень просто.

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

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

Множества проще и, возможно, из-за этого более популярны, чем отображения. Множество хранит набор элементов, содержащих ключи — атрибуты, используемые для упорядочивания данных. Например, множество может хранить объекты класса person, которые упорядочиваются в алфавитном порядке. В качестве ключа при этом используется значение name. При такой организации данных можно очень быстро найти нужный объект, осуществляя поиск по имени объекта (ищем объект класса person по атрибуту name). Если в множестве хранятся значения одного из базовых типов, таких, как int, ключом является сам элемент. Некоторые авторы называют ключом весь объект, хранящийся в множестве, но мы будем употреблять термин ключевой объект, чтобы подчеркнуть, что атрибут, используемый для упорядочивания (ключ), — это не обязательно весь элемент данных.

Отображение хранит пары объектов. Один кортеж в такой «базе данных» состоит из двух «атрибутов»: ключевой объект и целевой (ассоциированный)

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

а целевой — значением этого индекса.

Контейнеры отображение и множество рзрешают сопоставлять только один ключ данному значению. Это имеет смысл в таких, например, случаях, как хранение списка работников, где каждому имени сопоставляется уникальный идентификационный номер. С другой стороны, мулътиотображения и мультимножества позволяют хранить несколько ключей для одного значения. Например,

слову «ключ» в толковом словаре может быть сопоставлено несколько статей.

Создаются ассоциативные контейнеры примерно так же, как и последовательные:

set<int> intSet; //создает множество значений int

или

multiset<employee> machinists; //создает мультимножество

//значений класса employee

Поиск по сайту: