Lists and vectors

Rationale for Ada 2005: 6a Containers

ENG

2. Lists and vectors

@ We will first consider the list container since in some ways it is the simplest. Here is its specification interspersed with some explanation

  1        generic
  2                type Element_Type is private;
  3                with function "=" (Left, Right : Element_Type) return Boolean is <>;
  4        package Ada.Containers.Doubly_Linked_Lists is
  5                pragma Preelaborate (Doubly_Linked_Lists);
  6                type List is tagged private;
  7                pragma Preelaborable_Initialization (List);
  8                type Cursor is private;
  9                pragma Preelaborable_Initialization (Cursor);
 10                Empty_List : constant List;
 11                No_Element : constant Cursor;

@ The two generic parameters are the type of the elements in the list and the definition of equality for comparing elements. This equality relation must be such that x = y and y = x always have the same value.

@ A list container is an object of the type List. It is tagged since it will inevitably be implemented as a controlled type. The fact that it is visibly tagged means that all the advantages of object oriented programming are available. For one thing it enables the use of the prefixed notation so that we can write operations such as

  1        My_List.Append (Some_Value);

@ rather than

  1        Append (My_List, Some_Value);

@ The type Cursor is an important concept. It provides the means of access to individual elements in the container. Not only does it contain a reference to an element but it also identifies the container as well. This enables various checks to be made to ensure that we don't accidentally meddle with an element in the wrong container.

@ The constants Empty_List and No_Element are as expected and also provide default values for objects of types List and Cursor respectively.

  1        function "=" (Left, Right : List) return Boolean;
  2        function Length (Container : List) return Count_Type;
  3        function Is_Empty (Container : List) return Boolean;
  4        procedure Clear (Container : in out List);

@ The function "=" compares two lists. It only returns true if both lists have the same number of elements and corresponding elements have the same value as determined by the generic parameter "=" for comparing elements. The subprograms Length, Is_Empty and Clear are as expected.

@ Note that A_List = Empty_List, Is_Empty (A_List) and Length (A_List) = 0 all have the same value.

  1        function Element (Position : Cursor) return Element_Type;
  2        procedure Replace_Element
  3        (       Container : in out List;
  4                Position  : in Cursor;
  5                New_Item  : in Element_Type);

@ These are the first operations we have met that use a cursor. The function Element takes a cursor and returns the value of the corresponding element (remember that a cursor identifies the list as well as the element itself). The procedure Replace_Element replaces the value of the element identified by the cursor by the value given; it makes a copy of course.

@ Note carefully that Replace_Element has both the list and cursor as parameters. There are two reasons for this concerning correctness. One is to enable a check that the cursor does indeed identify an element in the given list. The other is to ensure that we do have write access to the container (the parameter has mode in out). Otherwise it would be possible to modify a container even though we only had a constant view of it. So as a general principle any operation that modifies a container must have the container as a parameter whereas an operation that only reads it such as the function Element does not.

  1        procedure Query_Element
  2        (       Position : in Cursor;
  3                Process  : not null access procedure (Element : in Element_Type));
  4        procedure Update_Element
  5        (       Container : in out List;
  6                Position  : in Cursor;
  7                Process   : not null access procedure (Element : in out Element_Type));

@ These procedures provide in situ access to an element. One parameter is the cursor identifying the element and another is an access to a procedure to be called with that element as parameter. In the case of Query_Element, we can only read the element whereas in the case of Update_Element we can change it as well since the parameter mode of the access procedure is in out. Note that Update_Element also has the container as a parameter for reasons just mentioned when discussing Replace_Element.

@ The reader might wonder whether there is any difference between calling the function Element to obtain the current value of an element and using the seemingly elaborate mechanism of Query_Element. The answer is that the function Element makes a copy of the value whereas Query_Element gives access to the value without making a copy. (And similarly for Replace_Element and Update_Element.) This wouldn't matter for a simple list of integers but it would matter if the elements were large or of a controlled type (maybe even lists themselves).

  1        procedure Move (Target, Source : in out List);

@ This moves the list from the source to the target after first clearing the target. It does not make copies of the elements so that after the operation the source is empty and Length (Source) is zero.

  1        procedure Insert
  2        (       Container : in out List;
  3                Before    : in Cursor;
  4                New_Item  : in Element_Type;
  5                Count     : in Count_Type := 1);
  6        procedure Insert
  7        (       Container : in out List;
  8                Before    : in Cursor;
  9                New_Item  : in Element_Type;
 10                Position  : out Cursor;
 11                Count     : in Count_Type := 1);
 12        procedure Insert
 13        (       Container : in out List;
 14                Before    : in Cursor;
 15                Position  : out Cursor;
 16                Count     : in Count_Type := 1);

@ These three procedures enable one or more identical elements to be added anywhere in a list. The place is indicated by the parameter Before – if this is No_Element, then the new elements are added at the end. The second procedure is similar to the first but also returns a cursor to the first of the added elements. The third is like the second but the new elements take their default values. Note the default value of one for the number of elements.

  1        procedure Prepend
  2        (       Container : in out List;
  3                New_Item  : in Element_Type;
  4                Count     : in Count_Type := 1);
  5        procedure Append
  6        (       Container : in out List;
  7                New_Item  : in Element_Type;
  8                Count     : in Count_Type := 1);

