c - 可变大小数组

Question

我正在开发我的第一个大项目，我需要可变大小的数组(或者巨大的固定大小的数组，我基本上是在创建一种新的编程语言“所以是的”)

我至少想要这些功能:

ARRAY_NEW(type, arr) // Or something else for the arguments: Be creative :)
ARRAY_FREE(arr)
ARRAY_PUSH(arr, item)
ARRAY_POP(arr)
ARRAY_SIZE(arr)
// Optional, but would increase performance
ARRAY_ADD(arr, index, item)
ARRAY_REMOVE(arr  index)
ARRAY_SPLIT(arr, index, length)
ARRAY_MAP(arr, lambda) // Macros suck? You suck!

我使用了几种方法来实现这些可变大小的数组:

用于为每个数组名称创建 _length 后缀的宏(我将其称为 ARRAY)

#define NEWARRAY(type, name) (type* name = NULL; size_t name ## _length = 0;)
NEWARRAY(int, array);

用于在数组 - cells - 1 中存储长度的宏，其中 cells 是存储 size_t 所需的单元数:(称为 ARRAYLIST)

char[] array:
0 0 0 1 4 97

将是一个长度为 1 且值为 ['a'] 的数组(array[0] 将在我的实现中返回 'a'，这正是我喜欢的)注意:到目前为止，这是我唯一实现了 ARRAY_ADD 和 ARRAY_REMOVE 的数据类型

以自定义数据类型存储所有数组:(ARRAYTYPE 怎么样？)

struct ArrayType {
    int length;
    void** values;
}

我目前正在尝试分块数组(每隔几次 PUSH 分配新内存)(我们称之为 CHUNKEDARRAY 我认为它会像我使用 ARRAYLIST 那样存储长度。

我主要使用 2，有时使用 1(因为 2 是 100% 安全的，如果 name_length 已经声明，则 1 会失败(使其... 99% 安全)我并不真正使用 3，除非性能是一个问题，因为输入 array.values[0] 需要更多时间来编写并且看起来更糟)

您能给我更多一些使可变大小数组变得更容易的提示和技巧吗？你用什么？对我目前的做法有什么意见吗？还有更多可变大小且可在 C 中实现的数据结构吗？我在可变大小的数组上挣扎了很长一段时间。

Answer 1

首先会有一个linked list 。简单:

----------        ----------
- Data   -        - Data   -    
----------        ----------   
- Pointer- - - -> - Pointer-  
----------        ----------

但您也可以使用双链表。

然后就会有 heap数据结构。这些对于 sorting 非常有效和/或O(log(n))时间内的数据访问。

您可以使用链表或堆来替代简单数组。您可以使用各种算法对它们进行排序，例如O(n log(n)) 时间，并且在调整大小(添加/删除)时没有太多的计算开销(添加/删除) - 这与您可能已经知道，经典数组总是需要复制。

然后是我最喜欢的: don't re-invent the wheel (特别是不适用于“大”项目)-数据结构或“库”，就像有些人所说的那样。

当然有hash - map /集/表也可能有助于在 O(1) 时间内访问数据。