Есть ли какой-нибудь элегантный способ перебора списка, позиции элементов которого могут меняться?

Question

У меня сейчас отвратительная проблема. Предположим, что есть список aList объектов (тип которых мы называем Object ), и я хочу перебрать его. По сути, код будет выглядеть так:

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

Трудная часть здесь в том, что метод DoSth () может изменить позицию вызывающего в списке! Таким образом, могут возникнуть два последствия: во-первых, итерация может никогда не закончиться; во-вторых, некоторые элементы могут быть пропущены (итерация не обязательно похожа на описанную выше, поскольку это может быть связанный список). Конечно, первая из них - главная проблема.

Проблема должна быть решена с помощью следующих ограничений:

1) Нельзя исключать возможность выполнения операций обмена позициями;

2) Операции обмена позициями могут быть отложены до завершения итерации, если это необходимо и выполнимо;

3) Поскольку это происходит довольно часто, итерация может быть изменена лишь минимально (поэтому такие действия, как создание копии списка, не рекомендуется).

Я использую язык C ++, но я думаю, что в JAVA, C # и т. Д. Есть похожие проблемы и т. Д.

---

Вот что я пробовал:

а) Попробуйте запретить операции обмена позициями во время итерации. Однако для этого требуется слишком много файлов клиентского кода, и найти и изменить их все просто не практично.

b) Изменить каждый метод (например, Method () ) Object , который может изменить свою позицию и будет вызываться с помощью DoSth () прямо или косвенно, таким образом: сначала мы можем узнать, что aList выполняет итерацию, и мы будем соответственно обрабатывать Method () . Если итерация выполняется, то мы задерживаем то, что Method () хочет сделать; в противном случае он делает то, что хочет прямо сейчас. Здесь возникает вопрос: каков наилучший (простой в использовании, но достаточно эффективный) способ отсрочки вызова функции здесь? Параметры Method () могут быть довольно сложными. Более того, этот подход также включает в себя довольно много функций!

в) Попробуйте изменить процесс итерации. Реальная ситуация, с которой я здесь сталкиваюсь, довольно сложна, поскольку включает в себя два уровня итераций: первый из них - итерация простого массива, а второй - типичная итерация связанного списка, лежащая в рекурсивной функции. Лучшее, что я могу сейчас сделать со вторым уровнем итерации, - это ограничить время его итерации и предотвратить повторение одного и того же элемента более одного раза.

Итак, я думаю, что может быть лучший способ решить эту проблему? Может быть, поможет какая-то удивительная структура данных?

Answer 1

Ну, проблема решена, по крайней мере, в отношении ситуации, в которой я сейчас заинтересован. В моей ситуации aList на самом деле является связанным списком, а элементы Object доступны через указатели. Если размер aList относительно мал, то у нас есть элегантное решение, подобное этому:

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

    DoSth();
}

Это основополагающая гипотеза о том, что каждый pNext продолжает действовать в течение всего процесса. Но если операция удаления элемента уже была выполнена незаметно, то все в порядке.

Конечно, это очень особенный пример, и его нельзя применять в других ситуациях.

Answer 2

Ваш вопрос немного освещает детали, но из того, что вы написали, кажется, что вы делаете ошибку, смешивая проблемы.

Вполне вероятно, что ваш объект может выполнить какое-то действие, которое заставит его продолжать существовать или нет. Решение о том, что он больше не должен существовать, является отдельной заботой относительно фактического хранения его в контейнере.

Итак, давайте разделим эти проблемы:

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