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.
Vectors¶
In the following sections, we present a general overview of vectors, including instantiation, initialization, and operations on vector elements and vectors.
Instantiation¶
Here's an example showing the instantiation and declaration of a
vector V:
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 Index_Type to Natural, we specify
that the allowed range includes all natural numbers. We could have used a
more restrictive range if desired.
Initialization¶
One way to initialize a vector is from a concatenation of elements.
We use the & operator, as shown in the following example:
We specify 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: Length, which
retrieves the number of elements in the vector. We can use the dot
notation because Vector is a tagged type, allowing us to write
either V.Length or Length (V).
Appending and prepending elements¶
You add elements to a vector using the Prepend and Append
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
Appendoperation, andO(\(N log N\)) for the
Prependoperation.
Accessing first and last elements¶
We access the first and last elements of a vector using the
First_Element and 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
calling First and 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:
Iterating¶
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 E directly.
For example:
This code displays each element from the vector V.
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 V:
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.First_Index and
V.Last_Index. We can access the current element by using it as an
array index: 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
form V (I) or the longer form V.Element (I) but not V.I.
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
format 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
array index: 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
subsequent elements. 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_Index or 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).
Inserting elements¶
In the previous sections, we've seen examples of how to add elements to a vector:
using the concatenation operator (
&) at the vector declaration, orcalling the
PrependandAppendprocedures.
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 Insert. For
example:
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.
Removing elements¶
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_Index and 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.
Other Operations¶
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 V1 and 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
values (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.
After instantiating Generic_Sorting, we make all the operations
available to us with the use statement. We can then call Sort to
sort the vector and Merge to merge one vector into another.
The following example presents code that manipulates three vectors (V1,
V2, V3) using the concatenation, sorting and merging operations:
The Reference Manual requires that the worst-case complexity of a call to
Sort be O(\(N^2\)) and the average complexity be better than
O(\(N^2\)).
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
Insertthat returns a Boolean value indicating whether the insertion was successful;the
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:
DeleteandExcludeto remove elements;ContainsandFindto 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:
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 |
|
|
|---|---|---|
|
O(\((log N)^2)\) 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 |
|
Intersection |
|
Difference |
|
Symmetric difference |
|
The following example makes use of these operators:
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 keyElement_Type: type of the elementHash: hash function for theKey_TypeEquivalent_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 ofEquivalent_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:
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_Typehas a standard<operator, you can use it in a similar way as we did forEquivalent_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.
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 |
|
|
|---|---|---|
|
O(\((log N)^2)\) or better |
\(O(log N)\) |
Subprogram using cursor |
O(\(1\)) |
O(\(1\)) |