Đúc chức năng con trỏ

Question

Tôi viết một chức năng tiếp nhận một con trỏ tới một hàm so sánh và một mảng của MyStructs và được cho là để sắp xếp mảng theo chức năng so sánh:

void myStructSort(
        struct MyStruct *arr, 
        int size, 
        int (*comp)(const struct MyStruct *, const struct MyStruct *)) { 
    qsort(arr, size, sizeof(struct MyStruct), comp); 
} 

Thật không may điều này không biên dịch vì qsort hy vọng bộ so sánh sẽ nhận được các đối số void * chứ không phải const struct MyStruct *. Tôi nghĩ về một số giải pháp tồi và đã tự hỏi giải pháp chính xác là gì.

Lựa chọn 1

Cast comp-int (*)(const void *, const void*). Biên dịch này nhưng là hành vi không xác định (xem this SO question).

Lựa chọn 2

Tạo một biến toàn cầu int (*global_comp)(const struct MyStruct *, const struct MyStruct *) và thiết lập global_comp=comp bên myStructSort. Sau đó, tạo một hàm:

int delegatingComp(const void *a, const void *b) { 
    return globalComp((const struct MyStruct *)a, (const struct MyStruct *)b); 
} 

Và trong myStructSort gọi qsort(arr, size, sizeof(struct MyStruct), delegatingComp). Vấn đề với điều này là biến toàn cục icky.

Lựa chọn 3

reimplement qsort. Đây là thực hành an toàn về mặt chức năng nhưng rất kém.

Có lựa chọn thứ tư hoàn hảo kỳ diệu không?

Sửa

tôi không thể thay đổi API của myStructSort và tôi biên soạn mã của tôi sử dụng gcc c99 -Wall -Wextra -Wvla.

Answer 1

Tùy chọn 2 ngắt an toàn luồng, vì vậy tôi sẽ không chọn loại đó.

Tùy chọn 3 chỉ đơn giản là sai khi bạn chỉ ra. Không có lý do để tái triển khai quicksort và có khả năng mắc lỗi.

Tùy chọn 1 là UB nhưng nó sẽ hoạt động trên bất kỳ trình biên dịch lành mạnh nào. Nếu bạn chọn tùy chọn này, hãy đảm bảo thêm nhận xét.

tôi cũng sẽ xem xét:

Tùy chọn 4. Thiết kế lại giao diện của myStructSort lấy int (*)(const void *, const void*) hoặc loại bỏ nó hoàn toàn và gọi qsort trực tiếp. Về cơ bản gửi nó trở lại architecht, bởi vì ông đã thực hiện một sự lựa chọn thiết kế kém.

Answer 2

cách tiếp cận sau chỉ hoạt động đối với gcc. Đó là một phần của phần mở rộng gnu. hơn nữa xin vui lòng tham khảo để https://gcc.gnu.org/onlinedocs/gcc-4.8.5/gcc/Nested-Functions.html#Nested-Functions

đầu tiên hãy chắc chắn rằng nguyên mẫu của qsort là trong such a form:

void qsort(void *base, size_t nmemb, size_t size, 
      int (*compar)(const void *, const void *)); 

sau đó bạn có thể:

void myStructSort(
        struct MyStruct *arr, 
        int size, 
        int (*comp)(const struct MyStruct *, const struct MyStruct *)) { 
    int comparator(const void * a, const void *b) { 
    return comp((const struct MyStruct *)a, (const struct MyStruct *)b); 
    } 
    qsort(arr, size, sizeof *arr, comparator); 
} 

Nhưng một lần nữa, vì nó sử dụng phần mở rộng gnu, don' t mong đợi quá nhiều tính di động.

GIỚI THIỆU BÌNH LUẬN CỦA BẠN: đối với hiện đại gcc, tiêu chuẩn gnu là mặc định thay vì iso. cụ thể, mới nhất gcc nên sử dụng tiêu chuẩn gnu11. những người lớn tuổi đang sử dụng gnu89. vì vậy, tôi không biết về các tham số dòng lệnh của bạn, nhưng nếu không đặt -std, điều này sẽ hoạt động.

sau đây là ví dụ được lấy từ info gcc, chỉ trong trường hợp liên kết bị chết.nó cho thấy cách sử dụng giống như hàm lồng nhau:

