How write sort with unknown argument. Cant iterate with void*/

Question

In this void* ic = b + j * sz; and this void* jc = ic - sz; lines ide writing that expression must be a pointer to a complete type. I need to wright function which can sort everything so i use void*. I don't now how to iterate with void*. How get access to elements void* baselike array.

UPD pcharToInt is wrong. At fist i cast void* to char* and turned out heart symbols. Than i tried to work with void*.

#include <iostream>

using namespace std;

typedef int (*CFT) (const void*, const void*);

int pcharToInt(char* a);
int cmp1(const void* a, const void* b);
void insort(void* base, size_t n, size_t sz, CFT cmp);

int main() {
    int arr[] = { 9, 3, 5, 3, 7, 9, 4 };
    void* a = arr;
    char* b = static_cast<char*>(a);
    return 0;
}

int pcharToInt(char* a) {
    int b = 0;
    char* tmp = a;
    while (*a) {
        b *= 10;
        b += (*a++ - '0');
    }
    a = tmp;
    return b;
}

int cmp1(const void* a, const void* b) {
    int n1 = 0;
    int n2 = 0;
    n1 = pcharToInt((char*)a);
    n2 = pcharToInt((char*)b);
    if (n1 > n2) return 1;
    else return 0;
}

void insort(void* base, size_t n, size_t sz, CFT cmp) {
    void* b = base;
    for (int i = 1; i < n; i++)
    {
        for (int j = i; j > 0; j--)
        {
            void* ic = b + j * sz;
            void* jc = ic - sz;
            if (cmp1(jc, ic)) {
                for (int k = 0; k < sz; k++) {
                    char tmp = jc[k];
                    jc[k] = ic[k];
                    ic[k] = tmp;
                }
            }
            break;
        }
    }
}

UPD2 Its old code vitch char

char* b = static_cast<char*> (base);
    for (int i = 1; i < n; i++)
    {
        for (int j = i; j > 0; j--)
        {
            char* ic = b + j * sz;
            char* jc = ic - sz;
            if (cmp1(jc, ic)) {
                for (int k = 0; k < sz; k++) {
                    char tmp = jc[k];
                    jc[k] = ic[k];
                    ic[k] = tmp;
                }
            }
            break;
        }
    }

UPD3 Trouble in line where I cast void* to char*. In result where are not right symbols. It must be numbers in example code.

