title: C++:List iterators are pointing to the wrong location
body: <p><strong>Warning. Huge question length.</strong></p>
  
  <p>Hi.
  So, I'm trying to write a program that takes a sequence of n points in the xy plane as input (a simple polygon), along with a line ax + by =c, and outputs a list of polygons that the line divides the original one into.</p>
  
  <p>So i define the following :</p>
  
  <pre><code>      struct point
      {
          public:
          float x, y;
          list &lt;point&gt;::iterator it;//if the point is an intersection point, this points to the position in the other list in class polygon where the point is located. This value is not defined for a point which is only in list pts (see class polygon)
          bool operator &lt;(point );
          int pair;//paired intersection points will have identical pairing values 
          int poly;//poly shows if it is part of polygon or not
          point intersection( point, point, line);//returns the point of intersection
  
           void output();
           };
  
      class polygon
      {
          public:
          int n;
          list &lt;point&gt; pts;//stores points of original polygon as well as intersection points
          list &lt;point&gt; intr;// stores intersection points
          void init_it();//initialises iterators of points present in original polygon
          void init_pair();//initialises "pair" for consecutive points as 1,1,0,0,1,1...
  //This allows pairing up of consecutive points the line intersects for convenient traversal of the polygon in one direction only
          void intersects(line);//solves every relevant side of polygon with the line to get a list of relevant points
          void output();
          polygon()
          {n=0;}
      };
  
      class line
      {
          public:
          float a,b,c;    
          float eval(point p);
      };
  </code></pre>
  
  <p>Look at the <code>intersects()</code> and <code>main()</code> functions here.</p>
  
  <pre><code>void polygon::intersects(line l)
  {
      list &lt;point&gt;::iterator i=pts.begin();
      list &lt;point&gt;::iterator j=i;
  
      while(true)
      {   
          j++;
          if (j==pts.end())
                 j=pts.begin();
  
  
                         if(intersect(*i,*j,l))
             {
              point p=intersection(*i,*j,l);
              pts.insert(j,p);
              intr.push_front(p);
              i++;
              list &lt;point&gt;::iterator k=intr.begin();
              (*i).it=k;
              (*k).it=i;
              (*k).poly=(*i).poly=0;
          }
      i=j;
  }
  
  }   
  </code></pre>
  
  <p>(Snippet from <code>main()</code>)</p>
  
  <pre><code>while(p.n&gt;0)//flag= new beginning, beg= current beginning
      { 
          //Initialise stuff
          while(i!=beg)   
          {
  
  
              t.pts.push_back(*i);
              if( (*i).poly==1 )//point from original polygon 
              {
              //do stuff, increment i
              }
              else if(((*i).poly)==0)
              {
                  //DO something
  
  
  
                  list &lt;point&gt;:: iterator j= (*i).it;
                  list &lt;point&gt;:: iterator k1=j,k2=j;
                  if( j==p.intr.begin() )
                  {
                      j++;
                  }
                  else if(j==end)
                  {
                      j--;
                  }
                  else
                  {// Gets into an infinite loop here
  
  
                      k1--;
                      k2++;
                      if((*j).pair==(*k1).pair)
                      {
  
                          j--;
                      }
                      else
                      {
                          j++;
                      }
                  }
                  t.pts.push_back(*j);
                  i=(*j).it;// This line is supposed to set i to the next iterator in the "intr" list, but it doesnt change!
  
  
              }
              else
              i++;
          }
  
      output.push_back(t);
      }
  </code></pre>
  
  <p>The problem here is in the <code>main()</code> function. When i write <code>i=(*j).it</code>, it does not return the value i want it to. The iterator seems to be pointing to the same point, leading to an infinite loop. I can't find any problem with it.</p>
  
  <p>Here's a sample test case with its answer:</p>
  
  <p>Test case:</p>
  
  <pre><code>12
  0 0 0 5 5 5 5 2 2 2 2 3 4 3 4 4 1 4 1 1 5 1 5 0
  1 0 3
  </code></pre>
  
  <p>Answer expected:</p>
  
  <pre><code>4
  8
  0 0 0 5 3 5 3 4 1 4 1 1 3 1 3 0
  4
  2 2 2 3 3 3 3 2
  4
  3 0 3 1 5 1 5 0
  8
  3 2 3 3 4 3 4 4 3 4 3 5 5 5 5 2
  </code></pre>
  
  <p>Note: The <em>algorithm</em> i used here seems to work (checked with other people who'd used a similar one), but I seem to have made some mistake in implementing it.</p>