1
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

0
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the advice, I've honestly had no idea things you've mentioned in "Passing the score function" existed. On the topic of being limited to a 32-bit value, I wonder if you can do ceil(str.length()/4) radix sorts for every 4 chars since the sort is stable-- I guess that's a bit dumb, though \$\endgroup\$
    – t1mur4tr
    May 19 at 19:36
  • \$\begingroup\$ In theory you can, in practice that would require you to have arrays of \$2^{32}\$ elements, which is not great. It would be best if you use a radix size such that the working set fits in your processor's L1 cache. \$\endgroup\$
    – G. Sliepen
    May 19 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.