# STL list containing iterators

This topic is 3248 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I'd like to make two linked lists with elements that can reference each other: typedef list< pair<xy, iter> >::iterator iter; list< pair<xy, iter> > list1; list< pair<xy, iter> > list2; iter it = list1.insert(list1.begin(), make_pair(xy(0,0), NULL)); list2.insert(list2.begin, make_pair(xy(0,0), it)); As you can see, I cannot define the iterator type since the list itself needs to be defined, which needs the iterator, and so on. Is there a base type of iterator that I can use, or anything I can cast between? I tried void* but it can't be casted. I can store a pointer to the address of an iterator (by casting (&it) to void *), but this would involve making a vector of iterators. Is this the best way?

##### Share on other sites
It works well to make a vector of iterators and store in the list the index within the vector (pair<xy, int>). It's a little extra work but it's pretty clean.

##### Share on other sites
Why do you need linked lists with cross links? The awkwardness and lack of clarity may be a sign you need a different data structure.

##### Share on other sites
Great, I've been pondering on this for 15 minutes, and now I have a knot in my brain :)

##### Share on other sites
List nodes never change their location in memory, so you can just obtain and store pointers to elements. But what is the cross-linking for?

##### Share on other sites
A pointer to the elements gives me the data, but I need the node in the linked list so that I can traverse forwards and backwards within the list.

The problem is to calculate intersecting polygons. I store each vertex in a linked list, so that I can travel forwards/backwards, and efficiently remove or add vertices on the fly.

I find all the intersection points, and add them to the lists for both polygons as I go. For each intersection, I need the cross-link information of how to get to the associated vertex on the other polygon.

Then, to find the subtraction of two polygons, I can travel one counter-clockwise until I find an intersection, switch over to the other polygon, and travel that clockwise.

This approach works, but I ran into trouble in the special cases, like when I try and subtract a polygon from itself, or deal with colinear edges. I found a nice library called GPC (Generic Polygon Clipper) which works very well so far.

##### Share on other sites
I think you've over complexified. I know "just use a simple pointer" is considered scary advice in some circles, but if you have element A and B in separate lists, and you want to get from A to B, having A simply point to B seems simple and obvious. Intrusive, yes, but that's not as evil as some make it out to be.

It's possible that what you really want is a lattice, where the intersection points have two parents and two children and everything else is essentially linked lists, but I don't know if STL supports them directly.

I had a problem that involved computing many unions and intersections of simple polygons (and sometimes circles), and I went far, far out of my way to avoid solving the polygon intersection problem in pure form. Ask yourself if you *need* to do this. I found I didn't.

##### Share on other sites
Can't you just make a third list that contains a pair of iterators?

[source language="cpp"]typedef std::list<point> poly_type;typedef std::pair<poly_type::iterator, poly_type::iterator> iter_pair;typedef std::list<iter_pair> intersection_type;poly_type poly1;poly_type poly2;intersection_type intersection;bool done = false;while (!done){   //By searching poly1 and poly2 in parallel, suppose you find that   //the line formed by v_a and v_b from poly1 intersect the line formed   //by v_k and v_j from poly2, at the point x.  Furthermore, since these   //vertices were found by searching through the lists, WLOG we can assume   //that v_k, v_j, v_a, and v_b are iterators into their respective lists,   //rather than actual points.        //If the intersection point was in poly1, don't re-insert it.  Either way   //when this is done v_k is an iterator inside poly1 to the intersection   //point and the insert operation takes constant time due to the hint.   if (*v_a != x)      v_a = poly1.insert(v_a, x);   //If the intersection point was in poly2, don't re-insert it.  Either way   //when this is done v_k is an iterator inside poly2 to the intersection   //point and the insert operation takes constant time due to the hint.   if (*v_k != x)      v_k = poly2.insert(v_k, x);   intersection.insert(std::make_pair(v_a, v_k));}

Now you can iterate over the list "intersection", which will contain iterators into each of the respective lists

##### Share on other sites
Why not just create the subtraction as a separate list? Are you familiar with the .splice() member function? You might find it useful here.

• 34
• 12
• 10
• 9
• 9
×