c++ - 使用索引项避免重复条目

Question

我正在阅读 robert sedwick 关于算法的书中关于队列的内容

When the items in the data structure are themselves array indices, so we refer to such item as "index items". Typically, we have a set of M objects, kept in yet another array, that we need to pass through a generalized queue structure as a part of a more complex algorithm. Objects are put on the queue by index and processed when they are removed, and each object is to be processed precisely once. Usually array indices in a queue with no duplicates accompliches this goal directly.

我在最后一句中的问题“对象按索引放入队列并在它们被删除时进行处理，并且每个对象都将被精确地处理一次”？我们只使用一个数组而不是两个数组？

作者所说的“通常队列中没有重复项的数组索引直接实现了这个目标”是什么意思。 ？

感谢您的时间和帮助

Answer 1

嗯，作者想解决处理存储在数组中的数据的算法任务:

       +-----+-----+---------+-----+
Data = | Foo | Bar | Grandma | Zip |
       +-----+-----+---------+-----+

我们需要按照我们的算法确定的某种顺序处理这些数据，并且有一些我们接下来要处理的“待办”项目队列。复制实际数据对象可能是不可取的或不可能的(对象可能很大或不可复制)。 索引的队列就可以了:

             --+---+---+--\
ToDo = [2] --> | 0 | 3 | -----> (1)
             --+---+---+--/

队列告诉我们 Data[1] 是下一个要处理的项目。 Data[3] 和 Data[0] 正在等待，我们刚刚决定 Data[2] 作为最近的任务进入。

(例如，队列用于树结构的广度优先搜索:您将下一个要访问的节点从一侧的队列中弹出，并将该节点的子节点插入作为 future 的工作另一边。每个节点应该恰好访问一次。上面的索引队列让您可以将 实际 树元素存储在 Data 数组中，并通过轻量级引用它们仅索引。)