[boost] A new way of sorting and searching

From: Nic Roets (cpp_at_[hidden])
Date: 2004-06-26 05:46:22

Often when I write searching or sorting code in C or C++, I'm
frustrated that I have to make a new "callback type" compare function.
E.g. when you want to sort a number of points in 2D space according to
their distance from a reference point, it's tempting to do something
like

struct Pt {
  int x, y;
};

static Pt center; // Global or static variable yuck.

int PtDistToCenterCmp (Pt &a, Pt &b)
{
  return Dist (a, center) - Dist (b, center);
}

main() 
{
  ...
  center.x = ...;
  center.y = ...;
  ...
  sort (...);
  ...
}

This type of solution has many problems. Reviewing the code for correctness is
difficult because now you have to read half way through main, stop to
find the definition of center, then continue with main, then find the
definition of PtDistToCenterCmp, then continue with main.

To solve this problem I suggest a new template class "sorter" :
template<class t> struct sorter {
  // Qsort would require a stack here. Heapsort only a few variables.

  iterator a, b;

  sorter(iterator begin, iterator end); // Exuse my cpp if it's
  // incorrect
 
  int Operate (int cmpResult);
};

Then it would be used like this :

void main ()
{
  ...
  sorter<Pt> sortObj (..., ...);
  while (sortObj.Operate (
    Dist (sortObj.a, center) - Dist (sortObj.b, center))) {}
  ...
}

IMHO this is much clearer.

A binary searching template class can also be implemented in this way.

-- 
Regards
Nic Roets