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.
In the following sections, we present a general overview of vectors, including instantiation, initialization, and operations on vector elements and vectors.
Here's an example showing the instantiation and declaration of a
Containers are based on generic packages, so we can't simply declare a vector as we would declare an array of a specific type:
A : array (1 .. 10) of Integer;
Instead, we first need to instantiate one of those packages. We
with the container package (
Ada.Containers.Vectors in this
case) and instantiate it to create an instance of the generic package for
the desired type. Only then can we declare the vector using the type from
the instantiated package. This instantiation needs to be done for any
container type from the standard library.
In the instantiation of
Integer_Vectors, we indicate that the vector
contains elements of
Integer type by specifying it as the
Element_Type. By setting
Natural, we specify
that the allowed range includes all natural numbers. We could have used a
more restrictive range if desired.
One way to initialize a vector is from a concatenation of elements.
We use the
& operator, as shown in the following example:
use Integer_Vectors, so we have direct access to the
types and operations from the instantiated package. Also, the example
introduces another operation on the vector:
retrieves the number of elements in the vector. We can use the dot
Vector is a tagged type, allowing us to write
Appending and prepending elements
You add elements to a vector using the
operations. As the names suggest, these operations add elements to the
beginning or end of a vector, respectively. For example:
This example puts elements into the vector in the following sequence: (100, 40, 30, 20, 10, 0, 13).
The Reference Manual specifies that the worst-case complexity must be:
O(log N) for the
O(N log N) for the
Accessing first and last elements
We access the first and last elements of a vector using the
Last_Element functions. For example:
You can swap elements by calling the procedure
Swap and retrieving a
reference (a cursor) to the first and last elements of the vector by
Last. A cursor allows us to iterate over a
container and process individual elements from it.
With these operations, we're able to write code to swap the first and last elements of a vector:
The easiest way to iterate over a container is to use a
for E of Our_Container loop. This gives us a reference (
E) to the
element at the current position. We can then use
This code displays each element from the vector
Because we're given a reference, we can display not only the value of an
element but also modify it. For example, we could easily write a loop to
add one to each element of vector
for E of V loop E := E + 1; end loop;
We can also use indices to access vector elements. The format is
similar to a loop over array elements: we use a
for I in <range> loop. The range is provided by
V.Last_Index. We can access the current element by using it as an
V (I). For example:
Here, in addition to displaying the vector elements, we're also
displaying each index,
I, just like what we can do for array
indices. Also, we can access the element by using either the short
V (I) or the longer form
V.Element (I) but not
As mentioned in the previous section, you can use cursors to iterate over
containers. For this, use the function
Iterate, which retrieves a
cursor for each position in the vector. The corresponding loop has the
for C in V.Iterate loop. Like the previous example using
indices, you can again access the current element by using the cursor as an
V (C). For example:
Instead of accessing an element in the loop using
V (C), we could
also have used the longer form
Element (C). In this example, we're
using the function
To_Index to retrieve the index corresponding to
the current cursor.
As shown in the comments after the loop, we could also use a
while ... loop to iterate over the vector. In this case, we
would start with a cursor for the first element (retrieved by calling
V.First) and then call
Next (C) to retrieve a cursor for
Next (C) returns
No_Element when the
cursor reaches the end of the vector.
You can directly modify the elements using a reference. This is what it looks like when using both indices and cursors:
-- Modify vector elements using index for I in V.First_Index .. V.Last_Index loop V (I) := V (I) + 1; end loop; -- Modify vector elements using cursor for C in V.Iterate loop V (C) := V (C) + 1; end loop;
The Reference Manual requires that the worst-case complexity for accessing an element be O(log N).
Another way of modifing elements of a vector is using a process
procedure, which takes an individual element and does some processing on
it. You can call
Update_Element and pass both a cursor and an access
to the process procedure. For example:
Finding and changing elements
You can locate a specific element in a vector by retrieving its index.
Find_Index retrieves the index of the first element matching the value
you're looking for. Alternatively, you can use
Find to retrieve a
cursor referencing that element. For example:
As we saw in the previous section, we can directly access vector elements
by using either an index or cursor. However, an exception is raised if we
try to access an element with an invalid index or cursor, so we must check
whether the index or cursor is valid before using it to access an element.
In our example,
Find might not have found the element
in the vector. We check for this possibility by comparing the index to
No_Index or the cursor to
No_Element. For example:
-- Modify vector element using index if Idx /= No_Index then V (Idx) := 11; end if; -- Modify vector element using cursor if C /= No_Element then V (C) := 14; end if;
Instead of writing
V (C) := 14, we could use the longer form
V.Replace_Element (C, 14).
In the previous sections, we've seen examples of how to add elements to a vector:
using the concatenation operator (
&) at the vector declaration, or
You may want to insert an element at a specific position, e.g. before a
certain element in the vector. You do this by calling
In this example, we're looking for an element with the value of 10. If we find it, we insert an element with the value of 9 before it.
You can remove elements from a vector by passing either a valid index or
cursor to the
Delete procedure. If we combine this with the functions
Find from the previous section, we can write a
program that searches for a specific element and deletes it, if found:
We can extend this approach to delete all elements matching a certain value. We just need to keep searching for the element in a loop until we get an invalid index or cursor. For example:
In this example, we remove all elements with the value 10 from the vector by retrieving their index. Likewise, we remove all elements with the value 13 by retrieving their cursor.
We've seen some operations on vector elements. Here, we'll see operations on the vector as a whole. The most prominent is the concatenation of multiple vectors, but we'll also see operations on vectors, such as sorting and sorted merging operations, that view the vector as a sequence of elements and operate on the vector considering the element's relations to each other.
We do vector concatenation using the
& operator on vectors. Let's
consider two vectors
V2. We can concatenate them by doing
V := V1 & V2.
V contains the resulting vector.
The generic package
Generic_Sorting is a child package of
Ada.Containers.Vectors. It contains sorting and merging operations.
Because it's a generic package, you can't use it directly, but have to
instantiate it. In order to use these operations on a vector of integer
Integer_Vectors, in our example), you need to instantiate it
directly as a child of
Integer_Vectors. The next example makes it clear
how to do this.
Generic_Sorting, we make all the operations
available to us with the
use statement. We can then call
sort the vector and
Merge to merge one vector into another.
The following example presents code that manipulates three vectors (
V3) using the concatenation, sorting and merging operations:
The Reference Manual requires that the worst-case complexity of a call to
Sort be O(N2) and the average complexity be better than
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
Insertthat returns a Boolean value indicating whether the insertion was successful;
Includeprocedure, 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:
Operations on elements
In this section, we briefly explore the following operations on sets:
Excludeto remove elements;
Findto verify the existence of elements.
To delete elements, you call the procedure
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
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:
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:
O((log N)2) or better
Subprogram using cursor
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:
The following example makes use of these operators:
The previous sections presented containers for elements of definite
types. Although most examples in those sections presented
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
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 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
Equivalent_Keys: an equality operator (e.g.
=) that indicates whether two keys are to be considered equal.
If the type specified in
Key_Typehas a standard operator, you can use it, which you do by specifying that operator as the value of
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
("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:
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_Typehas a standard
<operator, you can use it in a similar way as we did for
Equivalent_Keysabove for hashed maps.
Let's see an example:
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.
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:
O((log N)2) or better
Subprogram using cursor