Список итератор стирания вне диапазона

Question

У меня есть следующий код:

static std::map<int,int> myFunction(std::list<int>& symbols){
    std::map<int,int> currCounts;
    std::map<int,int> payHits;
    for (std::list<int>::iterator l_itr = symbols.begin(); l_itr != symbols.end(); ++l_itr){
        myFunction_helper(*l_itr, l_itr, symbols, currCounts, payHits, 0);
    }
    return payHits;
}

static inline void myFunction_helper(int next, std::list<int>::iterator& pos, std::list<int> remainingSymbols, std::map<int,int> currCounts, std::map<int,int>& payHits, int i){
    currCounts[next] = currCounts.count(next) > 0 ? currCounts[next] + 1 : 1;
    remainingSymbols.erase(pos);
    if (i < numTiles && remainingSymbols.size() > 0){
        if (currCounts[next] == hitsNeeded[next]){
            int pay = symbolPays[next];
            payHits[pay] = payHits.count(pay) > 0 ? payHits[next] + 1 : 1;
        }
        else{
            for (std::list<int>::iterator l_itr = remainingSymbols.begin(); l_itr != remainingSymbols.end(); ++l_itr){
               myFunction_helper(*l_itr, l_itr, remainingSymbols, currCounts, payHits, i+1);
            }
        }
    }
    else{
        payHits[0] = payHits.count(0) > 0 ? payHits[0] + 1 : 1;
    }

}

Предполагается, что он принимает набор значений с учетом некоторых требований (numTiles (int), hitNeeded (карта символов и количество раз, которое они должны быть выбраны для победы)). Мой код построен на визуальных студиях (самая последняя версия), но когда я пытаюсь выполнить его, я получаю сообщение об ошибке «Итератор удаления списка вне диапазона» при первом вызове myFunction_helper. Как мне избежать этого? Я намеренно передал оставшиеся символы по значению, чтобы я мог изменить его, не затрагивая другие рекурсивные элементы стека. Как я могу это исправить и почему это вызывает исключение?

---

Решение

Удалить итератор из аргументов. Затем, когда вы выполняете итерацию, вы используете следующий фрагмент кода:

int next = *l_itr;
l_itr = symbols.erase(l_itr);
myFunction_helper(next, remainingSymbols, currCounts, payHits, i+1);
symbols.push_front(next);

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

Answer 1

Нельзя использовать итератор из одного контейнера с другим, вместо этого можно использовать смещение, но это будет очень неэффективно с std::list. Кроме того, использование std::list с int в целом не очень хорошая идея - ваши данные маленькие, и, скорее всего, вы используете как минимум вдвое больше памяти для хранения элементов списка, чем сами данные плюс потери в кеше. Вам лучше использовать std::vector<int> и передавать смещение, а не итератор. Кроме того, с помощью vector<> вы можете использовать идиому стирания перемещения, но даже удаление int в середине вектора относительно дешево, скорее всего, дешевле, чем стоимость перехода std::list узлов.

Answer 2

Согласен с комментариями ниже. Это дерьмовый ответ, потому что мы недостаточно знаем о бизнес-кейсе, чтобы предложить хорошее решение. Я оставляю отредактированную версию здесь, потому что я только что вернул вандализованный вопрос, и это объясняет, почему попытка не удалась.

Почему это вызывает исключение

std::list<int> remainingSymbols передается по значению, поэтому pos больше не имеет значения. Это относится к источнику list, а не к копии списка источников в remainingSymbols. Использование итератора для одного list в другом, даже в копии, является фатальным.

решение

Общим решением является передача remainingSymbols по ссылке: std::list<int> & remainingSymbols, но, поскольку это нарушит возврат, вы не сможете этого сделать.

Вместо этого вам придется передать другой идентификатор для позиции, возможно, индекс. К сожалению, интеграция и повторение list - это дорогостоящая задача, которая почти всегда перевешивает преимущества быстрой вставки и удаления list.

.