如何使用未知参数写入排序。不能用 void*/ 迭代

Question

在void* ic = b + j * sz;和void* jc = ic - sz;行ide中，写的表达式必须是一个指向完整类型的指针。我需要可以对所有内容进行排序的 wright 函数，所以我使用 void*。我现在不知道如何使用 void* 进行迭代。如何访问元素 void* baselike array.

UPD pcharToInt 是错误的。在拳头我投 void* 到 char* 和原来是心形符号。比起我尝试使用 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 它的旧代码 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 在我将 void* 转换为 char* 的行中出现问题。结果哪里没有正确的符号。它必须是示例代码中的数字。

Answer 1

如果您试图模仿 C 标准库中 qsort() 的操作，则需要根据正在排序的元素的类型和排序顺序（升序或降序）调整比较函数。使用 const void * 类型的指针参数调用比较，因为 qsort() 设计用于任何类型的数组，而 void * 是最通用的对象指针类型。

对于比较 int 元素的特定情况，const void * 参数应转换为 const int * 并取消引用以获得 int 元素的值比较的。比较函数应该 return 一个负值、零值或正值，以指示被比较的两个元素的相对顺序。对于int类型的元素进行升序排序，比较合适的比较函数如下：

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;
}

用于按降序顺序对 int 元素进行排序的比较函数与上述类似，但具有 -1 和 1 return 值交换。

您的 insort() 函数需要与比较函数不同的 return 值，returning 0 而不是负值。为了与您的 insort() 函数兼容，需要对函数进行如下修改：

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);
}

对于标准 C（和 C++？），void * 上的指针算法是不允许的，因为指针算法只允许指向 complete 对象类型的指针，并且 void 根据定义是 不完整 对象类型。一些编译器（例如 GCC）允许 void * 的指针算术作为 C 标准的扩展，就指针算术而言，将其视为与 char * 相同。可移植代码应避免在 void * 上进行指针运算。为了便于移植，您的 insort() 函数可以修改如下：

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;
        }
    }
}

Answer 2

在 C++ 中，您不会丢弃类型信息。

而不是

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);

你应该写

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; 
}

请注意，您忽略了第一个元素，break 看起来很可疑。当您发现某处出现问题时，通常需要移动多个元素。

正确的插入排序 (adapted from here) 应该是

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));
    }
}

如何使用未知参数写入排序。不能用 void*/ 迭代

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

c++

sorting

insertion-sort