c++ - 大多数数据结构可以使用 vector 来实现吗?

标签 c++ data-structures vector

我使用 C++ vector 来实现堆栈、队列、堆、优先级队列和有向加权图。在书籍和引用资料中,我看到了这些数据结构的大类,所有这些都可以使用 vector 在短时间内实现。 (可能使用指针更灵活)

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

是为了牢记低层次的思想,那样更生动还是让学生具备指针的这种用法?

最佳答案

的确,许多数据结构都可以在 vector (数组,为了这个答案的缘故)之上实现,基本上所有数据结构都可以,因为每个计算任务都可以实现在图灵机上运行,​​而图灵机具有更基本的数据访问能力(或者,在现实世界中,你可以说你用指针实现的任何程序最终都在一个 CPU 上运行,CPU 有一个简单的类似于数组的虚拟内存空间,所以你可以称它为一个巨大的数组) .然而,它并不总是聪明的。两个主要原因:

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

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

请注意,第二个参数很可能归结为性能(“嘿,这是一种笨拙的方法,但我仍然设法使用 vector !”),但不仅如此 - 它会使您的代码复杂化,使您的代码困惑数据结构设计,并可能使其更容易出现错误。

现在,“但是”来了 - 尽管使用该语言为您提供的所有可能工具意义重大,但使用基于 vector 的结构来执行性能关键型任务已被广泛接受。查看几乎所有科学 CPU 基准测试,其中大部分最终都依赖 vector (未引用,但如果有人感兴趣,我可以进一步详细说明。足以说明即使是著名的 *graph*500 也是如此) .

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

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

关于c++ - 大多数数据结构可以使用 vector 来实现吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18935167/

相关文章:

适合在动态有序列表中查找第 n 个元素的 C++ STL 容器?

c - 如何隐藏并打印结构体成员的void指针数组?

c - 错误 : A function Can't return char type in C

c++ - vector 中 bool 值的均匀分布

c++ - 理解 vector 乘法

c++ - CV::imwrite 来自 std::vector 的缓冲区

c++ - 在 std::accumulate 中使用变异函数

c++ - C++ 中的翻转抛物线

c++ - 将 OpenGL 基元转换为 OpenGLES

c++ - gcc Woverloaded-虚拟警告