有几种可能的选择:
如果我需要树形结构,我会毫不犹豫地编写一棵树。是否有广泛使用的类库含有这样的结构(例如C++的boost库)?还是因为你必须存储void *而被认为是不好的风格?
非常感谢您分享的经验!
这完全取决于您将在数据结构上执行哪些操作。如果您将通过索引检索数据(例如,data [3]),那么列表是一个可怕的选择,因为每次读取都需要遍历整个列表。如果您将经常插入到第一个位置(例如,data [0] = x),那么数组将非常糟糕,因为每次插入都需要移动所有数据。
如果您要使用std :: vector,则动态数组可能是最佳替代品。但是也许std :: vector不是正确的选择。
我记得有一段时间前,我读过苹果公司发布的一份文档,其中说这样的事情可以用类似下面的结构天真地实现:
struct {
void *data; //other type rather than void is easier
int length;
} MyArray;
MyArray *MyArrayCreate(){
//mallocate memory
return ...
}
void MyArrayRelease(){
free(...);
}
MyArrayInsertAt(MyArray *array, index, void *object){
if (length < index){
//mallocate again, copy data
//update length
}
data[index] = object;
}
这样它就可以像这样使用:
MyArray *array = MyArrayCreate();
MyArrayInsertAt(array, 5, something);
MyArrayRelease(array);
MyArrayInsertAt() 函数的性能不会获得奖项,但它可能是非高要求程序/应用的解决方案。
我就是找不到那个链接...也许有人也看到了?
添加: 我发现 GNU NSMutableArray (Objective-C) 方法的实现是用 C 语言完成的,它们做的与上述方法相同。每次需要添加一个对象且无法适应数组时,它们会将数组大小加倍。请参见第 131 至 145 行。
动态链表在C语言中被广泛使用,特别是当需要存储的项目数量未知时。
向量是一种动态数组,内部实现为动态数组。我建议您使用向量,因为机器优化了检索连续的内存位置,而链表不会存储在连续位置。
话虽如此,如果您的用例不需要通过索引快速检索元素,则也可以选择链表。链表还具有不浪费空间的好处(不像动态数组那样在即将满时加倍),并且在开头或元素之间插入比数组更便宜。
每种数据结构都有其优缺点。
静态数组:适用于查找表和在程序执行期间大小不变的数据。它们在程序启动时分配,因此您无需以任何方式管理此内存。缺点是您无法调整静态数组的大小或释放它 - 它会一直存在,直到程序终止。
动态增长数组:易于管理的数据结构,几乎可以替代C ++中的向量数组。缺点是在运行时分配内存的开销,但如果一次性分配更大的块,则可以缓解这种情况。
链表:如果要有很多元素,请注意,如果不使用内存池单独分配每个元素可能会导致内存浪费和碎片化。
O(n)
的情况下进行n
次插入。这并不意味着每个插入都是O(1)
。例如,请参见https://dev59.com/OXVC5IYBdhLWcg3wtzyt。 - NPE