Asking for C++ advice based on a radix sort function

Question

Can someone point out what possible edge cases/leaks/inefficiencies my code has and how they could be avoided/fixed. Basically, I want to know what mistakes I make so I can avoid making them in the future.
I chose an LSD radix sort function as a sample for no particular reason.

The function:

//arrPtr - pointer to the array being sorted; count - its count
//scoreFunction - function that assigns scores to elements based on which they will be sorted in ascending order
//args - pointer to an array of pointers used to pass data to the scoreFunction
template<class T>
void rsort(T *arrPtr, size_t count, int scoreFunction(T val, void **args) = [](T val, void **args) {return val; }, void **args = nullptr) {
    struct elem { //Pairing indices with their scores
        size_t idx;
        int scr;
    };
    struct elemPtr { //Pointer struct to avoid memory leaks in case of an exception
        elem *ptr;
        ~elemPtr() { delete[] ptr; }
        void swap(elemPtr &aux) {
            elemPtr t{ ptr };
            ptr = aux.ptr;
            aux.ptr = t.ptr;
            t.ptr = nullptr;
        }
    };
    elemPtr srt{ new elem[count] }, srtAux{ new elem[count] };
    for (size_t i = 0; i < count; ++i) { //Assigning indices and scores that are converted to unsigned representation + 2^31
        srt.ptr[i].idx = i;
        srt.ptr[i].scr = scoreFunction(arrPtr[i], args) ^ 0x80000000;
    }
    for (unsigned char bShft = 0; bShft < 32; bShft += 8) { // Base 256 LSD radix sort based on the scores
        size_t dCnt[256]{};
        for (size_t i = 0; i < count; ++i) 
            ++dCnt[srt.ptr[i].scr >> bShft & 255];
        for (unsigned char i = 0; i < 255; ++i) 
            dCnt[i + 1] += dCnt[i];
        for (size_t i = count; i > 0; --i) {
            --dCnt[srt.ptr[i - 1].scr >> bShft & 255];
            srtAux.ptr[dCnt[srt.ptr[i - 1].scr >> bShft & 255]] = srt.ptr[i - 1];
        }
        srt.swap(srtAux);
    }
    for (size_t i = 0; i < count; ++i) //Filling with 0s to reuse as an array of bools that represent if the element is in the right place
        srtAux.ptr[i].idx = 0;
    for (size_t i = 0; i < count; ++i) { //Rearranging the original array by dividing the elements into enclosed loops
        if (srtAux.ptr[i].idx)
            continue;
        T temp = arrPtr[i];
        size_t curIdx = i;
        while (srt.ptr[curIdx].idx != i) {
            srtAux.ptr[curIdx].idx = 1;
            arrPtr[curIdx] = arrPtr[srt.ptr[curIdx].idx];
            curIdx = srt.ptr[curIdx].idx;
        }
        srtAux.ptr[curIdx].idx = 1;
        arrPtr[curIdx] = temp;
    }
}

I didn't use any libraries to make the function independent-- if that makes sense.

Answer 1

Use the standard library, or emulate it

I didn't use any libraries to make the function independent-- if that makes sense.

It can indeed be a burden for developers if a library they want to use has lots of dependencies, as they need to incorporate those into their build system, have to deal with licensing issues, and so on. However, on almost any platform you will have a standard library that you can rely on without doing anything special.

Consider your elemPtr, this is basically the same as std::unique_ptr. So I would strongly recommend using the latter instead. And in case this isn't available on the platform you want to run it on, you could create a drop-in replacement for std::unique_ptr. You should avoid adding things to the std namespace yourself, so a way to do this properly would be:

#if HAVE_UNIQUE_PTR
#include <memory>
using std::unique_ptr;
#else
class unique_ptr {
    // ...
};
#endif

Passing the score function

You are passing the score function as a regular function pointer, and you want to be able to have a variable number of arguments passed to it. Using void** is not very safe. Again, if you can I would recommend using the standard library here, and use std::function<int(T)> to pass the function. It will allow you to pass lambdas with captures, so you don't have to worry about any extra arguments.

Another solution is to make the template itself variadic, allowing you to really pass an arbitrary number of arguments without resorting to void**, like so:

template<typename T, typename... Args>
void rsort(T *arrPtr, size_t count, int scoreFunction(T val, Args...) = [](T val, Args...) {return val;}, Args... args) {
    // ...
    srt.ptr[i].scr = scoreFunction(arrPtr[i], args...) ^ 0x80000000;
    // ...
}

Pass by const reference where appropriate

Passing val and args by value to scoreFunction() can be inefficient, depending on their types. Prefer to pass them by const reference instead:

int scoreFunction(const T& val, const Args&...)

Use of a score function might be problematic

You are not radix sorting T, you are radix sorting the 32-bit score associated with each element of the array pointed to by arrPtr. However, it might not always be easy to create a score function. Consider having an array of std::strings. It would be easy to radix-sort strings, using char as the radix. However, given an set of arbitrary strings that I want to sort alphabetically, it's very hard to create a scoreFunction() that would map every string to a 32-bit value and still keep them in the same order.