Standard library: Containers

In previous chapters, we've used arrays as the standard way to group multiple objects of a specific data type. In many cases, arrays are good enough for manipulating those objects. However, there are situations that require more flexibility and more advanced operations. For those cases, Ada provides support for containers — such as vectors and sets — in its standard library.

We present an introduction to containers here. For a list of all containers available in Ada, see Appendix B.

Sets

Sets are another class of containers. While vectors allow duplicated elements to be inserted, sets ensure that no duplicated elements exist.

In the following sections, we'll see operations you can perform on sets. However, since many of the operations on vectors are similar to the ones used for sets, we'll cover them more quickly here. Please refer back to the section on vectors for a more detailed discussion.

Initialization and iteration

To initialize a set, you can call the Insert procedure. However, if you do, you need to ensure no duplicate elements are being inserted: if you try to insert a duplicate, you'll get an exception. If you have less control over the elements to be inserted so that there may be duplicates, you can use another option instead:

a version of Insert that returns a Boolean value indicating whether the insertion was successful;
the Include procedure, which silently ignores any attempt to insert a duplicated element.

To iterate over a set, you can use a for E of S loop, as you saw for vectors. This gives you a reference to each element in the set.

Let's see an example:

    
    
    
        with Ada.Containers; use Ada.Containers;
with Ada.Containers.Ordered_Sets;

with Ada.Text_IO; use Ada.Text_IO;

procedure Show_Set_Init is

   package Integer_Sets is new
     Ada.Containers.Ordered_Sets
       (Element_Type => Integer);

   use Integer_Sets;

   S : Set;
   --  Same as:  S : Integer_Sets.Set;
   C : Cursor;
   Ins : Boolean;
