Friday, July 2, 2010

Sorting List Interfaces

Qub Library is a cross-platform C++ library that I'm developing for my own uses, but also so that I can learn C++ and cross-platform principles better. This library has built in data structures, that I am already enjoying using. One of the common interfaces to the data structures I am using is the IList, which is just a random-accessible structure. One key thing about random-accessible structures is that they are generally sortable. The thing I've been thinking recently is whether the Sort() function should be a part of the data structure or whether it should be an external function that operates on the data structure. The way I currently have things set up is that there is an Algorithms::ShellSort() or Quicksort() method that takes a pointer to an IList object. I also have an IList abstract method that will sort the IList, but all it does on the inside is calls the Algorithms::ShellSort() function. While this is useful, in C++ it means that anything that could be placed into an IList must implement the "<" operator, which is the standard way of comparing two items in the list. This doesn't sound so great to me, because not only is that just another method I have to implement in my classes, it also won't make sense to certain concepts. What if I have an IList of thread pointers? Or function pointers? There are probably ways to order those types of objects, but if that isn't part of your initial design, why should a developer have to put those operators in? So, I think I'm going to remove the Sort() method from the IList interface and just leave it in the Algorithms static class.
This small example is an example of the question whether classes that hold data should have methods that operate on the data, or should there be other classes that manipulate the data. i think the answer to that question rests in the question: "What are the different ways that the data can be manipulated?" Take sorting a list for example. There are almost countless algorithms for sorting a list, whether it be a BubbleSort, Shell/SelectionSort, QuickSort, MergeSort, HeapSort, etc. If a sort method was implemented on a particular list object, then to keep these different options available you would have to pass a Sorter type of object that is given a list and an object that compares two elements of the list. This simple double-dispatch method provides the options that we wanted, but it is at the cost of having to add a parameter to the Sort() function. However, maybe that really wouldn't be so bad. I suppose it may just be a matter of style and taste.

No comments:

Post a Comment