Linked list within a linked list

J

joshd

Hello,

Im sorry if this question has been asked before, but I did search
before posting and couldnt find an answer to my problem. I have two
classes each with corresponding linked lists, list1 and list2, each
node within list1 has various data and needs to have a pointer to the
corresponding node in list2, but I cant figure out how to do this.

Could someone explain what I might be missing, or maybe point me in the
direction of a good article which would help me out? Because for
something that should be so simple, it's really got me stumped.

Thanks,
Josh
 
J

John Carson

joshd said:
Hello,

Im sorry if this question has been asked before, but I did search
before posting and couldnt find an answer to my problem. I have two
classes each with corresponding linked lists, list1 and list2, each
node within list1 has various data and needs to have a pointer to the
corresponding node in list2, but I cant figure out how to do this.

Could someone explain what I might be missing, or maybe point me in
the direction of a good article which would help me out? Because for
something that should be so simple, it's really got me stumped.

I don't see how this question relates to the title of your post. There is
nothing in your description to suggest a linked list within a linked list.

More generally, stating the problem clearly would help. Is this a one-off
synchronisation of the lists or does it have to be done repeatedly as the
lists are added to? If so, how are the lists added to? Are the two classes
friends of each other? Is the "corresponding node" the node that occurs in
the same position in the list?

Assuming the answer to the last question is yes, for a one-off
synchronisation, you can do it by iterating over both lists. The address of
a list item is given by

&(*iter)

where iter is the iterator. Iterating over both lists simultaneously means
you can retrieve the addresses of corresponding items at the same time and
then store a pointer in each. Obviously the T1 in

list<T1> list1;

will need to have a member variable that is a pointer to the T2 type in

list<T2> list2;

and vice versa.

If you want synchronisation on the run, then you will need to add to both
lists at the same time (or else do a search over each list to find the nodes
that are "corresponding"). If you add to the end of both lists, then you can
get the address from

&(*list1.end()) and &(*list2.end())

after you have made the addition. Adding at the beginning is analogous.

If you add in the middle using insert to add a single element, then insert
returns an iterator pointing to the new element. You retrieve a pointer from
this iterator following the same pattern as illustrated above.
 
G

Gianni Mariani

joshd said:
Hello,

Im sorry if this question has been asked before, but I did search
before posting and couldnt find an answer to my problem. I have two
classes each with corresponding linked lists, list1 and list2, each
node within list1 has various data and needs to have a pointer to the
corresponding node in list2, but I cant figure out how to do this.

Could someone explain what I might be missing, or maybe point me in the
direction of a good article which would help me out? Because for
something that should be so simple, it's really got me stumped.

This is just a proof of concept, i.e. how to do it using std::list.
These are using iterators to point to one another.

#include <list>

// declare 2 structs
struct A;
struct B;

// define the respective list type
typedef std::list<A> Alist_t;
typedef std::list<B> Blist_t;

// define the classes
struct A
{
Blist_t::iterator bitr;

A( const A & ) {} // no copying bitr
A() {}
};

struct B
{
Alist_t::iterator aitr;
B( const B & ) {} // no copying aitr !
B() {}
};

// some silly example code
void tst()
{
Alist_t al;
Blist_t bl;

// make an A element
al.push_front( A() );

// make a B element
bl.push_front( B() );

// Set up iterators to point to each other
al.front().bitr = bl.begin();
bl.front().aitr = al.begin();

}

int main()
{
tst();
}
 
J

joshd

I apologize that I wasnt too clear with my first post, Im still trying
to grasp the linked list concept. Maybe this visual representation I
jotted out, with a parent-child scenario, will help you understand my
needs.

parent linklist
|
parent node -> child linklist + child2 list + child3 list + ....
parent node -> child linklist + child2 list + ....
parent node -> child linklist + child2 list + ....

Can this be done without iterators? or should I study more to wrap my
mind around STL and iterators?

Thanks for all your help!

Josh
 
K

Kai-Uwe Bux

Gianni said:
This is just a proof of concept, i.e. how to do it using std::list.
These are using iterators to point to one another.

#include <list>

// declare 2 structs
struct A;
struct B;

