Стандартная библиотека: Контейнеры
В предыдущих главах мы использовали массивы в качестве стандартного способа, который группирует нескольких объектов определенного типа данных. Во многих случаях массивы достаточно хороши для работы с групрой объектов. Однако бывают ситуации, которые требуют большей гибкости и более совершенные операций. Для этих случаев Ада предоставляет поддержку контейнеров - таких как векторы и множества - в своей стандартной библиотеке.
Здесь мы представляем введение в контейнеры. Список всех контейнеров, имеющихся в Аде, см. в Приложении B.
Векторы
В следующих разделах мы представляем общий обзор векторов, включая создание экземпляров, инициализацию и операции с элементами вектора и самими векторами.
Создание экземпляра
Вот пример, показывающий настройку и объявление вектора V:
Контейнеры основаны на настраиваемых пакетах, поэтому мы не можем просто объявить вектор, как если бы объявляли массив определенного типа:
A : array (1 .. 10) of Integer;
Вместо этого нам сначала нужно создать экземпляр одного из этих
пакетов. Мы используем пакет контейнера (в данном случае
Ada.Containers.Vectors) и настраиваем
его, чтобы создать экземпляр настраиваемого пакета для желаемого
типа. Только затем мы сможем объявить вектор, используя тип из
созданного пакета. Такая настройка необходима для любого типа
контейнера стандартной библиотеки.
При настройки экземпляра Integer_Vectors мы указываем, что вектор
содержит элементы типа Integer, указывая его как Element_Type.
Подставляя для Index_Type тип Natural, мы указываем,
что допустимый диапазон индекса включает все натуральные числа. При желании мы
могли бы использовать более ограниченный диапазон.
Инициализация
Один из способов инициализации вектора - это конкатенация элементов. Мы
используем оператор &, как показано в следующем примере:
Мы указываем use Integer_Vectors, чтобы получить прямой доступ к
типам и операциям из созданного пакета. Кроме того, пример знакомит нас с еще
одной операцией вектора: Length, она возвращает количество
элементов в векторе. Мы можем использовать точечную нотацию, потому что
Vector - это теговый тип, и это
позволяет нам писать, как V.Length, так и Length (V).
Добавление элементов
Вы добавляете элементы в вектор с помощью операций Prepend и
Append. Как следует из названий, эти операции добавляют элементы
в начало или конец вектора соответственно. Например:
В этом примере элементы помещаются в вектор в следующей последовательности: (100, 40, 30, 20, 10, 0, 13).
Справочное руководство указывает, что сложность наихудшего случая должна быть:
O(log N) для операции
AppendиO(N log N) для операции
Prepend.
Доступ к первому и последнему элементам
Мы получаем доступ к первому и последнему элементам вектора с помощью
функций First_Element и Last_Element. Например:
Вы можете поменять местами элементы с помощью процедуры Swap,
передав ей курсоры на первый и последний элементы вектора
полученные функциями First и Last.
Курсор используются при переборе элементов контейнера и для
указания на отдельные его элементы.
С помощью этих операций мы можем написать код, чтобы поменять местами первый и последний элементы вектора:
Итерация
Самый простой способ перебрать элементы контейнера - использовать цикл
for E of Our_Container.
Это дает нам ссылку (E) на элемент в текущей позиции. Затем мы можем
использовать E непосредственно. Например:
Этот код отображает каждый элемент вектора V.
Поскольку у нас есть ссылка, мы можем отобразить не только значение
элемента, но и изменить его. Например, мы могли бы легко записать
цикл, чтобы добавить единицу к каждому элементу вектора V:
for E of V loop
E := E + 1;
end loop;
Мы также можем использовать индексы для доступа к элементам вектора.
Формат аналогичен циклу по элементам массива: мы используем в цикле
for I in <range>. Диапазон строим из V.First_Index
и V.Last_Index. Мы можем обратиться к текущему элементу, используя
операцию индексирования массива: V (I).
Например:
Здесь, помимо вывода элементов вектора, мы также печатаем
каждый индекс I, точно так же, как то, что мы можем сделать для
индексов массива. Получить элемент можено, как с помощью
краткой формы V (I), так и с помощью вызова функции
V.Element (I), но не как V.I.
Как упоминалось в предыдущем разделе, курсоры можно использовать для
итерации по контейнерам. Для этого используйте функцию Iterate,
которая выдает курсоры для каждой позиции в векторе. Соответствующий цикл
имеет формат for C in V.Iterate loop. Как и в предыдущем примере с
использованием индексов, можно снова получить доступ к текущему элементу,
используя курсор в качестве индекса массива V (C). Например:
Мы также могли бы использовать более длинную форму Element (C), вместо
V (C), для доступа к элементу в цикле. В этом примере мы используем
функцию To_Index для получения индекса, соответствующего текущему
курсору.
Как показано в комментариях после цикла, мы также можем использовать
цикл while ... loop для прохода по вектору. В этом случае мы должны
начать с курсора первого элемента (полученного с помощью вызова
V.First), а затем вызывать Next (C), чтобы получить курсор для
последующих элементов. Функция Next (C) возвращает No_Element,
когда курсор достигает конца вектора. Используя курсор вы можете изменять
элементы вектора непосредственно.
Вот как это выглядит при использовании, как индексов, так и курсоров:
-- Modify vector elements using index
for I in V.First_Index .. V.Last_Index loop
V (I) := V (I) + 1;
end loop;
-- Modify vector elements using cursor
for C in V.Iterate loop
V (C) := V (C) + 1;
end loop;
Справочное руководство требует, чтобы сложность доступа к элементу в наихудшем случае составляла O (log N).
Другой способ изменения элементов вектора - использование
процедуры обработки, которая получает отдельный элемент и выполняет над ним
некоторую работу. Вы можете вызвать Update_Element, передав
курсор и ссулку на процедуру обреботки. Например:
Поиск и изменение элементов
Вы можете найти определенный элемент в векторе и получить его индекс.
Функция Find_Index вернет индекс первого элемента, соответствующего
искомому значению. В качестве альтернативы вы можете использовать
Find, чтобы получить курсор, ссылающийся на этот элемент. Например:
Как мы видели в предыдущем разделе, мы можем осуществлять прямой доступ к
элементам вектора используя индекс или курсор.
Но, если мы пытаемся получить доступ к элементу с недопустимым
индексом или курсором, будет возбуждено исключение,
поэтому мы сначала должны проверить, действителен ли
индекс или курсор, прежде чем использовать его для доступа к элементу.
В нашем примере Find_Index или Find могли не найти элемент
в векторе. Мы проверяем эту ситуацию, сравнивая индекс с No_Index
или курсора с No_Element. Например:
-- Modify vector element using index
if Idx /= No_Index then
V (Idx) := 11;
end if;
-- Modify vector element using cursor
if C /= No_Element then
V (C) := 14;
end if;
Вместо того, чтобы писать V (C) := 14, мы могли бы использовать более
длинную форму V.Replace_Element (C, 14).
Вставка элементов
В предыдущих разделах мы видели примеры того, как добавлять элементы в вектор:
с помощью оператора конкатенации (
&) при объявлении вектора, иливызвав процедуры
PrependиAppend.
Вам может потребоваться вставить элемент в определенное место, например,
перед определенным элементом в векторе. Вы делаете это, вызывая
Insert. Например:
В этом примере мы ищем элемент со значением 10. Если он найден, перед ним вставляется элемент со значением 9.
Удаление элементов
Вы можете удалить элементы из вектора, передав соответствующий индекс
или курсор в процедуру удаления Delete. Если мы объединим это с
функциями Find_Index и Find из предыдущего раздела, мы
сможем написать программу, которая ищет определенный элемент и удаляет
его, если он найден:
Мы можем расширить этот подход, чтобы удалить все элементы, соответствующие определенному значению. Нам просто нужно продолжать поиск элемента в цикле, пока мы не получим недопустимый индекс или курсор. Например:
В этом примере мы удаляем из вектора все элементы со значением 10, получая их индекс. Точно так же мы удаляем все элементы со значением 13 использую курсор.
Другие операции
Мы видели некоторые операции с элементами вектора. Здесь мы продемонстрируем операции с вектором в целом. Наиболее заметным является объединение нескольких векторов, но мы также увидим такие операции с векторами, как сортировка и слияния отсортированных массивов, которые рассматривают вектор, как последовательность элементов, при этом учитывают отношения элементов друг с другом.
Мы выполняем конкатенацию векторов с помощью оператора & для векторов.
Рассмотрим два вектора V1 и V2. Мы можем объединить их,
выполнив V := V1 & V2. Результирующий вектор содержится в V.
Настраиваемый пакет Generic_Sorting является дочерним пакетом
Ada.Containers.Vectors. Он содержит операции
сортировки и объединения. Поскольку это настраиваемый пакет, вы не можете
использовать его непосредственно, но должны сначала настроить его. Чтобы
использовать эти операции с вектором целочисленных значений
(Integer_Vectors в нашем примере), вам необходимо настроить
пакет дочерний к Integer_Vectors.
Следующий пример поясняет, как это сделать.
После настройки Generic_Sorting мы делаем все операции
доступными с помощью спецификатора use.
Затем мы можем вызвать Sort, чтобы отсортировать
вектор, и Merge, чтобы объединить один вектор с другим.
В следующем примере представлен код, который работает тремя векторами
(V1, V2, V3) и использует операций конкатенации,
сортировки и слияния:
Справочное руководство требует, чтобы худшей сложностью вызова для
сортировки Sort было O(Nsup:2) и средняя сложность должна
быть лучше, чем O(Nsup:2).
Множества
Множества это другим вид контейнеров. В то время как векторы позволяют вставлять дублирующиеся элементы, множества гарантируют, что дублированных элементов не будет.
В следующих разделах мы рассмотрим операции, которые вы можете выполнять с множествами. Однако, поскольку многие операции с векторами аналогичны тем, которые используются для множеств, мы рассмотрим их здесь лишь кратко. Пожалуйста, обратитесь к разделу о векторах для более подробного обсуждения.
Инициализация и итерация
Чтобы инициализировать множество, вы можете вызвать процедуру Insert.
Делая это, вы должны убедиться, что не вставляются повторяющиеся
элементы: если вы попытаетесь вставить дубликат, вы получите
исключение. Если вы не уверены, что нет дубликатов, вы можете
воспользоваться другими вариантами:
версия
Insert, которая возвращает логическое значение, указывающее, была ли вставка успешной;процедура
Include, которая молча игнорирует любую попытку вставить повторяющийся элемент.
Чтобы перебрать множество, вы можете использовать цикл for E of S,
аналогично векторам. Вы получаете ссылку на элемент в множестве.
Посмотрим на пример:
Операции с элементами
В этом разделе мы кратко рассмотрим следующие операции над множествами:
DeleteиExclude, чтобы удалить элементы;ContainsиFind, чтобы проверить наличие элементов.
Чтобы удалить элементы, вы вызываете процедуру Delete. Однако,
аналогично описанной выше процедуре Insert, Delete возбуждает
исключение, если элемент, подлежащий удалению, отсутствует в множестве. Если
элемент может отсутствовать в момент удаления и вам не нужна проверка, то вы
можете вызвать процедуру Exclude, которая молча
игнорирует любую попытку удалить несуществующий элемент.
Функция Contains возвращает логическое значение Boolean, указывающее,
содержится ли значение в множестве. Find также ищет элемент в множестве,
но возвращает курсор на элемент или No_Element, если элемент не
существует. Вы можете использовать любую из этих функций для проверки
наличия элементов в множестве.
Давайте рассмотрим пример, в котором используются эти операции:
В дополнение к упорядоченным множествам, используемым в приведенных выше примерах, стандартная библиотека также предлагает хешированные множества. Справочное руководство требует следующей средней сложности каждой операции:
Операции |
|
|
|---|---|---|
|
O((log N)2) или лучше |
O(log N) |
Подпрограмма с использованием курсора |
O(1) |
O(1) |
Другие операции
Предыдущие разделы в основном касались операций с отдельными
элементами множествоа. Но Ада также предоставляет типичные операции над
множествами: объединение, пересечение, разность и симметричная
разность. В отличие от некоторых векторных операций, которые мы видели
раньше (например, слияния - Merge), здесь вы можете использовать
общепринятые операторы, такие как -. В следующей таблице перечислены
операции и связанный с ними оператор:
Операции над множеством |
Оператор |
|---|---|
Объединение |
|
Пересечение |
|
Разность |
|
Симметричная разность |
|
В следующем примере используются эти операторы:
Отображения для неопределенных типов
В предыдущих разделах были представлены контейнеры для элементов
определенных типов. Хотя большинство примеров в этих разделах
использовали целочисленный тип Integer как тип элемента контейнера,
контейнеры также могут использоваться с неопределенными типами,
примером которых является тип String. Однако неопределенные типы
требуют другого вида контейнеров, разработанных специально для них.
Мы также изучим другой класс контейнеров: отображения. Они связывают ключ с определенным значением. Примером отображения является связь «один к одному» между человеком и его возрастом. Если мы считаем имя человека ключевым, то значение - возраст человека.
Хэшированные отображения
Хэшированные отображения - это отображения, которые используют хэш ключа. Сам хэш вычисляется с помощью предоставленной вами функции.
На других языках
Хэшированные отображения похожи на словари в Python и хэши в Perl. Одно из основных отличий заключается в том, что эти скриптовые языки позволяют использовать разные типы для значений, содержащихся в одном отображении, в то время как в Аде, тип ключа и тип значение указываются в настройке пакета и остаются постоянными для этого конкретного отображения. У вас не может быть отображения, содержащего два элемента или два ключа разног типов. Если вы хотите использовать несколько типов, вы должны создать разные отображения для каждого и использовать только одино из них.
При создании настройке хешированного отображения
Ada.Containers.Indefinite_Hashed_Maps мы указываем следующие элементы:
Key_Type: тип ключаElement_Type: тип элементаHashKey_TypeEquivalent_Keys: оператор равенства (например,=), который указывает, должны ли два ключа считаться равными.Если тип, указанный в
Key_Type, имеет стандартный оператор, вы можете использовать его. В примере мы так и делаем. Мы указываем этот оператор как значениеEquivalent_Keys.
В следующем примере мы будем использовать строку в качестве типа
ключа. Мы будем использовать функцию Hash, предоставляемую стандартной
библиотекой для строк (в пакете Ada.Strings), и стандартный оператор
равенства.
Вы добавляете элементы в хешированное отображение, вызывая Insert. Если
элемент уже содержится в отображении M, вы можете получить к нему доступ
непосредственно, используя его ключ.
Например, вы можете изменить значение элемента,
написав M ("My_Key") := 10. Если ключ не найден, возбуждается исключение.
Чтобы проверить, доступен ли ключ, используйте функцию Contains (как
мы видели выше в разделе о множествоах).
Посмотрим на пример:
Упорядоченные отображения
Упорядоченные отображения имеют много общих черт с хэшированными отображениями. Основными отличиями являются:
Хэш-функция не нужна. Вместо этого вы должны предоставить функцию сравнения (
<operator), которую упорядоченное отображение будет использовать для сравнения элементов и обеспечения быстрого доступа (сложность O(log N)), используя двоичный поиск.Если тип, указанный в
Key_Type, имеет стандартный оператор<, вы можете использовать его аналогично тому, как мы это делали дляEquivalent_Keysвыше для хэшированных отображений.
Давайте посмотрим на пример:
Вы можете увидеть большое сходство между примерами, приведенными выше, и примерами из предыдущего раздела. Фактически, поскольку оба типа отображений имеют много общих операций, нам не нужно было вносить существенные изменения, когда мы изменили наш пример, чтобы использовать упорядоченные отображения вместо хешированных. Основное различие видно, когда мы запускаем примеры: вывод для хешированных отображений обычно неупорядочен, но вывод для упорядоченных отображений всегда упорядочен, как следует из его имени.
Сложность
Хэшированные отображения, как правило, являются самой быстрой структурой данных, доступной в Аде, если необходимо связать неоднородные ключи со значениями и быстро находить их. В большинстве случаев они немного быстрее упорядоченных отображений. Так что, если вам не важен порядок, используйте хэшированные отображения.
Справочное руководство требует следующей средней сложности операций:
Операции |
|
|
|---|---|---|
|
O((log N)2) or better |
O(log N) |
Подпрограмма с использованием курсора |
O(1) |
O(1) |