Using this in C++
Typically, you will be calling your sort routine from within a C++ class. However,
the function must not be a class member function, one that requires a this pointer,
because that is not supported in C. And qsort is a C library function, not a
C++ library function.
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);