C'ye sınıf şablonuna benzer genel kod yazmanın en iyi yolu nedir?

Question

C dilinde genel türüyle AVL ağacı yazmam gerekiyor. Bildiğim en iyi yol, [void *] kullanımı ve oluşturma, kopyalama, atama ve imha için bazı işlevler yazmaktır. Lütfen bana biraz daha iyi bir yol söyle.

Answer 1

Size, C'deki jenerik işlevlerine nasıl ulaşabileceğinize dair bir örnek vereceğim. Örnek, bağlantılı bir listede yer alıyor, ancak gerekirse AVL ağacınıza uyarlayabildiğinizden eminim.

Öncelikle liste öğesi için bir yapı tanımlamanız gerekecektir. Olası bir (en basit uygulama):

Bilgilerinizi saklamak için gidiyoruz "konteyner" olarak hareket edecek 'veri' ve 'gelecek' doğrudan bağlantılı elemana referanstır

struct list_element_s { 
    void *data; 
    struct list_element_s *next; 

}; 
typedef struct list_element_s list_element; 

. (NOT: İkili ağaç öğeniz, sağ/sol alt öğelere bir başvuru içermelidir).

Öğe yapısını oluşturduktan sonra, liste yapınızı oluşturmanız gerekir. İyi bir uygulama, fonksiyonlara işaret eden bazı üyelere sahip olmaktır: yıkıcı ('veri' ile tutulan belleği boşaltmak için gerekli) ve karşılaştırıcı (listenizden iki öğeyi karşılaştırabilmek için).

listesi yapı uygulama aşağıdaki gibi görünebilir: Eğer veri yapısını tasarladıktan sonra

struct list_s { 
    void (*destructor)(void *data);  
    int (*cmp)(const void *e1, const void *e2); 
    unsigned int size; 
    list_element *head; 
    list_element *tail; 

}; 
typedef struct list_s list; 

, veri yapısı arayüzünü tasarlamak gerekir. en Listemiz sonrasında en basit arayüzü olacak diyelim:

nmlist *list_alloc(void (*destructor)(void *data)); 
int list_free(list *l); 
int list_insert_next(list *l, list_element *element, const void *data); 
void *list_remove_next(list *l, list_element *element); 

Nerede:

• list_alloc: Listenizdeki için bellek alocate edecektir.
• list_free: liste için ayrılmış bellek ve list_element (ler) tarafından tutulan tüm 'veriler' boş bırakılacaktır.
• list_insert_next: 'element' öğesinin yanında yeni bir öğe ekler. 'Eleman' NULL ise, ekleme listenin başında yapılacaktır.
• list_remove_next: 'element-> next' tarafından tutulan & return (void *) 'data' öğesini kaldıracaktır. 'Element' NULL ise, "list-> head removal" işlemini gerçekleştirir.

Ve şimdi fonksiyonları uygulama:

list *list_alloc(void (*destructor)(void *data)) 
{ 
    list *l = NULL; 
    if ((l = calloc(1,sizeof(*l))) != NULL) { 
     l->size = 0; 
     l->destructor = destructor; 
     l->head = NULL; 
     l->tail = NULL; 
    } 
    return l; 
} 

int list_free(list *l) 
{ 
    void *data; 
    if(l == NULL || l->destructor == NULL){ 
     return (-1); 
    }  
    while(l->size>0){  
     if((data = list_remove_next(l, NULL)) != NULL){ 
      list->destructor(data); 
     } 
    } 
    free(l); 
    return (0); 
} 

int list_insert_next(list *l, list_element *element, const void *data) 
{ 
    list_element *new_e = NULL; 
    new_e = calloc(1, sizeof(*new_e)); 
    if (l == NULL || new_e == NULL) { 
     return (-1); 
    } 
    new_e->data = (void*) data; 
    new_e->next = NULL; 
    if (element == NULL) { 
     if (l->size == 0) { 
      l->tail = new_e; 
     } 
     new_e->next = l->head; 
     l->head = new_e; 
    } else { 
     if (element->next == NULL) { 
      l->tail = new_e; 
     } 
     new_e->next = element->next; 
     element->next = new_e; 
    } 
    l->size++; 
    return (0); 
} 

void *list_remove_next(list *l, list_element *element) 
{ 
    void *data = NULL; 
    list_element *old_e = NULL; 
    if (l == NULL || l->size == 0) { 
     return NULL; 
    } 
    if (element == NULL) { 
     data = l->head->data; 
     old_e = l->head; 
     l->head = l->head->next; 
     if (l->size == 1) { 
      l->tail = NULL; 
     } 
    } else { 
     if (element->next == NULL) {  
      return NULL;  
     }  
     data = element->next->data; 
     old_e = element->next; 
     element->next = old_e->next; 
     if (element->next == NULL) { 
      l->tail = element; 
     } 
    } 
    free(old_e); 
    l->size--; 
    return data; 
} 

