Algorithm

Algorithms are ways to processes data like a sort or search, however they are also a special combination of classes and functions to do processes. Sounds confusig but is a simple concept best built bottom up. Here is a simple function that double every value in a vector.

void f(const vector&V)
{
   for(int i=0; i<v.size(); i++)
      v[i]=v[i]*2;
}

Now let's make a simple modifing class called double. It will take in an integer and double it.

class Double
{
   public:
     void work(int& i) {i = i*2;}   
};

Now let's substitute Double into the f function, for the assignment. The integer reference of V is passed into work() which then doubles it.

void f(const vector&V)
{
   for(int i=0; i<v.size(); i++)
   {
      Double d;
      d.work(v[i]);
   }
}

Now let's create an abstract class called Action. All it has is a function called work. Then let's have Double be a derive class of Action, and of course redine work().

class Action
{
   public:
      virtual void work(int& i);
}
class Double : public Action
{
   public:
     virtual void work(int& i) {i = i*2;}   

}

Now let's substitute Double with Action. Since Action is an abract class it can only be used with a pointer, so that will be a parameter to f(). Also since it is a pointer it will dynamically call the work class appropriately for whatever derived class is used. Now since we want to double the elements in V still a Double for the Action to be used.

void f(const vector&V, Action* act)
{
   for(int i=0; i<v.size(); i++)
      act->work(V[i]);
}

// more code

f(numList, new Double());

Now we just change the name of f() to for_all() and viola!, we have our first Algorithm.


void for_all(const vector&V, Action* act)
{
   for(int i=0; i<v.size(); i++)
      act->work(V[i]);
}


The for_all() function will apply the work() function of an Action class to all the elements in the vector passed in. If we wanted to do somthing else for all of the vector's elements all we have to do is make a custom derived Action class. 
Here is an application of for_all(). Say a statistician wanted to normalize every all the value with a given average and standard deviation. Just create a Normalize class derived from Action to do it. Here is how it may look like.  


class Normalize : public Action
{
   public:
      Normalize(int ave, int standev) : theMean(ave), theSD(standev) {};
      virtual void work(int& i)
      {
         i = (i-theMean)/theSD;
      }
      
   private:
      int theMean;
      int theSD;      
};

int main()
{
   vector<int> data = getData();
   Normalize n = (getAverage(), getStanDev());
   ActionPrint actPrn(cout);
   for_all(data, n);
   for_all(data, actPrn);
   return 0;
}


Notice how a ActionPrint class was used to print all the values in data. What could it look like? 

Standard Algorithms
Algorithms in this sense are mainly used in C++. This is becuase of C++'s operaor overloaded and conversions make is easy and better to use. In fact useing an algorithm with these action classes may be faster than hardcoding like the first function! Here are more standard algorithm and note that some require premise classes. A predicate class is one that returns a boolean. A typical example of a predicate is LessThan. Can you guess what is could be used for?


for_each()
find()
find_if()
count()
count_if()
replace()
replace_if()
sort()

 

Prev --
Back to Portal --
Next