无需排序/复制/引用原容器，能否高效按特定顺序遍历无序容器？

这是个非常有深度的算法研究问题！先直接给你结论：通用场景下，不存在完全满足你所有要求的高效遍历方式，你的猜测基本是对的——要么需要牺牲时间效率，要么就得接受某些“限制条件”，或者依赖容器的特殊结构。

核心约束下的矛盾点 #

你要求的三个关键约束（不排序原容器、不复制元素、不保存元素引用/指针）和“高效按特定顺序遍历”本质上是冲突的：
要按Less函数定义的顺序遍历，我们每次都需要找到当前未被访问过的最小元素。如果不保存任何已访问元素的状态，也不维护候选元素的结构，那每次查找都得完整遍历整个容器——这直接导致遍历的总时间复杂度变成O(n²)，显然算不上“高效”。

如果想把总时间复杂度降到接近排序的O(n log n)，就必须要维护一个能快速获取下一个最小元素的结构（比如堆），而这必然需要保存原元素的引用/指针，或者元素副本——否则堆里没有可以比较的对象。

受限场景下的可行方案 #

虽然通用场景不行，但在一些特殊条件下，还是能实现类似的效果：

• 基于有限键空间的容器：如果你的元素键是可枚举且范围有限的（比如整数0-100），可以预先按键的顺序创建“桶”，遍历的时候直接按顺序访问每个桶里的元素。这种方式不需要排序、复制元素，也不需要保存额外引用，但只适用于键空间明确且不大的场景。
• 允许修改原容器的标记位：如果可以给原容器的每个元素加一个“已访问”标记，那可以用迭代式选择排序的思路：每次遍历容器找到第一个未标记的最小元素，标记后返回，下次继续找剩下的。这种方式不需要复制或保存引用，但时间复杂度是O(n²)，而且修改了原容器。
• 接受保存位置引用：如果放宽“不保存引用/指针”的限制，最常用的方案就是用一个最小堆，初始化时把所有元素的引用/指针放入堆（时间O(n)），每次弹出堆顶的最小元素（时间O(log n)），总时间O(n log n)。这就是你设想的SortedIterator的高效实现方式，但确实需要保存元素的引用/指针。

总结 #

回到你的问题：如果严格遵守所有约束（不排序、不复制、不保存引用/指针），那么只能接受O(n²)的时间复杂度，这算不上高效；如果要高效遍历，就必须放弃其中至少一个约束——要么保存元素引用/指针，要么依赖容器的特殊结构。

内容的提问来源于stack exchange，提问作者rubenvb