有没有一种优雅的方式来迭代一个列表，其中元素的位置可能会改变？

Question

我现在遇到了一个令人不爽的问题。假设有一个对象列表 aList (其类型称为 Object)，我想要迭代它。基本上，代码应该像这样:

for(int i = 0; i < aList.Size(); ++i)
{
    aList[i].DoSth();
}

这里的难点在于，DoSth() 方法可能会改变调用者在列表中的位置！因此，可能会出现两种结果：第一，迭代可能永远无法结束；第二，可能会跳过某些元素（迭代并不一定像上面那样，因为它可能是一个链表）。当然，第一种情况是主要问题。

必须在以下约束条件下解决该问题：

1）不能排除进行位置交换操作的可能性；

2）如果需要且可行，可以将位置交换操作延迟到迭代完成后进行；

3）由于经常发生，因此只能最小程度地修改迭代（因此不建议执行创建列表副本等操作）。

我使用的语言是C++，但我认为在JAVA和C#等语言中也存在类似的问题。

以下是我尝试过的方法：

a）尝试禁止在迭代过程中进行位置交换操作。但是，这涉及太多客户端代码文件，找到并修改所有这些文件实际上是不可行的。

b）修改每个可以直接或间接被DoSth() 调用的Object 的单个方法（例如Method()），以以下方式进行修改：首先我们可以知道正在进行迭代的是aList，并且我们将相应地处理Method()。如果迭代正在进行中，则我们将延迟Method()想要执行的操作；否则，它立即执行想要的操作。问题在于：如何最好地（易于使用且足够高效）延迟此处的函数调用？Method()的参数可能相当复杂。此外，这种方法还涉及相当多的函数！

c）尝试修改迭代过程。我在这里遇到的实际情况非常复杂，因为它涉及两层迭代：第一层是简单的数组迭代，而第二层是递归函数中的典型链接列表迭代。对于现在的第二层迭代，我能做的最好的事情是限制它的迭代次数并防止同一个元素被迭代多次。

因此，我想可能有更好的方法来解决这个问题吗？也许一些优秀的数据结构会有所帮助？

- SuperSaiyanGod

---

在迭代列表时修改它是体验奇怪行为甚至未定义行为的好方法。这可能是由于设计问题或实现设计时的问题导致的。 - Some programmer dude

使用索引列表来存储位置，并在循环后应用位置交换。 - Thomas Sablik

作为一种可能的（也许是暂时的）解决方案，您可以创建一个新容器，并在迭代第一个原始容器时将其插入其中。然后在完成后从新容器复制到原始容器。或者您可以更改迭代方式，不使用迭代器而是位置，当您拥有“默认”容器vector时，这非常容易实现。 - Some programmer dude

任何订单的修改是否可能发生，或者它们之间有什么保证（例如总是向后，总是向前）？DoSth能否被修改以返回新位置？ - Angew is no longer proud of SO

@Angew DoSth()只是一个简单的函数，可以被客户端代码覆盖以执行任何他们想要的操作。它没有任何返回值，也不应该关心。至于位置交换问题，实际上它可以以任何可能的方式发生（在第一次迭代层内，在第二次迭代层内或在它们之间），但我认为仅处理第二层就足够了。 - SuperSaiyanGod

Answer 1

你的问题缺少细节，但从你的描述中可以看出你犯了混淆职责的错误。

很可能你的对象可以执行某些操作，导致它要么继续存在，要么不存在。决定它不再存在是与将其存储在容器中的问题是两个独立的问题。

所以我们需要分开处理这些问题：

#include <vector>

enum class ActionResult {
    Dies,
    Lives,
};

struct Object
{
    ActionResult performAction();
};

using Container = std::vector<Object>;

void actions(Container& cont)
{
    for (auto first = begin(cont), last = end(cont)
        ; first != last
        ; )
    {
        auto result = first->performAction();
        switch(result)
        {
            case ActionResult::Dies:
                first = cont.erase(first);  // object wants to die so remove it
                break;

            case ActionResult::Lives:       // object wants to live to continue
                ++first;
                break;
        }
    }
}

如果操作仅有两个结果，活着和死亡，则我们可以用成语表达这种迭代方式：

#include <algorithm>

// ...

void actions(Container& cont)
{
    auto actionResultsInDeath = [](Object& o)
    {
        auto result = o.performAction();
        return result == ActionResult::Dies;
    }; 

    cont.erase(remove_if(begin(cont), end(cont), 
                         actionResultsInDeath),
               end(cont));
}

- Richard Hodges

---

使用 remove_if + erase 可以使代码更简洁。 - paler123

@paler123 更新了，但有两件事要说：第一，如果OP的问题只有两种结果（他没有说他想要插入还是重新排序，这将更加棘手），那么它更符合习惯用语；第二，对于你和我来说，这已经是第二天性了，但对于OP来说可能不是。 - Richard Hodges

XY 问题。我们需要问清楚为什么楼主觉得需要这样做疯狂的事情。 - Paul Sanders

@SuperSaiyanGod 如果行为不是“存活”和“死亡”之类的重新排序，那么看起来像是一个设计问题，比如为什么和如何DoSth()甚至知道aList？ - Gaurav Sehgal

@GauravSehgal 嗯，看起来确实像是一个设计问题，但这对我来说是有意义的。在 DoSth() 中所做的操作确实会对调用者产生影响；aList 重新排序是一些副作用，但现在这是最好的方法。细节太微妙，超出了这个问题的范围。 - SuperSaiyanGod

Answer 2

好的，问题解决了，至少就我现在感兴趣的情况而言是这样。 在我的情况下，aList 是一个链表，并且通过指针访问Object元素。 如果aList 的大小相对较小，则我们可以像这样得到一个优雅的解决方案：

Object::DoSthBig()
{
    Object* pNext = GetNext();
    if(pNext)
        pNext->DoSthBig();

    DoSth();
}

这个假设的前提是在整个过程中每个pNext都保持有效。但是，如果元素删除操作已经被谨慎处理过了，那么一切都没问题。

当然，这是一个非常特殊的例子，无法应用于其他情况。

- SuperSaiyanGod