Rationale for Ada 2005: 6a Containers

RUSTOPBACKNEXT

ENG

1. Organization of containers

@ A major enhancement to the predefined library in Ada 2005 is the addition of a container library.

@ This is quite extensive and merits this separate paper on its own. Other aspects of the predefined library and the overall rationale for extending the library were described in the previous paper.

@ The main packages in the container library can be grouped in various ways. One set of packages concerns the manipulation of objects of definite types and another, essentially identical, set concerns indefinite types. (Remember that an indefinite (sub)type is one for which we cannot declare an object without giving a constraint.) The reason for the duplication concerns efficiency. It is much easier to manipulate definite types and although the packages for indefinite types can be used for definite types, this would be rather inefficient.

@ We will generally only consider the definite packages. These in turn comprise two groups.

@ Sequence containers – these hold sequences of elements. There are packages for manipulating vectors and for manipulating linked lists. These two packages have much in common. But they have different behaviours in terms of efficiency according to the pattern of use. In general (with some planning) it should be possible to change from one to the other with little effort.

@ Associative containers – these associate a key with each element and then store the elements in order of the keys. There are packages for manipulating hashed maps, ordered maps, hashed sets and ordered sets. These four packages also have much in common and changing between hashed and ordered versions is usually feasible.

@ There are also quite separate generic procedures for sorting arrays which we will consider later.

@ The root package is 

  1        package Ada.Containers is
  2                pragma Pure (Containers);
  3                type Hash_Type is mod implementation-defined;
  4                type Count_Type is range 0 .. implementation-defined;
  5        end Ada.Containers;

@ The type Hash_Type is used by the associative containers and Count_Type is used by both kinds of containers typically for the number of elements in a container. Note that we talk about elements in a container rather than the components in a container – components is the Ada term for the items of an array or record as an Ada type and it is convenient to use a different term since in the case of containers the actual data structure is hidden.

@ Worst-case and average-case time complexity bounds are given using the familiar O ( ... ) notation.

@ This encourages implementations to use techniques that scale reasonably well and avoid junk algorithms such as bubble sort.

@ Perhaps a remark about using containers from a multitasking program would be helpful. The general rule is given in paragraph 3 of Annex A which says "The implementation shall ensure that each language defined subprogram is reentrant in the sense that concurrent calls on the same subprogram perform as specified, so long as all parameters that could be passed by reference denote nonoverlapping objects." So in other words we have to protect ourselves by using the normal techniques such as protected objects when container operations are invoked concurrently on the same object from multiple tasks even if the operations are only reading from the container.

Rationale for Ada 2005: 6a Containers

ENGRUSTOPBACKNEXT

1. Организация контейнеров

@ Главным улучшением предопределенной библиотеки Ады 2005 является добавленение контейнеров.

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

@ Основные пакеты контейнерной библиотеки могут быть сгруппированы несколькими способами. Один набор пакетов касается манипуляции объектами определенных типов, а другой, практически идентичный, касается неопределенных типов. (Напомним, что неопределенный (sub)тип это такой, для которого мы не можем объявить объект, не давая ограничение). Причина для такого дублирования касается эффективности. Намного легче управлять определенными типами и хотя пакеты для неопределенных типов могут использоваться для определенных типов, это было бы довольно неэффективно.

@ Мы вообще рассмотрим только определенные пакеты. Они в свою очередь включают две группы.

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

@ Ассоциативные контейнеры - они связывают ключ с каждым элементом и затем хранят элементы в порядке ключей. Есть пакеты для того, чтобы управлять Hash картами, упорядоченными (ordered) картами, Hash наборами и упорядоченными (ordered) наборами. Эти четыре пакета также имеют много общего, и отличия между Hash и Упорядоченными версиями обычно невелики.

@ Есть также отдельные настраиваемые процедуры для сортировки массивов, которые мы рассмотрим позже.

@ Корневой пакет имеет вид:

 
  1        package Ada.Containers is
  2                pragma Pure (Containers);
  3                type Hash_Type is mod implementation-defined;
  4                type Count_Type is range 0 .. implementation-defined;
  5        end Ada.Containers;

@ Тип Hash_Type используется ассоциативными контейнерами, а Count_Type обычно используется обоими видами контейнеров для ряда элементов в контейнере. Отметим, что мы говорим об элементах в контейнере, а не компонентах в контейнере, компонент - термин Ады для элементов массива или записи, это отличие в терминологии важно, т.к. в случае контейнеров, фактическая структура данных скрыта.

@ ??? Худший случай и границы сложности времени среднего случая даны, используя знакомое примечание O (...). ???

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

@ Некоторое замечание об использовании контейнеров в мультизадачных программах было бы полезно. Общее для этого правило дано в параграфе 3 Приложения A, которое говорит, что "выполнение должно гарантировать, что определенная подпрограмма каждого языка - ??? переучастник в смысле, что параллельные вызовы одной и той же подпрограммы выступают как определено, пока все параметры, которые могла передать ссылка, обозначают неналожившиеся объекты. ???" Другими словами, мы должны защитить себя использованием нормальных методов, таких как защищенные объекты, когда контейнерные операции пересекаются на одном и том же объекте от нескольких задач, даже если операции осуществляют только чтение из контейнера.

ENG RUS

TOP BACK NEXT

2010-10-24 00:26:57

. .