Section 5 - Smart Pointers

9A.5.1 Smart Pointers

Let's do a naive version of this strategy. It consists of three phases:

Creating the pointer array and setting its elements to point to the client array.
Sorting the pointer array.
Untangling the client array using the sorted pointers as a guide.

We will ignore the final phase for now, and focus on building the pointers and sorting them. Here is the overview of indirectSort():

template <typename Comparable>
void indirectSort( FHvector<Comparable> & a )
{
   int arraySize = a.size();

   Comparable *p = new Comparable*[arraySize];  // won't work but the idea is right
   
   // point each pointer to its corresponding client object
   for( k = 0; k < arraySize; k++ )
      p[k] = &a[k];

   // do the sort - it only changes the smart pointer order
   quickSort(p);

   // untangle the client elements so they match the pointer order
   ... whatever this ends up being ...
}

Very simple conceptually. In the first part, I did exactly what I said I would do in the last page: constructed a parallel array, p[] consisting of pointers which point to the client array elements. Then, I pass that pointer array (which is very "light", each element nothing more than an address, i.e., just an integer) to the quickSort() method.

Before going on, it's a good idea to understand the intuitive correctness of the above first try at a coding solution to the problem. So do that now. I'll wait.

Now, that we see why it should work, we have to understand why it won't work. It might actually compile (I don't see why not, but I haven't tried it), but it certainly won't do anything. The reason is that the array of pointers (basically integers) are already sorted. p[0] is &a[0]. But this is exactly one position less than &a[1] which is one position less than &a[2], and so on. Because the a[] array is stored in consecutive memory locations, the addresses of those elements, stored in p[], form a sorted sequence. The call to quickSort() will not change that.

To fix this, we turn back the page and recall this marching order:

The Key

We compare objects using the values in the client array, but when it comes time to swap elements, we only swap elements in the pointer array.

When we are inside any sort algorithm , we do two things, repeatedly: we compare them (using <) and we assign them (using =). Here is a sample block from insertionSort() but it contains these two ops, common to all sorts:

     tmp = a[pos];
     for(k = pos; k > 0 && tmp < a[k - 1]; k--)
         a[k] = a[k - 1];

Remember, we are inside the sort algorithm here, so a[] is whatever we pass in, and we are passing in the p[] array of pointers (sorry for the potential confusion). If we can make these two lines do the right thing (when passing in a pointer array, p[]), we will be good. So what has to happen?

For the assignment statements like tmp = a[pos] and a[k] = a[k-1] we want the pointers themselves to be copied. But this behavior happens automatically, so this works, already. We are passing in an array of pointers, p[], and any assignments between them, will cause the pointers to move around, as desired. This, evidently, is not our problem.
For comparisons like tmp < a[k - 1], we do not want to compare the pointers, but the items to which they point. We cannot make any changes inside the quickSort(), insertionSort() or mergeSort() algorithms, and that means that comparing two pointers (which, if we use the proposed code above will be Comparable* items) can never do anything other than compare the addresses those pointers contain. That tells us that the idea of passing an array of Comparable* elements will never work.

We need a way around item 2. We know we cannot pass a simple array of pointers like this:

   Comparable *p = new Comparable*[arraySize];  // won't work but right idea

so we have to build our own data type, which we'll call SmartPointer. This will be a template class used by indirectSort().

The challenge is to create a class that does what we want using the existing syntax of operators like < , = and even the pointer dereference operator, *. It's actually pretty easy in C++ and there isn't really a single wrinkle. Here is a prototype of such a class.

Each object contains only one data member, a Comparable*, exactly what we need. We'll call that member pointee, and means "that which is pointed to". This will point to its alter-ego client object in the client array.

Rather than jump into the definitions of these methods, let's just talk about the < operator. While we will have two pointers in our comparisons, as in

we really want the objects to which they point, not the pointers themselves, to determine whether this comparison returns true or false. This is easy to do once we know what we are trying to, do and we can rattle off the definition with alacrity.

Pretty simple. The < operator reports exactly what we want it to report - the status of the two objects pointed to.

Let's take another example: the assignment operator. I said earlier, that assignments like tmp = a[pos] and a[k] = a[k-1] don't require any special attention. Our array of pointers, p[], -- whether it consists of elements that are primitive pointers or fancier SmartPointers -- will always obey assignments correctly. If that's so, why am I overloading the assignment operator?

To answer that, we look, not inside the sort algorithm, which will be fine with regard to = operators, but back at the first step in the indirect sort algorithm: Creating the pointer array and setting its elements to point to the client array. Here is the code that we want to work, copied from our above first try at indirect sort:

Ah, we see that in this loop we have our new SmartPointer type on the left and a primitive pointer, Comparable*, on the right. So we overload =, not for smartPointer = smartPointer, but for smartPointer = Comparable*. Here it is:

So, this is simple, right? When we have a Comparable * on the RHS of the assignment operator and a SmartPointer object on the left, the expression will result in the right behavior. Now the for loop will do the right thing.

A third important operation is that of dereferencing a SmartPointer object using *. We would like the expression:

to turn the RHS into a Comparable object that the expression can use. This is so easy that the class prototype holds the definition in-line.

The other operators are defined similarly. Here is the entire collection, including the ones we just described:

The use of these overloads will be seen when we complete the full indirectSort() method. However, we can, at least, now present the corrected version of the first two parts of the sort: