使用void指针的C中的泛型列表 [英] Generic List in C using void pointer

问题描述

我正在尝试创建一个通用列表，该列表将允许输入任何类型.但是，我在is_element_of函数的比较中遇到了问题(因为我正在使用void指针).有什么帮助吗?

I'm trying to create a generic list that will allow any type to be entered. However, I am having problems with the comparism in the is_element_of function (since I am making use of void pointers). Any help?

 typedef struct Item{ 
            void* data;
        } Item;

    typedef struct Node{
        Item Item; 
        struct Node* next; 
        struct Node* previous;
    } Node;

    typedef Node* List;

bool is_element_of(Item Item, List *pointertolist) {
    bool isinlist = false;
    Node *scan = *pointertolist; 
    while (scan->next != NULL) { 
        if ((scan->Item.data) == (Item.data)) {
            printf("Match!");
            isinlist = true;
        } else {
            printf("No Match!");
            isinlist = false;
        }
        scan = scan->next; 
    }

    return isinlist;
}

推荐答案

您需要将类型识别操作委派给单独的函数，然后通过函数指针将该函数附加到列表中.我已经很自由地将您的结构类型定义更改为我以前使用过的东西，这让我觉得更加自然.随时不同意.

You'll need to delegate type-aware operations to a separate function, then attach that function to your list via a function pointer. I've taken the liberty of changing your struct type definitions to something I've used before that I feel is a little more natural. Feel free to disagree.

struct Node {
  void *data;
  struct Node *prev;
  struct Node *next;
};

除非您打算让Item结构类型保留除void *之外的任何其他内容，然后再将其删除.抽象是一件好事，但是有些事情太过分了.就我个人而言，我认为不创建一堆typedef更干净，而且我真的不喜欢typedef指针类型(指针语义是特殊的，不应隐藏) ).当然是YMMV.

Unless you intend for the Item struct type to hold anything other than a void *, then get rid of it. Abstraction is a Good Thing, but there is such a thing as going overboard. Personally, I think it's cleaner to not create a bunch of typedefs, and I really don't like typedef'ing pointer types (pointer semantics are special and should not be hidden). Of course, YMMV.

struct List {
  struct Node *head;
  struct Node *tail;
  int (*cmp)( const void *, const void *);
};

我已经修改了您的List类型，以包含头和尾指针以及指向比较函数的指针.您可以使用此结构创建任何类型的列表.您需要做的就是为该类型创建一个比较函数，并将其附加到列表中.例如，如果您希望列表包含整数:

I've modified your List type to contain your head and tail pointers, as well as a pointer to a comparison function. You can use this structure to create lists of any type; all you need to do is create a comparison function for that type and attach it to the list. For example, if you want your list to contain integers:

int compareInt( const void *lhs, const void *rhs )
{
  const int *llhs = (const int *) lhs;  
  const int *lhrs = (const int *) rhs;  

  if ( *llhs < *lrhs )                  
    return -1;
  else if ( *llhs > *lrhs )
    return 1;

  return 0;
}

比较函数遵循与qsort所使用的模型相同的模型；它使用两个参数const void *并返回一个int值-如果lhs<则返回-1. rhs，如果lhs> rhs则为1，如果lhs == rhs则为0.

The comparison function follows the same model as those used by qsort; it takes two parameters of const void * and returns an int value -- -1 if lhs < rhs, 1 if lhs > rhs, and 0 if lhs == rhs.

struct List intList = { NULL,  NULL, compareInt };

bool contains( const Item data, struct List *l ) 
{
  bool result = false;

  assert( l != NULL && l->cmp != NULL);

  struct Node *cur = l->head;

  while ( cur != NULL )
  {
    if ( l->cmp( cur->data, data ) == 0 )
    {
      result = true;
      break;
    }
    cur = cur->next;
  }

  return result;
}

因此，您的函数将遍历列表并比较值，如果找到匹配项，则返回true，否则返回false.

So your function will walk through the list and compare values, returning true if it finds a match, false otherwise.

现在，这种方法有很多缺点.它很复杂，很杂乱，可能很难遵循，可能涉及到很多的内存管理，并且您失去了类型安全性的任何冒充.没有什么可以阻止您将错误的函数与列表相关联，或者混淆列表中的类型.但是，它确实允许您创建可以处理任何类型的通用"容器，并且可以添加新类型，而无需掌握基本的容器逻辑.您只需为每种类型实现一个新的比较功能.

Now, this approach has a lot of drawbacks; it's complex, it's messy, it can be hard to follow, it can involve a lot of memory management, and you lose any pretense of type safety. There's nothing to stop you from associating the wrong function with a list, or mixing up types within the list. But, it does allow you to create "generic" containers that can handle any type, and you can add new types without having to hack the basic container logic. You only need to implement a new comparison function for each type.

尽管，老实说，您不仅应该实现比较功能，而且还应该实现赋值，复制，显示和取消分配功能，以相同的方式将它们附加到列表，以及轻量级的类型识别接口.每种类型.它是更多的代码，但从长远来看，它将节省您的胃灼热.

Although, to be honest, you should implement not only comparison functions, but assignment, copy, display, and deallocation functions as well, attaching them to the list in the same way, along with a lightweight, type-aware interface for each type. It's more code, but it will save you heartburn in the long run.

这篇关于使用void指针的C中的泛型列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！