## 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, searching an element requires a method call that 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.

So what we need is a data type set that 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 that 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].