// define the respective list type
typedef std::list<A> Alist_t;
typedef std::list<B> Blist_t;


Formally, this is undefined behavior because A and B are incomplete types
(see [17.4.3.6/1 and 2]). Accordingly, the code fails with g++ and stdlibc++
when g++ is compiled with --enable-concept-check.

// define the classes
struct A
{
Blist_t::iterator bitr;

A( const A & ) {} // no copying bitr
A() {}
};

struct B
{
Alist_t::iterator aitr;
B( const B & ) {} // no copying aitr !
B() {}
};

// some silly example code
void tst()
{
Alist_t al;
Blist_t bl;

// make an A element
al.push_front( A() );

// make a B element
bl.push_front( B() );

// Set up iterators to point to each other
al.front().bitr = bl.begin();
bl.front().aitr = al.begin();

}

int main()
{
tst();
}


Best

Kai-Uwe Bux
 
J

John Carson

joshd said:
I apologize that I wasnt too clear with my first post, Im still trying
to grasp the linked list concept. Maybe this visual representation I
jotted out, with a parent-child scenario, will help you understand my
needs.

parent linklist
|
parent node -> child linklist + child2 list + child3 list + ....
parent node -> child linklist + child2 list + ....
parent node -> child linklist + child2 list + ....

Still not clear. You have used three symbols, | -> and +. I think I have got
the first two, but what does + denote? And what does the switch from
"linklist" to "list" signify?

Is it simply that you have a parent linked list and that each node in the
parent linked list contains a linked list?
Can this be done without iterators? or should I study more to wrap my
mind around STL and iterators?

If you are writing your own linked list, then you can avoid iterators. If
you are using the standard library linked list, then iterators are
fundamental. Writing your own linked list can be a useful learning exercise,
but using the standard library containers is almost always preferable for
any program that isn't a learning exercise. You should definitely learn the
standard library containers, along with iterators.
 
G

Gianni Mariani

Kai-Uwe Bux wrote:
....
Formally, this is undefined behavior because A and B are incomplete types
(see [17.4.3.6/1 and 2]). Accordingly, the code fails with g++ and stdlibc++
when g++ is compiled with --enable-concept-check.

Ah - well, this makes lists much stl containers much less
interesting...sigh.

I'd better go back and finish up the Austria containers then.

Just as a matter of interest, do you know why does the standard need this ?

BTW - the version of the gcc compiler I have does not support
--enable-concept-check.
 
G

Gianni Mariani

Kai-Uwe Bux wrote:
....
Formally, this is undefined behavior because A and B are incomplete types
(see [17.4.3.6/1 and 2]). Accordingly, the code fails with g++ and stdlibc++
when g++ is compiled with --enable-concept-check.


OK - this should conform now.

#include <list>

template <typename T>
struct Foo
{
// declare 2 structs
struct A;
struct B;

// define the respective list type
typedef std::list<A> Alist_t;
typedef std::list<B> Blist_t;

// define the classes
struct A
{
typename Blist_t::iterator bitr;

A( const A & ) {} // no copying bitr
A() {}
};

struct B
{
typename Alist_t::iterator aitr;
B( const B & ) {} // no copying aitr !
B() {}
};
};

typedef Foo<int> X;

// some silly example code
void tst()
{
X::Alist_t al;
X::Blist_t bl;

// make an A element
al.push_front( X::A() );

// make a B element
bl.push_front( X::B() );

// Set up iterators to point to each other
al.front().bitr = bl.begin();
bl.front().aitr = al.begin();

}

int main()
{
tst();
}
 
K

Kai-Uwe Bux

Gianni said:
Kai-Uwe Bux wrote:
...
Formally, this is undefined behavior because A and B are incomplete types
(see [17.4.3.6/1 and 2]). Accordingly, the code fails with g++ and
stdlibc++ when g++ is compiled with --enable-concept-check.

Ah - well, this makes lists much stl containers much less
interesting...sigh.

Yeah, it's a real bummer. I once had a nice caching container (generically
implementing a last recently used drop policy) but it suffers from this
flaw.
I'd better go back and finish up the Austria containers then.
Huh?


