general purpose Singly-linked list implementation with inheritance
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Thread: general purpose Singly-linked list implementation with inheritance

  1. #1
    Join Date
    Mar 2009
    Location
    Riga, Latvia
    Posts
    128

    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 10:41 AM. Reason: ambiguous wording of the things to do and not to do

  2. #2
    Join Date
    Apr 1999
    Posts
    27,446

    Re: general purpose Singly-linked list implementation with inheritance

    Quote Originally Posted by andrey_zh View Post
    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

  3. #3
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    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.

  4. #4
    Join Date
    Jan 2008
    Location
    California, USA
    Posts
    822

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

  5. #5
    Join Date
    Mar 2009
    Location
    Riga, Latvia
    Posts
    128

    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.

  6. #6
    Join Date
    Jan 2004
    Location
    Düsseldorf, Germany
    Posts
    2,401

    Re: general purpose Singly-linked list implementation with inheritance

    Quote Originally Posted by andrey_zh View Post
    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 View Post
    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 View Post
    I think the implementation with templates is trivial.
    So, do it.
    Quote Originally Posted by andrey_zh View Post
    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 View Post
    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 View Post
    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 10: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.

  7. #7
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,891

    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 10:58 AM.

  8. #8
    Join Date
    Apr 1999
    Posts
    27,446

    Re: general purpose Singly-linked list implementation with inheritance

    Quote Originally Posted by andrey_zh View Post
    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

  9. #9
    Join Date
    Mar 2009
    Location
    Riga, Latvia
    Posts
    128

    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 12:33 PM.

  10. #10
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,891

    Re: general purpose Singly-linked list implementation with inheritance

    Quote Originally Posted by andrey_zh View Post
    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.

  11. #11
    Join Date
    Mar 2009
    Location
    Riga, Latvia
    Posts
    128

    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 01:08 PM.

  12. #12
    Join Date
    Apr 1999
    Posts
    27,446

    Re: general purpose Singly-linked list implementation with inheritance

    Quote Originally Posted by andrey_zh View Post
    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

  13. #13
    Join Date
    Mar 2009
    Location
    Riga, Latvia
    Posts
    128

    Re: general purpose Singly-linked list implementation with inheritance

    Quote Originally Posted by Paul McKenzie View Post
    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.

  14. #14
    Join Date
    Jan 2004
    Location
    Düsseldorf, Germany
    Posts
    2,401

    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.

  15. #15
    Join Date
    Jan 2004
    Location
    Düsseldorf, Germany
    Posts
    2,401

    Re: general purpose Singly-linked list implementation with inheritance

    Quote Originally Posted by andrey_zh View Post
    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.

Page 1 of 2 12 LastLast

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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center