Sign in to follow this  
plywood

Interfaces & C++ Class Templates

Recommended Posts

I am in the middle of writing my own generic LinkedList<T> class in C++ for my own fun and profit; I am not interested of using existing (standard) linked lists. One of the list operations I would like to implement is a sort(), for instance: LinkedList<int> x = MakeIntList(); x.sort(ASCENDING); LinkedList<Car> cars = MakeCarList(); cars.sort(BY_YEAR); I am realizing that by making my linked list generic, there's no guarantee that my <typename T> data are comparable. Observe:
// This is a summary...
template <typename T>
class LinkedList
{
    // ... the list declaration
    void sort(int);
};

// Our sort function...
template <typename T> void LinkedList<T>::sort(int flag)
{
    // Aaaahhhh! How do we sort *any* generic T data?????
}

You could always just have the sort() function above call something like T.compare() or T.equals(), but we have no guarantee that these methods exist for an arbitrary T class. And this got me thinking: how to you make C++ classes flexible enough to handle generics *and* yet still guarantee functionality (i.e. implementing, in this case, a Comparable interface)?

Share this post


Link to post
Share on other sites
Even if you don't use the standard library list, you can still look at its implementation to see how they've managed to do things.

In this case, the sort function has a signature of the form:
template <typename F> void sort(F compare);


This means that the comparison predicate (whether a value is smaller than another) is passed as an argument to the sort function. Of course, there is also a default sort algorithm which uses operator < for these purposes, and thus requires no argument.

You can the set up the predicate you provide to sort in ascending or descending order, by a particular field, or whatever.

Share this post


Link to post
Share on other sites
A predicate is anything which supports the syntax f(a,b): it can be a function pointer, or an object overloading operator(). While it would be possible to use a simple function pointer, the inability for C++ to store a closure context in a function pointer makes it extremely limiting (for instance, what if the order between objects depends on, say, the distance within a 2D tile map obtained through pathfinding?) and as such, it's much more expressive to use a generic predicate instead of a function pointer.

Share this post


Link to post
Share on other sites
Quote:
Original post by plywood

You could always just have the sort() function above call something like T.compare() or T.equals(), but we have no guarantee that these methods exist for an arbitrary T class.


If it doesn't, you get compile-time error.

That's how STL containers do it.

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