@ These add one or more new elements at the beginning or end of a list respectively. Clearly these operations can be done using Insert but they are sufficiently commonly needed that it is convenient to provide them specially.

  1        procedure Delete
  2        (       Container : in out List;
  3                Position  : in out Cursor;
  4                Count     : in Count_Type := 1);
  5        procedure Delete_First (Container : in out List; Count : in Count_Type := 1);
  6        procedure Delete_Last (Container : in out List; Count : in Count_Type := 1);

@ These delete one or more elements at the appropriate position. In the case of Delete, the parameter Position is set to No_Element upon return. If there are not as many as Count elements to be deleted at the appropriate place then it just deletes as many as possible (this clearly results in the container becoming empty in the case of Delete_First and Delete_Last).

  1        procedure Reverse_Elements (Container : in out List);

@ This does the obvious thing. It would have been nice to call this procedure Reverse but sadly that is a reserved word.

  1        procedure Swap (Container : in out List; I, J : in Cursor);

@ This handy procedure swaps the values in the two elements denoted by the two cursors. The elements must be in the given container otherwise Program_Error is raised. Note that the cursors do not change.

  1        procedure Swap_Links (Container : in out List; I, J : in Cursor);

@ This performs the low level operation of swapping the links rather than the values which can be much faster if the elements are large. There is no analogy in the vectors package.

  1        procedure Splice
  2        (       Target : in out List;
  3                Before : in Cursor;
  4                Source : in out List);
  5        procedure Splice
  6        (       Target   : in out List;
  7                Before   : in Cursor;
  8                Source   : in out List;
  9                Position : in out Cursor);
 10        procedure Splice
 11        (       Container : in out List;
 12                Before    : in Cursor;
 13                Position  : in out Cursor);

@ These three procedures enable elements to be moved (without copying). The place is indicated by the parameter Before – if this is No_Element, then the elements are added at the end. The first moves all the elements of Source into Target at the position given by Before; as a consequence, like the procedure Move, after the operation the source is empty and Length (Source) is zero. The second moves a single element at Position from the list Source to Target and so the length of target is incremented whereas that of source is decremented; Position is updated to its new location in Target.

@ The third moves a single element within a list and so the length remains the same (note the formal parameter is Container rather than Target in this case). There are no corresponding operations in the vectors package because, like Swap_Links, we are just moving the links and not copying the elements.

  1        function First (Container : List) return Cursor;
  2        function First_Element (Container : List) return Element_Type;
  3        function Last (Container : List) return Cursor;
  4        function Last_Element (Container : List) return Element_Type;
  5        function Next (Position : Cursor) return Cursor;
  6        function Previous (Position : Cursor) return Cursor;
  7        procedure Next (Position : in out Cursor);
  8        procedure Previous (Position : in out Cursor);
  9        function Find
 10        (       Container : List;
 11                Item      : Element_Type;
 12                Position  : Cursor := No_Element) return Cursor;
 13        function Reverse_Find
 14        (       Container : List;
 15                Item      : Element_Type;
 16                Position  : Cursor := No_Element) return Cursor;
 17        function Contains (Container : List; Item : Element_Type) return Boolean;

@ Hopefully the purpose of these is almost self-evident. The function Find searches for an element with the given value starting at the given cursor position (or at the beginning if the position is No_Element); if no element is found then it returns No_Element. Reverse_Find does the same but backwards. Note that equality used for the comparison in Find and Reverse_Find is that defined by the generic parameter "=".

  1        function Has_Element (Position : Cursor) return Boolean;

@ This returns False if the cursor does not identify an element; for example if it is No_Element.

  1        procedure Iterate
  2        (       Container : in List;
  3                Process   : not null access procedure (Position : in Cursor));
  4        procedure Reverse_Iterate
  5        (       Container : in List;
  6                Process   : not null access procedure (Position : in Cursor));

@ These apply the procedure designated by the parameter Process to each element of the container in turn in the appropriate order.

  1        generic
  2                with function "<" (Left, Right : Element_Type) return Boolean is <>;
  3        package Generic_Sorting is
  4                function Is_Sorted (Container : List) return Boolean;
  5                procedure Sort (Container : in out List);
  6                procedure Merge (Target, Source : in out List);
  7        end Generic_Sorting;

@ This generic package performs sort and merge operations using the order specified by the generic formal parameter. Note that we use generics rather than access to subprogram parameters when the formal process is given by an operator. This is because the predefined operations have convention Intrinsic and one cannot pass an intrinsic operation as an access to subprogram parameter. The function Is_Sorted returns True if the container is already sorted. The procedure Sort arranges the elements into order as necessary – note that no copying is involved since it is only the links that are moved. The procedure Merge takes the elements from Source and adds them to Target. After the merge Length (Source) is zero. If both lists were sorted before the merge then the result is also sorted.

@ And finally we have

  1        private
  2                ... -- not specified by the language
  3        end Ada.Containers.Doubly_Linked_Lists;

