It is perhaps worth starting this discussion by summarizing the containers introduced in Ada 2005. First, there is a parent package Ada.Containers which simply declares the types Hash_Type and Count_Type.

Then there are six containers for definite objects, namely (abbreviating the prefix Ada.Containers to just A.C)

The declarations of these six containers all start with

and we see that the type Element_Type has to be definite. There are also containers for the manipulation of indefinite types whose names are

and these are very similar to the definite containers except that the formal type Element_Type is now declared as

so that the actual type can be indefinite such as String.

Finally, there are two generic packages for sorting arrays namely

which apply to unconstrained and constrained arrays respectively.

The first change in Ada 2012 is that the parent package Ada.Containers now includes the declaration of the exception Capacity_Error so that it becomes

The names of the new containers with bounded storage capacity are

The facilities of the bounded containers are almost identical to those of the original unbounded ones so that converting a program using one form to the other is relatively straightforward. The key point of the bounded ones is that storage management is guaranteed (implementation advice really) not to use features such as pointers or dynamic allocation and therefore can be used in high-integrity or safety-critical applications.

The major differences between the packages naturally concern their capacity. In the case of the bounded packages the types such as Vector have discriminants thus

whereas in the original packages the type Vector is simply

The other types in the bounded packages are

Note that the types for hashed maps and sets have an extra discriminant to set the modulus; this will be explained in a moment.

Remember that the types Count_Type and Hash_Type are declared in the parent package Ada.Containers shown above.

When a bounded container is declared, its capacity is set once and for all by the discriminant and cannot be changed. If we subsequently add more elements to the container than it can hold then the exception Capacity_Error is raised.

If we are using a bounded container and want to make it larger then we cannot. But what we can do is create another bounded container with a larger capacity and copy the values from the old container to the new one. Remember that we can check the number of items in a container by calling the function Length.

So we might have a sequence such as

The specification of the function Copy is

If the parameter Capacity is not specified (or is given as zero) then the capacity of the copied list is the same as the length of Source.

If the given value of Capacity is larger than (or equal to) the length of the Source (as in our example) then the returned list has this capacity and the various elements are copied. If we foolishly supply a value which is less than the length of Source then Capacity_Error is naturally raised. Remember that a discriminant can be set by an initial value.

Note that if we write

then My_Copied_List will have the same capacity as My_List because discriminants are copied as well as the contents.

In order to make it easier to move from the bounded form to the unbounded form, a function Copy is added to the unbounded containers as well although it does not need a parameter Capacity in the case of lists and ordered maps and sets. So in the case of the list container it is simply

Similar unification between bounded and unbounded forms occurs with assignment. In Ada 2005, if we have two lists L and M, then we can simply write

and the whole structure is copied (including all its management stuff). Note that this will almost certainly require that the value of L be finalized which might be a nuisance. Such an assignment with discriminated types needs to check the discriminants as well (and raises Constraint_Error if they are different). This is a nuisance because although the capacities might not be the same, the destination L might have plenty of room for the actual elements in the source M.

This is all rather bothersome and so procedures Assign are added to both unbounded and bounded containers which simply copy the element values. Thus in both case we have

In the bounded case, if the length of Source is greater than the capacity of Target, then Capacity_Error is raised. In the unbounded case, the structure is automatically extended.

It might be recalled that in Ada 2005, lists and ordered maps and sets do not explicitly have a notion of capacity. It is in their very nature that they automatically extend as required. However, in the case of vectors and hashed maps and sets (which have a notion of indexing) taking a purely automatic approach could lead to lots of extensions and copying so the notion of capacity was introduced. The capacity can be set by calling

and the current value of the capacity can be ascertained by calling

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

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

The above refers to the existing unbounded forms and is unchanged in Ada 2012. For uniformity the new bounded forms for vectors and hashed maps and sets also declare a procedure Reserve_Capacity. However, since the capacity cannot be changed for the bounded forms it simply checks that the value of the parameter Capacity does not exceed the actual capacity of the container; if it does then Capacity_Error is raised and otherwise it does nothing. There is of course also a function Capacity for bounded vectors and hashed maps and sets which simply returns the fixed value of the capacity.

Many operations add elements to a container. For unbounded containers, they are automatically extended as necessary as just explained. For the bounded containers, if an operation would cause the capacity to be exceeded then Capacity_Error is raised.

There are a number of other differences between the unbounded and bounded containers. The original unbounded containers have pragma Preelaborate whereas the new bounded containers have pragma Pure.

The bounded containers for hashed maps and hashed sets are treated somewhat differently to those for the corresponding unbounded containers regarding hashing.

In the case of unbounded containers, the hashing function to be used is left to the user and is provided as an actual generic parameter. For example, in the case of hashed sets, the package specification begins

What the implementation actually does with the hash function is entirely up to the implementation The value returned is in the range of Hash_Type which is a modular type declared in the root package Ada.Containers. The implementation will typically then map this value onto the current range of the capacity in some way. If the unbounded container becomes nearly full then the capacity will be automatically extended and a new mapping will be required; this in turn is likely to require the existing contents to be rehashed. None of this is visible to the user.

In the case of the new bounded containers, these problems do not arise since the capacity is fixed. Moreover, the modulus to be used for the mapping is given when the container is declared since the type has discriminants thus

The user can then choose the modulus explicitly or alternatively can use the additional function Default_Modulus whose specification is

This returns an implementation defined value for the number of distinct hash values to be used for the given capacity. Thus we can write

Moreover, for these bounded hashed maps and sets, the function Copy has an extra parameter thus

If the capacity is given as zero then the newly returned set has the same capacity as the length of Source as mentioned above. If the modulus is given as zero then the value to be used is obtained by applying Default_Modulus to the new capacity.

As mentioned in Section 7.5 on hashing and comparison, Ada 2012 introduces additional functions for hashing strings (fixed, bounded and unbounded) to provide for case insensitive, wide and wide wide situations.

Finally, note that there are no bounded containers for indefinite types. This is because the size of an object of an indefinite type (such as String) is generally not known and so indefinite types need some dynamic storage management. However, the whole point of introducing bounded containers was to avoid such management.

© 2011, 2012, 2013 John Barnes Informatics.

Sponsored in part by: