Sets

Rationale for Ada 2005: 6a Containers

ENG

4. Sets

@ Sets, like maps, come in two forms: hashed and ordered. Sets are of course just collections of values and there is no question of a key (we can perhaps think of the value as being its own key). Thus in the case of an ordered set the values are stored in order whereas in the case of a map, it is the keys that are stored in order. As well as the usual operations of inserting elements into a set and searching and so on, there are also many operations on sets as a whole that do not apply to the other containers – these are the familiar set operations such as union and intersection.

@ Here is the specification of the ordered sets package giving just those facilities that are common to both kinds of sets.

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

@ The only differences from the maps package (apart from the identifiers) are that there is no key type and both "<" and "=" apply to the element type (whereas in the case of maps, the operation "<" applies to the key type). Thus the ordering relationship "<" defined on elements defines equivalence between the elements whereas "=" defines equality.

@ It is possible for two elements to be equivalent but not equal. For example if they were strings then we might decide that the ordering (and thus equivalence) ignored the case of letters but that equality should take the case into account. (They could also be equal but not equivalent but that is perhaps less likely.) And as in the case of the maps package, the equality operation on elements is only used by the function "=" for comparing two sets.

@ Again we have the usual rules as explained for maps. Thus if x < y is true then y < x must be false; x < y and y < z must imply x < z; and x = y and y = x must be the same.

@ For the convenience of the user the function Equivalent_Elements is declared explicitly. It is equivalent to

  1        function Equivalent_Elements (Left, Right : Element_Type) return Boolean is
  2        begin
  3                return not (Left < Right) and not (Right < Left);
  4        end Equivalent_Elements;

@ This function Equivalent_Elements corresponds to the formal generic parameter of the same name in the hashed sets package discussed below. This should make it easier to convert between the two forms of packages.

  1        function "=" (Left, Right : Set) return Boolean;
  2        function Equivalent_Sets (Left, Right : Set) return Boolean;
  3        function To_Set (New_Item : Element_Type) return Set;
  4        function Length (Container : Set) return Count_Type;
  5        function Is_Empty (Container : Set) return Boolean;
  6        procedure Clear (Container : in out Set);

@ Note the addition of Equivalent_Sets and To_Set. Two sets are equivalent if they have the same number of elements and the pairs of elements are equivalent. This contrasts with the function "=" where the pairs of elements have to be equal rather than equivalent. Remember that elements might be equivalent but not equal (as in the example of a string mentioned above). The function To_Set takes a single element and creates a set. It is particularly convenient when used in conjunction with operations such as Union described below. The other subprograms are as in the other containers.

  1        function Element (Position : Cursor) return Element_Type;
  2        procedure Replace_Element (Container : in out Set;
  3                Position : in Cursor;
  4                New_Item : in Element_Type);
  5        procedure Query_Element (Position : in Cursor;
  6                Process : not null access procedure (Element : in Element_Type));

@ Again these are much as expected except that there is no procedure Update_Element. This is because the elements are arranged in terms of their own value (either by order or through the hash function) and if we just change an element in situ then it might become out of place (this problem does not arise with the other containers). This also means that Replace_Element has to ensure that the value New_Item is not equivalent to an element in a different position; if it is then Program_Error is raised. We will return to the problem of the missing Update_Element later.

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

@ This is just as for the other containers.

  1        procedure Insert (Container : in out Set;
  2                New_Item : in Element_Type;
  3                Position : out Cursor;
  4                Inserted : out Boolean);
  5        procedure Insert (Container : in out Set;
  6                New_Item : in Element_Type);

@ These insert a new element into the set unless an equivalent element already exists. If it does exist then the first one returns with Inserted set to False and Position indicating the element whereas the second raises Constraint_Error (the element value is not changed). If an equivalent element is not in the set then it is added and Position is set accordingly.

  1        procedure Include (Container : in out Set; New_Item : in Element_Type);

@ This is somewhat like the last Insert except that if an equivalent element is already in the set then it is replaced (rather than raising Constraint_Error).

  1        procedure Replace (Container : in out Set; New_Item : in Element_Type);

@ In this case, Constraint_Error is raised if an equivalent element does not already exist.

  1        procedure Exclude (Container : in out Set; Item : in Element_Type);

@ If an element equivalent to Item is already in the set, then it is deleted.

  1        procedure Delete (Container : in out Set; Item : in Element_Type);
  2        procedure Delete (Container : in out Set; Position : in out Cursor);

@ These delete an element. In the first case if there is no such equivalent element then Constraint_Error is raised. In the second case if the cursor is No_Element then again Constraint_Error is also raised – there is also a check to ensure that the cursor otherwise does designate an element in the correct set (remember that cursors designate both an entity and the container); if this check fails then Program_Error is raised.

@ And now some new stuff, the usual set operations.

  1        procedure Union (Target : in out Set; Source : in Set);
  2        function Union (Left, Right : Set) return Set;
  3        function "or" (Left, Right : Set) return Set renames Union;
  4        procedure Intersection (Target : in out Set; Source : in Set);
  5        function Intersection (Left, Right : Set) return Set;
  6        function "and" (Left, Right : Set) return Set renames Intersection;
  7        procedure Difference (Target : in out Set; Source : in Set);
  8        function Difference (Left, Right : Set) return Set;
  9        function "–" (Left, Right : Set) return Set renames Difference;
 10        procedure Symmetric_Difference (Target : in out Set; Source : in Set);
 11        function Symmetric_Difference (Left, Right : Set) return Set;
 12        function "xor" (Left, Right : Set) return Set renames Symmetric_Difference;