Just as a matter of interest, do you know why does the standard need this?

It does not: most implementation will work just fine and implementors have
to put in extra code to make it fail :)

However, the standard just takes the easy wording option: since templates
like pair need complete types, the standard just put a general requirement.
Also, at the time they were just careful: you can always lift requirements
in future version of the standard, but you cannot tighten them. Probably, a
proposal to replace the general requirement by more finetuned ones could
pass.

BTW - the version of the gcc compiler I have does not support
--enable-concept-check.

--enable-concept-check is a built option, you have to pass it to the
configure script before you build g++ from the source.


Best

Kai-Uwe Bux
 
K

Kai-Uwe Bux

Gianni said:
Kai-Uwe Bux wrote:
...
Formally, this is undefined behavior because A and B are incomplete types
(see [17.4.3.6/1 and 2]). Accordingly, the code fails with g++ and
stdlibc++ when g++ is compiled with --enable-concept-check.


OK - this should conform now.

#include <list>

template <typename T>
struct Foo
{
// declare 2 structs
struct A;
struct B;

// define the respective list type
typedef std::list<A> Alist_t;
typedef std::list<B> Blist_t;

Still incomplete types.
// define the classes
struct A
{
typename Blist_t::iterator bitr; // line 17

A( const A & ) {} // no copying bitr
A() {}
};

struct B
{
typename Alist_t::iterator aitr; // line 25
B( const B & ) {} // no copying aitr !
B() {}
};
};

typedef Foo<int> X;

// some silly example code
void tst()
{
X::Alist_t al; // line 36
X::Blist_t bl;

// make an A element
al.push_front( X::A() );

// make a B element
bl.push_front( X::B() );

// Set up iterators to point to each other
al.front().bitr = bl.begin();
bl.front().aitr = al.begin(); // line 47

}

int main()
{
tst();
}
[Line numbers added for reference]

Still fails using concept checks:

mariani_002.cc: In instantiation of 'Foo<int>::B':
/added/pkg/gcc-4.1.1/usr/lib/gcc/i686-pc-linux-gnu/4.1.1/../../../../include/c++
/4.1.1/bits/boost_concept_check.h:216: instantiated
from '__gnu_cxx::_SGIAssig
nableConcept<Foo<int>::B>'
/added/pkg/gcc-4.1.1/usr/lib/gcc/i686-pc-linux-gnu/4.1.1/../../../../include/c++
/4.1.1/bits/stl_list.h:402: instantiated from 'std::list<Foo<int>::B,
std::all
ocator<Foo<int>::B> >'
mariani_002.cc:17: instantiated from 'Foo<int>::A'
/added/pkg/gcc-4.1.1/usr/lib/gcc/i686-pc-linux-gnu/4.1.1/../../../../include/c++
/4.1.1/bits/boost_concept_check.h:216: instantiated
from '__gnu_cxx::_SGIAssig
nableConcept<Foo<int>::A>'
/added/pkg/gcc-4.1.1/usr/lib/gcc/i686-pc-linux-gnu/4.1.1/../../../../include/c++
/4.1.1/bits/stl_list.h:402: instantiated from 'std::list<Foo<int>::A,
std::all
ocator<Foo<int>::A> >'
mariani_002.cc:36: instantiated from here
mariani_002.cc:25: error: no type named 'iterator' in 'class
std::list<Foo<int>:
:A, std::allocator<Foo<int>::A> >'
mariani_002.cc: In function 'void tst()':
mariani_002.cc:47: error: 'struct Foo<int>::B' has no member named 'aitr'


Best

Kai-Uwe Bux
 
J

joshd

Still not clear. You have used three symbols, | -> and +. I think I have got
the first two, but what does + denote? And what does the switch from
"linklist" to "list" signify?

They have no meaning, I just used those characters to distinguish
relationships between the linked list, node, and so on.
Is it simply that you have a parent linked list and that each node in the
parent linked list contains a linked list?

