Huge performance slowdown - vectors the problem?

This part of my code is meant to take an irregularly-shaped outline of Tile objects and loop through creating a ring and decreasing the height value of the tiles in the ring while expanding the开发者_Python百科 ring each time to include those tiles just outside the previous ring (does that make sense?). What I find, however, is that I'm getting massive performance slowdowns, with each loop absurdly slower than the one before. Why could this be?

I was thinking it might be because of the noobish oldEdge = theEdge; and comparable lines (both are vectors, I'm assigning one to the other). But even so, I don't understand the huge performance drop. Maybe I'm doing something obviously silly. Can someone set me straight?

Note that oldEdge, theEdge and newEdge are all vector<Tile*>s.

int decrease = 1;
while(decrease < 10)
{
    cout << "Trying to smooth!\n";
    //First, modify the new edge.
    int newHeight = 70 - decrease;
    cout << "Height at: " << newHeight << endl;
    for(int i = 0; i < newEdge.size(); ++i)
    {
        newEdge[i]->SetHeight(newHeight);
    }
    //Increment decrease.
    decrease += 1;
    //Set the oldEdge and theEdge variables.
    oldEdge = theEdge;
    theEdge = newEdge;
    newEdge.clear();
    //Finally, find the new edge.
    cout << "Finding new edge!\n";
    for(int i = 0; i < theEdge.size(); ++i)
    {
        //cout << "Checking a tile's neighbors!\n";
        for(int j = 0; j < theEdge[i]->m_AdjacentTiles.size(); ++j)
        {
            bool valid = true;
            //Is this neighbor in theEdge?
            //cout << "Is this neighbor in theEdge?\n";
            for(int k = 0; k < theEdge.size(); ++k)
            {
                if(theEdge[i]->m_AdjacentTiles[j] == theEdge[k])
                {
                    valid = false;
                    break;
                }
            }
            //If not, is it in oldEdge?
            if(valid)
            {
                //cout << "Is this neighbor in oldEdge?\n";
                for(int k = 0; k < oldEdge.size(); ++k)
                {
                    if(theEdge[i]->m_AdjacentTiles[j] == oldEdge[k])
                    {
                        valid = false;
                        break;
                    }
                }
            }
            //If neither, it must be valid for continued expansion.
            if(valid)
            {
                newEdge.push_back(theEdge[i]->m_AdjacentTiles[j]);
            }
        }
    }
}

---

Your algorithm, as best I can tell, is O(n^2 * m) in the number of edges and adjacent tiles. Most likely just a small increase causes the asymptotic performance to blow up and you see the slowdown. If the edge containers were sorted you could use a binary search instead, or if you were able to hash them instead that would also be an option.

I'm not familiar enough with the algorithm you're trying to use but you might want to revisit if there's a fundamentally different approach you should use.

---

It's not the vector, it's the algorithm.

You have a three-times nested loop in there. Put some debug statements in to find out how many times it goes through each loop.