bar (int *array, int offset, int size) 
{ 
    int access (int *array, int index) 
    { return array[index + offset]; } 
    int i; 
    /* ... */ 
    for (i = 0; i < size; i++) 
    /* ... */ access (array, i) /* ... */ 
} 

Answer 3

Nếu bạn đang sử dụng gcc, sau đó bạn có thể sử dụng qsort_r chức năng trong glibc kể từ 2.8, cho phép bạn chỉ định một chức năng so sánh với thêm một đối số người dùng cung cấp:

void qsort_r(void *base, size_t nmemb, size_t size, 
      int (*compar)(const void *, const void *, void *), 
      void *arg); 

Đây không phải là di động, tất nhiên, và nó đòi hỏi bạn phải xác định vĩ mô tính năng kiểm tra:

#define _GNU_SOURCE 

(Trên FreeBSD - và, có lẽ, Mac OS X - có một tương tự nhưng không tương thích qsort_r; sự khác biệt là người sử dụng bối cảnh -supplied argum ent được cung cấp như các số đầu tiên với chức năng so sánh, chứ không phải là tranh luận cuối cùng)

Nhưng nếu bạn có nó, nó cho phép bạn để tránh sự toàn cầu trong phương án 2:.

/* This struct avoids the issue of casting a function pointer to 
* a void*, which is not guaranteed to work. It might not be 
* necessary, but I know of no guarantees. 
*/ 
typedef struct CompContainer { 
    int (*comp_func)(const struct MyStruct *, const struct MyStruct *); 
} CompContainer; 

int delegatingComp(const void *a, const void *b, void* comp) { 
    return ((CompContainer*)comp)->comp_func((const struct MyStruct *)a, 
              (const struct MyStruct *)b); 
} 

void myStructSort(
       struct MyStruct *arr, 
       int size, 
       int (*comp_func)(const struct MyStruct *, 
           const struct MyStruct *)) { 
    const CompContainer comp = {comp_func}; 
    qsort_r(arr, size, sizeof(struct MyStruct), delegatingComp, &comp); 
} 

(Live on ideone)

Answer 4

Tùy chọn lành mạnh duy nhất là viết lại giao diện bạn đã tạo hoặc tạo giao diện mới.

I've done something very similar with bubble sort on another answer of mine.

Nói tóm lại, với C, bạn muốn chức năng sắp xếp của bạn để có dạng:

void* bubbleSort(void* arr, int (*compareFcn)(void*, void*), 
    size_t sizeOfElement, size_t numElements) 

Và chức năng so sánh của bạn để có dạng:

int compareFunction(void *a, void *b); 

Answer 5

Cách tiếp cận đúng là đúc từ void const * đến MyStruct const * trong hàm so sánh.

Điều này được xác định rõ cho đối tượng đầu tiên, bởi vì con trỏ được chuyển đến hàm so sánh được tạo bởi một dàn diễn viên từ MyStruct const * đến void const * và truyền con trỏ đến void về kiểu ban đầu. thực sự điều duy nhất đó là).Đối với các thành viên mảng khác, giả sử rằng đúc void const * đến char const *, thêm bù đắp của đối tượng, được tạo bằng cách nhân kích thước đối tượng với vị trí của đối tượng trong mảng và truyền trở lại void const * sẽ cung cấp một con trỏ có thể được đưa trở lại MyStruct const *.

Đó là giả định táo bạo nhưng thường hoạt động. Có thể có các trường hợp góc trong trường hợp không hoạt động, nhưng trong các trình biên dịch tổng quát, hãy nhập struct foo vào nhiều liên kết để đảm bảo rằng địa chỉ bắt đầu của thành viên mảng có khoảng cách là sizeof(struct foo).

Con trỏ hàm thường không an toàn và cần tránh vì các kiểu dữ liệu khác nhau có thể có các biểu diễn khác nhau - ví dụ: void * phải thể hiện mọi địa chỉ có thể vì nó có thể đã được chuyển đổi từ char *. a MyStruct * được đảm bảo có một số bit ít quan trọng nhất rõ ràng như bất kỳ đối tượng hợp lệ nào sẽ được căn chỉnh - vì vậy hoàn toàn có thể quy ước gọi cho các loại này có thể khác nhau.