Предложения по правильной итерации по вектору

Question

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

Я предполагаю, что использование операторов <> может быть частью проблемы. Основная логика функции заключается в сравнении первого элемента с последним элементом, затем рядом с последним элементом и так далее. После сравнения первого элемента со всеми элементами вы снова начинаете сравнивать второй элемент с другими элементами и так далее ...

void compareAllGames(move& aMove) { /* aMove is a vector of games. games are a struct of data */
    vector<game>:: iterator frontIter = aMove.begin();
    vector<game>:: iterator rearIter = aMove.end() - 1;
    vector<game>:: iterator compIter;
    for (; frontIter < rearIter; frontIter++) { /* move along the games from first to last */
        for (compIter = aMove.end(); compIter > frontIter; ) { /* move along the games from last to first */
            /* checkForSymmetry compares *frontIter to all symmetries of *compIter */
            if (checkForSymmetry(*frontIter, *compIter)) {
                compIter--;
                aMove.erase(compIter + 1);
            }
            else {
                compIter--;
            }
        } /* reset iterators for next loop */
        compIter = aMove.end();
        rearIter = aMove.end();
    }
}

Answer 1

Похоже, что есть хотя бы одно или два места, к которым вы получаете доступ end, которые находятся за концом вашего контейнера. Вместо того, чтобы пытаться исправить несколько запутанную логику, я бы предложил один из:

Если вы можете создать порядок, который всегда размещает симметричные решения рядом, вы можете применить этот порядок, а затем использовать std::unique с предикатом для удаления дубликатов.

Если вы не можете этого сделать, тогда используйте remove_if вместо вашего сложного внутреннего цикла:

void compareAllGames(move& aMove) { /* aMove is a vector of games. games are a struct of data */
    vector<game>:: iterator frontIter = aMove.begin();
    for (; frontIter < aMove.end() - 1; frontIter++) { /* move along the games from first to last */
        aMove.erase(std::remove_if(frontIter + 1, aMove.end(), std::bind1st(checkForSymmetry, *frontIter)), aMove.end());
    }
}

Answer 2

Это на самом деле не ответ на каждое высказывание, а просто чтобы прояснить для ОП, что я имел в виду в своем комментарии.

/* aMove is a vector of games. games are a struct of data */
void compareAllGames( move &aMove ) 
{
    typedef vector<game>::iterator game_it;
    /* move along the games from first to last */
    for( game_it frontIter = aMove.begin(); frontIter != aMove.end(); ++frontIter ) 
    {
        /* move along the games from last to first */
        for( game_it compIter = aMove.end(); compIter != frontIter; --compIter )  
        {
            /* checkForSymmetry compares *frontIter to all symmetries of *compIter */
            if( checkForSymmetry( *frontIter, *compIter ) )
            {
                compIter = aMove.erase( compIter );
            }

        }
    }
}

Answer 3

for (; frontIter < rearIter; frontIter++) { /* move along the games from first to last */

Вы правы: вы должны использовать != вместо <. Это, вероятно, не имеет никакого значения, но в отсутствие причины поступить иначе, вы, как правило, также хотите использовать преинкремент, а не постинкремент, давая:

for (;frontIter != readiter; ++frontIter)
    for (compIter = aMove.end(); compIter > frontIter; ) { /* move along the games from last to first */

Чтобы просмотреть коллекцию в обратном порядке, вы обычно хотите использовать reverse_iterator:

    vector<game>::reverse_iterator compIter;
    for (compIter=aMove.rbegin(); compIter != frontIter; ++compIter);

Впрочем, я не помню, можете ли вы напрямую сравнить итератор с reverse_iterator - вам, вероятно, нужно преобразовать fronIter в reverse_iterator, чтобы сделать сравнение.

        /* checkForSymmetry compares *frontIter to all symmetries of *compIter */
        if (checkForSymmetry(*frontIter, *compIter)) {
            compIter--;
            aMove.erase(compIter + 1);
        }
        else {
            compIter--;
        }
    } /* reset iterators for next loop */

Хотя преобразование не будет полностью простым, похоже, что это в конечном итоге представляет собой вариант std::remove_if, поэтому вы можете изменить его для использования стандартного алгоритма.

Answer 4

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

Вот последняя функция, которую я использовал:

bool compareAllGames(move& aMove) {
    vector<game>:: iterator frontIter = aMove.begin();
    vector<game>:: iterator rearIter = aMove.end() - 1;

    for (; frontIter != rearIter; ++frontIter) { // move along the games from first to last
        if (checkForSymmetry(*frontIter, aMove.back())) {
            aMove.pop_back();
            return true;
        }
    }
    return false;
}

Теперь мне просто нужно добавить свой код обратно в этосчета для победителей, и я буду иметь надлежащим образом настроенный счет для дерева игры крестики-нолики.Нескорректированный счет (без учета победителей) по ходу: 1, 2, 12, 38, 108, 174, 228, 174, 89 и 23.