Tables

View Code

Tables a.k.a. Map is an associative array. That means instead of using numbers of a mememory location to get an element from the array, another element that is associated with what you want is used to return it. For examples, a social security number in indexed and a person's name is returned, a letter grade is inputed and the lowest percent value for it is returned, an animal name is indexed and its pluralized form is returned. Basically it is an array that stores pairs of things, and one is used to get the other.

Implementation

An table is implemented with just an array and an association class. An association class, let's call it Pair, will just hold and return the two matched elements. Now the table is just an array of these Pairs. The table can have all the basic container functions, and just to make things easy let's use a vector instead of standarnd array to avoid the memeory functions.

Since a Table can associate two things let's use string to decimal. It could be use to store student and grades, merchandise and their cost, atomic elements and their weghts, whatever.


struct Pair
{
   string theString;
   double theDecimal;
};

class
{
   public:
      Table();  //no copy constructor, destructor, or assignment, 
                //since no memery management is needed for a vector
                
      int add(string s, double d);
      int get(string s);      
      int remove(string s);

      int empty();
      int size();
      
   private:
      vector>Pair< theTable;
};

The Table's is pretty easy to implement especial with the vector instead of the array. Also note that the same trick for removal in a Set is used with the Table. Remeber association not order is needed.

Performance

Function	Evaluation	Order
Table()	Simple contruction.	O(1)
add()	Simple operations except for resize are used.	O(resize)
get()	Simple for loop search.	O(n)
remove()	Basic for loop search with a resize.	O(n + resize)
empty()	Simple return.	O(1)
size()	Simple return.	O(1)

The table is as quick as a linked list. However that is excepted since it is not dealing with direct addresing of memory like an array.

Prev -- Back to Portal -- Next