Как использовать указатели на функции в полиморфизме?

Question

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

Answer 1

Вот простой универсальный интерфейс сортировки, сортировка вставкой, реализованная через этот интерфейс, и некоторый тестовый код, демонстрирующий его использование:

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

struct sort_interface {
    // number of elements
    size_t nmemb;

    // passed through to 'arg' of compare() and swap()
    void *arg;

    // compares elements at 'i' and 'j'
    int (*compare)(void *arg, size_t i, size_t j);

    // swaps elements at 'i' and 'j'
    void (*swap)(void *arg, size_t i, size_t j);
};

static void insertion_sort (struct sort_interface iface)
{
    for (size_t i = 0; i < iface.nmemb; i++) {
        size_t j = i;
        while (j > 0) {
            if (iface.compare(iface.arg, j - 1, j) <= 0) {
                break;
            }
            iface.swap(iface.arg, j - 1, j);
            j--;
        }
    }
}

static int func_comparator (void *arg, size_t i, size_t j)
{
    int *arr = arg;

    if (arr[i] < arr[j]) {
        return -1;
    }
    if (arr[i] > arr[j]) {
        return 1;
    }
    return 0;
}

static void func_swap (void *arg, size_t i, size_t j)
{
    int *arr = arg;

    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

int main (int argc, char *argv[])
{
    int arr[] = {7, 6, 8, 2, 9, 1, 156, 1, 62, 1671, 15};
    size_t count = sizeof(arr) / sizeof(arr[0]);

    struct sort_interface iface;
    iface.nmemb = count;
    iface.arg = arr;
    iface.compare = func_comparator;
    iface.swap = func_swap;

    insertion_sort(iface);

    for (size_t i = 0; i < count; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Возможно, вы также захотите взглянуть на функцию qsort () стандартной библиотеки C, которая тоже использует компаратор указателя функции, но несколько ограничен по сравнению с вышеупомянутым. В частности, предполагается, что вы сортируете непрерывный массив, и если у вас есть указатели на элементы или их элементы, они будут повреждены (но интерфейс выше позволяет исправлять указатели в swap ()).

Вот пример того, как использовать интерфейс qsort (), а также реализация сортировки вставкой, которая использует тот же интерфейс, что и qsort ():

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

static void insertion_sort (void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *))
{
    char temp[size];

    for (size_t i = 0; i < nmemb; i++) {
        size_t j = i;
        while (j > 0) {
            char *x = (char *)base + (j - 1) * size;
            char *y = (char *)base + j * size;
            if (compar(x, y) <= 0) {
                break;
            }
            memcpy(temp, x, size);
            memcpy(x, y, size);
            memcpy(y, temp, size);
            j--;
        }
    }
}

static int int_comparator (const void *ve1, const void *ve2)
{
    const int *e1 = ve1;
    const int *e2 = ve2;

    if (*e1 < *e2) {
        return -1;
    }
    if (*e1 > *e2) {
        return 1;
    }
    return 0;
}

int main (int argc, char *argv[])
{
    int arr[] = {7, 6, 8, 2, 9, 1, 156, 1, 62, 1671, 15};
    size_t count = sizeof(arr) / sizeof(arr[0]);

    qsort(arr, count, sizeof(arr[0]), int_comparator); // or insertion_sort()

    for (size_t i = 0; i < count; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}