@ If the reader has got this far they have probably understood how to use this package so extensive examples are unnecessary. However, as a taste, here is a simple stack of floating point numbers

  1        package Stack is
  2                procedure Push (X : in Float);
  3                function Pop return Float;
  4                function Size return Integer;
  5        exception Stack_Empty;
  6        end;
  7        with Ada.Containers.Doubly_Linked_Lists;
  8        use Ada.Containers;
  9        package body Stack is
 10                package Float_Container is new Doubly_Linked_Lists (Float);
 11                use Float_Container;
 12                The_Stack : List;
 13                procedure Push (X : in Float) is
 14                begin
 15                        Append (The_Stack, X); -- or The_Stack.Append (X);
 16                end Push;
 17                function Pop return Float is
 18                        Result : Float;
 19                begin
 20                        if Is_Empty (The_Stack) then
 21                                raise Stack_Empty;
 22                        end if;
 23                        Result := Last_Element (The_Stack);
 24                        Delete_Last (The_Stack);
 25                        return Result;
 26                end Pop;
 27                function Size return Integer is
 28                begin
 29                        return Integer (Length (The_Stack));
 30                end Size;
 31        end Stack;

@ This barely needs any explanation. The lists package is instantiated in the package Stack and the object The_Stack is of course the list container. The rest is really straightforward. We could of course use the prefixed notation throughout as indicated in Push.

@ An important point should be mentioned concerning lists (and containers in general). This is that attempts to do foolish things typically result in Constraint_Error or Program_Error being raised. This especially applies to the procedures Process in Query_Element, Update_Element, Iterate and Reverse_Iterate. The concepts of tampering with cursors and elements are introduced in order to dignify a general motto of "Thou shalt not violate thy container".

@ Tampering with cursors occurs when elements are added to or deleted from a container (by calling Insert and so on) whereas tampering with elements means replacing an element (by calling Replace_Element for example). Tampering with elements is a greater sin and includes tampering with cursors. The procedure Process in Query_Element and Update_Element must not tamper with elements and the procedure Process in the other cases must not tamper with cursors. The reader might think it rather odd that Update_Element should not be allowed to tamper with elements since the whole purpose is to update the element; this comes back to the point mentioned earlier that update element gives access to the existing element in situ via the parameter of Process and that is allowed – calling Replace_Element within Process would be tampering. Tampering causes Program_Error to be raised.

@ We will now consider the vectors package. Its specification starts

  1        generic
  2                type Index_Type is range <>;
  3                type Element_Type is private;
  4                with function "=" (Left, Right : Element_Type) return Boolean is <>;
  5        package Ada.Containers.Vectors is
  6                pragma Preelaborate (Vectors);

@ This is similar to the lists package except for the additional generic parameter Index_Type (note that this is an integer type and not a discrete type). This additional parameter reflects the idea that a vector is essentially an array and we can index directly into an array.

@ In fact the vectors package enables us to access elements either by using an index or by using a cursor. Thus many operations are duplicated such as

  1        function Element (Container : Vector; Index : Index_Type) return Element_Type;
  2        function Element (Position : Cursor) return Element_Type;
  3        procedure Replace_Element
  4        (       Container : in out Vector;
  5                Index     : in Index_Type;
  6                New_Item  : in Element_Type);
  7        procedure Replace_Element
  8        (       Container : in out Vector;
  9                Position  : in Cursor;
 10                New_Item  : in Element_Type);

@ If we use an index then there is always a distinct parameter identifying the vector as well. If we use a cursor then the vector parameter is omitted if the vector is unchanged as is the case with the function Element. Remember that we stated earlier that a cursor identifies both an element and the container but if the container is being changed as in the case of Replace_Element then the container has to be passed as well to ensure write access and to enable a check that the cursor does identify an element in the correct container.

@ There are also functions First_Index and Last_Index thus

  1        function First_Index (Container : Vector) return Index_Type;
  2        function Last_Index (Container : Vector) return Extended_Index;

@ These return the values of the index of the first and last elements respectively. The function First_Index always returns Index_Type'First whereas Last_Index will return No_Index if the vector is empty. The function Length returns Last_Index–First_Index+1 which is zero if the vector is empty.

@ Note that the irritating subtype Extended_Index has to be introduced in order to cope with end values. The constant No_Index has the value Extended_Index'First which is equal to Index_Type'First–1.

@ There are operations to convert between an index and a cursor thus

  1        function To_Cursor (Container : Vector; Index : Extended_Index) return Cursor;
  2        function To_Index (Position : Cursor) return Extended_Index;

@ It is perhaps slightly messier to use the index and vector parameters because of questions concerning the range of values of the index but probably slightly faster and maybe more familiar. And sometimes of course using an index is the whole essence of the problem. In the paper on access types we showed a use of the procedure Update_Element to double the values of those elements of a vector whose index was in the range 5 to 10. This would be tedious with cursors.

@ But an advantage of using cursors is that (provided certain operations are avoided) it is easy to replace the use of vectors by lists.

@ For example here is the stack package rewritten to use vectors

  1        with Ada.Containers.Vectors; -- changed
  2        use Ada.Containers;
  3        package body Stack is
  4                package Float_Container is new Vectors (Natural, Float); -- changed
  5                use Float_Container;
  6                The_Stack : Vector; -- changed
  7                procedure Push (X : in Float) is
  8                begin
  9                        Append (The_Stack, X);
 10                end Push;
 11                -- etc exactly as before
 12        end Stack;

@ So the changes are very few indeed and can be quickly done with a simple edit.

@ Note that the index parameter has been given as Natural rather than Integer. Using Integer will not work since attempting to elaborate the subtype Extended_Index would raise Constraint_Error when evaluating Integer'First–1. But in any event it is more natural for the index range of the container to start at 0 (or 1) rather than a large negative value such as Integer'First.

