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::Data : 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()
?

Quote:

---

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

The idea of std::list::push_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/

---

Quote:

---

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;
};

---

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.

Quote:

---

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.

Quote:

---

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"?

Quote:

---

Originally Posted by andrey_zh

I think the implementation with templates is trivial.

---

So, do it.

Quote:

---

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?

Quote:

---

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.

Quote:

---

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.

....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......

Quote:

---

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:

Quote:

---

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?

Quote:

---

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

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.

Quote:

---

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.

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;
}

---

Quote:

---

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

Quote:

---

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.

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.

Quote:

---

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.

It seems to me, that Iterator is exactly the thing I need. So I have to give up with template implementation.
Two more questions, probably the last ones:

1) Is that ok, to allow access to data of the list only via Iterator?
2) Should I allow to inherit my slist?

Quote:

---

Originally Posted by andrey_zh

It seems to me, that Iterator is the exactly thing I need. So I have to give up with template implementation.

---

You don't have to "give up" anything. How does the std::list accomplish this? An std::list uses iterators to access the elements.

Code:

---

#include <list>
#include <iostream>

int main()
{
  std::list<int> IntList;
  //...
  IntList.push_back(10);
  IntList.push_back(20);
  IntList.push_back(30);
  std::list<int>::iterator it = IntList.begin();
  std::list<int>::iterator itend = IntList.end();
  while (it != itend)
        std::cout << *it << "\n";
  //
}

---

Everything you've said about templates is proven to be wrong:

1) You don't need all of that indirection to access an element.
2) Iterators can be implemented and used with a templated class.

So you need to answer a basic question -- how does std::list seem to accomplish everything that you say you want to do?

The only conclusion that anyone reasonable can come with as to why you can't implement templated list class with iterators is that you do not currently have the knowledge to write the templated class correctly to do these things. The code above proves that there is nothing stopping you from writing the singly-linked list as a templated code using iterators to access the elements.

There is nothing wrong with not knowing how to do something, all of us has asked questions and learned. However, what is wrong is stating conclusions based on faulty "facts".

Regards,

Paul McKenzie

Quote:

---

Originally Posted by andrey_zh

But how about "black box" concept? I want something simple outside and not seen complexity level inside.

---

The std::list is a black box. You give it a T, and by the magic of templated code, you have a linked list of T. You don't have to change any code in the std::list to support your T.

This is why templates are used. With the code you have now, you have to fool around with the internals of your list class just to support a different type. That is not user-friendly or simple.

Regards,

Paul McKenzie