dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 12 of 12

Thread: Templates: Generic Linked List, I stuck at returning type in template functions.

  1. #1
    Join Date
    Jul 2017
    Location
    Greece
    Posts
    112

    Question Templates: Generic Linked List, I stuck at returning type in template functions.

    Hello.

    Until now, I used to do things the old way (As I learned in the java course). For example, in order to create a generic linked list, I would create a Node class which the user can inherit to define what data this node will contain and a List class which the user can inherit in order to override things like the search method etc.

    I started learning templates and for learning purposes, I'm trying to make a linked list. This is where I stuck:

    Code:
            //Search.
            template<typename U>
            T *search(bool (*compare)(const T other, U custom), U custom)
            {
                //Current node starts from the head.
                LinkedListNode<T> *current = m_Head;
    
                //GO though each node until the end.
                while (current != NULL)
                {   
                    //Do the comparison based on the user's custom function.
                    if ( compare(current->m_Data, custom) )
                        return current->m_Data;
    
                    //Next node.
                    current = current->m_Next;
                }
          
                //??????????????????????????????????????????????????????
                //Not found.
                return null; //WHAT SHOULD I RETURN HERE????????????????????
               //??????????????????????????????????????????????????????
            }
    If the comparison (as defined by the user) returns true, then I'm returning current->m_Data which is type T. But if the search fails what should I return? I don't know what type T is yet.

    I solved this by returning the entire list node to the user as a pointer. This solves the problem but the following is very confusing:
    Code:
    //Search.
            template<typename U>
            LinkedListNode<T> *search(bool (*compare)(const T other, U custom), U custom)
            {
                //Current node starts from the head.
                LinkedListNode<T> *current = m_Head;
    
                //GO though each node until the end.
                while (current != NULL)
                {   
                    //Do the comparison based on the user's custom function.
                    if ( compare(current->m_Data, custom) )
                        return current;
    
                    //Next node.
                    current = current->m_Next;
                }
    
                //Not found.
                return NULL;
            }
    
    
            //Remove.
            template<typename U>
            bool remove(bool (*compare)(const T other, U custom), U custom)
            {
                LinkedListNode<T> *found = this->search(compare, custom);
    
                if (found != NULL)
                {
                    delete found;
                    return true;
                }
    
                return false;
            }
    Remove() uses the search method to find and remove a node from the list. As you can see it returns a boolean. The thing is that I want to return the actual data T which is stored in found->m_Data. The reason is that if that data is an allocated object I want to give the user that object back to him because the deletion of the node won't handle the deletion of the data too. Also, I can't return the node as I did in the search method because I am deleting it.

    Should I create another wrapper class to hold the data? But this is not good. After returning that wrapper object, who is going to delete it afterward, the user?

    What should I do?

    Should I ask the user through a constructor to provide me with a T value that will be returned in cases such as the above? For example, if the linked list stores int's the user might give me the value -1 in case of a search not found error. If he stores pointers, he might give me NULL.
    Last edited by babaliaris; September 7th, 2019 at 11:35 AM.

  2. #2
    Arjay's Avatar
    Arjay is offline Moderator / MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    13,108

    Re: Templates: Generic Linked List, I stuck at returning type in template functions.

    Look at the stl std::list<> implementation to get ideas.

  3. #3
    Join Date
    Jul 2017
    Location
    Greece
    Posts
    112

    Re: Templates: Generic Linked List, I stuck at returning type in template functions.

    Quote Originally Posted by Arjay View Post
    Look at the stl std::list<> implementation to get ideas.
    I just tried and my eyes popped out

  4. #4
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,876

    Re: Templates: Generic Linked List, I stuck at returning type in template functions.

    You don't return the data. You return an iterator for the data and if the search doesn't find, then you return the equivalent of list::end().

    If you haven't yet done much with iterators, now is the time to get to grips with them.

    If you look at std::list, you'll find that there is no .find() method. You don't need one. There is the standard algorithm std::find() (see http://www.cplusplus.com/reference/algorithm/find/) which works with the containers. if you write your own container, then you don't provide your own search method, you make sure that your container works with the standard algorithms (find() in this case) using iterators.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.3.5)

  5. #5
    Join Date
    Jul 2017
    Location
    Greece
    Posts
    112

    Re: Templates: Generic Linked List, I stuck at returning type in template functions.

    Quote Originally Posted by 2kaud View Post
    You don't return the data. You return an iterator for the data and if the search doesn't find, then you return the equivalent of list::end().

    If you haven't yet done much with iterators, now is the time to get to grips with them.

    If you look at std::list, you'll find that there is no .find() method. You don't need one. There is the standard algorithm std::find() (see http://www.cplusplus.com/reference/algorithm/find/) which works with the containers. if you write your own container, then you don't provide your own search method, you make sure that your container works with the standard algorithms (find() in this case) using iterators.
    The concept of an iterator is fundamental to understanding the C++ Standard Template Library (STL) because iterators provide a means for accessing data stored in container classes such a vector, map, list, etc.
    source of the above quote

    Ok, I searched c++ iterators on the internet and found this. I'm new to STL and I didn't know that. Thank you for pointing me in the right direction. I'm off my way studying! It's time to move on to some more c++ and start leaving C once and for all.

  6. #6
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,876

    Re: Templates: Generic Linked List, I stuck at returning type in template functions.

    If you've not yet ready to use iterators, then another option would be to return in c++17 optional<>. See https://en.cppreference.com/w/cpp/utility/optional. optional can either have a value (eg in this case the data) or no value (nullopt) which would be returned if the search didn't find any items.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.3.5)

  7. #7
    Join Date
    Jul 2017
    Location
    Greece
    Posts
    112

    Re: Templates: Generic Linked List, I stuck at returning type in template functions.

    I think I get the idea now. Tell me if I understood it correctly

    Something like this (code did not tested):
    User's Code:
    Code:
    //The other must be the same type as the search method template.
    bool compareIterator(int self, int other)
    {
        return self==other;
    }
    
    int main()
    {
    LinkedList<int> list;
    
    for (int i = 0; i < 10; i++)
        list.append(i);
    
    list.setCompareIterator(compareIterator);
    
    //search can take any template value.
    if ( list.search(5) != list.end() )
        list.get( list.search(5) );
    }
    list.get() will return the template data based on the return address of list.search() . If list.get() receives a wrong address or the empty end node of the list, it will throw an exception.

    Also If I'm right, most STL data structures have some marking nodes for this purpose, right? For example, in a linked list the head and the tail should be empty nodes and the actuall data should be between them. For example, if I have a list with 10 data inside it the total nodes of the list will be 12 (plus two for the mark nodes).

    PS: I know about the std::\optional and std::any but I would like to avoid them for now.
    Last edited by babaliaris; September 7th, 2019 at 02:45 PM.

  8. #8
    Join Date
    Jul 2017
    Location
    Greece
    Posts
    112

    Re: Templates: Generic Linked List, I stuck at returning type in template functions.

    This is my current implementation and it works quite well.

    Code:
    #ifndef VMPS_LINKEDLIST_HPP
    #define VMPS_LINKEDLIST_HPP
    #include <iostream>
    
    namespace VMPS
    { 
    
        template<class T>
        class LinkedList
        {
            
            //Node
            private:
            struct Node
            {
                T     m_Data;
                Node *m_Next;
                Node *m_Prev;
    
                //Default Constructor.
                Node()
                : m_Next(nullptr), m_Prev(nullptr)
                {
                }
    
                //Initialize m_Data constructor.
                Node(T data)
                : m_Data(data), m_Next(nullptr), m_Prev(nullptr)
                {
                }
            };
    
    
    
            //Public Methods.
            public:
    
            //Default Constructor.
            LinkedList()
            : m_Size(0), m_Head(new Node()), m_Tail(new Node())
            {
                m_Head->m_Next = m_Tail;
                m_Tail->m_Prev = m_Head;
                m_Current      = m_Head;
            }
    
            //Deconstructor.
            ~LinkedList()
            {
                this->clear();
            }
    
    
            //Append Data.
            void append(T data)
            {
    
                //New Node.
                Node *new_node = new Node(data);
    
                //First node into the list.
                if (m_Size == 0)
                {
                    m_Head->m_Next = new_node;
                    m_Tail->m_Prev = new_node;
    
                    new_node->m_Next = m_Tail;
                    new_node->m_Prev = m_Head;
    
                    m_Size++;
                }
    
                //Second, or later into the list.
                else
                {
                    m_Tail->m_Prev->m_Next = new_node;
                    new_node->m_Prev       = m_Tail->m_Prev;
                    m_Tail->m_Prev         = new_node;
                    new_node->m_Next       = m_Tail;
                    m_Size++;
                }
            }
    
    
    
            //Search.
            template<typename U>
            void *search(bool (*compare)(const T other, U custom), U custom)
            {
                //Current node starts from the first node.
                Node *current = m_Head->m_Next;
    
                //Go though each node until the end.
                while (current != m_Tail)
                {   
                    //Do the comparison based on the user's custom function.
                    if ( compare(current->m_Data, custom) )
                        return current;
    
                    //Next node.
                    current = current->m_Next;
                }
    
                //Not found.
                return m_Tail;
            }
    
    
            //Remove.
            template<typename U>
            T remove(bool (*compare)(const T other, U custom), U custom)
            {
                Node *found = this->search(compare, custom);
    
                if (found != m_Tail)
                {
                    T temp = found->m_Data;
                    delete found;
                    return temp;
                }
    
                throw "exception";
            }
    
    
    
            //Get the data at a specific mem address.
            T get(void *addr)
            {
                Node *node = (Node *)addr;
    
                if (node != m_Tail)
                    return node->m_Data;
    
                throw "exception";
            }
    
    
            //Return the tail.
            void *end() {return (void *)m_Tail;}
    
    
            //Reset.
            void reset(){m_Current = m_Head;}
    
            //Has Next.
            bool hasNext()
            {
                return m_Current != m_Tail && 
                  m_Head->m_Next != m_Tail && 
                  m_Current->m_Next != m_Tail;
            }
    
            //Get Size.
            unsigned int getSize(){return m_Size;}
    
            //Get Next.
            T getNext()
            { 
                m_Current = m_Current->m_Next;
                return m_Current->m_Data;
            }
    
            //Clear.
            void clear()
            {
                Node *current = m_Head->m_Next;
                Node *temp;
    
                //Remove all the nodes.
                while (current != m_Tail)
                {
                    temp    = current;
                    current = current->m_Next;
                    delete temp;
                    m_Size--;
                }
    
                //Reconnect the two mark nodes.
                m_Head->m_Next = m_Tail;
                m_Tail->m_Prev = m_Head;
    
                //Reset the current node.
                m_Current      = m_Head;
            }
    
    
            //Private Members.
            private:
            unsigned int m_Size;
            Node *m_Head;
            Node *m_Tail;
            Node *m_Current;
        };
    }
    
    #endif
    The end user can check if the return pointer of the list.search() method is equal to list.end(). If so, he should not use list.get() to get the value because it will throw an exception.
    Last edited by babaliaris; September 7th, 2019 at 04:25 PM.

  9. #9
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,876

    Re: Templates: Generic Linked List, I stuck at returning type in template functions.

    For double linked lists (bidirectional) iterators, you should also implement .begin(), equality comparisons and auto increment/decrement. See http://www.cplusplus.com/reference/iterator/

    Are you sure that .remove() works OK? It doesn't seem to alter the pointers for the previous/next block?

    Also, it's better to stick to the STL conventions when writing a container. So instead of Append, you have push_front() and push_back(). Get() becomes operator *(). getSize() becomes size() etc. getNext() becomes ++ for the iterator. hasNext() isn't needed - as the caller checks the returned iterator value against .end(). search() is replaced by the STL find(). See http://www.cplusplus.com/reference/list/list/ for details of the functionality provided by the STL list container. Obviously, your class doesn't need to provide all of this functionality, but where it does it's best to conform to expected conventions.

    A quick test for a container class - does it compile and work OK when used with a range-based for loop?
    Last edited by 2kaud; September 8th, 2019 at 06:58 AM.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.3.5)

  10. #10
    Join Date
    Jul 2017
    Location
    Greece
    Posts
    112

    Re: Templates: Generic Linked List, I stuck at returning type in template functions.

    Quote Originally Posted by 2kaud View Post
    For double linked lists (bidirectional) iterators, you should also implement .begin(), equality comparisons and auto increment/decrement. See http://www.cplusplus.com/reference/iterator/

    Are you sure that .remove() works OK? It doesn't seem to alter the pointers for the previous/next block?

    Also, it's better to stick to the STL conventions when writing a container. So instead of Append, you have push_front() and push_back(). Get() becomes operator *(). getSize() becomes size() etc. getNext() becomes ++ for the iterator. hasNext() isn't needed - as the caller checks the returned iterator value against .end(). search() is replaced by the STL find() and remove becomes erase() that erases the specified iterator.

    A quick test for a container class - does it compile and work OK when used with a range-based for loop?
    I fixed the remove method. (Yes I wasn't handling the disconnection of the deleted node from the list).

    Well about the for loop, it works if the size does not change. if you do something like this:
    Code:
    for (int i = 0; i < list.size; i++)
    {
        list.pop_front();
    }
    it will cause bugs, because in each pop the size changes. But the same thing happens if you use an std::vector.

    So this is why I prefer doing something like this:
    Code:
    while (list.notEmpty())
        list.pop_front();
    Or if I want to go through all the elements of the list and remove some of them.

    Code:
    //This goes through the list untill it finds the tail of the list.
    while (list.hasNext())
    {
        if (condition)
            list.remove(remove_somthing_here);
    }
    If you do this like this:
    Code:
    for (int i = 0; i < list.size; i++)
    {
        if (condition)
            list.remove(remove_somthing_here);
    }
    This will break since the size changes as I remove stuff. It will probably cause an overflow.

  11. #11
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,876

    Re: Templates: Generic Linked List, I stuck at returning type in template functions.

    I referred to range-based for loop:

    Code:
    for (auto& l : list)
    ...
    Code:
    //This goes through the list untill it finds the tail of the list.
    while (list.hasNext())
    {
        if (condition)
            list.remove(remove_somthing_here);
    }
    would be coded as:

    Code:
    for (auto l = list.begin(); l != list.end(); )
        if (condition)
            l = list.remove(whattoremove);    //returns iterator to the next element in the list after the one removed
        else
            ++l;
    Last edited by 2kaud; September 8th, 2019 at 07:42 AM.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.3.5)

  12. #12
    Arjay's Avatar
    Arjay is offline Moderator / MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    13,108

    Re: Templates: Generic Linked List, I stuck at returning type in template functions.

    Quote Originally Posted by babaliaris View Post
    I fixed the remove method. (Yes I wasn't handling the disconnection of the deleted node from the list).

    Well about the for loop, it works if the size does not change. if you do something like this:
    Code:
    for (int i = 0; i < list.size; i++)
    {
        list.pop_front();
    }
    it will cause bugs, because in each pop the size changes. But the same thing happens if you use an std::vector.

    So this is why I prefer doing something like this:
    Code:
    while (list.notEmpty())
        list.pop_front();
    Or if I want to go through all the elements of the list and remove some of them.

    Code:
    //This goes through the list untill it finds the tail of the list.
    while (list.hasNext())
    {
        if (condition)
            list.remove(remove_somthing_here);
    }
    If you do this like this:
    Code:
    for (int i = 0; i < list.size; i++)
    {
        if (condition)
            list.remove(remove_somthing_here);
    }
    This will break since the size changes as I remove stuff. It will probably cause an overflow.
    You need to cycle through the list using an enumerator if you wish to remove items. See the std::list<> implementation.

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




On-Demand Webinars (sponsored)