时间戳

首页 > 解决方案 > 是否有任何优雅的方式来遍历元素位置可以改变的列表？

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

问题描述

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

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

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

该问题必须通过以下约束来解决：

1）不能排除进行换仓操作的可能性；

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

3) 由于它经常发生，因此只能对迭代进行最低限度的修改（因此不推荐创建列表副本等操作）。

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

以下是我尝试过的：

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

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

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

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

标签： c++list

解决方案

您的问题对细节有点轻描淡写，但从您所写的内容来看，您似乎犯了混淆关注点的错误。

您的对象可能会执行某些操作，导致它继续存在或不存在。它应该不再存在的决定与实际将其存储在容器中的决定不同。

所以让我们把这些担忧分开：

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

推荐阅读