Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Linked list within a linked list

Reply
Thread Tools

Linked list within a linked list

 
 
joshd
Guest
Posts: n/a
 
      09-30-2006
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

 
Reply With Quote
 
 
 
 
John Carson
Guest
Posts: n/a
 
      09-30-2006
"joshd" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com
> 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.

--
John Carson




 
Reply With Quote
 
 
 
 
Gianni Mariani
Guest
Posts: n/a
 
      09-30-2006
joshd wrote:
> 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();
}
 
Reply With Quote
 
joshd
Guest
Posts: n/a
 
      09-30-2006
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

 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      10-01-2006
Gianni Mariani wrote:

> joshd wrote:
>> 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;



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
 
Reply With Quote
 
John Carson
Guest
Posts: n/a
 
      10-01-2006
"joshd" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com
> 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.

--
John Carson



 
Reply With Quote
 
Gianni Mariani
Guest
Posts: n/a
 
      10-01-2006
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.
 
Reply With Quote
 
Gianni Mariani
Guest
Posts: n/a
 
      10-01-2006
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();
}
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      10-01-2006
Gianni Mariani wrote:

> 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
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      10-01-2006
Gianni Mariani wrote:

> 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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Detection of a loop in a linked tree (or linked list) mac C Programming 1 05-27-2008 01:43 PM
Airplane Program with Linked Lists. The linked list portion is veryconfusing to me. jawdoc C++ 9 03-10-2008 03:38 AM
Linked list, New try (was:Linked list, no out put,help) fool C Programming 14 07-03-2006 12:29 AM
Generating a char* from a linked list of linked lists Chris Ritchey C++ 7 07-10-2003 10:12 PM
Generating a char* from a linked list of linked lists Chris Ritchey C Programming 7 07-10-2003 10:12 PM



Advertisments