@ There are other important properties of vectors that should be mentioned. One is that there is a concept of capacity. Vectors are adjustable and will extend if necessary when new items are added.

@ However, this might lead to lots of extensions and copying and so we can set the capacity of a container by calling

  1        procedure Reserve_Capacity (Container : in out Vector; Capacity : in Count_Type);

@ There is also

  1        function Capacity (Container : Vector) return Count_Type;

@ which naturally returns the current capacity. Note that Length (V) cannot exceed Capacity (V) but might be much less.

@ If we add items to a vector whose length and capacity are the same then no harm is done. The capacity will be expanded automatically by effectively calling Reserve_Capacity internally. So the user does not need to set the capacity although not doing so might result in poorer performance.

@ There is also the concept of "empty elements". These are elements whose values have not been set.

@ There is no corresponding concept with lists. It is a bounded error to read an empty element. Empty elements arise if we declare a vector by calling

  1        function To_Vector (Length : Count_Type) return Vector;

@ as in

  1        My_Vector : Vector := To_Vector (100);

@ There is also the much safer

  1        function To_Vector (New_Item : Element_Type; Length : Count_Type) return Vector;

@ which sets all the elements to the value New_Item.

@ There is also a procedure

  1        procedure Set_Length (Container : in out Vector; Length : in Count_Type);

@ This changes the length of a vector. This may require elements to be deleted (from the end) or to be added (in which case the new ones are empty).

@ The final way to get an empty element is by calling one of

  1        procedure Insert_Space
  2        (       Container : in out Vector;
  3                Before    : in Extended_Index;
  4                Count     : in Count_Type := 1);
  5        procedure Insert_Space
  6        (       Container : in out Vector;
  7                Before    : in Cursor;
  8                Position  : out Cursor;
  9                Count     : in Count_Type := 1);

@ These insert the number of empty elements given by Count at the place indicated. Existing elements are slid along as necessary. These should not be confused with the versions of Insert which do not provide an explicit value for the elements – in those cases the new elements take their default values.

@ Care needs to be taken if we use empty elements. For example we should not compare two vectors using "=" if they have empty elements because this implies reading them. But the big advantage of empty elements is that they provide a quick way to make a large lump of space in a vector which can then be filled in with appropriate values. One big slide is a lot faster than lots of little ones.

@ For completeness, we briefly mention the remaining few subprograms that are unique to the vectors package.

@ There are further versions of Insert thus

  1        procedure Insert
  2        (       Container : in out Vector;
  3                Before    : in Extended_Index;
  4                New_Item  : in Vector);
  5        procedure Insert
  6        (       Container : in out Vector;
  7                Before    : in Cursor;
  8                New_Item  : in Vector);
  9        procedure Insert
 10        (       Container : in out Vector;
 11                Before    : in Cursor;
 12                New_Item  : in Vector;
 13                Position  : out Cursor);

@ These insert copies of a vector into another vector (rather than just single elements).

@ There are also corresponding versions of Prepend and Append thus

  1        procedure Prepend (Container : in out Vector; New_Item : in Vector);
  2        procedure Append (Container : in out Vector; New_Item : in Vector);

@ Finally, there are four functions "&" which concatenate vectors and elements by analogy with those for the type String. Their specifications are

  1        function "&" (Left, Right : Vector) return Vector;
  2        function "&" (Left : Vector; Right : Element_Type) return Vector;
  3        function "&" (Left : Element_Type; Right : Vector) return Vector;
  4        function "&" (Left, Right : Element_Type) return Vector;

@ Note the similarity between

  1        Append (V1, V2);
  2        V1 := V1 & V2;

@ The result is the same but using "&" is less efficient because of the extra copying involved. But "&" is a familiar operation and so is provided for convenience.

Rationale for Ada 2005: 6a Containers

ENGRUSTOPBACKNEXT

2. Списки и вектора

@ Сначала мы рассмотрим контейнерные списки т.к. из всех контейнеров они является наиболее простым. Рассмотрим спецификацию:

  1        generic
  2                type Element_Type is private;
  3                with function "=" (Left, Right : Element_Type) return Boolean is <>;
  4        package Ada.Containers.Doubly_Linked_Lists is
  5                pragma Preelaborate (Doubly_Linked_Lists);
  6                type List is tagged private;
  7                pragma Preelaborable_Initialization (List);
  8                type Cursor is private;
  9                pragma Preelaborable_Initialization (Cursor);
 10                Empty_List : constant List;
 11                No_Element : constant Cursor;

@ Два настраиваемых параметра здесь тип элемента списка и определение функции равенства для сравнения элементов. Это равенство должно быть таким, что X = Y эквивалентно Y = X.

@ Контейнерный список это объект типа List. Он теговый, так как он будет неизбежно осуществлён как управляемый (controlled) тип. Факт того, что он теговый даёт все преимущества объектно-ориентированного программирования. С одной стороны это позволяет нам использовать префиксную нотацию:

  1        My_List.Append (Some_Value);

@ вместо:

  1        Append (My_List, Some_Value);

@ Тип Cursor - важное понятие. Он обеспечивает средства доступа к индивидуальным элементам в контейнере. Помимо того, что он содержит ссылку на элемент он также идентифицирует и сам контейнер. Это позволяет выполнить соответствующие проверки для гарантии что мы случайно не влезаем в элемент в неправильном контейнере.

