练习34:动态数组
动态数组是自增长的数组,它与链表有很多相同的特性。它通常占据更少的空间,跑得更快,还有一些其它的优势属性。这个练习会涉及到它的一些缺点,比如从开头移除元素会很慢,并给出解决方案(只从末尾移除)。
动态数组简单地实现为指针的数组,它是预分配内存的,并且指向数据。在链表中你创建了完整的结构体来储存void *value
指针,但是动态数组中你只需要一个储存它们的单个数组。也就是说,你并不需要创建任何其它的指针储存上一个或下一个元素。它们可以直接索引。
这个头文件向你展示了static inline
的新技巧,它就类似#define
宏的工作方式,但是它们更清楚,并且易于编写。如果你需要创建一块代码作为宏,并且不需要代码生成,可以使用static inline
函数。
为链表生成for
循环的LIST_FOREACH
不可能写为static inline
函数,因为它需要生成循环的内部代码块。实现它的唯一方式是灰调函数,但是这不够块,并且难以使用。
之后我会修改代码,并且让你创建DArray
的单元测试。
这占你展示了另一种处理复杂代码的方法,观察头文件并阅读单元测试,而不是一头扎进.c
实现中。这种“具体的抽象”让你理解代码如何一起工作,并且更容易记住。
DArray
在你需要这些操作时占优势。
- 迭代。你可以仅仅使用基本的
for
循环,使用DArray_count
和DArray_get
来完成任务。不需要任何特殊的宏。并且由于不处理指针,它非常快。 - 销毁。你只需要以两个操作销毁结构体和
content
。但是List
需要一些列的free
调用同时遍历每个元素。 - 克隆。你只需要复制结构体和
content
,用两步复制整个结构。List
需要遍历所有元素并且复制每个ListNode
和值。 - 排序。你已经见过了,如果你需要对数据排序,
List
非常麻烦。DArray
上可以实现所有高效的排序算法,因为你可以随机访问任何元素。 - 大量数据。如果你需要储存大量数据,
DArray
由于基于content
,比起相同数量的ListNode
占用更少空间而占优。
然而List
在这些操作上占优势。
- 分割和连接。
List
只需要复制一些指针就能完成,但是需要复制涉及到的所有数组。 - 少量数据。如果你只需要存储几个元素,通常使用
List
所需的空间要少于DArray
,因为DArray
需要考虑到日后的添加而扩展背后的空间,但是List
只需要元素所需的空间。
像往常一样,浏览每个函数和操作,并且执行防御性编程检查,以及添加先决条件、不变量等任何可以使实现更健壮的东西。
- 改进单元测试来覆盖耕作操作,并使用
for
循环来测试迭代。 - 研究
DArray
上如何实现冒泡排序和归并排序,但是不要马上实现它们。我会在下一张实现DArray
的算法,之后你可以完成它。 - 观察
DArray_expand
如何使用固定增长(size + 300
)来实现。通常动态数组都以倍数增长()的方式实现,但是我发现它会花费无用的内存并且没有真正取得性能收益。测试我的断言,并且看看什么情况下需要倍数增长而不是固定增长。