• Advertisement
Sign in to follow this  

STL list containing iterators

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement