c++ - 大多数数据结构都可以用向量来实现吗？

Question

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

我们是否还可以使用向量实现更高级的数据结构？
如果是，为什么 C++ 书籍仍然使用指针解释长类的概念？

是要记住较低层次的想法，如果这样更生动，还是让学生具备这种指针用法？

Answer 1

的确，许多数据结构可以在向量（数组，为了这个答案）之上实现，基本上所有数据结构都可以，因为每个计算任务都可以实现在图灵机上运行，​​而图灵机具有更多基本的数据访问能力（或者，在现实世界中，您可能会说您使用指针实现的任何程序最终都会在 CPU 上运行，该 CPU 具有简单的类似数组的虚拟内存空间，因此您可以称其为巨大的数组）。然而，它并不总是聪明的。两个主要原因：

1. 性能/时间复杂度 - 向量根本无法提供 O(1) 中的所有基本操作。有一个快速初始化的解决方案，但是尝试将值随机插入到一个大向量中，看看你的表现有多糟糕——那是因为你必须一遍又一遍地将所有元素移动一个位置。列表可以在一次操作中完成。当然，其他结构也有其自身的性能缺陷，但这就是使用这些基本构建块设计复杂数据结构的美妙之处。

2. 结构复杂性 - 您可以将沿向量同一行的列表视为有序容器，并可能将其扩展为可以在它们之上实现的多维矩阵，因为它们仍然保留一些基本排序，但还有更复杂的结构. 以一棵树为例，一个简单的完整二叉树可以很容易地用一个向量来实现，因为父子关系可以很容易地转换为索引算术，但是如果树不完整并且每个树有不同数量的子节点怎么办？节点？现在，您可能会说它仍然可以完成（例如，任何图形都可以通过邻接矩阵或邻接列表使用向量来实现），但是当您可以使用指针链接进行更简单的实现时，这样做几乎没有意义。想想用一个数组做一个 AVL 滚动。：不寒而栗：

请注意，第二个参数很可能归结为性能（“嘿，这是一种尴尬的方法，但我仍然设法使用向量！”），但不仅如此 - 它会使您的代码复杂化，使您的数据结构设计混乱，并且可能使其更容易出现错误。

现在，“但是”出现了——尽管使用该语言为您提供的所有可能的工具很有意义，但将基于向量的结构用于性能关键任务已被广泛接受。查看几乎所有科学 CPU 基准测试，其中大多数最终都依赖于向量（未引用，但如果有人感兴趣，我可以进一步详细说明。可以说，即使是众所周知的 * graph *500 也能做到这一点）。

原因不是它是最佳编程实践，而是它更适合 CPU 内部结构，并从硬件中获得更多“汁液”。这是由于空间局部性 - CPU 非常喜欢它，因为它允许内存单元并行访问（在数组中你总是知道下一个元素在哪里，在列表中你必须等到当前元素被获取），而且发出流/跨步预取，以减少未来请求的延迟。我不能说这总是一个好的做法，当你浏览一个图时，即使你使用数组实现，访问仍然非常不规则，但这仍然是一种非常常见的做法。

总而言之，从字面上理解这个问题 - 他们中的大多数都可以（对于“大多数”的给定定义，好吗？），但如果意图是“为什么教指针”，我相信你可以看到这一点以便理解你的限制以及你可以和应该使用的东西——你需要知道的不仅仅是数组甚至指针。一个好的程序员应该对所有事情都略知一二——操作系统设计、CPU 设计等。除非你真的了解你正在运行的结构，否则你无法做任何像样的事情，不幸的是（或不）包含很多指针

Answer 2

您可以使用 an作为后备存储来实现一种分配器。std::vector如果你这样做了，所有基础计算机科学的标准数据结构都可以在向量之上实现。但是，它几乎不会让您从使用指针中解放出来：向量实际上只是带有一些有用的附加操作的内存块，最显着的是扩展能力。

更重要的是：如果您不了解指针，您也不会了解如何使用vector高级数据结构。vector是一个有用的抽象，但它遵循 C++ 规则“你没有得到你不付出的代价”，所以它也是一个非常“薄”的抽象，并且你确实为抽象的成本付出了代价您必须编写的代码量。

（Jonathan Wakely 在评论中指出，当您在vector.记忆。）

Answer 3

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

话虽如此，生产代码应该始终使用标准库，除非有充分的理由不这样做。