Ve şimdi, basit jenerik bağlantılı liste uygulamasını nasıl kullanılacağı.Aşağıdaki örnekte liste yığını gibi davranmaktadır: Bunun yerine "int * j" daha karmaşık yapılar başvuran bir işaretçiyi kullanarak

#include <stdlib.h> 
#include <stdio.h> 
#include "nmlist.h" 

void simple_free(void *data){ 
    free(data); 
} 

int main(int argc, char *argv[]){ 
    list *l = NULL; 
    int i, *j; 

    l = list_alloc(simple_free); 
    for(i = 0; i < 10; i++){ 
     j = calloc(1, sizeof(*j)); 
     if(j != NULL){ 
      *j = i; 
      list_insert_next(l, NULL, (void*) j); 
     } 
    } 

    for(i = 0; i < 10; i++){ 
     j = (int*) list_remove_next(l, NULL); 
     if(j != NULL){ 
      printf("%d \n", *j); 
     } 
    } 

    list_free(l); 

    return (0); 
} 

Not. Eğer yaparsanız, 'list-> destructor' işlevinizi buna göre değiştirmeyi unutmayın.

Answer 2

Alex ne dedi. C, void * var.

C içinde çalışmanız gerektiğini varsayalım, ancak ... Neden kütüphaneye oluşturma/kopyalama/atama/imha etme işlevlerini sağlamanız gerekiyor? Bu kütüphanenin hangi özellikleri AVL ağacı kodunu bu işlemleri kullanacak?

Arama ağacındaki önemli işlemler ekleme, silme ve arama, düzeltmedir? Bu işlemlerin tümü için bir karşılaştırma işlevi sağlamanız gerekir, ancak bu kütüphanedeki istemcilerin diğer tüm işlemleri gerçekleştirmesine izin vermelisiniz. Bu durumda muhtemelen daha basittir.

Answer 3

C'deki gerçek, performans jeneriklerini yapmak için önişlemciyle uğraşırsınız. Bu yaklaşım, C++ şablon yaklaşımının birçok dezavantajına sahiptir; yani, tüm (çoğu, zaten) kodun, başlık dosyalarında bulunması ve hata ayıklama ve testin bir acı olması gerekir. Avantajlar da var; üstün performans elde edebileceğiniz ve derleyicinin işleri hızlandırmak için her tür iniş yapmasına izin verdiğinizi, dolaylılığı azaltarak tahsisleri en aza indirgeyebildiğinizi ve tür güvenliğinin bir modicum olmasını sağlayabilirsiniz.

tanım

int my_int_set(int x); 
#define HASH_SET_CONTAINED_TYPE int 
#define HASH_SET_TYPE my_int_set 
#define HASH_SET_FUNC hash_int 
#include "hash_set.h" 

(en bir karma set var düşünelim) Ve sonra kullanmak için, sadece yukarıda oluşturduğunuz türü kullanmak gibi görünür: Dahili olarak

my_int_set x; 
my_int_set_init(&x); 
my_int_set_add(&x, 7); 
if (my_int_set_check(&x, 7)) printf("It worked!\n"); 
... 
// or, if you prefer 
my_int_set *x = my_int_set_create(); 

, bu bir sürü jeton yapıştırma, vb. tarafından uygulanır ve (yukarıda belirtildiği gibi) test etmek için büyük bir acıdır.

Yani böyle bir şey:

#ifndef HASH_SET_CONTAINED_TYPE 
    #error Must define HASH_SET_CONTAINED_TYPE 
#endif 
... /// more parameter checking 

#define HASH_SET_ENTRY_TYPE HASH_SET_TYPE ## _entry 
typedef struct HASH_SET_ENTRY_TYPE ## _tag { 
    HASH_SET_CONTAINED_TYPE key; 
    bool present; 
} HASH_SET_ENTRY_TYPE; 
typedef struct HASH_SET_TYPE ## _tag { 
    HASH_SET_TYPE ## _entry data[]; 
    size_t elements; 
} HASH_SET_TYPE; 

void HASH_SET_TYPE ## _add(HASH_SET_CONTAINED_TYPE value) { 
    ... 
} 
... 
#undef HASH_SET_CONTAINED_TYPE 
... // remaining uninitialization 

Hatta seçenekleri ekleyebilirsiniz; HASH_SET_VALUE_TYPE veya #define HASH_SET_DEBUG gibi.