Special home made list problem

[mrcpp]

I'm making a special list and I came into a problem.
The linked list is special because it has sub levels. A cell in a list can include other cells.

The classes that I have are:
record - the cell container of the list that has an item.
rlist - the linked list
rlist::iterator - the iterator of the list

rlist and rlist::iterator are friends of record, and this is the problem that
arrises.

I have:

class record {
public:
   friend class rlist;
   friend class rlist::iterator
...
}

class rlist {
public:
   class iterator {
   ...
   }
...
}

The compiler says about the line "friend class rlist::iterator":
use of undefined type 'rlist'

How can I solve the problem?

[jtsaur]

The error message says it. The compiler has no idear of rlist when it was first encountered.

Reverse the declarations of record and rlist should fix the problem.

Jiryih Tsaur

[mrcpp]

That doesn't solves the problem because rlist and rlist::iterator have to access to the elements of the record that isn't already defined. So this is what the compiler says in that case:

use of undefined type 'record'

[helios]

Hmm... A record doesn't really need to know what an iterator is. rlist needs to know record, and iterator needs to know rlist and record, but that's it.

[MacG]

Not very sure about that, but friends are not inherited, so could it be that iterator can't be a friend of record when it's not a friend of rlist?

[jtsaur]

Okay, rlist needs to know record!

And, you had to have "friend class rlist::iterator" in record which gave you "undefined type 'rlist'" since record needs to know rlist as well due to the nested class iterator.

One way to get around this is to make iterator a top level class such as rlistiterator and you can simply have "friend rlistiterator" in record without declaring any class first.

Otherwise, record needs to know rlist, rlist needs to know record, compiler will complain no matter which one is declared first.

Jiryih Tsaur

[MacG]

couldn't he just make a forward declaration?

[helios]

Okay, look. Here's a sample declaration of a working doubly linked list:

template <class T>
struct Node{
	Node<T> *prev;
	T data;
	Node<T> *next;
	Node();
	Node(const Node<T> &a);
	Node(T a);
};

template <class T>
class List{
	Node<T> *beg;
	Node<T> *end;
	ulong last;
	Node<T> *pLast;
	ulong size;
public:
	List();
	~List();
	void add(T a);
	Node<T> *gml(ulong a);
	void remove(ulong a);
	T &operator[](ulong offset);
	T operator[](ulong offset) const;
	ulong len();
	bool contains(T &search);
	ulong indexof(T &search);
};

There's no reason for Node to know that it belongs to a list. I could take this Node class and use it for a binary tree without making any changes to it.

Now, the iterator only need this information to work: the location of the current node, and the location of the next node. It would be initialized by passing a pointer to the list and it can figure out where the start of the list is.

[jtsaur]

Template is good, and std::list should be looked at first.

However, to simply get rid of dependency problem encountered, use encapsulation. record should only be accessed using its public interface/member methods. Use a friend only when no member method could achieve the same purpose.

Below is a piece of sample code. rlist needs not be a friend. The only friend is the non-member output operator which gives a "cout << record" syntax.

// This sample is by no means a complete list or iterator implemenation.
// It simply shows the idea how they may be implemented.
#include <ostream>

using namespace std;

class record {
private:
int id;
public:
record() : id(0) {}
record(int i) : id(i) {}
void operator<<(ostream &os) { os << id; }
friend ostream &operator<<(ostream &os, const record &r);
};

ostream &operator<<(ostream &os, const record &r)
{
os << r.id;
return os;
}

class rlist {
private:
struct node {
struct node *prev;
struct node *next;
record rec;
node() : prev(this), next(this), rec() {}
node(const record &r) : prev(this), next(this), rec(r) {}
};
struct node *head;
public:
class iterator {
private:
struct node *pnode;
public:
iterator() : pnode(0) {}
iterator(struct node *pn) : pnode(pn) {}
iterator(const iterator &it) : pnode(it.pnode) {}
iterator operator=(const iterator &it) { pnode = it.pnode; return *this; }
bool operator==(const iterator &it) { return pnode == it.pnode; }
bool operator!=(const iterator &it) { return !(*this == it); }
record &operator*() { return pnode->rec; }
record *operator->() { return &pnode->rec; }
iterator& operator++() { pnode = pnode->next; return *this; }
const iterator operator++(int) { iterator tmp = *this; ++*this; return tmp; }
iterator& operator--() { pnode = pnode->prev; return *this; }
const iterator operator--(int) { iterator tmp = *this; --*this; return tmp; }
struct node *getPnode() { return pnode; }
};
rlist() : head(new struct node()) {}
iterator begin()
{
return iterator(head->next);
}
iterator end()
{
return iterator(head);
}
iterator insert(iterator it, const record &r)
{
struct node *itNode = it.getPnode();
struct node *newNode = new struct node(r);
newNode->next = itNode;
newNode->prev = itNode->prev;
itNode->prev->next = newNode;
itNode->prev = newNode;
return iterator(newNode);
}
void push_back(const record& r)
{
insert(end(), r);
}
};

int main()
{
record r1(1);
record r2(2);
rlist rl;
rl.push_back(r1);
rl.push_back(r2);
cout << "member operator: " << endl;
for (rlist::iterator it = rl.begin(); it != rl.end(); ++ it)
{
(*it).operator<<(cout); // okay, but looks weird
cout << endl;
}
cout << "non-member operator: " << endl;
for (rlist::iterator it = rl.begin(); it != rl.end(); ++ it)
cout << *it << endl; // now it's better
}

Jiryih Tsaur

[mrcpp]

Thanks a lot to all for the help
I adopted for one of the solutions that best fits to my problem specificity
.