@ Константы Empty_List и No_Element, как и ожидается, обеспечивают значения по умолчанию для объектов типа List и Cursor соответственно.

  1        function "=" (Left, Right : List) return Boolean;
  2        function Length (Container : List) return Count_Type;
  3        function Is_Empty (Container : List) return Boolean;
  4        procedure Clear (Container : in out List);

@ Функция "=" сравнивает два списка. Она возвращает True только если оба списка имеют одинаковый ряд элементов, и у соответствующих элементов одинаковые значения в соответствии с настраиваемой функцией "=" для сравнения элементов. Назначение подпрограмм Length, Is_Empty и Clear понятно из названия.

@ Заметим, что выражения A_List = Empty_List, Is_Empty (A_List) и Length (A_List) = 0 эквивалентны.

  1        function Element (Position : Cursor) return Element_Type;
  2        procedure Replace_Element
  3        (       Container : in out List;
  4                Position  : in Cursor;
  5                New_Item  : in Element_Type);

@ Это первые операции где мы встречаем использование курсора. Функция Element берет курсор и возвращает значение соответствующего элемента (напомним, что курсор идентифицирует как список так и элемент непосредственно). Процедура Replace_Element заменяет значение элемента, идентифицированного курсором данным значением; это делается копированием, конечно.

@ Обратите внимание, что Replace_Element имеет и список и курсор в качестве параметров. Есть две причины для этого. Первая, это то что нужно обеспечить проверку того, что курсор действительно идентифицирует элемент в данном списке. Другая, состоит в том, что нужно гарантировать, что у нас действительно есть доступ для записи в контейнер (у параметра есть режим in out). Иначе было бы возможно изменить контейнер даже при том, что он был бы представлен константой. Общий принцип такой, у любой операции, которая изменяет контейнер должен быть контейнер в качестве параметра, тогда как операция, которая только читает значение такого параметра нет (например, функция Element).

  1        procedure Query_Element
  2        (       Position : in Cursor;
  3                Process  : not null access procedure (Element : in Element_Type));
  4        procedure Update_Element
  5        (       Container : in out List;
  6                Position  : in Cursor;
  7                Process   : not null access procedure (Element : in out Element_Type));

@ Эти процедуры обеспечивают непосредственный доступ к элементу. Один из параметров - курсор, идентифицирующий элемент, а другой - ссылка на процедуру, которая вызывается с этим элементом в качестве параметра. В случае Query_Element мы можем только читать элемент, тогда как в случае Update_Element мы можем изменить его также, так как режим параметра процедуры in out. Отметим, что Update_Element также принимает контейнер в качестве параметра, по причинам только упомянутым при обсуждении Replace_Element.

@ Читатель мог бы задаться вопросом, есть ли какое-нибудь различие между вызовом функции Element для получения текущего значени элемента и использования более сложного механизма Query_Element. Ответ состоит в том, что функция Element делает копию значения, тогда как Query_Element предоставляет ссылку на значение, не делая копию. (аналогично для Replace_Element и Update_Element). Это не имело бы значения для простого списка целых чисел, но имело бы значение, если бы элементы были большими или управляемого (controllrd) типа (возможно даже списки непосредственно).

  1        procedure Move (Target, Source : in out List);

@ Эта процедура перемещает список из Source в Target после первоначальной очистки Target. После выполнения операции источник не очищается, и Length (Source) не становится равным нулю.

  1        procedure Insert
  2        (       Container : in out List;
  3                Before    : in Cursor;
  4                New_Item  : in Element_Type;
  5                Count     : in Count_Type := 1);
  6        procedure Insert
  7        (       Container : in out List;
  8                Before    : in Cursor;
  9                New_Item  : in Element_Type;
 10                Position  : out Cursor;
 11                Count     : in Count_Type := 1);
 12        procedure Insert
 13        (       Container : in out List;
 14                Before    : in Cursor;
 15                Position  : out Cursor;
 16                Count     : in Count_Type := 1);

@ Эти три процедуры позволяют добавлять в список один или более идентичных элементов. Позиция в списке обозначается параметром Before, если указать No_Element, то новые элементы будут добавляються в конец списка. Вторая процедура подобна первой но ещё и возвращает курсор первого из добавленных элементов. Третья походит на вторую, но новые элементы принимают свои значения по умолчанию. Отметим значение по умолчанию одного для ряда элементов.

  1        procedure Prepend
  2        (       Container : in out List;
  3                New_Item  : in Element_Type;
  4                Count     : in Count_Type := 1);
  5        procedure Append
  6        (       Container : in out List;
  7                New_Item  : in Element_Type;
  8                Count     : in Count_Type := 1);

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

  1        procedure Delete
  2        (       Container : in out List;
  3                Position  : in out Cursor;
  4                Count     : in Count_Type := 1);
  5        procedure Delete_First (Container : in out List; Count : in Count_Type := 1);
  6        procedure Delete_Last (Container : in out List; Count : in Count_Type := 1);

@ Эти процедуры удаляют один или более элементов в соответствующей позиции. В случае Delete, параметр Position устанавливается в No_Element по возвращению. Если число элементов в списке справа от Position меньше чем Count тогда удаляются столько элементов сколько возможно (ясно, что это приводит к полной очистке контейнера в случае Delete_First и Delete_Last).

  1        procedure Reverse_Elements (Container : in out List);

