One of the most common questions about the simple container types of LEDA is simply “When do I use which of these types, then”? or “I must remember objects of a type T and access them later or look up whether I have seen a certain object before. Do I take a list now, or a set, or what?” This section tries to summarize in Table 2.1 what we have said about these types until now and to give rules of thumb for their use; therein, n stands for the number of elements stored in the structure at a particular point in time.

The most important deciding factor is for sure the type of the elements that shall be used. Only integral values that, moreover, should be from a not too large interval can be stored in a d_int_set. The key type must be linearly ordered for a set.

Usually, a linear order can be defined easily so that - if the structure does not have to support any special functionality - one is most often faced with the choice between array, list, and set. The access time then plays a large role here. As a rule of thumb one can say: If access is mainly read-only and the position of the access is known, an array should be preferred. If, in contrast, elements are often added or deleted, a list or a set are usually a better choice, a set primarily if the position of the insertion or deletion is unknown. No elements can occur multiply in a set, though.

Another important criterion is the functionality of the container type. stack and queue are out of the question if the accesses to the elements are carried out at some other position than the two ends of the structure or if all elements of the structure have to be iterated over. Furthermore the questions play a role whether the structure is to be split up into several partial structures and whether partial structures are to be united to a whole; in these cases, stack and queue are ruled out, and array does not support this directly either.

The class slist is even more space efficient than the class list; however, it shows a considerably smaller functionality.

As well, b_stack and b_queue are more space efficient than stack or queue, respectively; however, they must know the number of elements to be stored in advance.

The insertion time of int_set is, amortizedly speaking, a little shorter than the one of d_int_set; in return, the interval from which the integral elements originate must be known in advance and the functionality is limited in comparison to int_set.

Tip

LEDA does not have a special class for the realization of a bag, that is of a simple container type in which elements may multiply occur and where access to an element, insertion, and deletion of an element are possible in short time, that is in O(log(n)) in the worst case. In this situation, the associative container types, which we will get to know in Chapter 3, Associative container types, may come in handy. One possibility for storing duplicates in such a structure is the following one: The elements to be stored are used as the key of the key-value pairs and the associated value counts how often a certain element is stored.