Deleting from a multimap with an iterator

Pierre (2)
I'm building a graph (of the graph theory kind). I add points to a complicated data structure, keeping track of the convex hull, and when I add a point, I then delete the points that are no longer in the convex hull. The convex hull is stored in a multimap, ordered by the direction from the starting point. I've built graphs of over a thousand points by this method, so I know the structures are sound, but if I remove three or more points from the hull, sometimes it fails to remove a point, resulting in a corrupt (non-planar) graph. Here's the code for this section:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
      // Now make a list of the visible points. There are 3 on average.
      visible.clear();
      edgeoff=edgelist.size();
      for (k=left,n=0,m=1;m;k++,n++,m++)
          {if (k==convexhull.end())
              k=convexhull.begin();
           if (k!=inspos) // skip the point just added - don't join it to itself
              {visible.push_back(k->second);
               edgelist.resize(edgelist.size()+1);
               edgelist[edgelist.size()-1].a=j->second;
               edgelist[edgelist.size()-1].b=k->second;
               //printf("Adding edge from %p to %p\n",j->second,k->second);
               }
           if (k==right || n==maxedges) m=-1;
           }
      val=--n; //subtract one for the point itself
      printf("%d points visible\n",n);
      // Now delete old convex hull points that are now in the interior.
      //for (k=left,n=0;n<=val;k++,n++)
      for (k=left,n=cycles=0;n<=val-2 && cycles<val;k++,cycles++)
          {if (k==convexhull.end())
              k=convexhull.begin();
           printf("Trying to delete %f %p\n",k->first,k->second);
           for (m=1;m<visible.size()-1;m++)
               if (k->second==visible[m])
                  {printf("Deleting %p, #%d in visible, from convexhull\n",visible[m],m);
                   convexhull.erase(k);
                   n++;
                   break;
                   }
           }

visible is a vector<point*>;convexhull is a multimap<double,point*>. I have to use multimaps because two points could be in the same direction from the starting point. When I run the output through less, I find that when it makes a mistake, the line "Deleting %p" is followed by jumping to a different part of the convex hull. It looks like trying to increment an iterator that has been used to delete something is invalid. What is the proper way to do this?
Last edited on
jsmith (5804)
Unfortunately removing an element from a multimap (and other STL containers) invalidates the iterator used to remove it. You might consider wrapping the deletion in a function:

1
2
3
4
5
6
7
8
9
10
11
12
 
// Warning: Not compiled or tested
template< typename Key, typename Tp, typename Compare, typename Alloc >
std::multimap<Key,Tp,Compare,Alloc>::iterator erase(
  std::multimap<Key,Tp,Compare,Alloc>& container,
  std::multimap<Key,Tp,Compare,Alloc>::iterator target
  )
{
    assert( target != container.end() );
    std::multimap<Key,Tp,Compare,Alloc>::iterator removeMe( target++ );
    container.erase( removeMe );
    return target;
}


Generally, you need to get an iterator to the element immediately after the
one you are going to erase before erasing it.

Last edited on
Pierre (2)
I thought that's what was happening. convexhull normally has about sqrt(n) points, while visible has 3 on average. I think it would make more sense to iterate through visible, look up the point in convexhull, and delete it.
Topic archived. No new replies allowed.