-
March 16th, 2009, 06:20 PM
#1
general purpose Singly-linked list implementation with inheritance
The challenge is to implement a general purpose Singly-linked list.
I've found a good decision with templates, it looks natural and works good, but it's too long to write something like list->get_node()->get_data()->get_some_stuff()->set_value(value), when number of fields is more than one, and I have to add class or structure to a node. So class template is not the thing i'm searching for.
Particularly, I want to incorporate new fields to a node witch is an inner class of a Slist class.
But I'm stuck with syntax
Here is my code:
class Slist
{
private:
class Node; // just enough for a node
class Sentinel; // sentinel node, no data fields
protected:
class Data; // data node, opened for inheritance - ???
private:
Sentinel *first_node;
Node *last_node;
};
class Slist::Node
{
public:
// trivial interface stuff
private:
Node *next_node;
};
class Slist::Sentinel : public Slist::Node
{
// it seems, that's all
};
class Slist:ata : public Slist::Node
{
// that's all, but only for some time
};
That is to say, I want to inherit Slist and add fields to it's inner class Data
How it could be done?
P.S.: What will happen in such an erroneous case:
((Node *)(first_node/*Remenber, It's Sentinel*/))->call_some_interface_method_of_Data_class()
?
Last edited by andrey_zh; March 17th, 2009 at 09:41 AM.
Reason: ambiguous wording of the things to do and not to do
-
March 16th, 2009, 07:10 PM
#2
Re: general purpose Singly-linked list implementation with inheritance
Originally Posted by andrey_zh
The challenge is to implement a general purpose Singly-linked list.
I've found a good decision with templates, it looks natural, but it's too long to write something like list->get_node()->get_data()->get_some_stuff()->set_value(value), when number of fields is more than one, and I have to add class or structure to a node
In your invesigative searches, did you see std::list? It is a doubly linked list. Do you see anywhere in using std::list anything as you've described, using all of those function calls to set a value?
No. All you need to do is call std::list::push_back(). All of those indirections are not necessary. So you should investigate the interface to well-known, standard classes such as std::list, so that you get a more coherent understanding of how to implement your home-made singly linked list.
Regards,
Paul McKenzie
-
March 17th, 2009, 03:12 AM
#3
Re: general purpose Singly-linked list implementation with inheritance
The idea of std::list:ush_back() is create a new node and pass value as argument to set its underlying value.
Code:
void push_back ( const T& x );
HTML Code:
http://www.cplusplus.com/reference/stl/list/
Thanks for your help.
-
March 17th, 2009, 05:30 AM
#4
Re: general purpose Singly-linked list implementation with inheritance
I've found a good decision with templates, it looks natural, but it's too long to write something like list->get_node()->get_data()->get_some_stuff()->set_value(value), when number of fields is more than one, and I have to add class or structure to a node
Hm... please excuse me if I'm not getting this right,
but if it's a general purpose, shouldn't you be using templates like you said?
but I don't see any templates there
And like Paul McKenzie noted, I don't think you need all that indirections.
maybe something like this might help?
Code:
template <typename T>
class SList
{
public:
// ...
void push_back(const T& ref)
{
SListData<T>* ptr = new SListData<T>(ref);
if(empty()) // assume empty() is defined
{
head = tail = ptr;
}
else
{
tail->next = ptr;
tail = ptr;
}
}
private:
// ...
SListData<T>* head;
SListData<T>* tail;
};
template <typename T>
class SListData
{
// friend and others ...
T item;
SListData* next;
};
-
March 17th, 2009, 09:29 AM
#5
Re: general purpose Singly-linked list implementation with inheritance
Sorry, if someone understood that I'm working on implementation with templates. Templates are the thing I'm not interested in! I *do not* want to write some_node->get_item()->get_one_more_field() when my nodes will have *more than one* field.
I think the implementation with templates is trivial.
I want (but I'm not sure, is it possible) to add fields to inner class Data of class Slist.
I assume it could be done inheriting the whole class Slist. But the question is how to do it?
Do not:
1) provide solutions with STL
2) provide solutions with templates
Why so complex?
1) I don't want to clog global name space
1.1 ) but I do want to have short type names inside my classes
2) It is not a part of a real program but a small exercise aimed to deeper learn C++
Sorry once more for my pure English.
-
March 17th, 2009, 09:48 AM
#6
Re: general purpose Singly-linked list implementation with inheritance
Originally Posted by andrey_zh
Sorry, if someone understood that I'm working on implementation with templates. Templates are the thing I'm not interested in!
You should be if you are interested in writing container classes like lists.
Originally Posted by andrey_zh
I *do not* want to write some_node->get_item()->get_one_more_field() when my nodes will have *more than one* field.
So don't. Implement iterators and write
Code:
it->get_one_more_field();
Or do you want to be able to access a member "one_more_field" without writing "one_more_field"?
Originally Posted by andrey_zh
I think the implementation with templates is trivial.
So, do it.
Originally Posted by andrey_zh
I want (but I'm not sure, is it possible) to add fields to inner class Data of class Slist.
I assume it could be done inheriting the whole class Slist. But the question is how to do it?
No, the question is why to do it?
Originally Posted by andrey_zh
1) I don't want to clog global name space
1.1 ) but I do want to have short type names inside my classes
Neither namespaces, nor the names of your member functions have anything to do with this.
Originally Posted by andrey_zh
2) It is not a part of a real program but a small exercise aimed to deeper learn C++
If your aim is to deeper learn C++, I would suggest you take some advice from people here in this form that do have this deep knowledge.
Last edited by treuss; March 17th, 2009 at 09:51 AM.
More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason - including blind stupidity. --W.A.Wulf
Premature optimization is the root of all evil --Donald E. Knuth
Please read Information on posting before posting, especially the info on using [code] tags.
-
March 17th, 2009, 09:49 AM
#7
Re: general purpose Singly-linked list implementation with inheritance
....So you want to learn how to use the language by jumping through all sorts of hoops to do something without using the tools the language provides for the purpose? That doesn't make sense to me.
It might if you were restricted to C, but if you're not......
Last edited by Lindley; March 17th, 2009 at 09:58 AM.
-
March 17th, 2009, 10:44 AM
#8
Re: general purpose Singly-linked list implementation with inheritance
Originally Posted by andrey_zh
Sorry, if someone understood that I'm working on implementation with templates. Templates are the thing I'm not interested in!
Here is what you stated in your first post:
I've found a good decision with templates, it looks natural and works good, but it's too long to write something like list->get_node()->get_data()->get_some_stuff()->set_value(value)
So my response to you is that you did not implement your template class correctly.
You say you need to do all of that work when you use templates, but at the same time, there is a linked list class that uses templates that doesn't need all of that. So what is your conclusion there? Why do you need to do so much work with your template implementation to set a value, and std::list doesn't need all that work?
It is not a part of a real program but a small exercise aimed to deeper learn C++
You really need to go back and see what you did wrong when you implemented your template "solution", since there is no need for all of that work, as proven by std::list.
Regards,
Paul McKenzie
-
March 17th, 2009, 11:27 AM
#9
Re: general purpose Singly-linked list implementation with inheritance
My template solution is following. Here are class definitions only. It's OK, it works, but it looks like an example in a book for newbies.
Code:
template <class T>
class Slist
{
public:
// dull interface stuff
protected:
class Node;
class Sentinel;
class Data;
Sentinel *first_node;
Node *last_node;
};
template <class T>
class Slist<T>::Node
{
public:
friend Slist<T>;
Node( void );
Node( const Node* next_node );
Node* get_next( void ) const;
void set_next( Node* next_node );
virtual const T& get_data( void ) const = 0; // fail for Sentinel
virtual void set_data( const T& data ) = 0; // and do asked for Data
protected:
Node *next_node;
};
template <class T>
class Slist<T>::Sentinel : public Slist<T>::Node
{
public:
Sentinel( void ) : Node() { }
Sentinel( const Sentinel* next_node ) : Node( next_node ) { }
const T& get_data( void ) const;
void set_data( const T& data );
};
template <class T>
class Slist<T>::Data : public Slist<T>::Node
{
public:
Data( const T& data, const Node* next_node = 0 );
const T& get_data( void ) const;
void set_data( const T& data );
private:
T data;
};
Saying simply, I want the same except for adding new fields to Data by inheriting Slist.
Last edited by andrey_zh; March 17th, 2009 at 11:33 AM.
-
March 17th, 2009, 11:42 AM
#10
Re: general purpose Singly-linked list implementation with inheritance
Originally Posted by andrey_zh
It's OK, it works, but it looks like an example in a book for newbies.
That's a good thing. Clean, simple code that just works is the best kind of code.
-
March 17th, 2009, 12:05 PM
#11
Well could someone help me with this one
Well could someone help me with this one. This demonstrates one(particular) of the problems I have with my "Slist with inheritance".
The code is wrong! I assume I should add 'virtual' and probaly something more somewhere to compile it. Where?
Is it possibly to do the thing I want?
/Don't pay attention that everything is public./
Code:
class Base
{
public:
Base( void ) { inner = new Inner; }
~Base( void ) { delete inner; }
class Inner
{
public:
int inherited_field;
};
Inner *inner;
};
class Derived : public Base
{
public:
Derived( void ) : Base() { }
class Inner
{
public:
int further_field;
};
};
int main( void )
{
Derived object;
object.inner->inherited_field = 1;
object.inner->further_field = 2;
}
Last edited by andrey_zh; March 17th, 2009 at 12:08 PM.
-
March 17th, 2009, 12:33 PM
#12
Re: general purpose Singly-linked list implementation with inheritance
Originally Posted by andrey_zh
It's OK, it works, but it looks like an example in a book for newbies.
So what?
So you're saying that because it looks simple, it is no good? You have already everything -- just change the type T, and you have your other list type.
What do you think you're accomplishing by making the code complicated? If you make things overly complex for no reason, that is the sign of a newbie programmer. The expert programmer is the one that can turn the complex into simple code that can be maintained.
Regards,
Paul McKenzie
-
March 17th, 2009, 12:42 PM
#13
Re: general purpose Singly-linked list implementation with inheritance
Originally Posted by Paul McKenzie
The expert programmer is the one that can turn the complex into simple code that can be maintained.
But how about "black box" concept? I want something simple outside and not seen complexity level inside.
-
March 17th, 2009, 12:51 PM
#14
Re: general purpose Singly-linked list implementation with inheritance
To make this work, you have to do some rather dirty programming:
Code:
class Base
{
public:
Base() { inner = new Inner; }
~Base() { delete inner; }
class Inner
{
public:
int inherited_field;
virtual ~Inner() {}
};
Inner *inner;
};
class Derived : public Base
{
public:
Derived() : Base() { delete inner; inner = new Inner(); }
class Inner : public Base::Inner
{
public:
int further_field;
virtual ~Inner() {}
};
};
int main( void )
{
Derived object;
object.inner->inherited_field = 1;
dynamic_cast<Derived::Inner*>(object.inner)->further_field = 2;
}
I believe the above code will work correctly, but I would really advise against using something like that. If you define Base::inner to be of type Base::Inner making it suddenly be of a different type (Derived::Inner) lacks clearness and style.
More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason - including blind stupidity. --W.A.Wulf
Premature optimization is the root of all evil --Donald E. Knuth
Please read Information on posting before posting, especially the info on using [code] tags.
-
March 17th, 2009, 01:08 PM
#15
Re: general purpose Singly-linked list implementation with inheritance
Originally Posted by andrey_zh
But how about "black box" concept? I want something simple outside and not seen complexity level inside.
Then look at how the STL containers and the Iterator concept are implemented.
More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason - including blind stupidity. --W.A.Wulf
Premature optimization is the root of all evil --Donald E. Knuth
Please read Information on posting before posting, especially the info on using [code] tags.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|