@ These all do exactly what one would expect using the equivalence relation on the elements.

  1        function Overlap (Left, Right : Set) return Boolean;
  2        function Is_Subset (Subset : Set; Of_Set : Set) return Boolean;

@ These are self-evident as well.

  1        function First (Container : Set) return Cursor;
  2        function Last (Container : Set) return Cursor;
  3        function Next (Position : Cursor) return Cursor;
  4        procedure Next (Position : in out Cursor);
  5        function Find (Container : Set; Item : Element_Type) return Cursor;
  6        function Contains (Container : Set; Item : Element_Type) return Boolean;

@ These should be self-evident and are very similar to the corresponding operations on maps. Again unlike the operations on vectors and lists, Find logically searches the whole set and not just starting at some point (there is also no Reverse_Find). Moreover, Find uses the equivalence relation based on the "<" parameter.

  1        function Has_Element (Position : Cursor) return Boolean;
  2        procedure Iterate (Container : in Set;
  3                Process : not null access procedure (Position : in Cursor));

@ These are also as for other containers.

@ The sets packages conclude with an internal generic package called Generic_Keys. This package enables some set operations to be performed in terms of keys where the key is a function of the element. Note carefully that in the case of a map, the element is defined in terms of the key whereas here the situation is reversed. An equivalence relationship is defined for these keys as well; this is defined by a generic parameter "<" for ordered sets and Equivalent_Keys for hashed sets.

@ In the case of ordered sets the formal parameters are

  1        generic
  2                type Key_Type (<>) is private;
  3                with function Key (Element : Element_Type) return Key_Type;
  4                with function "<" (Left, Right : Key_Type) return Boolean is <>;
  5        package Generic_Keys is

@ The following are then common to the package Generic_Keys for both hashed and ordered sets.

  1        function Key (Position : Cursor) return Key_Type;
  2        function Element (Container : Set; Key : Key_Type) return Element_Type;
  3        procedure Replace (Container : in out Set;
  4                Key : in Key_Type; New_Item : in Element_Type);
  5        procedure Exclude (Container : in out Set; Key : in Key_Type);
  6        procedure Delete (Container : in out Set; Key : in Key_Type);
  7        function Find (Container : Set; Key : Key_Type) return Cursor;
  8        function Contains (Container : Set; Key : Key_Type) return Boolean;
  9        procedure Update_Element_Preserving_Key (
 10                Container : in out Set; Position : in Cursor;
 11                Process : not null access procedure (Element : in out Element_Type));

@ and then finally

  1        end Generic_Keys;
  2        private
  3                ... -- not specified by the language
  4        end Ada.Containers.Ordered_Sets;

@ It is expected that most user of sets will use them in a straightforward manner and that the operations specific to sets such as Union and Intersection will be dominant.

@ However, sets can be used as sort of economy class maps by using the inner package Generic_Keys.

@ Although this is certainly not for the novice we will illustrate how this might be done by reconsidering the stock problem using sets rather than maps. We declare

  1        type Part_Type is
  2                record
  3                        Part_Number : Integer;
  4                        Year        : Integer;
  5                        Shelf       : Character range 'A' .. 'T';
  6                        Stock       : Integer;
  7                end record;

@ Here we have put all the information in the one type.

@ We then declare "<" much as before

  1        function "<" (Left, Right : Part_Type) return Boolean is
  2        begin
  3                return Left.Part_Number < Right.Part_Number;
  4        end "<";

@ and then instantiate the package thus

  1        package Store_Sets is new Ordered_Sets (Element_Type => Part_Type);
  2        The_Store : Store_Sets.Set;

@ We have used the default generic parameter mechanism for "<" this time by way of illustration.

@ In this case we add items to the store by calling

  1        The_Store.Insert ((34618, 1998, 'F', 25));
  2        The_Store.Insert ((27134, 2004, 'C', 45));
  3        ...

@ The procedure for checking the stock could now become

  1        procedure Request (Part : in Integer;
  2                Ok    : out Boolean;
  3                Year  : out Integer;
  4                Shelf : out Character)
  5        is
  6                C : Cursor;
  7                E : Part_Type;
  8        begin
  9                C := The_Store.Find ((Part, others => <>));
 10                if C = No_Element then
 11                        Ok := False; return; -- no such item
 12                end if;
 13                E := Element (C);
 14                Year := E.Year;
 15                Shelf := E.Shelf;
 16                if E.Stock = 0 then
 17                        Ok := False; return; -- out of stock
 18                end if;
 19                Replace_Element (C, (E.Part_Number, Year; Shelf, E.Stock–1));
 20                Ok := True;
 21        end Request;

@ This works but is somewhat unsatisfactory. For one thing we have had to make up dummy components in the call of Find (using <>) and moreover we have had to replace the whole of the element although we only wanted to update the Stock component. Moreover, we cannot use Update_Element because it is not defined for sets at all. Remember that this is because it might make things out of order; that wouldn't be a problem in this case because we don't want to change the part number and our ordering is just by the part number.

@ A better approach is to use the part number as a key. We define

  1        type Part_Key is new Integer;
  2        function Part_No (P : Part_Type) return Part_Key is
  3        begin
  4                return Part_Key (P.Part_Number);
  5        end Part_No;

@ and then

  1        package Party is new Generic_Keys (Key_Type => Part_Key, Key => Part_No);
  2        use Party;