Is there any reason why you don't just use `std::sort` on something like a `std::vector`? — Jan Schultke, Aug 18 '20 at 11:20
cast `void*` to `char*` or `unsigned char*` to increment/decrement it — Mestkon, Aug 18 '20 at 11:22
In the `pcharToInt` function, what is the `tmp` variable for? You never modify the contents that `a` is pointing to, only the *local* variable `a`. Furthermore, why not use [`strtol`](https://en.cppreference.com/w/c/string/byte/strtol)? — Some programmer dude, Aug 18 '20 at 11:25
Mestkon, i tried to do this, but when i cast to `char*` incomprehensible characters are obtained. — LoaDeadd, Aug 18 '20 at 11:25
One major problem is that you have an array of *integers*, but your comparison function treats it as an array of *strings*. And the casting in the `main` function tries to convert the array into an actual string (`char*`), and not an array of strings. — Some programmer dude, Aug 18 '20 at 11:27
You ***can't*** sort things if you don't know what they are, which is why you're having problems. A pointer only points to the beginning of any object. You **must** know how big is it and what the bytes that compose it mean so you can compare objects and sort them. — Andrew Henle, Aug 18 '20 at 11:34
*sz its size of object* That's not enough to properly sort. The string literal "0123456" is 8 bytes long, as is a `uint64_t`. Yet the sorting of those two types is different. Imagine a `struct` with padding of indeterminate (and therefore irrelevant) content. — Andrew Henle, Aug 18 '20 at 11:37
The `std::sort` is written to sort things without knowing the specific type being sorted. Your algorithm should use that for inspiration on how to separate the sorting algorithm from the thing being sorted. Using `void*` and hail mary casting is not going to work. — Eljay, Aug 18 '20 at 12:22

Ian Abbott · Answer 1 · 2020-08-18T13:51:51.247

If you are trying to mimic the operation of qsort() from the C standard library, the comparison function needs to be tailored to the type of the element being sorted and the sort order (ascending or descending). The comparison is called with pointer arguments of type const void * because qsort() is designed to work with arrays of any type and void * is the most general object pointer type.

For the specific case of comparing int elements, the const void * arguments should be converted to const int * and dereferenced to get the values of the int elements to be compared. The comparison function should return a negative, zero, or positive value to indicate the relative ordering of the two elements being compared. For sorting elements of int type in ascending order, a suitable comparison function is the following:

int cmp1(const void *a, const void *b)
{
    int aa = *(const int *)a; // convert pointer a and dereference
    int bb = *(const int *)b; // convert pointer b and defererence

    if (aa < bb)
        return -1;
    if (aa > bb)
        return 1;
    return 0;
}

A comparison function for sorting int elements in descending order would be similar to the above but with the -1 and 1 return values swapped.

Your insort() function requires a different return value from the comparison function, returning 0 instead of a negative value. For compatibility with your insort() function, the function needs to be modified as follows:

int cmp1(const void *a, const void *b)
{
    int aa = *(const int *)a; // convert pointer a and dereference
    int bb = *(const int *)b; // convert pointer b and defererence

    return (aa > bb);
}

For standard C (and C++?), pointer arithmetic on void * is not allowed because pointer arithmetic is only allowed on pointers to complete object types, and void is an incomplete object type by definition. Some compilers such as GCC permit pointer arithmetic of void * as an extension to the C standard be treating it the same as char * as far as pointer arithmetic is concerned. Portable code should avoid pointer arithmetic on void *. Your insort() function can be modified as follows for portability:

void insort(void* base, size_t n, size_t sz, CFT cmp) {
    char* b = (char*)base;
    for (int i = 1; i < n; i++)
    {
        for (int j = i; j > 0; j--)
        {
            char* ic = b + j * sz;
            char* jc = ic - sz;
            if (cmp1((void*)jc, (void*)ic)) {
                for (int k = 0; k < sz; k++) {
                    char tmp = jc[k];
                    jc[k] = ic[k];
                    ic[k] = tmp;
                }
            }
            break;
        }
    }
}

thanks for the help, your answer helped me shorten and expose the code — LoaDeadd, Aug 19 '20 at 22:47

Caleth · Accepted Answer · 2020-08-18T13:25:58.093

In C++ you don't throw away type information.

Instead of

typedef int (*CFT) (const void*, const void*);
void insort(void* base, size_t n, size_t sz, CFT cmp);
int cmp1(const void* a, const void* b);

You should be writing

template<typename T>
using CFT = bool(*)(const T *, const T *);

template<typename T>
void insort(T* base, size_t n, CFT<T> cmp) {
    for (T* i = base + 1; i < base + n; i++)
    {
        for (T* j = i; j > base; j--)
        {
            if (cmp(j, i)) {
                std::swap(*j, *i)
            }
            break;
        }
    }
}

int cmp1(const int * a, const int * b)
{ 
    return *a > *b; 
}

Note that you ignore the first element, and the break seems suspicious. You generally need to move more than one element when you find something out of order.

A proper insertion sort (adapted from here) would be

template<typename T, typename Compare = std::less<>>
void insertion_sort(T* first, size_t n, Compare cmp = Compare{})
{
    for (T* it = first; it != first + n; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it)); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

I didn't understand your answer well, because I just started learning c ++ and I don't understand the constructions that you used, but you wrote something about `break` and in fact the mistake was in it, it had to be written in the `else` block. I also don't understand English well, but thanks for the help. — LoaDeadd, Aug 19 '20 at 22:44

How write sort with unknown argument. Cant iterate with void*/

2 Answers2