Sign in to follow this  
Winegums

Sorting algorithms and templates

Recommended Posts

I've been looking at writing sorting algorithms recently. I've written a few C++ implementations with int arrays. However, I've also been looking at templateing these sorting algorithms to make them more generic. However, I'm wondering if there's a way to make a templated algorithm accept an object type and variable of this type to sort by?
class cClass
{
public:
   int mInt;
};

template<typename T>
void Sort(std::list<T>, void* variableToSortBy)
{
   
}

int main()
{
Sort(list, cClass::mInt);
return 0;
}


(I'm aware the above sourcecode is possibly a bit horrific and wouldn't work..) I guess an alternative would be to store the offset in a class instance of the variable you want to sort by, then pass that in as well and use that to find the variable you want to sort by in each object, but that sounds very messy (and would require strict variable order sorting in classes...). [Edited by - Winegums on October 12, 2008 9:13:29 AM]

Share this post


Link to post
Share on other sites
A very generic way is to make the sorted test itself a templated type.

template <typename Iterator, typename Functor>
void sort(Iterator begin, Iterator end, Functor functor)
{
// instead of if(a.x < b.x)
// use if(functor(a,b))
}


We can then define a custom sort function:

bool sort_by_int_member(const Class &one, const Class &two)
{
return one.mInt < two.mInt;
}


Or as a functor:

struct sort_by_int_member
bool operator()(const Class &one, const Class &two) const
{
return one.mInt < two.mInt;
}
};


And then use it:

// function pointer
sort(list.begin(),list.end(), &sort_by_int_member);

// functor
sort(list.begin(),list.end(), sort_by_int_member());


Of course, C++ already defines this function, the aptly named std::sort.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this