@ Эта процедура делает очевидную из названия вещь. Было бы правильно назвать её Reverse, но к сожалению, это является зарезервированным словом.

  1        procedure Swap (Container : in out List; I, J : in Cursor);

@ Эта удобная процедура обменивает значения между двумя элементами, обозначенных этими двумя курсорами. Элементы должны быть в данном контейнере иначе возбуждается исключение Program_Error. Отметим, что курсоры не изменяются.

  1        procedure Swap_Links (Container : in out List; I, J : in Cursor);

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

  1        procedure Splice
  2        (       Target : in out List;
  3                Before : in Cursor;
  4                Source : in out List);
  5        procedure Splice
  6        (       Target   : in out List;
  7                Before   : in Cursor;
  8                Source   : in out List;
  9                Position : in out Cursor);
 10        procedure Splice
 11        (       Container : in out List;
 12                Before    : in Cursor;
 13                Position  : in out Cursor);

@ Эти три процедуры позволяют перемещать элементы (без копирования). Позиция для перемещения обозначается параметром Before, если его значение - No_Element, то элементы добавляются в конец. Первая процедура перемещает все элементы из списка Source в список Target в позицию Before; как и в процедуре Move после операции источник опустошается и Length (Source) становится нулем. Вторая процедура перемещает единственный элемент из Position списка Source в список Target длина которого увеличивается, тогда как длина источника уменьшается на еденицу; Position обновляется к её новому местоположению в Target.

@ Третья процедура перемещает единственный элемент в пределах списка и длина при этом не изменяется (обратите внимание, что формальный параметр называется Container, а не Target в этом случае). Соответствующих операций в векторном пакете нет, потому что, подобно Swap_Links, мы только перемещаем ссылки и не копируем элементы.

  1        function First (Container : List) return Cursor;
  2        function First_Element (Container : List) return Element_Type;
  3        function Last (Container : List) return Cursor;
  4        function Last_Element (Container : List) return Element_Type;
  5        function Next (Position : Cursor) return Cursor;
  6        function Previous (Position : Cursor) return Cursor;
  7        procedure Next (Position : in out Cursor);
  8        procedure Previous (Position : in out Cursor);
  9        function Find
 10        (       Container : List;
 11                Item      : Element_Type;
 12                Position  : Cursor := No_Element) return Cursor;
 13        function Reverse_Find
 14        (       Container : List;
 15                Item      : Element_Type;
 16                Position  : Cursor := No_Element) return Cursor;
 17        function Contains (Container : List; Item : Element_Type) return Boolean;

@ Назначение большинства этих процедур очевидна из названия. Функция Find ищет элемент с указанным значением начиная с данной позиции курсора (или сначала списка, если позиция - No_Element); если никакой элемент не найден, тогда возвращается значение No_Element. Reverse_Find делает то же самое, но обратном порядке. Отметим, что равенство, используемое для сравнения в Find и Reverse_Find, состоит в том что определено универсальным параметром "=".

  1        function Has_Element (Position : Cursor) return Boolean;

@ Здесь возвращается False, если курсор не идентифицирует элемент; например, если это - No_Element.

  1        procedure Iterate
  2        (       Container : in List;
  3                Process   : not null access procedure (Position : in Cursor));
  4        procedure Reverse_Iterate
  5        (       Container : in List;
  6                Process   : not null access procedure (Position : in Cursor));

@ Эти процедуры применяют процедуру, определяемую параметром Process для каждого элемента контейнера в соответствующем порядке.

  1        generic
  2                with function "<" (Left, Right : Element_Type) return Boolean is <>;
  3        package Generic_Sorting is
  4                function Is_Sorted (Container : List) return Boolean;
  5                procedure Sort (Container : in out List);
  6                procedure Merge (Target, Source : in out List);
  7        end Generic_Sorting;

@ Этот настраиваемый пакет выполняет сортировку и операцию слияния используя порядок определяемый настраиваемым формальным параметром. Отметим, что мы используем настраиваемое средство, а не ссылку на подпрограмму передаваемую параметром, когда формальный процесс задаётся оператором. Причина этого состоит в том, что у предопределенных операций есть соответствующие Intrinsic средства, и нельзя передать встроенную операцию как ссылку на подпрограмму передаваемую как параметр. Функция Is_Sorted возвращает True, если контейнер уже отсортирован. Процедура Sort упорядочивает элементы в необходимом порядке, при этом не происходит никакого копирования, так как перемещаются только ссылки. Процедура Merge берет элементы из Source и добавляет их к Target. После этого Length (Source) обнуляется. Если оба списка были отсортированы перед слиянием тогда также сортируется и результат.

@ В конце мы имеем:

  1        private
  2                ... -- not specified by the language
  3        end Ada.Containers.Doubly_Linked_Lists;

