我有一个 C++ 任务，我必须设计一个简单的解决方案来解决我选择的容器的 Knuth 问题，并研究生成的性能数据。请参阅以下问题:
Three million men with distinct names were laid end-to-end, reaching from New York to California. Each participant was given a slip of paper on which he wrote down his own name and the name of the person immediately west of him in the line. The man at the extreme western end of the line didn’t understand what to do, so he threw his paper away; the remaining 2,999,999 slips of paper were put in a huge basket and taken to the National Archives in Washington, D.C. Here the contents of the basket were shuffled completely and transferred to magnetic tapes.
At this point an information scientist observed that there was enough information on the tapes to reconstruct the list of people in their original order. And a computer scientist discovered a way to to do the reconstruction with fewer than 1000 passes through the data tapes, using only sequential accessing of tapes and a small amount of random-access memory. How was this possible?
[In other words, given the pairs (xi, xi+1) for 1 ≤ i < N, in random order, where the xi are distinct, how can the sequence x1 x2….xN be obtained, restricting all operations to serial techniques, suitable for use on magnetic tapes. This is the problem of sorting into order when there is no easy way to to tell which of two given keys precedes the other;
根据我的研究，我决定使用 unordered_map，而不是列表或法线贴图。我不明白的是提供给我们作为代码实现的天真的解决方案:
Consider the papers to be a collection of (Name, Name) tuples, both the successor (westerly neighbour) and the predecessor (easterly neighbour) can be established from these tuples.
- identify an individual xc
- append xc to empty list
- while xc has westerly neighbour
- xc < westerly neighbour of xc
- append xc to list
- xc < head of list
- while xc has easterly neighbour
- xc < easterly neighbour of xc
- prepend xc to list
我的第一个问题 - xc 是否只是一个随机元素，因为容器的性质无法确定顺序？
我的第二个问题 - 我们得到的名字在一个文件中，如下所示:
Hazbgaei,Ckwkkkxa
Hrunmkoc,Usjgmunt
Cmkcwncb,Ycrnwzjl
Oygvmrhf,Hylmukiw
Jursaual,Gzrddsbg
那么天真的解决方案是说我应该把名字放在一个列表中，然后把姓氏放在另一个列表中吗？
如果我完全不理解，我深表歉意，但我真的很努力去理解这一点!
最佳答案
我相信解决方案是使用一个列表。选择第一个元组，并将其名字作为列表的头部，将西边的邻居作为下一项。然后，找到以该西风邻居作为其名字的元组(当然，这是困难的部分)，并从该元组中获取西风邻居并将其添加到列表中。重复，直到找不到包含最后添加的人的名字的元组。然后您就知道您已经到达了西海岸。
因此，第一个 xc 本质上是随机的。之后，xc 是确定性的。那行说
- while xc has westerly neighbour
本质上是在说“找到以当前西风邻居为自身名称的元组”。
当然，后半部分只是反向应用相同的逻辑，将向东的链条填满。
关于c++ - 天真的 c++ 解决方案的无序映射，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14551031/