@ Note that we do not have to define "<" on the type Part_Key at all because it already exists since Part_Key is an integer type. And the instantiation uses it by default.

@ And now we can rewrite the Request procedure as follows

  1        procedure Request (Part : in Part_Key; Ok : out Boolean;
  2                Year : out Integer; Shelf : out Character)
  3        is
  4                C : Cursor;
  5                E : Part_Type;
  6        begin
  7                C := Find (The_Store, Part);
  8                if C = No_Element then
  9                        Ok := False; return; -- no such item
 10                end if;
 11                E := Element (C);
 12                Year := E.Year; Shelf := E.Shelf;
 13                if E.Stock = 0 then
 14                        Ok := False; return; -- out of stock
 15                end if;
 16                -- we are now going to update the stock level
 17                declare
 18                        procedure Do_It (E: in out Part_Type) is
 19                        begin
 20                                E.Stock := E.Stock – 1;
 21                        end Do_It;
 22                begin
 23                        Update_Element_Preserving_Key (The_Store, C, Do_It'Access);
 24                end;
 25                Ok := True;
 26        end Request;

@ This seems hard work but has a number of advantages. The first is that the call of Find is more natural and only involves the part number (the key) – note that this is a call of the function Find in the instantiation of Generic_Keys and takes just the part number. And the other is that the update only involves the component being changed. We mentioned earlier that there was no Update_Element for sets because of the danger of creating a value that was in the wrong place. In the case of the richly named Update_Element_Preserving_Key it also checks to ensure that the element is indeed still in the correct place (by checking that the key is still the same); if it isn't it removes the element and raises Program_Error.

@ But the user is warned to take care when using the package Generic_Keys. It is absolutely vital that the relational operation and the function (Part_No) used to instantiate Generic_Keys are compatible with the ordering used to instantiate the parent package Containers.Ordered_Sets itself. If this is not the case then the sky might fall in.

@ Incidentally, the procedure for checking the stock which previously used the maps package now becomes

  1        procedure Check_Stock (Low : in Integer) is
  2                procedure Check_It (C : in Cursor) is
  3                begin
  4                        if Element (C).Stock < Low then
  5                                -- print a message perhaps
  6                                Put ("Low stock of part ");
  7                                Put_Line (Element (C).Part_Number); -- changed
  8                        end if;
  9                end Check_It;
 10        begin
 11                The_Store.Iterate (Check_It'Access);
 12        end Check_Stock;

@ The only change is that the call of Key in

  1        Put_Line (Key (C).Part_Number);

@ when using the maps package has been replaced by Element. A minor point is that we could avoid calling Element twice by declaring a constant E in Check_It thus

  1        E : constant Part_Type := Element (C);

@ and then writing E.Stock < Low and calling Put_Line with E.Part_Number.

@ A more important point is that if we have instantiated the Generic_Keys inner package as illustrated above then we can leave Check_It unchanged to call Key. But it is important to realise that we are then calling the function Key internal to the instantiation of Generic_Keys (flippantly called Party) and not that from the instantiation of the parent ordered sets package (Store_Sets) because that has no such function. This illustrates the close affinity between the sets and maps packages.

@ And finally there is a hashed sets package which has strong similarities to both the ordered sets package and the hashed maps package. We can introduce this much as for hashed maps by giving the differences between the two sets packages, the extra facilities in each and the impact on the part number example.

@ The specification of the hashed sets package starts

  1        generic
  2                type Element_Type is private;
  3                with function Hash (Element : Element_Type) return Hash_Type;
  4                with function Equivalent_Elements (Left, Right : Element_Type) return Boolean;
  5                with function "=" (Left, Right : Element_Type) return Boolean is <>;
  6        package Ada.Containers.Hashed_Sets is
  7                pragma Preelaborate (Hashed_Sets);

@ The differences from the ordered sets package are that there is an extra generic parameter Hash and the ordering parameter "<" has been replaced by the function Equivalent_Elements.

@ So if we have

  1        function Equivalent_Parts (Left, Right : Part_Type) return Boolean is
  2        begin
  3                return Left.Part_Number = Right.Part_Number;
  4        end Equivalent_Parts;
  5        function Part_Hash (P : Part_Type) return Hash_Type is
  6                M31 : constant := 2**31–1; -- a nice Mersenne prime
  7        begin
  8                return Hash_Type (P.Part_Number) * M31;
  9        end Part_Hash;

@ (which are very similar to the hashed map example – the only changes are to the parameter type name) then we can instantiate the hashed sets package as follows

  1        package Store_Sets is
  2                new Hashed_Sets (Element_Type => Part_Type,
  3                        Hash => Part_Hash,
  4                        Equivalent_Elements => Equivalent_Parts);
  5        The_Store : Store_Sets.Set;

@ and then the rest of our example will be exactly as before. It is thus easy to convert from an ordered set to a hashed set and vice versa provided of course that we only use the facilities common to both.

@ It should also be mentioned that the inner package Generic_Keys for hashed sets has the following formal parameters

  1        generic
  2                type Key_Type (<>) is private;
  3                with function Key (Element : Element_Type) return Key_Type
  4                with function Hash (Key : Key_Type) return Hash_Type;
  5                with function Equivalent_Keys (Left, Right : Key_Type) return Boolean;
  6        package Generic_Keys is

@ The differences from that for ordered sets are the addition of the function Hash and the replacement of the comparison operator "<" by Equivalent_Keys. (Incidentally the package Generic_Keys for ordered sets also exports a function Equivalent_Keys for uniformity with the hashed sets package.) Although our example itself is unchanged we do have to change the instantiation of Generic_Keys thus

  1        type Part_Key is new Integer;
  2        function Part_No (P : Part_Type) return Part_Key is
  3        begin
  4                return Part_Key (P.Part_Number);
  5        end Part_No;
  6        function Part_Hash (P : Part_Key) return Hash_Type is
  7                M31 : constant := 2**31–1; -- a nice Mersenne prime
  8        begin
  9                return Hash_Type (P) * M31;
 10        end Part_Hash;
 11        function Equivalent_Parts (Left : Right : Part_Key) return Boolean is
 12        begin
 13                return Left = Right;
 14        end Equivalent_Parts;

@ and then

  1        package Party is
  2                new Generic_Key (Key_Type => Part_Key,
  3                        Key => Part_No;
  4                        Hash => Part_Hash
  5                        Equivalent_Keys => Equivalent_Parts);
  6        use Party;

@ The hash function is similar to that used with hashed maps. The type Part_Key and function Part_No are the same as for ordered sets. We don't really need to declare the function Equivalent_Parts since we could use "=" as the actual parameter for Equivalent_Keys.

@ We will finish this discussion of sets by briefly considering the additional facilities in the two sets packages (and their inner generic keys packages) just as we did for the two maps packages (the discussion is almost identical).

@ The ordered sets package has the following additional subprograms

  1        procedure Delete_First (Container : in out Set);
  2        procedure Delete_Last (Container : in out Set);
  3        function First_Element (Container : Set) return Element_Type;
  4        function Last_Element (Container : Set) return Element_Type;
  5        function Previous (Position : Cursor) return Cursor;
  6        procedure Previous (Position : in out Cursor);
  7        function Floor (Container : Set; Item : Element_Type) return Cursor;
  8        function Ceiling (Container : Set; Item : Element_Type) return Cursor;
  9        function "<" (Left, Right : Cursor) return Boolean;
 10        function ">" (Left, Right : Cursor) return Boolean;
 11        function "<" (Left : Cursor; Right : Element_Type) return Boolean;
 12        function ">" (Left : Cursor; Right : Element_Type) return Boolean;
 13        function "<" (Left : Element_Type; Right : Cursor) return Boolean;
 14        function ">" (Left : Element_Type; Right : Cursor) return Boolean;
 15        procedure Reverse_Iterate (Container : in Set;
 16        Process : not null access procedure (Position : in Cursor));

@ These are again largely self-evident. The functions Floor and Ceiling are similar to those for ordered maps – Floor searches for the last element which is not greater than Item and Ceiling searches for the first element which is not less than Item – they return No_Element if there is not one.

@ The functions "<" and ">" are very important for ordered sets. The first is equivalent to

  1        function "<" (Left, Right : Cursor) return Boolean is
  2        begin
  3                return Element (Left) < Element (Right);
  4        end "<";

@ There is a general philosophy that the container packages should work efficiently even if the elements themselves are very large – perhaps even other containers. We should therefore avoid copying elements. (Passing them as parameters is of course no problem since they will be passed by reference if they are large structures.) So in this case the built-in comparison is valuable because it can avoid the copying which would occur if we wrote the function ourselves with the explicit internal calls of the function Element.

@ On the other hand, there is a general expectation that keys will be small and so there is no corresponding problem with copying keys. Thus such built-in functions are less important for maps than sets but they are provided for maps for uniformity.

@ The following are additional in the package Generic_Keys for ordered sets

  1        function Equivalent_Keys (Left, Right : Key_Type) return Boolean;

@ This corresponds to the formal generic parameter of the same name in the package Generic_Keys for hashed sets as mentioned earlier.

  1        function Floor (Container : Set; Key : Key_Type) return Cursor;
  2        function Ceiling (Container : Set; Key : Key_Type) return Cursor;

@ These are much as the corresponding functions in the parent package except that they use the formal parameter "<" of Generic_Keys for the search.

@ Hashed sets, like hashed maps also have the facility to specify a capacity as for the vectors package.

@ Thus we have

  1        procedure Reserve_Capacity (Container : in out Set; Capacity : in Count_Type);
  2        function Capacity (Container : Set) return Count_Type;

@ The behaviour is much as for vectors and hashed maps. We don't have to set the capacity ourselves since it will be automatically extended as necessary but it might significantly improve performance to do so. Note again that Length (S) cannot exceed Capacity (S) but might be much less.

@ The other additional subprograms for hashed sets are

  1        function Equivalent_Elements (Left, Right : Cursor) return Boolean;
  2        function Equivalent_Elements (Left : Cursor; Right : Element_Type) return Boolean;
  3        function Equivalent_Elements (Left : Element_Type; Right : Cursor) return Boolean;

@ Again, these are very important for sets. The first is equivalent to

  1        function Equivalent_Elements (Left, Right : Cursor) return Boolean is
  2        begin
  3                return Equivalent_Elements (Element (Left), Element (Right));
  4        end Equivalent_Elements;

@ and once more we see that the built-in functions can avoid the copying of the type Element that would occur if we wrote the functions ourselves.

Rationale for Ada 2005: 6a Containers

ENGRUSTOPBACKNEXT

4. Наборы

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

@ Вот спецификация пакета упорядоченных наборов, где представлены только те средства, которые распространены у обоих видов наборов.

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

@ Единственное отличие от пакета карт (кроме идентификаторов) состоит в том, что нет никакого ключевого типа, функции "<" и "=" относятся к типу элемента (тогда как в случае карт, операция "<" относится к типу ключа). Таким образом, отношение упорядочения "<" определённое на элементах определяет эквивалентность между элементами, тогда как "=" определяет равенство.

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

@ Снова у нас есть обычные правила как и для карт. Таким образом, если X < Y является истиной тогда Y < X должно быть ложью; X < Y и Y < Z должен подразумевать X < Z; и X = Y и Y = X должно быть эквивалентно.

@ Для удобства пользователя функция Equivalent_Elements объявлена явно. Она выглядит выполняет примерно следующее:

  1        function Equivalent_Elements (Left, Right : Element_Type) return Boolean is
  2        begin
  3                return not (Left < Right) and not (Right < Left);
  4        end Equivalent_Elements;

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

  1        function "=" (Left, Right : Set) return Boolean;
  2        function Equivalent_Sets (Left, Right : Set) return Boolean;
  3        function To_Set (New_Item : Element_Type) return Set;
  4        function Length (Container : Set) return Count_Type;
  5        function Is_Empty (Container : Set) return Boolean;
  6        procedure Clear (Container : in out Set);

@ Отметим добавление функций Equivalent_Sets и To_Set. Два набора эквивалентны если у них один и тот же ряд элементов и пары элементов эквивалентны. Это контрастирует с функцией "=" где пары элементов должны быть равными, а не эквивалентными. Помните, что элементы могут быть эквивалентны, но при этом не обязательно должны быть равными (как в примере упомянутой выше строки). Функция To_Set берет единственный элемент и создает набор. Она особенно удобна когда используется вместе с операциями, такими как Union, описывемыми ниже. Другие подпрограммы как в других контейнерах.

  1        function Element (Position : Cursor) return Element_Type;
  2        procedure Replace_Element
  3        (       Container : in out Set;
  4                Position  : in Cursor;
  5                New_Item  : in Element_Type);
  6        procedure Query_Element
  7        (       Position : in Cursor;
  8                Process  : not null access procedure (Element : in Element_Type));

@ Опять же они такие как и ожидается за исключением того что нет никакой процедуры Update_Element. Это потому что элементы упорядочены в терминах их собственного значения (в соответствии с установленным порядком или через хеш-функцию) и если мы только изменяем элемент на месте тогда это может стать неуместным (эта проблема не возникает с другими контейнерами). Это также означает, что Replace_Element должен гарантировать что значение New_Item не эквивалентно элементу в различной позиции; в этом случае возбуждается исключение Program_Error. Мы вернёмся к проблеме без вести пропавшей Update_Element позже.

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

@ Производит такое же действие как и в других контейнерах.

  1        procedure Insert
  2        (       Container : in out Set;
  3                New_Item  : in Element_Type;
  4                Position  : out Cursor;
  5                Inserted  : out Boolean);
  6        procedure Insert
  7        (       Container : in out Set;
  8                New_Item  : in Element_Type);

@ Эти процедуры вставляют новый элемент в набор, если эквивалентный элемент ещё не существует. Если он действительно существует тогда первая возвращается с параметром Inserted установленным в False и параметром Position указывающим на элемент, тогда как вторая процедура поднимает исключение Constraint_Error (значение элемента при этом не изменяется). Если эквивалентный элемент не находится в наборе, тогда он добавляется и Position устанавливается соответственно.

  1        procedure Include (Container : in out Set; New_Item : in Element_Type);

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

  1        procedure Replace (Container : in out Set; New_Item : in Element_Type);

@ В этом случае Constraint_Error возбуждается, если эквивалентный элемент не существует.

  1        procedure Exclude (Container : in out Set; Item : in Element_Type);

@ Если элемент, эквивалентный Item уже находится в наборе, то он удаляется.

  1        procedure Delete (Container : in out Set; Item : in Element_Type);
  2        procedure Delete (Container : in out Set; Position : in out Cursor);

@ Они удаляют элемент. В первом случае, если нет такого элемента, возбуждается исключение Constraint_Error. Во втором случае, если курсор - No_Element, также имеет место Constraint_Error - есть также проверка для гарантии того что курсор определяет элемент в правильном наборе (напомним, что курсоры определяют и объект и контейнер); если эта проверка терпит неудачу, возбуждается исключение Program_Error.

@ И теперь некоторый новый материал, обычные операции набора.

  1        procedure Union (Target : in out Set; Source : in Set);
  2        function Union (Left, Right : Set) return Set;
  3        function "or" (Left, Right : Set) return Set renames Union;
  4        procedure Intersection (Target : in out Set; Source : in Set);
  5        function Intersection (Left, Right : Set) return Set;
  6        function "and" (Left, Right : Set) return Set renames Intersection;
  7        procedure Difference (Target : in out Set; Source : in Set);
  8        function Difference (Left, Right : Set) return Set;
  9        function "–" (Left, Right : Set) return Set renames Difference;
 10        procedure Symmetric_Difference (Target : in out Set; Source : in Set);
 11        function Symmetric_Difference (Left, Right : Set) return Set;
 12        function "xor" (Left, Right : Set) return Set renames Symmetric_Difference;

@ Они все делают точно, что можно было бы ожидать используяь отношение эквивалентности элементов.

  1        function Overlap (Left, Right : Set) return Boolean;
  2        function Is_Subset (Subset : Set; Of_Set : Set) return Boolean;

@ Они также самоочевидны.

  1        function First (Container : Set) return Cursor;
  2        function Last (Container : Set) return Cursor;
  3        function Next (Position : Cursor) return Cursor;
  4        procedure Next (Position : in out Cursor);
  5        function Find (Container : Set; Item : Element_Type) return Cursor;
  6        function Contains (Container : Set; Item : Element_Type) return Boolean;

@ Они должны быть самоочевидными и очень похожи на соответствующие операции карт. Снова в отличие от операций векторов и списков Find логически ищет целый набор, а не только начинающийся в некоторой точке (нет также никакого Reverse_Find). Кроме того, Find использует отношение эквивалентности основанное на параметре "<".

  1        function Has_Element (Position : Cursor) return Boolean;
  2        procedure Iterate
  3        (       Container : in Set;
  4                Process   : not null access procedure (Position : in Cursor));

@ Они такие же что и для других контейнеров.

@ Пакеты наборов включают внутренний настраиваемый пакет по имени Generic_Keys. Этот пакет позволяет некоторым операциям набора быть выполненными в терминах ключей, где ключ - функция элемента. Обратите внимание, что в случае карты, элемент определен в терминах ключа, тогда как здесь ситуация полностью изменена. Эквивалентные отношения определены для этих ключей также; они определены настраиваемым параметром "<" для упорядоченных наборов и Equivalent_Keys для хэш - наборов.

@ В случае упорядоченного набора формальные параметры следующие:

  1        generic
  2                type Key_Type (<>) is private;
  3                with function Key (Element : Element_Type) return Key_Type;
  4                with function "<" (Left, Right : Key_Type) return Boolean is <>;
  5        package Generic_Keys is

@ Следующее является общим для пакета Generic_Keys как для хэш так и для упорядоченных наборов.

  1        function Key (Position : Cursor) return Key_Type;
  2        function Element (Container : Set; Key : Key_Type) return Element_Type;
  3        procedure Replace
  4        (       Container : in out Set;
  5                Key       : in Key_Type;
  6                New_Item  : in Element_Type);
  7        procedure Exclude (Container : in out Set; Key : in Key_Type);
  8        procedure Delete (Container : in out Set; Key : in Key_Type);
  9        function Find (Container : Set; Key : Key_Type) return Cursor;
 10        function Contains (Container : Set; Key : Key_Type) return Boolean;
 11        procedure Update_Element_Preserving_Key
 12        (       Container : in out Set;
 13                Position  : in Cursor;
 14                Process   : not null access procedure (Element : in out Element_Type));

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

  1        end Generic_Keys;
  2        private
  3                ... -- not specified by the language
  4        end Ada.Containers.Ordered_Sets;

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

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

@ Хотя это конечно не для новичка, мы покажем пример того как это можно использовать наборы вместо карт. Мы объявляем:

  1        type Part_Type is
  2                record
  3                        Part_Number : Integer;
  4                        Year        : Integer;
  5                        Shelf       : Character range 'A' .. 'T';
  6                        Stock       : Integer;
  7                end record;

@ Здесь мы поместили всю информацию в один тип.

@ Мы тогда объявляем "<" как обычно:

  1        function "<" (Left, Right : Part_Type) return Boolean is
  2        begin
  3                return Left.Part_Number < Right.Part_Number;
  4        end "<";

@ и затем иллюстрируем пакет таким образом:

  1        package Store_Sets is new Ordered_Sets (Element_Type => Part_Type);
  2        The_Store : Store_Sets.Set;

@ Мы использовали механизм заданный по умолчанию для настраиваемого параметра "<" на сей раз посредством иллюстрации.

@ В этом случае мы добавляем элементы к памяти следующим образом:

  1        The_Store.Insert ((34618, 1998, 'F', 25));
  2        The_Store.Insert ((27134, 2004, 'C', 45));
  3        ...

@ Процедура для проверки стойки может теперь быть такой:

  1        procedure Request
  2        (       Part  : in Integer;
  3                Ok    : out Boolean;
  4                Year  : out Integer;
  5                Shelf : out Character)
  6        is
  7                C : Cursor;
  8                E : Part_Type;
  9        begin
 10                C := The_Store.Find ((Part, others => <>));
 11                if C = No_Element then
 12                        Ok := False; return; -- no such item
 13                end if;
 14                E := Element (C);
 15                Year := E.Year;
 16                Shelf := E.Shelf;
 17                if E.Stock = 0 then
 18                        Ok := False; return; -- out of stock
 19                end if;
 20                Replace_Element (C, (E.Part_Number, Year; Shelf, E.Stock–1));
 21                Ok := True;
 22        end Request;

@ Хотя это и работает, но не совсем удовлетворительно. С одной стороны, мы должны были вставить фиктивные компоненты в вызове Find (используя <>), кроме того, мы должны были заменить весь элемент, хотя мы только хотели обновить Stock компонент. Кроме того, мы не можем использовать Update_Element, потому что он не определен для наборов вообще. Напомним, что это могло бы нарушить порядок элементов; но в данном случае это не было бы проблемой, потому что мы не хотим менять числовой код запчасти.

@ Лучший подход должен использовать числовой код запчасти как ключ. Мы определяем:

  1        type Part_Key is new Integer;
  2        function Part_No (P : Part_Type) return Part_Key is
  3        begin
  4                return Part_Key (P.Part_Number);
  5        end Part_No;

@ и тогда:

  1        package Party is new Generic_Keys (Key_Type => Part_Key, Key => Part_No);
  2        use Party;

@ Отметим, что мы не должны определять функцию "<" для типа Part_Key вообще, потому что она уже существует, так как Part_Key - целочисленный тип. И реализация использует соответствующую функцию по умолчанию.

@ И теперь мы можем перезаписать процедуру Request следующим образом:

  1        procedure Request
  2        (       Part  : in Part_Key;
  3                Ok    : out Boolean;
  4                Year  : out Integer;
  5                Shelf : out Character)
  6        is
  7                C : Cursor;
  8                E : Part_Type;
  9        begin
 10                C := Find (The_Store, Part);
 11                if C = No_Element then
 12                        Ok := False; return; -- no such item
 13                end if;
 14                E := Element (C);
 15                Year := E.Year; Shelf := E.Shelf;
 16                if E.Stock = 0 then
 17                        Ok := False; return; -- out of stock
 18                end if;
 19                -- we are now going to update the stock level
 20                declare
 21                        procedure Do_It (E: in out Part_Type) is
 22                        begin
 23                                E.Stock := E.Stock – 1;
 24                        end Do_It;
 25                begin
 26                        Update_Element_Preserving_Key (The_Store, C, Do_It'Access);
 27                end;
 28                Ok := True;
 29        end Request;

@ Это кажется тяжелой работой, но имеет ряд преимуществ. Во-первых, вызов Find является более естественным и вовлекает только числовой код запчасти (ключ) - отметим, что это вызов функции Find в реализации Generic_Keys использует только числовой код запчасти. Во-вторых, это обновление вовлекает только изменяемый компонент. Мы упоминали ранее, что нет никакого Update_Element для наборов из-за опасности создания значения, которое было бы в неправильном месте. В случае длинно названного Update_Element_Preserving_Key также выполняется проверка для гарантии того что элемент находится действительно все еще в правильном месте (проверяется что ключ - всё ещё тот же самый); если это не так, то элемент удаляется и возбуждается исключение Program_Error.

@ Если пользователь пожелает воспользоваться пакетом Generic_Keys абсолютно жизненно важно, чтобы относительная операция и функция (Part_No), используемая для иллюстрации Generic_Keys, были совместимы с упорядочением, используемым для иллюстрации родительского пакета Containers.Ordered_Sets непосредственно. Если дело обстоит не так, тогда небо могло бы обрушиться.

@ Случайно, процедура для того, чтобы проверить стойку, которая ранее использовала пакет карт теперь становится:

  1        procedure Check_Stock (Low : in Integer) is
  2                procedure Check_It (C : in Cursor) is
  3                begin
  4                        if Element (C).Stock < Low then
  5                                -- print a message perhaps
  6                                Put ("Low stock of part ");
  7                                Put_Line (Element (C).Part_Number); -- changed
  8                        end if;
  9                end Check_It;
 10        begin
 11                The_Store.Iterate (Check_It'Access);
 12        end Check_Stock;

@ Здесь единственное изменение состоит в том, что вызов Key в:

  1        Put_Line (Key (C).Part_Number);

@ заменен на Element. Небольшое отличие состоит в том, что мы можем избежать вызова Element дважды, объявляя константу E в Check_It таким образом:

  1        E : constant Part_Type := Element (C);

@ и затем написав E.Stock < Low и вызывая Put_Line с E.Part_Number.

@ Более важный момент состоит в том, что если мы проиллюстрировали внутренний пакет Generic_Keys как было проиллюстрировано выше, тогда мы можем оставить Check_It неизменной, чтобы вызвать Key. Но важно понять, что тогда мы вызываем функцию Key внутренней к реализации Generic_Keys (flippantly вызываемый абонент) а не от реализации родительского пакета упорядоченных наборов (Store_Sets), потому что у этого нет такой функции. Это показывает тесную близость между пакетами наборов и пакетами карт.

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

@ Спецификация пакета хэш - наборов начинается:

  1        generic
  2                type Element_Type is private;
  3                with function Hash (Element : Element_Type) return Hash_Type;
  4                with function Equivalent_Elements (Left, Right : Element_Type) return Boolean;
  5                with function "=" (Left, Right : Element_Type) return Boolean is <>;
  6        package Ada.Containers.Hashed_Sets is
  7                pragma Preelaborate (Hashed_Sets);

@ Отличие от пакета упорядоченных наборов состоит в том, что появляется дополнительный настроечный параметр Hash, а параметр упорядочения "<" заменяется функцией Equivalent_Elements.

@ Так, если мы имеем:

  1        function Equivalent_Parts (Left, Right : Part_Type) return Boolean is
  2        begin
  3                return Left.Part_Number = Right.Part_Number;
  4        end Equivalent_Parts;
  5        function Part_Hash (P : Part_Type) return Hash_Type is
  6                M31 : constant := 2**31–1; -- a nice Mersenne prime
  7        begin
  8                return Hash_Type (P.Part_Number) * M31;
  9        end Part_Hash;

@ (которые очень похожи на пример хэш - карты, за исключением имени типа параметра), тогда мы можем иллюстрировать пакет хэш - наборов следующим образом:

  1        package Store_Sets is
  2                new Hashed_Sets
  3                (       Element_Type        => Part_Type,
  4                        Hash                => Part_Hash,
  5                        Equivalent_Elements => Equivalent_Parts);
  6        The_Store : Store_Sets.Set;

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

@ Нужно также упомянуть, что у внутреннего пакета Generic_Keys для хэш - наборов есть следующие формальные параметры:

  1        generic
  2                type Key_Type (<>) is private;
  3                with function Key (Element : Element_Type) return Key_Type
  4                with function Hash (Key : Key_Type) return Hash_Type;
  5                with function Equivalent_Keys (Left, Right : Key_Type) return Boolean;
  6        package Generic_Keys is

@ Отличие от упорядоченных наборов состоит в добавлении функции Hash и замене оператора сравнения "<" на функцию Equivalent_Keys. (Кстати, пакет Generic_Keys для упорядоченных наборов также экспортирует функцию Equivalent_Keys для однородности с пакетом хэш - наборов). Хотя сам наш пример неизменен, мы действительно должны изменить реализацию Generic_Keys таким образом:

  1        type Part_Key is new Integer;
  2        function Part_No (P : Part_Type) return Part_Key is
  3        begin
  4                return Part_Key (P.Part_Number);
  5        end Part_No;
  6        function Part_Hash (P : Part_Key) return Hash_Type is
  7                M31 : constant := 2**31–1; -- a nice Mersenne prime
  8        begin
  9                return Hash_Type (P) * M31;
 10        end Part_Hash;
 11        function Equivalent_Parts (Left : Right : Part_Key) return Boolean is
 12        begin
 13                return Left = Right;
 14        end Equivalent_Parts;

@ и тогда:

  1        package Party is
  2                new Generic_Key
  3                (       Key_Type => Part_Key,
  4                        Key      => Part_No;
  5                        Hash     => Part_Hash
  6                        Equivalent_Keys => Equivalent_Parts);
  7        use Party;

@ Хеш-функция подобна используемой с хэш - картами. Тип Part_Key и функция Part_No такая же что и у упорядоченных наборов. Мы действительно не должны объявлять функцию Equivalent_Parts, так как мы можем использовать "=" как фактический параметр для Equivalent_Keys.

@ Мы закончим обсуждение наборов кратко рассматривая дополнительные средства в двух пакетах наборов (и их внутренние настраиваемые пакеты ключей) так же как мы это делали для двух пакетов карт (обсуждение почти идентично).

@ У пакета упорядоченных наборов есть следующие дополнительные подпрограммы:

  1        procedure Delete_First (Container : in out Set);
  2        procedure Delete_Last (Container : in out Set);
  3        function First_Element (Container : Set) return Element_Type;
  4        function Last_Element (Container : Set) return Element_Type;
  5        function Previous (Position : Cursor) return Cursor;
  6        procedure Previous (Position : in out Cursor);
  7        function Floor (Container : Set; Item : Element_Type) return Cursor;
  8        function Ceiling (Container : Set; Item : Element_Type) return Cursor;
  9        function "<" (Left, Right : Cursor) return Boolean;
 10        function ">" (Left, Right : Cursor) return Boolean;
 11        function "<" (Left : Cursor; Right : Element_Type) return Boolean;
 12        function ">" (Left : Cursor; Right : Element_Type) return Boolean;
 13        function "<" (Left : Element_Type; Right : Cursor) return Boolean;
 14        function ">" (Left : Element_Type; Right : Cursor) return Boolean;
 15        procedure Reverse_Iterate (Container : in Set;
 16        Process : not null access procedure (Position : in Cursor));

@ Они снова в значительной степени самоочевидны. Функции Floor и Ceiling такие же что и для упорядоченных карт - Floor ищет последний элемент, который не больше чем Item, а Ceiling ищет первый элемент, который не меньше чем Item - все они возвращают No_Element, если такого элемента нет.

@ Функции "<" и ">" очень важны для упорядоченных наборов. Первая эквивалентна:

  1        function "<" (Left, Right : Cursor) return Boolean is
  2        begin
  3                return Element (Left) < Element (Right);
  4        end "<";

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

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

@ Следующее дополнение в пакете Generic_Keys для упорядоченных наборов:

  1        function Equivalent_Keys (Left, Right : Key_Type) return Boolean;

@ Это соответствует формальному настроечному параметру с токим же именем в пакете Generic_Keys для хэш - наборов упомянутых ранее.

  1        function Floor (Container : Set; Key : Key_Type) return Cursor;
  2        function Ceiling (Container : Set; Key : Key_Type) return Cursor;

@ Они эквивалентны аналогичным функциям родительского пакета за исключением того, что они используют формальный параметр "<" для Generic_Keys для поиска.

@ У хэш - наборов как и хэш - карт имеется средство для определения ёмкости как и у векторного пакета.

@ Таким образом мы имеем:

  1        procedure Reserve_Capacity (Container : in out Set; Capacity : in Count_Type);
  2        function Capacity (Container : Set) return Count_Type;

@ Поведение такое же как для векторов и хэш - карт. Мы не обязаны устанавливать ёмкость самостоятельно, так как она будет автоматически расширена по мере необходимости, но мы можем значительно улучшить производительность если мы установим ёмкость заранее. Обратите внимание, что Length (S) не может превысить Capacity (S).

@ Другие дополнительные подпрограммы для хэш - наборов:

  1        function Equivalent_Elements (Left, Right : Cursor) return Boolean;
  2        function Equivalent_Elements (Left : Cursor; Right : Element_Type) return Boolean;
  3        function Equivalent_Elements (Left : Element_Type; Right : Cursor) return Boolean;

@ Снова, они очень важны для наборов. Первая выполняет примерно следующее:

  1        function Equivalent_Elements (Left, Right : Cursor) return Boolean is
  2        begin
  3                return Equivalent_Elements (Element (Left), Element (Right));
  4        end Equivalent_Elements;

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

ENG RUS

TOP BACK NEXT

2010-10-24 00:26:58

. .