CODEWITHSUNDEEP
c++vectoriterator
fryeguy
fryeguy

Reputation: 953

Suggestions for properly iterating through a vector

I wrote a program to determine the game tree for tic-tac-toe. I believe most of the code is in good order. I wrote a function that compares elements of a vector to determine if any elements are duplicates. Duplicate items can either be truly identical or they can be symmetrical. Duplicate elements are deleted from the vector. My compare function appears to have a problem where it incorrectly eliminates elements. Please take a look at how I iterate through the vector and see if the syntax/logic seems reasonable.

My guess is that using < > operators may be part of the problem. The basic logic of the function is to compare the first element with the last element, then the next to last element and so on. After comparing the first element with all elements you start again comparing the second element to the other elements and so on...

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

Upvotes: 1

Views: 396

Answers (4)

fryeguy
fryeguy

Reputation: 953

Thanks for all the comments. In the end I simplified my function that had the two confusing loops and determined that instead of adding all games to a move and then check for duplicates/symmetry, I could add a single game and compare it to the current list. This has two advantages: simpler coding that is easy to understand and a much lower number of comparisons. It doesn't hurt that this code actually works too. These changes led me to find a couple of bugs in my symmetry functions.

Here is the final function that I used:

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

Now I just need to add my code back in that accounts for winners and I will have a proper adjusted count for the tic tac toe game tree. The unadjusted count (ignoring winners) by move is: 1, 2, 12, 38, 108, 174, 228, 174, 89, and 23.

Upvotes: 0

Jerry Coffin
Jerry Coffin

Reputation: 490808

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

You're right: you should be using != instead of <. It probably doesn't make any difference, but absent a reason to do otherwise, you generally want to use pre-increment rather than post-increment as well, giving:

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

To traverse a collection in reverse, you usually want to use a reverse_iterator:

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

Offhand I don't remember whether you can directly compare an iterator to a reverse_iterator though -- you probably need to convert fronIter to a reverse_iterator to do the comparison.

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

While the conversion won't be entirely straightforward, it looks like this ends up as a variation of std::remove_if, so you may be able to change it to use a standard algorithm.

Upvotes: 1

greatwolf
greatwolf

Reputation: 20888

This isn't really an answer per-say but just to help clarify to the OP what I meant in my comment.

/* 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 );
            }

        }
    }
}

Upvotes: 1

Mark B
Mark B

Reputation: 96311

It looks like there are at least one or two places you access end which is past the end of your container. Instead of trying to fix the somewhat convoluted logic, I'd suggest one of:

If you can create an ordering that always arranges symmetric solutions adjacently you can apply that order and then use std::unique with a predicate to remove the duplicates.

If you can't do that, then use remove_if instead of your complicated inner loop:

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

Upvotes: 2

Related Questions