begin
   S.Insert (20);
   S.Insert (10);
   S.Insert (0);
   S.Insert (13);

   --  Calling S.Insert(0) now would raise
   --  Constraint_Error because this element
   --  is already in the set. We instead call a
   --  version of Insert that doesn't raise an
   --  exception but instead returns a Boolean
   --  indicating the status

   S.Insert (0, C, Ins);
   if not Ins then
      Put_Line ("Inserting 0 into set was not successful");
   end if;

   --  We can also call S.Include instead
   --  If the element is already present,
   --  the set remains unchanged
   S.Include (0);
   S.Include (13);
   S.Include (14);

   Put_Line ("Set has "
             & Count_Type'Image (S.Length)
             & " elements");

   --
   --  Iterate over set using for .. of loop
   --
   Put_Line ("Elements:");
   for E of S loop
       Put_Line ("- " & Integer'Image (E));
   end loop;
end Show_Set_Init;
    
    
        
            
        
    
    
    
        
            
            
                
                    
                    Enable tabbed editor view for this editor
                
                
                    
                    Use the dark theme

Operations on elements

In this section, we briefly explore the following operations on sets:

Delete and Exclude to remove elements;
Contains and Find to verify the existence of elements.

To delete elements, you call the procedure Delete. However, analogously to the Insert procedure above, Delete raises an exception if the element to be deleted isn't present in the set. If you want to permit the case where an element might not exist, you can call Exclude, which silently ignores any attempt to delete a non-existent element.

Contains returns a Boolean value indicating whether a value is contained in the set. Find also looks for an element in a set, but returns a cursor to the element or No_Element if the element doesn't exist. You can use either function to search for elements in a set.

Let's look at an example that makes use of these operations:

    
    
    
        with Ada.Containers; use Ada.Containers;
with Ada.Containers.Ordered_Sets;

with Ada.Text_IO; use Ada.Text_IO;

procedure Show_Set_Element_Ops is

   package Integer_Sets is new
     Ada.Containers.Ordered_Sets
       (Element_Type => Integer);

   use Integer_Sets;

   procedure Show_Elements (S : Set) is
   begin
      New_Line;
      Put_Line ("Set has "
                & Count_Type'Image (S.Length)
                & " elements");
      Put_Line ("Elements:");
      for E of S loop
         Put_Line ("- " & Integer'Image (E));
      end loop;
   end Show_Elements;

   S : Set;
begin
   S.Insert (20);
   S.Insert (10);
   S.Insert (0);
   S.Insert (13);

   S.Delete (13);

   --  Calling S.Delete (13) again raises
   --  Constraint_Error because the element
   --  is no longer present in the set, so
   --  it can't be deleted. We can call
   --  V.Exclude instead:
   S.Exclude (13);

   if S.Contains (20) then
      Put_Line ("Found element 20 in set");
   end if;

   --  Alternatively, we could use S.Find
   --  instead of S.Contains
   if S.Find (0) /= No_Element then
      Put_Line ("Found element 0 in set");
   end if;

   Show_Elements (S);
end Show_Set_Element_Ops;
    
    
        
            
        
    
    
    
        
            
            
                
                    
                    Enable tabbed editor view for this editor
                
                
                    
                    Use the dark theme

In addition to ordered sets used in the examples above, the standard library also offers hashed sets. The Reference Manual requires the following average complexity of each operation:

Operations	`Ordered_Sets`	`Hashed_Sets`
Insert Include Replace Delete Exclude Find	O((log N)²) or better	O(log N)
Subprogram using cursor	O(1)	O(1)

Other Operations

The previous sections mostly dealt with operations on individual elements of a set. But Ada also provides typical set operations: union, intersection, difference and symmetric difference. In contrast to some vector operations we've seen before (e.g. Merge), here you can use built-in operators, such as -. The following table lists the operations and its associated operator:

Set Operation	Operator
Union	`or`
Intersection	`and`
Difference	`-`
Symmetric difference	`xor`

The following example makes use of these operators:

    
    
    
        with Ada.Containers; use Ada.Containers;
with Ada.Containers.Ordered_Sets;

with Ada.Text_IO; use Ada.Text_IO;

procedure Show_Set_Ops is

   package Integer_Sets is new
     Ada.Containers.Ordered_Sets
       (Element_Type => Integer);

   use Integer_Sets;

   procedure Show_Elements (S : Set) is
   begin
      Put_Line ("Elements:");
      for E of S loop
         Put_Line ("- " & Integer'Image (E));
      end loop;
   end Show_Elements;

   procedure Show_Op (S       : Set;
                      Op_Name : String) is
   begin
      New_Line;
      Put_Line (Op_Name
                & "(set #1, set #2) has "
                & Count_Type'Image (S.Length)
                & " elements");
   end Show_Op;

   S1, S2, S3 : Set;
begin
   S1.Insert (0);
   S1.Insert (10);
   S1.Insert (13);

   S2.Insert (0);
   S2.Insert (10);
   S2.Insert (14);

   S3.Insert (0);
   S3.Insert (10);

   New_Line;
   Put_Line ("---- Set #1 ----");
   Show_Elements (S1);

   New_Line;
   Put_Line ("---- Set #2 ----");
   Show_Elements (S2);

   New_Line;
   Put_Line ("---- Set #3 ----");
   Show_Elements (S3);

   New_Line;
   if S3.Is_Subset (S1) then
      Put_Line ("S3 is a subset of S1");
   else
      Put_Line ("S3 is not a subset of S1");
   end if;

   S3 := S1 and S2;
   Show_Op (S3, "Intersection");
   Show_Elements (S3);

   S3 := S1 or S2;
   Show_Op (S3, "Union");
   Show_Elements (S3);

   S3 := S1 - S2;
   Show_Op (S3, "Difference");
   Show_Elements (S3);

   S3 := S1 xor S2;
   Show_Op (S3, "Symmetric difference");
   Show_Elements (S3);

end Show_Set_Ops;
    
    
        
            
        
    
    
    
        
            
            
                
                    
                    Enable tabbed editor view for this editor
                
                
                    
                    Use the dark theme

Indefinite maps

The previous sections presented containers for elements of definite types. Although most examples in those sections presented Integer types as element type of the containers, containers can also be used with indefinite types, an example of which is the String type. However, indefinite types require a different kind of containers designed specially for them.

We'll also be exploring a different class of containers: maps. They associate a key with a specific value. An example of a map is the one-to-one association between a person and their age. If we consider a person's name to be the key, the value is the person's age.

Hashed maps

Hashed maps are maps that make use of a hash as a key. The hash itself is calculated by a function you provide.

In other languages

Hashed maps are similar to dictionaries in Python and hashes in Perl. One of the main differences is that these scripting languages allow using different types for the values contained in a single map, while in Ada, both the type of key and value are specified in the package instantiation and remains constant for that specific map. You can't have a map where two elements are of different types or two keys are of different types. If you want to use multiple types, you must create a different map for each and use only one type in each map.

When instantiating a hashed map from Ada.Containers.Indefinite_Hashed_Maps, we specify following elements:

Key_Type: type of the key
Element_Type: type of the element
Hash: hash function for the Key_Type
Equivalent_Keys: an equality operator (e.g. =) that indicates whether two keys are to be considered equal.
- If the type specified in Key_Type has a standard operator, you can use it, which you do by specifying that operator as the value of Equivalent_Keys.

In the next example, we'll use a string as a key type. We'll use the Hash function provided by the standard library for strings (in the Ada.Strings package) and the standard equality operator.

You add elements to a hashed map by calling Insert. If an element is already contained in a map M, you can access it directly by using its key. For example, you can change the value of an element by calling M ("My_Key") := 10. If the key is not found, an exception is raised. To verify if a key is available, use the function Contains (as we've seen above in the section on sets).

Let's see an example:

    
    
    
        with Ada.Containers.Indefinite_Hashed_Maps;
with Ada.Strings.Hash;

with Ada.Text_IO; use Ada.Text_IO;

procedure Show_Hashed_Map is

   package Integer_Hashed_Maps is new
     Ada.Containers.Indefinite_Hashed_Maps
       (Key_Type        => String,
        Element_Type    => Integer,
        Hash            => Ada.Strings.Hash,
        Equivalent_Keys => "=");

   use Integer_Hashed_Maps;

   M : Map;
   --  Same as:
   --
   --  M : Integer_Hashed_Maps.Map;
begin
   M.Include ("Alice", 24);
   M.Include ("John",  40);
   M.Include ("Bob",   28);

   if M.Contains ("Alice") then
      Put_Line ("Alice's age is "
                & Integer'Image (M ("Alice")));
   end if;

   --  Update Alice's age
   --  Key must already exist in M.
   --  Otherwise an exception is raised.
   M ("Alice") := 25;

   New_Line; Put_Line ("Name & Age:");
   for C in M.Iterate loop
      Put_Line (Key (C) & ": "
                & Integer'Image (M (C)));
   end loop;

end Show_Hashed_Map;
    
    
        
            
        
    
    
    
        
            
            
                
                    
                    Enable tabbed editor view for this editor
                
                
                    
                    Use the dark theme

Ordered maps

Ordered maps share many features with hashed maps. The main differences are:

A hash function isn't needed. Instead, you must provide an ordering function (< operator), which the ordered map will use to order elements and allow fast access, O(log N), using a binary search.
- If the type specified in Key_Type has a standard < operator, you can use it in a similar way as we did for Equivalent_Keys above for hashed maps.

Let's see an example:

    
    
    
        with Ada.Containers.Indefinite_Ordered_Maps;

with Ada.Text_IO; use Ada.Text_IO;

procedure Show_Ordered_Map is

   package Integer_Ordered_Maps is new
     Ada.Containers.Indefinite_Ordered_Maps
       (Key_Type        => String,
        Element_Type    => Integer);

   use Integer_Ordered_Maps;

   M : Map;
begin
   M.Include ("Alice", 24);
   M.Include ("John",  40);
   M.Include ("Bob",   28);

   if M.Contains ("Alice") then
      Put_Line ("Alice's age is "
                & Integer'Image (M ("Alice")));
   end if;

   --  Update Alice's age
   --  Key must already exist in M
   M ("Alice") := 25;

   New_Line; Put_Line ("Name & Age:");
   for C in M.Iterate loop
      Put_Line (Key (C) & ": "
                & Integer'Image (M (C)));
   end loop;

end Show_Ordered_Map;
    
    
        
            
        
    
    
    
        
            
            
                
                    
                    Enable tabbed editor view for this editor
                
                
                    
                    Use the dark theme

You can see a great similarity between the examples above and from the previous section. In fact, since both kinds of maps share many operations, we didn't need to make extensive modifications when we changed our example to use ordered maps instead of hashed maps. The main difference is seen when we run the examples: the output of a hashed map is usually unordered, but the output of a ordered map is always ordered, as implied by its name.

Complexity

Hashed maps are generally the fastest data structure available to you in Ada if you need to associate heterogeneous keys to values and search for them quickly. In most cases, they are slightly faster than ordered maps. So if you don't need ordering, use hashed maps.

The Reference Manual requires the following average complexity of operations:

Operations	`Ordered_Maps`	`Hashed_Maps`
Insert Include Replace Delete Exclude Find	O((log N)²) or better	O(log N)
Subprogram using cursor	O(1)	O(1)

Standard library: Containers

Vectors

Instantiation

Initialization

Appending and prepending elements

Accessing first and last elements

Iterating

Finding and changing elements

Inserting elements

Removing elements

Other Operations

Sets

Initialization and iteration

Operations on elements

Other Operations

Indefinite maps

Hashed maps

Ordered maps

Complexity