A new way of sorting and searching

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

Nic Roets <cpp@rational.co.za> writes:
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 (...); ... }
I think the Boost.Lambda library already provides what you want in a way that's not sorting-specific: std::sort(first, last, bind(Dist, _1, center) < bind(Dist, _2, center)); Cheers, Dave -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

Nic Roets wrote:
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.
int PtDistToCenterCmp( Pt const & a, Pt const & b, Pt const & center ) { return Dist (a, center) - Dist (b, center); } int main() { sort( first, last, boost::bind( PtDistToCenterCmp, _1, _2, center ) ); }
participants (3)
-
David Abrahams
-
Nic Roets
-
Peter Dimov