Двойное указание при передаче массива в функцию

Question

Я хотел освежить свои знания алгоритмов, и я использовал следующую книгу: Алгоритмы в двух словах

На странице 65 они печатают алгоритм для вставки сортировки. Алгоритм довольно прост и понятен. Моя проблема связана с тем, как они это реализовали. Я работаю в основном на управляемых языках (C#/Java), поэтому мой указатель на кунг-фу немного ржавый. Вот пример кода, который они предоставляют:

void sortPointers(void **ar, int n, int(*cmp)(const void *, const void *)) {
    int j;
    for(j = 1; j < n; j++) {
        int i = j - 1;
        void* value = ar[j];

        while(i >= 0 && cmp(ar[i], value) > 0) {
            ar[i+1] = ar[i];
            i--;
        }

        ar[i+1] = value;
    }
}

Вот что я добавил, чтобы иметь рабочий пример:

int cmp(const void* t1, const void* t2) {
    if(t1 > t2) {
        return 1;
    }
    else if(t2 > t1) {
        return -1;
    }
    else {
        return 0;
    }
}

void main() {
    int values[] = { 51, 3, 5, 60, 9, 2, 7};

    sortPointers((void**)values, 7, cmp);

    for(int i = 0; i < 7; i++) {
        cout << values[i] <<  " ";
    }
}

Пока это работает, я не совсем понимаю, почему и как? Кроме того, почему (void **) приведение в основной функции работает, почему они использовали косвенное указание двойного указателя и т. Д.?

Еще в школе единственное место, где мы использовали множественное косвенное обращение, было при динамическом размещении многомерных массивов. Единственное другое использование, которое я знаю, - это когда вам нужно изменить адрес, который содержит указатель, который вы передаете методу.

Кроме того, я пошел дальше и изменил код так, чтобы он выглядел следующим образом:

void sortPointers2(int* arr, int n, int (*cmp)(int, int)) {
    int j;
    for(j = 1; j < n; j++) {
        int i = j - 1;
        int value = arr[j];

        while(i >= 0 && cmp(arr[i], value) > 0) { 
            arr[i+1] = arr[i];
            i--;
        }

        arr[i+1] = value;
    }
}

int cmp2(int t1, int t2) {
    if(t1 > t2) {
        return 1;
    }
    else if(t2 > t1) {
        return -1;
    }
    else {
        return 0;
    }
}

void main() {
    int values[] = { 51, 3, 5, 60, 9, 2, 7};

    sortPointers2(values, 7, cmp2);

    for(int i = 0; i < 7; i++) {
        cout << values[i] <<  " ";
    }
}

Я почти уверен, что упускаю что-то фундаментальное и очевидное. Спасибо, что кто-то прочитал это и поделился идеей или двумя. Дайте мне знать, если вам нужны какие-либо дополнительные детали или я испортил терминологию.

EDIT: исправлена ​​опечатка в первой функции cmp

Answer 1

Если я правильно следую примеру, они используют void ** потому что это действительно (void *)[]; массив нетипизированной памяти. Функция сравнения дает два указателя на нетипизированную память (void *) и просят сравнить данные.

Что вы не понимаете, так это то, что в первом примере ваш массив должен быть массивом указателей, а не массивом значений. Ваш массив должен выглядеть так:

int *val0 = malloc(sizeof(int)); *val0 = 51;
int *val1 = malloc(sizeof(int)); *val1 = 3;
// ... for all values
int *values[] = { val0, val1, val2, ... };

Тогда функция сравнения cmp должен возвращать значение сравнения на основе значений, а не указателей, которые ему даны. Код:

int cmp(const void* t1, const void* t2) {
    if((const int)(*t1) > (const int)(*t2)) {
        return 1;
    }
    else if((const int)(*t2) > (const int)(*t1)) {
        return -1;
    }
    else {
        return 0;
    }
}

Таким образом, учитывая указатели на нетипизированную память, ваша функция сравнения найдет два целых числа в этих указателях и сравнит эти значения.

Единственная причина, по которой ваш cmp Функция работала с кодом книги, потому что вы говорили функции сортировки, что ваш массив полон указателей на нетипизированную память, тогда как на самом деле это был просто массив целых чисел. Ваша функция сравнения будет затем давать указатели на память, которые на самом деле были просто целыми числами, а затем сравнивать указатели, как если бы они были значениями. В этом случае они были.

Причина, по которой алгоритм книги использует void ** потому что таким образом это является общим. sort Функция может взять массив, содержащий любые данные, и передать общие данные в функцию сравнения, которая может разыменовывать указатели и интерпретировать данные по тем адресам, которые она пожелает.