2.8. Sets (class set)

2.8. Sets (class set)
	Chapter 2. Simple data types and simple container types

2.8. Sets (class `set`)

Arrays, lists, even stacks and queues store “sets” of elements. However, these “sets” are not sets in the strictly mathematical sense because every element may be contained only once in a set, as it is well known.^[29] Rather, arrays and lists store multisets, that is, an element may definitely occur multiply in these collections.

Moreover, arrays and lists support the most important set operations only badly. Whereas inserting a new element is quite simple, a method must be invoked for searching an element, which internally searches a linear structure. Section, union, and difference of (multi-)sets stored in arrays or lists, however, can usually be implemented only with relatively big time costs.

Whereas the elements are stored in a linear sequence in arrays and lists, our idea of a set is a collection of “freely floating” elements without any inner structure. Figure 2.24 shows a set with 7 elements.

Figure 2.24. A set

So what we need is a data type set which realizes the mathematical concept of a set:

Every element must occur only once.
Elements can easily be inserted and deleted.
It can be easily tested whether an element occurs in a set, and an arbitrary element of the set can be easily chosen.
The set operations section, union, and symmetric difference can be easily performed.

For collections of elements which satisfy these demands LEDA offers the class set.

^[29]We will not delve into the discussion here what exactly a set is, and we will not deal with the paradoxa and antinomies appearing in an attempt of an exact definition. All this can be referred to for example in [8].


2.7.2. Queues with a bounded number of elements (class b_queue)		2.8.1. Inserting elements and membership test