A common misunderstanding about the C++ language forces many programmers to create a function that is not a class function. This ends up creating a function that is somehow separate from the class. This is not always a good idea. The simple way to handle this is to simply declare the function as a static member function of the class. It will not require a this pointer, and can be used as an argument to qsort.
I discuss more about callbacks in my companion essay on callback methods in C++. But the simple explanation is to simply put the function in the class.
class whatever {
...
protected:
static int compareint(const void * v1, const void
* v2);
};
/* static */ int whatever::compareint(const void * v1, const void * v2)
{
return *(int *)v1 - *(int *)v2;
}
Sorting a CList or CMap
You can use qsort in all kinds of interesting ways. For example, you don't always need to sort the things, you may only need to get a sorted reference to the things! Suppose you have a list of objects that you want to display in sorted order. For this discussion, we can assume either that they are unsorted, or they are sorted in a fashion that is not what you want to see. Or you might have a CMap, which essentially uses the same techniques. I will concentrate on the CList here, and leave CMap as an Exercise For The Reader.
typedef CList<pmyData, pmyData> DataList;
DataList people;
Now you want to sort this and display it in, say, name order. Do you have to sort the list? No, not at all! You can create a "side vector" that represents the sorted data, and sort that! Note that in the code below I assume the list is nonempty.
void showByName(DataList & data)
{
int n = data.GetCount();
pmyData * vector = new pmyData[n];
POSITION p = data.GetHeadPosition;
int i = 0;
while(p != NULL)
{ /* build vector */
vector[i] = data.GetNext(p);
i++;
} /* build vector */
qsort(vector, n, sizeof(pmyData), byname1);
for(i = 0; i < n; i++)
ShowAnElement(vector[i]);
delete [] vector;
} // showByName
int byname1(const void * v1, const void * v2)
{
pmyData * data1 = (pmyData *)v1;
pmyData * data2 = (pmyData *)v2;
return _tcscmp( (*data1)->name, (*data2)->name);
} // byname1
Note that by creating the side vector of pointers, we introduce one more level of indirection; so what the sort routine gets is a pointer to the array element, which is itself a pointer to a myData item. So the extra level of indirection is required. You could also have written it as
int byname1(const void * v1, const void * v2)
{
pmyData data1 = *(pmyData *)v1;
pmyData data2 = *(pmyData *)v2;
return _tcscmp( data1->name, data2->name);
} // byname1
Note that the "side vector" is valid only as long as the list remains unchanged. One thing I have done is encapsulate the list and the side vector in a single class. When I need the sorted display, I create the side vector and sort it. When I add to, or delete from, the list, I delete the side vector. I then recompute it as necessary.
template <class type, class arg_type> SortedList : public
CList<type, arg_type> {
public:
POSITION AddHead(arg_type value) { CList<type, arg_type>::AddHead(value);
vector.RemoveAll(); }
void RemoveAll() { CList<type, arg_type>::RemoveAll(); vector.RemoveAll();
}
... etc
void Sort() {
if(vector.GetSize() ==
0)
{ /* sort
it */
vector.SetSize(GetCount());
POSITION
p = GetHeadPosition();
int i =
0;
while(p
!= NULL)
{
/* fill vector */
vector[i]
= GetNext(p);
}
/* fill vector */
} /* sort
it */
qsort(vector.GetData(),
vector.GetSize(), sizeof(type *), compare); // see below
}
int GetFirstSortPosition() { ASSERT(vector.GetSize() > 0); return
0; }
int GetLastSortPosition() { ASSERT(vector.GetSize() > 0); return
vector.GetSize() - 1; }
type * GetSortAt(int n) { return vector.GetAt(n); }
protected:
CArray<type *, type *> vector;
int compare(const void * v1, const void * v2) {
if( *(type *)v1 < *(type *)v2)
return -1;
else
if( *(type *)v1 > *(type *)v2)
return 1;
else
return 0;
}
};
Note this assumes that there are relationship operators, > and <, defined on your type. This is a sketch of how you might do comparison. The side vector is maintained as a "cache". However, note that with this method, you must override all the operations of CList that exist; using one you have not overridden and which modifies the list without deleting the contents of the side vector would have serious consequences.
Another method is not to derive, but to embed. In this model, you provide only the methods you need, and the CList is contained entirely within the class.
template <class type, class arg_type> class SortedList
{
public:
void AddTail(arg_type t) { list.AddTail(t); vector.RemoveAll();
}
POSITION GetHeadPosition() { return list.GetHeadPosition();
}
type GetNext(POSITION & p){ return list.GetNext(p);
}
void RemoveAll() { list.RemoveAll(); vector.RemoveAll();
}
protected:
CList<type, arg_type> list;
CArray<type *, type *>vector;
};
Note that in this case you do not need to override all the CList methods, because the only methods that can be called on this class are the methods you export. On the whole, I find embedding to be cleaner than derivation for this purpose, and it is my preeferred mechanism for handling this situation.
Sorting a CArray
A CArray is easy to sort. All we need is the sizes of the objects and the base pointer. The base pointer is easy. We use GetData to get that. The count is easy. That's GetSize. The width is easy. That's sizeof. So we have everything we need!
CArray<pmyData, pmyData> array;
qsort(array.GetData(), array.GetSize(), sizeof(pmyData), byname1);
Comments