1

I am having an interesting issue. For starters, I am currently developing a 2D geometry editor where the user is able to draw lines and arcs. In order to draw a line and arc, the user needs to select 2 nodes.

In an earlier question on the forum, I was wondering if there was anything available that will not invalidate pointers when elements are erased (or inserted) but is not an std::list (for various reasons that are scattered throughout stack overflow). A user recommended that I take a look at the plf::colony class. Which, in short, acts like std::list but has the speed of std::deque in many instances.

Anyways, I am implementing this class in my program to contain the nodes, lines, and arcs. I was able to successfully integrate the class and everything builds. However, I notice that there is a bug in my bug when I go to delete nodes.

I have narrowed down the issue to be this: If I create less then 10 nodes, my code is able to delete all of the nodes without an issue. However, if I select all of the 10 nodes, my program crashes. If I draw 20 nodes and select 10 of them for deletion, my program crashes. If I draw 15 nodes and select 5 of them, everything is good. If I draw 15 nodes and select 7 of them, everything is fine. If I draw 15 nodes and select 8, the program crashes. If I draw 50 nodes and select 8 for deletion, the program crashes. There is something about the 8th node that appears to crash the program.

Later, I stepped through the code (that I have posted below) and everything is fine until the iterator reaches the 8th item. There, the iterator points to nothing and crashes the program. The program crashes when it tries to erase the iterator from the colony.

I was wondering if anyone else using plf::colony ran into the same issue and what they did to fix the bug? Or is there something wrong with the way that I am setting up my code?

    for(int i = 1; i < 21; i++)
{
    _editor.addNode(0.25 * i, 0);
    _editor.getNodeList()->back()->setSelectState(true);
}


if(_editor.getNodeList()->size() > 0)
{
    plf::colony<node>::iterator stopIterator = _editor.getNodeList()->end();
    for(plf::colony<node>::iterator nodeIterator = _editor.getNodeList()->begin(); nodeIterator != _editor.getNodeList()->end(); ++nodeIterator)
    {
        if(nodeIterator->getIsSelectedState())
        {

            if(_editor.getNodeList()->size() <= 1 && _editor.getNodeList()->begin()->getIsSelectedState())
            {
                if(_editor.getNodeList()->size() == 1)
                    _editor.getNodeList()->clear();
                break; 
            }

           _editor.getNodeList()->erase(nodeIterator);
        }
    }
}

Edit:

Ok so this fix of from the code is unable to crash the program:

plf::colony<node>::iterator stopIterator = _editor.getNodeList()->end();
    for(plf::colony<node>::iterator nodeIterator = _editor.getNodeList()->begin(); nodeIterator != _editor.getNodeList()->end();)
    {
        if(nodeIterator->getIsSelectedState())
        {
            if(_editor.getLineList()->size() > 1)
            {
                /* Need to cycle through the entire line list and arc list in order to determine which arc/line the node is associated with and delete that arc/line by selecting i.
                 * The deletion of the arc/line occurs later in the code*/

                for(plf::colony<edgeLineShape>::iterator lineIterator = _editor.getLineList()->begin(); lineIterator != _editor.getLineList()->end(); ++lineIterator)
                {
                    if(*lineIterator->getFirstNode() == *nodeIterator || *lineIterator->getSecondNode() == *nodeIterator)
                    {
                        lineIterator->setSelectState(true);
                    }
                }
            }


            if(_editor.getArcList()->size() > 0)
            {
                for(plf::colony<arcShape>::iterator arcIterator = _editor.getArcList()->begin(); arcIterator != _editor.getArcList()->end(); ++arcIterator)
                {
                    if(*arcIterator->getFirstNode() == *nodeIterator || *arcIterator->getSecondNode() == *nodeIterator)
                    {
                        arcIterator->setSelectState(true);
                    }
                }
            }
           _editor.getNodeList()->erase(nodeIterator++);     
        }
        else
            nodeIterator++;
    }
codingDude
  • 331
  • 1
  • 2
  • 10
  • Strive to rewrite your code where you're not removing items while iterating over the same list. That can be accomplished using the `remove_if / erase` idiom. – PaulMcKenzie Mar 30 '17 at 16:30

1 Answers1

2

I'm not familiar with plf::colony, but the documentation states that elements are not invalidated with erase, with the exception of the erased element. You erase your nodeIterator and later you ++nodeIterator it.

My suggestion is trying to rewrite your loop so you can call the erase function with nodeIterator++.

Alexander Stante
  • 69
  • 4
  • ++nodeIterator and nodeIterator++ doesnt matter in a for loop: http://stackoverflow.com/questions/4706199/post-increment-and-pre-increment-within-a-for-loop-produce-same-output – codingDude Mar 30 '17 at 17:57
  • I'm not talking about the for loop. I'm talking when you call erase. After calling erase the `nodeIterator` is invalidated. And then you increment the invalidated iterator. My suggestion was to rewrite your loop so that you can have this line `_editor.getNodeList()->erase(nodeIterator++)`. In that case you step to the next element before the element is erased. This of course means you must write your loop a bit differently. – Alexander Stante Mar 30 '17 at 18:06
  • Oh I see, sorry that I misunderstood your contribution. But good news! That actually fixed the bug. Now I am wondering why it works precisely works that way – codingDude Mar 30 '17 at 18:22
  • First, the guarantee of `plf::colony` not invalidating iterators does not hold for the erased element. A call to erase does "only" no invalidate other iterators. With `erase(nodeIterator++)` you step to the next element before erase is then called for the previous element. In that way, the increment operation is never called on an invalidated iterator. – Alexander Stante Mar 30 '17 at 18:32
  • But wouldn't the nodeIterator++ operator erase the nodeIterator then increment the nodeIterator? If so, I am having a hard time seeing how that is different then when the nodeIterator gets incremented at the end for the for loop (I apologize for so many questions, I am trying to understand it so that I can have a nice detailed comment in my code) – codingDude Mar 30 '17 at 18:34
  • With `nodeIterator++` the iterator is incremented, and then the **old** value is passed to `erase()`. – Alexander Stante Mar 30 '17 at 18:37
  • Oh ok, I had a misunderstanding on the post increment which lead to a few problems! Thank you for the explanation – codingDude Mar 30 '17 at 18:42