Sunday, June 13, 2010

SLT algorithm basics

STL algorithms are very powerful. They have 2 fundamental components.

The Algorithms:
  • These are the outer flow of control functions that direct the action of the operator classes. In general the internals are some form of for loop that passes over a series of STL compatible iterators and performs an action.
  • A list of them is here: http://www.cplusplus.com/reference/algorithm/

The Function/Operator classes
  • These are a class that implement the operator() overloader to provide the listed functionally.
  • Within this group of objects are an important subgroup of wrapper operators. These wrappers are designed to expand or covert the abilities of the other operators and to adapt existing function and class members for use with the STL algorithms.
  • A list of them is here: http://www.cplusplus.com/reference/std/functional/

I think I need to break this down and approach it in smaller chunks and apologies for the template heavy code. It cut down my typing.
#include <iostream>
#include <list>
#include <string>

#include <algorithm>
#include <functional>
#include <iterator>
using namespace std;

class RandN
{
  int n;
public:
  RandN(const int _n) { n = _n; }

  int operator() () const { return rand()%n; }
};

void readInAFIle(string filename)
{
  vector<int> values;
  ifstream file (filename);
  if (file)
    copy(istream_iterator<string> (file), istream_iterator<string>(), back_inserter (values));
}

template<class itor>
itor filterToThreshold(itor start, itor end, int threshold)
{
  //move to the end if... why call did they call it "remove"...
  return remove_if(start, end, bind2nd(greater<int>(), threshold));
}

template<class itor>
bool checkIfPresent(itor start, itor end, int value)
{
  return find(start, end, value) != end;
}

template<class itor>
void createRandSamples(itor start, int size, int limit)
{
  generate_n(start, size, RandN(limit));  
}

template<class itor>
void printOut(itor start, itor end)
{
  // *copy* the data into the output stream
  copy (start, end, ostream_iterator<int>(cout, " ")); 
  cout << endl;
}

template<class itor> 
void doDemo(itor start, itor end, string kind)
{
  cout << endl;
  cout << "Working on a " << kind << "..." << endl;
  printOut(start, end);
  cout << (checkIfPresent(start, end, 5) ? "there is a 5" : "No 5's") << endl;
  
  itor splitPoint = filterToThreshold(start, end, 5);
  int count = distance(start, splitPoint);
  cout << kind << " was filtered to a count of " << count << endl;
  printOut(start, splitPoint);
}

int main()
{
  const int SIZE = 20;
  list<int> valuesList;
  int valuesArray[SIZE];

  //create a rand list of stuff...
  srand(time(NULL));
  createRandSamples(valuesArray, SIZE, 10);
  createRandSamples(back_inserter(valuesList), SIZE, 10);

  doDemo(valuesArray, valuesArray + SIZE, "Array");
  doDemo(valuesList.begin(), valuesList.end(), "List");
}

No comments:

Post a Comment