Is there any elegant way of iterating through a list whose elements' positions can change?

user_10282731 0
Viewed 206

I am currently running into a disgusting problem. Suppose there is a list aList of objects(whose type we call Object), and I want to iterate through it. Basically, the code would be like this:

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

The difficult part here is, the DoSth() method could change the caller's position in the list! So two consequences could occur: first, the iteration might never be able to come to an end; second, some elements might be skipped (the iteration is not necessarily like above, since it might be a linked list). Of course, the first one is the major concern.

The problem must be solved with these constraints:

1) The possibility of doing position-exchanging operations cannot be excluded;

2) The position-exchanging operations can be delayed until the iteration finishes, if necessary and doable;

3) Since it happens quite often, the iteration can be modified only minimally (so actions like creating a copy of the list is not recommended).

The language I'm using is C++, but I think there are similar problems in JAVA and C#, etc.

The following are what I've tried:

a) Try forbidding the position-exchanging operations during the iteration. However, that involves too many client code files and it's just not practical to find and modify all of them.

b) Modify every single method(e.g., Method()) of Object that can change the position of itself and will be called by DoSth() directly or indirectly, in this way: first we can know that aList is doing the iteration, and we'll treat Method() accordingly. If the iteration is in progress, then we delay what Method() wants to do; otherwise, it does what it wants to right now. The question here is: what is the best (easy-to-use, yet efficient enough) way of delaying a function call here? The parameters of Method() could be rather complex. Moreover, this approach will involve quite a few functions, too!

c) Try modifying the iteration process. The real situation I encounter here is quite complex because it involves two layers of iterations: the first of them is a plain array iteration, while the second is a typical linked list iteration lying in a recursive function. The best I can do about the second layer of iteration for now, is to limit its iteration times and prevent the same element from being iterated more than once.

So I guess there could be some better way to tackle this problem? Maybe some awesome data structure will help?

list c++
2 Answers

Your question is a little light on detail, but from what you have written it seems that you are making the mistake of mixing concerns.

It is likely that your object can perform some action that causes it to either continue to exist or not. The decision that it should no longer exist is a separate concern to that of actually storing it in a container.

So let's split those concerns out:

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

If there are indeed only two results of the operation, lives and dies, then we could express this iteration idiomatically:

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

Well, problem solved, at least in regard to the situation I'm interested in right now. In my situation, aList is really a linked list and the Object elements are accessed through pointers. If the size of aList is relatively small, then we have an elegant solution just like this:

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

    DoSth();
}

This has the underlying hypothesis that each pNext keeps being valid during the process. But if the element-deletion operation has already been dealt with discreetly, then everything is fine.

Of course, this is a very special example and is unable to be applied to other situations.

user_102827310
Related