| Online Eiffel Documentation

EiffelStudio

# EiffelBase, Sets

Sets are containers where successive occurrences of the same item are not distinguished: inserting the same item twice has the same observable effect as inserting it once.

## Deferred classes

The most general class describing sets is SET. The usual operations of set theory such as union and intersection have been relegated to SUBSET, an heir of SET. This enables a class to inherit from SET without having to effect these operations if it satisfies the basic set property but has no convenient implementation of the subset operations.

## Sets without a notion of order

LINKED_SET provides a basic implementation of SET by linked lists.

## Sets of comparable elements and sorted sets

The deferred class COMPARABLE_SET, declared as

    	deferred class
    		COMPARABLE_SET[G -> COMPARABLE]

    	inherit
    		SUBSET [G]
    		COMPARABLE_STRUCT [G]
    	...

describes sets whose items may be compared by a total order relation. The class has the features min and max.
Two implementations of COMPARABLE_SET are provided. One, TWO_WAY_SORTED_SET, uses sorted two-way lists. The other, BINARY_SEARCH_TREE_SET, uses binary search trees.
If the items are partially rather than totally ordered, you may use the class PART_SORTED_SET [G -> PART_COMPARABLE], which uses a two-way sorted list implementation.