Yes this is exactley what Im looking for. I just am unable to figure
out how to do it, maybe Im missing something simple or havent read the
correct articles. Could you please provide some information on doing
it this way.
If you are writing your own linked list, then you can avoid iterators. If
you are using the standard library linked list, then iterators are
fundamental. Writing your own linked list can be a useful learning exercise,
but using the standard library containers is almost always preferable for
any program that isn't a learning exercise. You should definitely learn the
standard library containers, along with iterators.

This is a learning exercise, I would really like to fully grasp the
concepts before moving onto something else. I dont like to 'partially'
know what Im doing.

Thanks for all your help! Greatly appreciated!

Josh
 
G

Gianni Mariani

Kai-Uwe Bux said:
Gianni said:
Kai-Uwe Bux wrote:
...
Formally, this is undefined behavior because A and B are incomplete types
(see [17.4.3.6/1 and 2]). Accordingly, the code fails with g++ and
stdlibc++ when g++ is compiled with --enable-concept-check.

OK - this should conform now.
....

Still fails using concept checks:

I think this is a compiler bug, although I'm not sure. The check in the
gcc concept check is too aggressive in this case.

The Comeau compiler failed to compile the first example and succeeded in
the second example. (not that it's a bug either way but just a data point).
 
J

John Carson

joshd said:
Yes this is exactley what Im looking for. I just am unable to figure
out how to do it, maybe Im missing something simple or havent read the
correct articles. Could you please provide some information on doing
it this way.


This is a learning exercise, I would really like to fully grasp the
concepts before moving onto something else. I dont like to
'partially' know what Im doing.


If the learning exercise includes writing the code for a linked list, then I
suggest you do that first, since it is fairly complicated, requiring a good
grasp of pointer manipulation.

Once you have a linked list class, then the rest of it isn't that hard, as I
will illustrate using std::list. The code uses structs with everything
public in order to keep it simple.

#include <list>
#include <iostream>
#include <string>
using namespace std;

// give the child some members for use in testing
struct ChildCell
{
size_t index;
string name;
ChildCell *pmatching;
ChildCell(size_t i, string nme) : index(i), name(nme), pmatching(0)
{}
ChildCell() : index(0), pmatching(0)
{}
};

struct ParentCell
{
list<ChildCell> childList;
int a, b;
};

int main()
{
list<ParentCell> parentList;
// add two nodes to parentList
parentList.push_back(ParentCell());
parentList.push_back(ParentCell());

// Add four nodes to the child list in each parent node
// Do it for first parent node
list<ParentCell>::iterator it = parentList.begin();
for(size_t i = 0; i<4; ++i)
it->childList.push_back(ChildCell(i, "First_Child_List_Cell"));
// for later use, store a reference to the first childList
list<ChildCell> & firstChildList = it->childList;

// Increment iterator to move to second parent node
// then add four nodes to its child list
++it;
for(size_t i = 0; i<4; ++i)
it->childList.push_back(ChildCell(i, "Second_Child_List_Cell"));
// for later use, store a reference to the second childList
list<ChildCell> & secondChildList = it->childList;

// Now we make each cell in the child list store a pointer to its
// corresponding cell in the other list
list<ChildCell>::iterator it1, it2;
for(it1 = firstChildList.begin(),
it2 = secondChildList.begin();
it1!= firstChildList.end()
&& it2!= secondChildList.end();
++it1, ++it2)
{
it1->pmatching = &(*it2);
it2->pmatching = &(*it1);
}

// test that it worked
cout << "Iterating over first child list\n";
for(it1 = firstChildList.begin();
it1!= firstChildList.end(); ++it1)
{
cout << "Name is " << it1->name;
cout << " and index is " << it1->index << endl;

cout << "Name of corresponding cell is ";
cout << it1->pmatching->name;
cout << " and index is ";
cout << it1->pmatching->index << endl << endl;
}

cout << "\n\nIterating over second child list\n";
for(it2 = secondChildList.begin();
it2!= secondChildList.end(); ++it2)
{
cout << "Name is " << it2->name;
cout << " and index is " << it2->index << endl;

cout << "Name of corresponding cell is ";
cout << it2->pmatching->name;
cout << " and index is ";
cout << it2->pmatching->index << endl << endl;
}
return 0;
}
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,832
Latest member
GlennSmall

Latest Threads

Top