Thread: Thoughts on return type from template container classes.

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485

    Thoughts on return type from template container classes.

    Hi,

    I'd like to hear some thoughts on a recommended approach to return types from template container classes. If I for example create a template stack class implemented with a linked list, I want my pop() function to return the item and delete the node.

    Returning a local variable is not suitable I guess, I can not return the value since it's a template and no assumptions can be made about the type, (it could be a struct and so on). Returning a pointer seems dumb since it's not convenient for simple types such as ints. How can this (can it?) be solved in the most generic manner?

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Of course you can return it. Since your class will be a template class, there shall be a type T, which shall be specified and shall be the type that your class shall store.
    Thus, knowing this type T, you can return this type T from your pop method.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Registered User
    Join Date
    May 2010
    Posts
    4,633
    You could use Template specialization to return different types as shown here Templates.

    Jim

  4. #4
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    @Elysia Hmm, still doing something like this seems to not be obvious.

    Code:
    #include "stack.h"
    
    struct A{ 
            int a;
            char b;
    };
    
    int main()
    { 
            A a = {1, 'a'};
    
            Stack<A> s;
            s.push(a);
    
            A b = pop();
    
            return 0;
    }
    Unless operator= is overloaded for my struct.

  5. #5
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    jimblumberg, I'll look into that link. Thanks.

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    In this case, it is implicitly defined. But this is the usual way to do it.
    In fact, I think it would be fair to require that whatever you store in your struct should be assignable (or at the very least copy constructable). Both for pop to work and push since you are going to need to copy the value you push in or make a copy of what you pop.

    I fail to see how template specialization would work here. It cannot circumvent the initial problem.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Hm, ok that seems to be a fair requirement I guess. I've made some mockup code for a stack class just for experiment. Does this look ok?

    Code:
    #ifndef STACK_H
    #define STACK_H
    
    #include <stdlib.h>
    
    template <class T> class Stack{
    	
    	private:
    
    	struct node{
    		T data;
    		node *next;
    	};
    
    	node *head;
    	size_t items;
    	
    	// destroy the stack
    	void trash_stack(){
    		while(this->size())
    			this->pop();
    	}
    
    	public:
    
    	Stack() : items(0), head(NULL) {}
    
    	~Stack(){
    		trash_stack();
    	}
    
    	const size_t size(){
    		return items;
    	}
    
    	void push(const T& data){
    		node *n = new node;
    		n->data = data;
    		n->next = NULL;
    
    		if(head){ // if stack is not empty!
    			n->next = head;
    			head = n;
    			items++;
    		} else {
    			head = n;
    			items++;
    		}
    	}
    
    	T pop(){
    		T tmp = T();
    		node *n;
    		if(head){
    			n = head;
    			tmp = n->data;
    			head = n->next;
    
    			delete(n);
    			items--;
    			return tmp;
    		} else { // stack is empty
    			return NULL;
    		}
    	}
    
    };
    #endif

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    I fail to see why you need a linked list. A vector is good enough for a stack.
    Also, your current design has several important problems. But we might discuss that later after you've decided how to implement the stack.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by Elysia View Post
    I fail to see why you need a linked list. A vector is good enough for a stack.
    std::list has pop_back(), push_front() and pop_front(), which is good for stacks and queues of all kinds.

    About the actual subject of this, while you can't necessarily know the type of the template argument in advance, you can make assumptions about it. A stack contains another type. So assume that the type is copy constructable. Then, before you delete, you make and return a copy of the item.

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    pop_front doesn't make sense for a stack (assuming pop_front pops the 0th element). Am I missing something?
    Regardless, a linked list is a complicated structure and certainly adds a lot of complexity to this, which I would say, is unnecessary.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Quote Originally Posted by whiteflags View Post
    ...Then, before you delete, you make and return a copy of the item.
    So, in my case using new to create a new item of type T on the heap in the pop function, then returning a reference to it? Would using static inside pop and overwrite the item T for every call be a sensible approach as well?

  12. #12
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Queues or stacks aren't suited to vector, I would say, as you have to insert at the beginning of the stack all the time. That means inserting at the front of an array (contained array or not) which has never been especially easy. Thus, double-ended insertion and deletion is quite important. Last in first out queues depend on pop_front() workings as well, which is not impossible with vector but pop_front() does less when its implemented in containers appropriate for it. Linked lists always do these quickly anyway, so it seems to be an appropriate choice.

  13. #13
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by Subsonics View Post
    So, in my case using new to create a new item of type T on the heap in the pop function, then returning a reference to it? Would using static inside pop and overwrite the item T for every call be a sensible approach as well?
    Both of those ideas are fraught with issues. With the dynamic memory solution, the thing that calls your function will have to clean up after the pointer when they are done. Static isn't as bad so much as it is unnecessary. In order to use the static solution properly, you have to copy the object, so just return the copy. The static part means nothing in this case.

  14. #14
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    You can easily insert and pop at the end of an array in stacks, making it a generally good choice with on consequences. Queues are better implemented with a deque though.
    Written from my Nokia N8.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  15. #15
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Quote Originally Posted by whiteflags View Post
    Both of those ideas are fraught with issues. With the dynamic memory solution, the thing that calls your function will have to clean up after the pointer when they are done.
    That was my thought as well, basically freeing up memory in one location, just to allocate it again somewhere else. It seems counter intuitive that pop() would not reduce the amount of allocated memory and also handing over that responsibility to the caller.

    Quote Originally Posted by whiteflags View Post
    Static isn't as bad so much as it is unnecessary. In order to use the static solution properly, you have to copy the object, so just return the copy. The static part means nothing in this case.
    Ok, thanks. I just got worried about returning a local variable, but it seems to work as intended.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Getting an error with OpenGL: collect2: ld returned 1 exit status
    By Lorgon Jortle in forum C++ Programming
    Replies: 6
    Last Post: 05-08-2009, 08:18 PM
  2. Code review
    By Elysia in forum C++ Programming
    Replies: 71
    Last Post: 05-13-2008, 09:42 PM
  3. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  4. ras.h errors
    By Trent_Easton in forum Windows Programming
    Replies: 8
    Last Post: 07-15-2005, 10:52 PM
  5. oh me oh my hash maps up the wazoo
    By DarkDays in forum C++ Programming
    Replies: 5
    Last Post: 11-30-2001, 12:54 PM