大多数数据结构能否使用向量来实现？

Question

我使用C++向量来实现堆栈、队列、堆、优先级队列和有向加权图。在书籍和参考文献中，我看到了这些数据结构的大类，所有这些类都可以用向量来实现。(可能在使用指针方面有更大的灵活性)

我们还能使用向量实现甚至先进的数据结构吗？

如果是，为什么C++书籍仍然使用指针解释长类的概念？

这是为了记住较低层次的想法，如果它是更生动的方式，还是它使学生配备了这样的指针使用？

Answer 1

的确，许多数据结构可以在向量(数组，为了这个答案)之上实现，实际上它们都可以实现，因为每个计算任务都可以在具有更基本的数据访问能力的图灵机上运行(或者，在现实世界中，您可能会说，您用指针实现的任何程序最终都运行在一个CPU上，就像虚拟内存空间一样，所以您只需调用一个巨大的数组)。然而，这并不总是聪明的。两个主要原因：

1. 性能/时间复杂度-向量不能提供O(1)中的所有基本操作。有一个快速初始化的解决方案，但是尝试将值随机插入到一个大向量中，看看执行得有多糟糕--这是因为您必须一次又一次地移动所有元素。一个列表可以在一次操作中做到这一点。当然，其他结构也有自己的性能缺陷，但这就是用这些基本的构建块设计复杂的数据结构的美妙之处。
2. 结构复杂性--您可以将向量的同一条线上的列表看作有序容器，并可能将其扩展到多维矩阵，这些矩阵可以在其之上实现，因为它们仍然保留一些基本的顺序，但还有更复杂的结构。以一棵树为例，一个简单的完整二叉树可以很容易地用一个向量来实现，因为父-子关系可以很容易地转换成索引算法，但是如果树不是满的并且每个节点有不同数量的子节点呢？现在，您可能会说仍然可以这样做(任何图都可以通过邻接矩阵或邻接列表来用向量来实现)，但是当您可以使用指针链接实现一个简单得多的实现时，这样做几乎是没有意义的。想象一下用数组做一个AVL滚动。*战栗：

请注意，第二个论点很可能归结为性能(“嘿，这是一种很尴尬的方法，但我仍然设法使用了向量！”)，但更重要的是--它会使代码复杂化、数据结构设计混乱，并可能使其更容易出现错误。

现在，出现了“但是”--尽管使用该语言提供的所有可能的工具很有意义，但是使用基于向量的结构来执行性能关键的任务是非常普遍的。查看几乎所有的科学CPU基准，其中大多数最终依赖于向量(没有，但我可以进一步阐述，如果有人感兴趣。即使是著名的*图*500也能做到这一点。

原因不是因为它是最好的编程实践，而是因为它更适合CPU内部结构，并从HW中获得更多的“活力”。这是由于空间局部性--CPU非常喜欢这样做，因为它允许内存单元并行访问(在数组中，您始终知道下一个元素在哪里，在列表中必须等到当前元素被获取为止)，还可以发出流/步长预取，以减少未来请求的延迟。我不能说这一直是一个很好的实践，当您在图中运行时，即使使用数组实现，访问仍然是非常不规则的，但这仍然是一种非常常见的做法。

总之，从字面上来看这个问题--它们中的大多数都可以，某种程度上(对于给定的“大多数”的定义，好吗？)，但如果你的意图是“为什么教指针”，我相信你可以看到，为了理解自己的极限，以及你可以和应该使用什么--你需要知道的不仅仅是数组，甚至指针。一个好的程序员应该对所有事情都有所了解--操作系统设计，CPU设计等等。除非你真正了解你正在运行的结构，否则你就不能做任何像样的事情，不幸的是，这包括了很多的指针。

Answer 2

您可以使用分配器作为后备存储来实现某种std::vector。如果这样做，基础计算机科学的所有标准数据结构都可以实现在向量之上。然而，它很难使您免于使用指针:向量实际上只是一些有用的附加操作的内存块，最显著的是扩展能力。

更重要的是:如果您不理解指针，那么您也不会理解如何为高级数据结构使用vector。vector是一种有用的抽象，但它遵循了C++规则，即“您没有得到您不需要付费的东西”，所以它也是一个非常“瘦”的抽象，并且您确实要根据您必须编写的代码量来支付抽象的成本。

(Jonathan在评论中指出，当您在C++上实现分配器数据结构时，您不会得到vector标准库所需的确切保证。原则上说，向量只是处理内存块的一种方式。)

Answer 3

如果您正在学习C++，您需要熟悉指针以及如何使用它们，即使有更高层次的概念为您完成这项工作。是的，使用向量或列表实现大多数数据结构是可能的，如果您刚刚开始学习编程，那么最好自己知道如何编写这些数据结构。

尽管如此，除非有充分的理由不使用标准库，否则生产代码应该始终使用标准库。