@ Если читатель забрался так далеко, он вероятно понял, как использовать этот пакет, и таким образом, приведение обширных примеров является излишним. Всё же рассмотрим простой стек чисел с плавающей запятой:

  1        package Stack is
  2                procedure Push (X : in Float);
  3                function Pop return Float;
  4                function Size return Integer;
  5        exception Stack_Empty;
  6        end;
  7
  8        with Ada.Containers.Doubly_Linked_Lists;
  9        use Ada.Containers;
 10        package body Stack is
 11                package Float_Container is new Doubly_Linked_Lists (Float);
 12                use Float_Container;
 13                The_Stack : List;
 14                procedure Push (X : in Float) is
 15                begin
 16                        Append (The_Stack, X); -- or The_Stack.Append (X);
 17                end Push;
 18                function Pop return Float is
 19                        Result : Float;
 20                begin
 21                        if Is_Empty (The_Stack) then
 22                                raise Stack_Empty;
 23                        end if;
 24                        Result := Last_Element (The_Stack);
 25                        Delete_Last (The_Stack);
 26                        return Result;
 27                end Pop;
 28                function Size return Integer is
 29                begin
 30                        return Integer (Length (The_Stack));
 31                end Size;
 32        end Stack;

@ Здесь мы нуждаемся в некотором пояснении. Пакет списков иллюстрируется в пакете Stack, и объект The_Stack - конечно же списковый контейнер. Остальные являются действительно прямыми. Мы конечно можем использовать префиксную нотацию повсюду как показано в Push.

@ Важный момент должен быть упомянут относительно списков (и контейнеров также). Это то, что приводит обычно к исключению Constraint_Error или Program_Error. Это особенно относится к процедурам Process в Query_Element, Update_Element, Iterate и Reverse_Iterate. Понятия вмешательства в курсороы и элементы введены чтобы обеспечить правило "Вы не должны нарушать ваш контейнер".

@ Вмешательство в курсоры происходит, когда элементы добавляются к или удаляются из контейнера (например, вызовом процедуры Insert), тогда как вмешательство в элементы означает заменять элемент (вызовом Replace_Element, например). Вмешательство в элементы является большим грехом и включает вмешательство в курсоры. Процедура Process в Query_Element и Update_Element не должна вмешиваться в элементы, и процедура Process в других случаях не должна вмешиваться в курсоры. Читатель мог бы посчитать это довольно странным, что Update_Element не позволяется вмешиваться в элементы, так как её цель состоит в том, чтобы обновить элемент; это возвращает нас к сути упомянутого ранее, что элемент обновления предоставляет ссылку к существующему элементу на месте через параметр Process, и это позволено вызовом Replace_Element в пределах Process, вмешался бы. Вмешательство приведит к возбуждению исключения Program_Error.

@ Теперь рассмотрим векторный пакет. Начало его спецификации:

  1        generic
  2                type Index_Type is range <>;
  3                type Element_Type is private;
  4                with function "=" (Left, Right : Element_Type) return Boolean is <>;
  5        package Ada.Containers.Vectors is
  6                pragma Preelaborate (Vectors);

@ Он подобен пакету списков за исключением дополнительного настраиваемого параметра Index_Type (отметим что это - целочисленный, а не дискретный тип). Этот дополнительный параметр отражает идею, что вектор - по существу массив, и мы можем индексировать непосредственно массив.

@ Фактически векторный пакет позволяет нам обратиться к элементам используя индекс или используя курсор. Таким образом, много операций таких же как и в пакете списков:

  1        function Element (Container : Vector; Index : Index_Type) return Element_Type;
  2        function Element (Position : Cursor) return Element_Type;
  3        procedure Replace_Element
  4        (       Container : in out Vector;
  5                Index     : in Index_Type;
  6                New_Item  : in Element_Type);
  7        procedure Replace_Element
  8        (       Container : in out Vector;
  9                Position  : in Cursor;
 10                New_Item  : in Element_Type);

@ Если мы используем индекс, тогда всегда есть другой параметр, идентифицирующий также вектор. Если мы используем курсор тогда, векторный параметр отсутствует, если вектор неизменен, как имеет место с функцией Element. Помните, что мы заявили ранее, что курсор идентифицирует и элемент и контейнер, но если контейнер изменяется как в случае Replace_Element тогда, контейнер нужно передать также, чтобы гарантировать ссылку на запись и выполнить проверку что курсор действительно идентифицирует элемент в правильном контейнере.

@ Есть также функции First_Index и Last_Index:

  1        function First_Index (Container : Vector) return Index_Type;
  2        function Last_Index (Container : Vector) return Extended_Index;

@ Они возвращают значения индекса первого и последнего элементов соответственно. Функция First_Index всегда возвращает Index_Type'First, тогда как Last_Index возвратит No_Index, если вектор будет пуст. Функция Length возвращается Last_Index-First_Index+1, который будет нулем, если вектор пуст.

@ Отметим, что раздражающий подтип Extended_Index должен быть введен, чтобы справиться с конечными значениями. У постоянного No_Index есть значение Extended_Index'First, который равен Index_Type'First-1.

@ Есть следующие операции для преобразований между индексом и курсором:

  1        function To_Cursor (Container : Vector; Index : Extended_Index) return Cursor;
  2        function To_Index (Position : Cursor) return Extended_Index;

@ Это возможно немного более грязно, чтобы использовать индекс и векторные параметры из-за вопросов относительно диапазона значений индекса, но вероятно немного быстрее и возможно более знакомо. Иногда конечно использование индекса является целой сущностью проблемы. В статье посвящённой ссылочным типам мы рассматривали использование процедуры Update_Element, чтобы удвоить значения тех элементов вектора, индекс которых был в диапазоне 5 - 10. Это было бы утомительно с курсорами.

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

