我使用 C++ vector 来实现堆栈、队列、堆、优先级队列和有向加权图。在书籍和引用资料中，我看到了这些数据结构的大类，所有这些都可以使用 vector 在短时间内实现。 (可能使用指针更灵活)
我们还可以使用 vector 实现更高级的数据结构吗？
如果是，为什么 C++ 书籍仍然使用指针解释长类的概念？
是为了牢记低层次的思想，那样更生动还是让学生具备指针的这种用法？
最佳答案
的确，许多数据结构都可以在 vector (数组，为了这个答案的缘故)之上实现，基本上所有数据结构都可以，因为每个计算任务都可以实现在图灵机上运行，而图灵机具有更基本的数据访问能力(或者，在现实世界中，你可以说你用指针实现的任何程序最终都在一个 CPU 上运行，CPU 有一个简单的类似于数组的虚拟内存空间，所以你可以称它为一个巨大的数组) .然而，它并不总是聪明的。两个主要原因:
性能/时间复杂度 - vector 根本无法提供 O(1) 中的所有基本操作。有一个快速初始化的解决方案，但是尝试将值随机插入到一个大 vector 中，看看你的表现有多糟糕——那是因为你必须一遍又一遍地将所有元素移动一个地方。列表可以在一次操作中完成。当然，其他结构有其自身的性能缺点，但这就是使用这些基本构建 block 设计复杂数据结构的美妙之处。
结构复杂性 - 您可以将一个列表沿 vector 的同一行视为一个有序容器，并可能将其扩展为多维矩阵，可以在它们之上实现，因为它们仍然保留一些基本顺序，但还有更复杂的结构。举个例子一棵树，一个简单的完整二叉树可以很容易地用 vector 实现，因为父子关系可以很容易地转换为索引算法，但是如果树不完整并且每个节点的子节点数量不同怎么办？现在，您可能会说它仍然可以完成(例如，任何图形都可以通过邻接矩阵或邻接列表用 vector 实现)，但是当您可以使用指针链接进行更简单的实现时，这样做几乎没有意义。想想用数组做一个 AVL 滚动。 :战栗:
请注意，第二个参数很可能归结为性能(“嘿，这是一种笨拙的方法，但我仍然设法使用 vector !”)，但不仅如此 - 它会使您的代码复杂化，使您的代码困惑数据结构设计，并可能使其更容易出现错误。
现在，“但是”来了 - 尽管使用该语言为您提供的所有可能工具意义重大，但使用基于 vector 的结构来执行性能关键型任务已被广泛接受。查看几乎所有科学 CPU 基准测试，其中大部分最终都依赖 vector (未引用，但如果有人感兴趣，我可以进一步详细说明。足以说明即使是著名的 *graph*500 也是如此) .
原因不是它是最佳编程实践，而是它更适合 CPU 内部结构并从硬件中获取更多“汁液”。这是由于空间局部性——CPU 非常喜欢它，因为它允许内存单元并行访问(在数组中你总是知道下一个元素在哪里，在列表中你必须等到当前元素被获取)，而且发出流/跨步预取，以减少 future 请求的延迟。 我不能说这总是一个好的做法，当你运行一个图时，即使你使用数组实现，访问仍然很不规则，但这仍然是一个非常普遍的做法。
总而言之，从字面上看这个问题 - 大多数问题都可以(对于“大多数”的给定定义，好吗？)，但如果意图是“为什么教指针”，我相信你可以在为了了解您的限制以及您可以和应该使用什么 - 您需要了解的不仅仅是数组甚至指针。一个好的程序员应该对所有事情都有所了解——操作系统设计、CPU 设计等。除非你真正了解你正在运行的结构，否则你无法做任何体面的事情，不幸的是(或不)包含很多指针
关于c++ - 大多数数据结构可以使用 vector 来实现吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18935167/