Computer Association of SIUE - Forums

CAOS Forums => Technical Knowledge => Topic started by: William Grim on 2007-10-10T23:36:58-05:00 (Wednesday)

Title: I got a fever, and the only prescription is more proxy.
Post by: William Grim on 2007-10-10T23:36:58-05:00 (Wednesday)
I'll let you guys look at this code and see if you can figure out what it's doing.  In a couple days I'll post an explanation, but feel free to discuss it (or not, if it scares you), hehe.

*edit: I added a helper function called "isNot" that adds some syntactic sugar, made "printAllFound" a little more generic, and removed the copying of the "last_" parameter to "printAllFound" and "findFirstOf".  I also corrected my naming conventions on the parameters to all have trailing "_".  I'm a little new to this convention, but I like it.*


#include

template
class Not
{
  _Predicate _predicate;
 
public:
  typedef typename _Predicate::value_type value_type;
  Not(const _Predicate &predicate_) : _predicate(predicate_) {}
  bool operator()(const value_type &value_) const
  {
    return !_predicate(value_);
  }
};

template
inline Not<_Predicate> isNot(const _Predicate &predicate_)
{
  return Not<_Predicate>(predicate_);
}

class DivisibleBy
{
  int _value;
 
public:
  typedef int value_type;
  DivisibleBy(int value_) : _value(value_) {}
  bool operator()(int value_) const
  {
    return !(value_ % _value);
  }
};

template
inline _Iterator findFirstOf(_Iterator first_, const _Iterator &last_,
     const _Predicate &predicate_)
{
  while (first_ != last_ && !predicate_(*first_)) ++first_;
  return first_;
}

template
void printAllFound(_Iterator first_, const _Iterator &last_,
  const _Predicate &predicate_)
{
  using namespace std;
  --first_;
  while ((first_ = findFirstOf(first_+1, last_, predicate_)) != last_) {
    cout << *first_ << ' ';
  }
  cout << endl;
}

int main()
{
  using namespace std;
  int nums[] = {0,1,2,3,4,5,6,7,8,9};
  int *end = nums + sizeof(nums) / sizeof(int);
  cout << "Given the numbers: ";
  for (int *iterator = nums; iterator != end; ++iterator) {
    cout << *iterator << ' ';
  }
  cout << "\nNumbers divisible by 3: ";
  printAllFound(nums, end, DivisibleBy(3));
  cout << "Numbers not divisible by 3: ";
  printAllFound(nums, end, isNot(DivisibleBy(3)));
  return 0;
}
Title: Re: I got a fever, and the only prescription is more proxy.
Post by: Gregory Bartholomew on 2007-10-11T13:59:08-05:00 (Thursday)
That has got to be the fanciest way of doing a bunch of mods that I have ever seen!  What would be really interesting would be to see just how inefficient the result of this algorithm is after the gnu compiler turns it into machine code verses if one were to do it in assembly.

I'm sure what you are really trying to show off is something to do with templates or default constructors or overloaded operators - I'm just looking for something to be critical about :-)

You've made very impressive use of templates and object-oriented programming principles in your sample program though.  I see that I could replace the "DivisibleBy" class with any class that did any operation on any datatype (as long as the result was boolian) without altering any of the rest of the code in any way.  Very impressive!  This would made an excellent sample program for introducing templates.
Title: Re: I got a fever, and the only prescription is more proxy.
Post by: Shaun Martin on 2007-10-11T17:47:56-05:00 (Thursday)
I want a Christopher Walken smiley... or a cowbell.  Right now.
Title: Re: I got a fever, and the only prescription is more proxy.
Post by: William Grim on 2007-10-11T18:49:02-05:00 (Thursday)
QuoteTalmai said:

That has got to be the fanciest way of doing a bunch of mods that I have ever seen! What would be really interesting would be to see just how inefficient the result of this algorithm is after the gnu compiler turns it into machine code verses if one were to do it in assembly.

Well, someone sufficiently advanced in assembly could make it faster than the compiler :-D  However, this code is actually really fast.  To give you an example of how fast, the STL does this kind of stuff all the time and is quite speedy!  Further, doing partial template specializations or full template specializations can let you hone the algorithm even more for specific data types.

All template class methods are inline, and so there isn't even an overhead with using them other than the increased object size.  The compiler will likely inline the template functions as well, since it can see them at compile-time, but making sure to add the "inline" keyword wouldn't hurt if function-call overhead is a concern.

Though, if abused, the templates can lead to code bloat and cause cache misses, but in general they're good things to use.  One thing that can be considered incorrect is that I didn't finish writing my classes: they don't have a copy constructor or overloaded assignment operator.  This is fine in my example, but with more complex data types, it will lead to a shallow-copy that could be potentially bad.  In a real program, you'd write these things.

Good discussion :-)  Like I said, I'll post an explanation soon.