Jump to content
  • Advertisement
Sign in to follow this  
Winegums

Sorting algorithms and templates

This topic is 3598 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
It seems a bit more intuitive to use function pointers here, passing a comparator. Even if you pass the variable in, you don't know how to compare it...

Which brings us to ... std::sort

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!