是否有任何优雅的方式迭代列表的元素位置可以改变？

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

如果确实只有两个操作,生命和死亡的结果,那么我们可以惯用地表达这个迭代:

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