Sets

Example

The following program shows how to use sets. It generates a set S of ints and inserts 100 ints into S. Then it searches for entry 37 in S.

#include <LEDA/core/set.h>

int main()
{
  leda::set<int> S;
  
  int i;
  for (i=1; i<=100; i++) S.insert(i);
  
  if (S.member(37)) std::cout << "37 is stored in S\n";
  else std::cout << "37 is not an element of S\n";

  return 0;	
}

Strengths

• space is proportional to current number of objects in the set
• no object appears more than once in the set
• searching for an element is fast (logarithmic in the size of the set)
• intuitive set operations are implemented efficiently
• iterating over all elements is fast (linear in the size of the set)

Disadvantages

• inserting and deleting an object is slow (logarithmic). Alternatives: Linear Lists, One Dimensional Array
• no order on objects. Alternatives: Linear Lists, One Dimensional Array
• access to any element of the set takes logarithmic time

Tips

• Use set if the number of search operations in your program is significantly larger than the number of insert and delete operations.
• Use set if you want to eliminate multiple copies of an object.
• If you want to store ints, consider using an Integer Set or a Dynamic Integer Set
• If you need an order on your objects or you need to access specified elements frequently, consider using a Linear List or an One Dimensional Array.

See also:

Integer Sets

Dynamic Integer Sets

Sets of Nodes

Sets of Edges

Linear Lists

Lists of Nodes

One Dimensional Arrays

Manual Entries:

Manual Page Sets

User Defined Parameter Types