Sets

External interface

• Create (set S)

• Insert (elementtype item, set S)

• Delete (elementtype item, set S)

• boolean Member (elementtype item, set S)

• set Union (set S1, set S2)

• set Intersection (set S1, set s2)

• set Difference (set S1, set S2)

Implementations

• Bit vector
  • Requires that elements be mapped to range 1..Max.
  • Member, Insert, and Delete are O(1).
  • Union, Intersection, and Difference are O(Max).
  • Space overhead is O(Max) not O(|S|)

• Sorted linked list
  • Can handle arbitrary element types
  • Member, Insert, and Delete are O(|S|)
  • Union, Intersection, and Difference are O(|S1|+|S2|)
  • Space overhead is O(|S|)

• Open hash table (supporting dictionary operations Member, Insert, Delete)
  • Member, Insert, and Delete are O(1) on average
  • Requires a good hash function