如何在C中处理具有不同类型的类似数据结构 [英] How are similar data structures with different types handled in C.

问题描述

回到 C 被广泛使用的日子里， C ++ ，怎么样？数据结构处理？我的意思是在 C ++ 中创建数据结构时，我们通常会使用 templates ，这对于程序员。使用 C ++ ，您可以实现链接列表（或其他一些数据结构），并始终使用不同的数据类型。



根据我的理解，在 C 或任何其他不支持模板元编程的语言中，你必须重写特定数据中的所有代码当你想改变它的节点类型时的结构。



ie;类型 int 的链接列表写在 C 中。如果你想让同一个链表与 double 一起使用，你怎么做？



Unix， Windows（非常大的部分），My SQL .... [etc]用C语言编写。它们必须包含许多数据结构。那些编写这些软件的程序员是否重新编写了使用不同数据类型的所有类似数据结构？或者是否使用了其他任何方法？

Back in the days when C was widely used than C++, how was the data structures handled ? I mean when creating data structures in C++, we usually get the use of templates, which is a huge advantage for the programmer. With C++ you can implement a linked list (or some other data structure) once and use it all the time with different data types as want.

With my understanding, in C or any other language which do not support template meta-programming you have to rewrite all the code in a particular data structure when you want to change it's node type.

i.e; A linked list of type int is written in C. If you want the same linked list to work with doubles, how do you do that ?

Unix, Windows (a very large portion), My SQL....[etc] is written in C. They must contain dozens of data structures. Did those programmers who wrote those software, rewrote all the similar data structures that work with different data types ? Or Was any other method used ?

推荐答案

有很多方法可以实现容器示例。它们都不像使用模板/泛型一样干净。



1.一个技巧是在容器实现中使用void指针，然后存储指向所需项目的指针存储在容器中。当然，您必须使用此实现进行丑陋的转换，并且与C ++模板相比，您使用的指针是不必要的，您可以在不使用分配的情况下按值存储项目。如果你想存储像char和short这样的基本类型，你可以将它们转换为指针并将它们直接按值存储到容器中，但如果void *的大小大于你想要存储的基元，你仍然会以这种方式浪费空间。



2.你在C ++中使用模板做的很多事情是用C语言完成的。我已经看过例如动态数组实现，你可以在其中生成通过使用宏声明它的给定类型的动态数组的源代码：

There are many ways to implement for example containers. None of them are so clean as using templates/generics.

1. One trick is using void pointers in the container implementation and later you store pointers to the items you want to store in the container. Of course you have to do ugly casts with this implementation and you are using pointers unnecessary compared to C++ templates where you can store the items by value without allocations. If you want to store primitive types like char and short you can cast these into pointers and store them directly by value to the container but your are still wasting space this way if the size of the void* is larger than the primitive you want to store.

2. Many things that you are doing with templates in C++ were done with macros in C. I've seen for example dynamic array implementation where you could generate the source code of the dynamic array for a give type by declaring it with a macro:

// The header file:
typedef struct SMyData
{
    int data0;
    char data1;
    float data2;
} SMyData;


DECLARE_DYN_ARRAY_FUNCTIONS(SMyData)

// the c file:
DEFINE_DYN_ARRAY_FUNCTIONS(SMyData)


// The above macros declared/defined functions like:
void DynArray_SMyData_Add_(DynArray_SMyData* arr, const SMyData* item);
void DynArray_SMyData_Remove(DynArray_SMyData* arr, const SMyData* item);
...

缺点：宏中的大量代码不仅仅是丑陋的bug - 你不能在宏中放置断点。



3.

我在链接列表实现中看到的另一个很好的技巧：

Drawbacks: Lots of code in macros is not only ugly bug undebuggable - you can not place breakpoints in macros.

3.
Another nice trick I've seen in C in a linked list implementation:

typedef struct LinkedListNode
{
    struct LinkedListNode* next;
} LinkedListNode;

void LinkedList_Append(LinkedListNode** head, LinkedListNode* node);
void LinkedList_Remove(LinkedListNode** head, LinkedListNode* node);

#define NODE_TO_DATA(node_ptr, node_member_name, data_type) \
    (data_type*)((char*)node_ptr - offsetof(data_type, node_member_name))

struct SMyNode
{
    int mydata;
    char mydata2;
    float mydata3;
    LinkedListNode node;
};

LinkedListNode* g_Head = NULL;

void LinkedListTest()
{
    // building the list
    LinkedListNode* it;
    SMyNode node0, node1;
    // TODO: fill in nodes with data
    LinkedList_Append(&g_Head, &node0.node);
    LinkedList_Append(&g_Head, &node1.node);

    // iteration, contains a bit of typecast but it isn't that
    it = g_Head;
    while (it)
    {
        SMyNode* node = NODE_TO_DATA(it, node, SMyNode);
        // TODO: use node
        it = it->next;
    }
}

这个技巧适用于任何由节点/项目组成的数据结构（例如在树木的情况下）必须通过将它们打包在一起来分配，就像阵列一样。基本上你的数据包含容器相关的东西，而不是容器包含你的数据......

This trick works with any data structures that consist of nodes/items (for example in case of trees) that don't have to be allocated by packing them together like in case of an array. Basically your data contains the container related stuff and not the container contains your data...

这篇关于如何在C中处理具有不同类型的类似数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！