c++ - 是否有任何优雅的方法来遍历其元素位置可以更改的列表？

Question

我目前遇到了一个令人作呕的问题。假设有一个对象列表 aList(我们称其类型为 Object)，我想遍历它。基本上，代码是这样的:

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

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

问题必须在这些约束条件下解决:

1)不排除做换仓操作的可能；

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

3) 由于它经常发生，因此只能对迭代进行最少的修改(因此不推荐创建列表拷贝等操作)。

我用的语言是C++，但是我觉得JAVA和C#等也有类似的问题。

---

以下是我尝试过的:

a) 尝试在迭代过程中禁止位置交换操作。但是，这涉及太多的客户端代码文件，查找和修改所有这些文件是不切实际的。

b) 修改Object 的每一个方法(例如，Method())，它可以改变自身的位置并被DoSth() 调用 直接或间接地，以这种方式:首先我们可以知道 aList 正在进行迭代，我们将相应地处理 Method()。如果迭代正在进行，那么我们延迟Method()想要做的事情；否则，它现在就做它想做的事。这里的问题是:在这里延迟函数调用的最佳(易于使用，但足够有效)方法是什么？ Method() 的参数可能相当复杂。而且，这种方法也会涉及到很多功能!

c) 尝试修改迭代过程。我在这里遇到的真实情况相当复杂，因为它涉及两层迭代:第一层是普通数组迭代，而第二层是典型的链表迭代，位于递归函数中。目前我对第二层迭代能做的最好的事情是限制它的迭代次数并防止同一元素被迭代多次。

所以我想可能有更好的方法来解决这个问题？也许一些很棒的数据结构会有所帮助？

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;
        }
    }
}

如果操作确实只有两个结果，lives 和 dies，那么我们可以地道地表达这个迭代:

#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));
}