向量(Vector)
Vector 是一种线性数据结构，其中的值按顺序存储，大小也会自动增大或缩小。Vector 是效率最高的线性数据结构之一，因为值的索引与缓冲区的索引直接映射，访问速度更快。DS 向量类允许我们使用 PHP 数组语法进行操作，但内部内存消耗比 PHP 数组少。它的 push、pop、get 和 set 操作时间不变。下面是 Vector 的一个示例：
Unresolved include directive in modules/ROOT/pages/ch12/ch12-06.adoc - include::example$Chapter12/3.php[]从前面的代码可以看出，我们可以使用 PHP 数组语法定义一个向量，也可以使用数组语法获取或设置值。不同之处在于，我们不能使用 PHP 数组语法添加新索引。为此，我们必须使用向量类的 push 方法。尝试设置或获取一个不存在的索引会在运行时抛出 OutofRangeException 异常。下面是前面代码的输出结果：
b
d
Size of vector: 4Map
映射是键值对的顺序集合。映射类似于数组，键可以是字符串、整数等，但键必须是唯一的。在 DS map 类中，键可以是任何类型，包括对象。它允许使用 PHP 数组语法进行操作，并保留插入顺序。其性能和内存效率也与 PHP 数组类似。当内存大小降低时，它还会自动释放内存。从下面的性能图中可以看出，当我们从一个大数组中删除项目时，DS 库中的 map 实现要比 PHP 数组快得多：
Set
集合也是序列，但集合只能包含唯一值。集合可以存储任何值，包括对象，也支持数组语法。它可以保留插入顺序，并在大小减小时自动释放内存。我们可以在恒定时间内实现添加、删除和包含操作。不过，该集合类不支持 push、pop、shift、insert 和 unshift 函数。集合类内置了一些非常有用的集合操作函数，如 diff、intersect、union 等。下面是一个集合操作示例：
Unresolved include directive in modules/ROOT/pages/ch12/ch12-06.adoc - include::example$Chapter12/3.php[]在前面的示例代码中，只有一个 1 条目，因为集合不能有重复的值。此外，当我们获取值 1 时，这表示索引 1 上的值。因此，前面示例的输出将是测试。这里可能会出现一个问题，为什么我们不使用 array_unique 来建立一个集合呢？下面的对比图可能就是我们要找的答案：
从上图可以看出，随着数组大小的增加，数组唯一函数的计算时间将比 DS 库中的集合类长。此外，随着数组大小的增加，set 类占用的内存也比 PHP 数组少：
栈和队列
DS 库还实现了堆栈和队列数据结构。DS\Stack 在内部使用 DS\Vector ，而 DS\Queue 在内部使用 DS\Deque 。与 SPL 的栈和队列实现相比，栈和队列的实现具有相似的性能。下图显示了这一点：
Deque
deque（读作 deck），即双端队列，用于 DS\Queue 的内部实现。该软件包中的 deque 实现在内存使用方面非常高效，还能在 \$O(1)\$ 的恒定时间内执行 get、set、push、pop、shift 和 unshift 操作。然而，DS\Deque 的缺点之一是插入或删除操作，其复杂度为 \$O(n)\$。下面是 DS\Deque 和 SPL 双链表的性能比较：
优先级队列
我们已经了解到，优先队列对许多算法都很重要。拥有一个高效的优先队列对我们来说也非常重要。到目前为止，我们已经看到，我们可以使用堆或 SPL 优先级队列来实现我们的解决方案。然而，DS\PriorityQueue 的速度是 SplPriorityQueue 的两倍多，而且只占用其 5% 的内存。这使得 DS\PriorityQueue 的内存效率是 SplPriorityQueue 的 20 倍。下图显示了对比情况：
通过前面几节的讨论，我们可以得出这样的结论：DS 扩展对于数据结构来说确实很高效，而且在类似的实现方面远远优于 SPL。虽然基准测试结果会因平台和内部配置的不同而略有差异，但它表明新的 DS 扩展很有前途，可能会对开发人员很有帮助。需要记住的一点是，该库尚未内置堆或树数据结构，因此我们无法从该库中获得内置的分层数据结构。
|
如需了解更多信息，请查看以下文章，因为比较图表摘自此处： https://medium.com/@rtheunissen/efficient-data-structures-for-php-7-9dda7af674cd |