@ Например вот пакет стека, перезаписанный, чтобы использовать векторы

  1        with Ada.Containers.Vectors; -- changed
  2        use Ada.Containers;
  3        package body Stack is
  4                package Float_Container is new Vectors (Natural, Float); -- changed
  5                use Float_Container;
  6                The_Stack : Vector; -- changed
  7                procedure Push (X : in Float) is
  8                begin
  9                        Append (The_Stack, X);
 10                end Push;
 11                -- etc exactly as before
 12        end Stack;

@ Таким образом, изменения действительно небольшие и могут быть быстро сделаны простым редактированием.

@ Отметим, что индексный параметр был задан как Natural, а не Integer. Использование Integer не будет работать, так как попытка иллюстрировать подтип Extended_Index вызовет исключение Constraint_Error при выполнении Integer'First-1. Но в любом случае для индексного диапазона контейнера начинаться с 0 (или 1) более естественно чем с наименьшего отрицательного значения Integer'First.

@ Есть другие важные свойства векторов, которые должны быть упомянуты. Первое - это понятие ёмкости. Границы векторов корректируемы и могут расширяться в случае добавления новых элементов.

@ Однако, это могло бы привести к большому количеству расширений и копирований и поэтому мы можем установить ёмкость контейнера вызовом:

  1        procedure Reserve_Capacity (Container : in out Vector; Capacity : in Count_Type);

@ Имеется также функция:

  1        function Capacity (Container : Vector) return Count_Type;

@ которая возвращает текущую ёмкость. Отметим, что Length (V) не может превысить Capacity (V), но может быть намного меньше.

@ Если мы добавляем элементы к вектору, длина которого равна ёмкости, в этом случае не возникнет никаких проблем. Ёмкость будет расширена автоматическим вызовом Reserve_Capacity. Таким образом, пользователь вовсе не обязан вегда устанавливать ёмкость, однако если это не сделать, это может привести к потере производительности.

@ Есть также понятие "пустых элементов". Это - элементы, значения которых не были установлены.

@ Нет такого понятия связанного со списками. Это ошибка границы пытаться читать пустой элемент. Пустые элементы возникают, если мы объявляем вектор вызывая функцию:

  1        function To_Vector (Length : Count_Type) return Vector;

@ как здесь:

  1        My_Vector : Vector := To_Vector (100);

@ Есть также намного более безопасный способ:

  1        function To_Vector (New_Item : Element_Type; Length : Count_Type) return Vector;

@ который инициализирует все элементы вектора значением New_Item.

@ Имеется также процедура:

  1        procedure Set_Length (Container : in out Vector; Length : in Count_Type);

@ Она изменяет длину вектора. Это может потребовать, чтобы элементы были удалены (с конца) или были добавлены новые (пустые).

@ Последний способ получить пустой элемент, вызывая одну из функций:

  1        procedure Insert_Space
  2        (       Container : in out Vector;
  3                Before    : in Extended_Index;
  4                Count     : in Count_Type := 1);
  5        procedure Insert_Space
  6        (       Container : in out Vector;
  7                Before    : in Cursor;
  8                Position  : out Cursor;
  9                Count     : in Count_Type := 1);

@ Они вставляют заданное число пустых элементов, определяемое параметром Count в указанном месте. Существующие элементы сдвигаются вправо по мере необходимости. Они не должны быть спутаны с версиями Insert, которые не обеспечивают явное значение для элементов - в тех случаях, новые элементы берут свои значения по умолчанию.

@ Мы должны быть внимательны при использовании пустых элементов. Например мы не должны сравнивать два вектора используя "=", если у них есть пустые элементы, потому что это подразумевает их чтение. Но большое преимущество пустых элементов состоит в том, что они обеспечивают быстрый способ выделить пространство в векторе, который может тогда быть заполнен в соответствующими значениями. Одна большая операция намного быстрее чем много небольших.

@ Для законченности мы кратко упоминаем наличие некоторых подпрограмм, которые уникальны для векторного пакета.

@ Есть ещё несколько версий процедуры Insert:

  1        procedure Insert
  2        (       Container : in out Vector;
  3                Before    : in Extended_Index;
  4                New_Item  : in Vector);
  5        procedure Insert
  6        (       Container : in out Vector;
  7                Before    : in Cursor;
  8                New_Item  : in Vector);
  9        procedure Insert
 10        (       Container : in out Vector;
 11                Before    : in Cursor;
 12                New_Item  : in Vector;
 13                Position  : out Cursor);

@ Они вставляют копию вектора в другой вектор (а не один элемент).

@ Имеются также соответствующие версии Prepend и Append:

  1        procedure Prepend (Container : in out Vector; New_Item : in Vector);
  2        procedure Append  (Container : in out Vector; New_Item : in Vector);

@ Наконец, есть четыре функции "&" которые связывают вектора и элементы аналогичные как для типа String. Их спецификация:

  1        function "&" (Left, Right : Vector) return Vector;
  2        function "&" (Left : Vector; Right : Element_Type) return Vector;
  3        function "&" (Left : Element_Type; Right : Vector) return Vector;
  4        function "&" (Left, Right : Element_Type) return Vector;

@ Таким образом, следующие две строки эквивалентны:

  1        Append (V1, V2);
  2        V1 := V1 & V2;

@ Результат уних одинаков, но использование "&" менее эффективено из-за вовлеченного дополнительного пространства. Но "&" знакомая операция и так предоставлена для удобства.

ENG RUS

TOP BACK NEXT

2010-10-24 00:26:57

. .