Set

A set is a simple container that just holds a bunch of integers. Order and placement is not important, just whether or not that number is in the Set. It is not a standard container but a simple one to demonstrate the basics.

Now the first step in designed a container after getting its basic concept down is what it can doing. Going down the list of common container functions add(), empty(), size(), clear() and copy() can be applied to the Set easily. Add() just adds an integer to it, empty() and size() are simple returns, clear() is a delete, and copy() depends on the implementation. However can or does it need to implelment remove() or get(), and if so how? Remove() can be a simple remove the first instance of that number. Get in this case would not be useful since the intergers are not orderd in any way. A count() function that tells how many times that number appears may be more usefull.

Knowing what the Set can do now how is it to be implemented? Well let's say we do not have other container classes like vector, so the only thing left would be an array. They are simple to use and can hold the numbers of the Set. Is there anything else? Depending on which language used an interger may be needed to hold the size of the array in case it cannot return it by itself. Also in this implementation another integer is used to represent the size of the Set. It is not needed exactly but will simplify things latter.

Since the Set now uses arrays some memory functions should be included, to help the programmer's life with memory management. Let's say there will be an ensure() that makes sure that bag can hold a certain amount of numbers. If allocated mememory would be usefull what about the opposite? A trim() will remove excess memory for the bag.

Now what about constructors? Useually these are defined latter when basic implementation of the class is understood. In this case is would be useful with a default constructor of an empty Set, and another for a specifc size Set. for a specific size.

Finally there are more subtle details. What the returns of the functions? Empty(), size(), and copy() are apparent, but what of the others? There are three styles of returns for classes. First is nothing, so they could return void. Another is intergers/booleans. They return whether the function was completed sucessfully. The final one is returning a reference to the class so that functions could be chained, like this bag.add(3).add(4).size(). For our usage integers will be returned in the container classes so that functions can easily be used in logical tests.

With everything defined all that's left is the implementation. It is shown on the code part of this site, but try to do it yourself. Here is the class declaration.


class Set
{
   public:
      Set();                 //makes bag of zero size 
      Set(int size);         //makes bag of size size
      Set(const Set& s); //since this is C++ and memory is being allocated
      ~Set();                //a copy constructor, deconstructor, and = is needed 
			                       
      bool empty();          //returns true if theSize==0
      bool size();           //returns theSize
      int add(int elmnt);    //adds elmnt to Bag
      int count(int elmnt);  //returns the number of elmnt is in Bag
      int remove(int elmnt); //remove first instance of element
      int clear();           //empties the bag to zero
      int ensure(int size);  //makes sure bag can hold size elements
      int trim();            //resizes bag to number of current total elements
		 
      Set& operator=(const Set& s);  //copy aka assignment
		 
   private:
      int theSize;
      int theArraySize;
      int theSet[]
};

View Code

The final step of designing a container is evaluating its performance. Let's assume that declaring an array is constant. This is done to see if there could be better ways to implement a function.

Function Evaluation Order
Set() Declare two integers and an array for O(3) == O(1). O(1)
Set(int) Ditto. O(1)
Set(Set&) Declare integers and an array for O(3). Then copy integers s.theArraySize times. O(n+3) == O(n). Could have only copied theSize amount of elements, but that would have resulted is O(n) still. Increases performace, but not by an order. O(n)
~Set() Simple delete for O(1). O(1)
empty() Simple return for O(1). O(1)
size() Ditto. O(1)
add() First there is a call to ensure for O(O(ensure)). Next are three constant staments O(ensure+3). On the worst it is the same as O(ensure) and at best it is O(1). O(n)
count() Simple linear counting for O(n). O(n)
remove() Simple linear search for element then a copy over, giving us O(n+3)==O(n). If we did keep order in the Set it could have been O(2n), but that reduces to O(n). On an order scale it is the same, but it is easier for the programmer. O(n)
clear() Simple assignments and deletion for O(1). O(n)
ensure() This function does simple asignments an one for loop copying to have O(n+1) == O(n). O(n)
trim() Simple assignments and copying for O(n+1)==O(n). O(n)
= At best this is O(1), since assigning to itself does nothing. Worst case results in simple copying, deleting, and a for loop assignment, O(n+1)==O(n). O(n)

Function	Evaluation	Order
Set()	Declare two integers and an array for O(3) == O(1).	O(1)
Set(int)	Ditto.	O(1)
Set(Set&)	Declare integers and an array for O(3). Then copy integers s.theArraySize times. O(n+3) == O(n). Could have only copied theSize amount of elements, but that would have resulted is O(n) still. Increases performace, but not by an order.	O(n)
~Set()	Simple delete for O(1).	O(1)
empty()	Simple return for O(1).	O(1)
size()	Ditto.	O(1)
add()	First there is a call to ensure for O(O(ensure)). Next are three constant staments O(ensure+3). On the worst it is the same as O(ensure) and at best it is O(1).	O(n)
count()	Simple linear counting for O(n).	O(n)
remove()	Simple linear search for element then a copy over, giving us O(n+3)==O(n). If we did keep order in the Set it could have been O(2n), but that reduces to O(n). On an order scale it is the same, but it is easier for the programmer.	O(n)
clear()	Simple assignments and deletion for O(1).	O(n)
ensure()	This function does simple asignments an one for loop copying to have O(n+1) == O(n).	O(n)
trim()	Simple assignments and copying for O(n+1)==O(n).	O(n)
=	At best this is O(1), since assigning to itself does nothing. Worst case results in simple copying, deleting, and a for loop assignment, O(n+1)==O(n).	O(n)

As you can see the Set is a pretty fast class having only constant or linear functions. Certain tricks may be used to increase performance but on a Big Oh scale they do litte. That is not to say to avoid them, but to keep in mind of what Big Oh measures.

Also a few modifications to the set would make it into a vector class. All that is needed is an index operator, a resizer, and a few other functions.

Prev -- Back to Portal -- Next