Jump to content

  • Log In with Google      Sign In   
  • Create Account

Class Template Error


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
15 replies to this topic

#1 lordimmortal2   Members   -  Reputation: 129

Like
0Likes
Like

Posted 09 November 2011 - 09:06 PM

I just tried to replace some classes and functions with templates to reduce some code substantially and seeing as how it's my first time using templates and inheritance, there's some confusing errors. I'm using C++.

I've worked it into getting errors such as this:
error C2440: '=' : cannot convert from 'cLinkedList<T> *const ' to 'cEntity *'
1>      	with
1>      	[
1>          	T=cEntity
1>      	]
1>      	Cast from base to derived requires dynamic_cast or static_cast
1>      	c:\users\owner\documents\visual studio 2010\projects\rpg\rpg\clinkedlist.cpp(9) : while compiling class template member function 'int cLinkedList<T>::FindEmptyID(void)'
1>      	with
1>      	[
1>          	T=cEntity
1>      	]

And I'm quite confused about how to fix this.

Relevant code:

cLinkedList.h:
#pragma once

template <class T>
class cLinkedList
{
public:
	T *next;

	int FindEmptyID();

	T * ScanListPrevious(int ID);
	T * ScanList(int ID);
	T * ScanListEnd();				// Returns the last entity in the list
};

cLinkedList.cpp:
#include "cLinkedList.h"

#include "cTile.h"
#include "cEntity.h"

template <class T>
int cLinkedList <T>::FindEmptyID()
{
	T *dummy, *dummyNext;
	
	if(this != 0)
	{
		dummy = this;

		while(true)
		{
			dummyNext = dummy->next;

			if(dummyNext == 0)
			{
				// Impossible to dicern the next ID, assume that the final one in the list is the last ID
				return dummy->ID + 1;
			}
			if(dummyNext->ID - dummy->ID > 1)
				// This checks if there is a break between ID numbers and returns ID + 1 which fills the hole
				return dummy->ID + 1;

			dummy = dummy->next;
		}
	}
	else
	{
		// Error, no root
	}
}

template <class T>
T * cLinkedList <T>::ScanListPrevious(int ID)
{
	T *previous;		// Dummy struct that contains the previous node
	T *listTraverse;	// Dummy struct to check if there is a next node as we traverse

	// Start at the beginning of the list
	listTraverse = this;

	if(listTraverse != 0)
	{
		while(listTraverse->next != 0)
		{
			previous = listTraverse;

			listTraverse = listTraverse->next;

			if(listTraverse->ID == ID)
				return previous;
		}
	}
	else
	{
		// Error, no root
	}
}

template <class T>
T * cLinkedList <T>::ScanList(int ID)
{
	// Dummy struct to check if there is a next node as we traverse
	T *listTraverse;

	// Start at the beginning of the list
	listTraverse = this;

	if(listTraverse != 0)
	{
		while(listTraverse->next != 0)
		{
			if(listTraverse->ID == ID)
				return listTraverse;

			listTraverse = listTraverse->next;
		}
	}
	else
	{
		// Error, no root
	}
}

template <class T>
T * cLinkedList <T>::ScanListEnd()
{
	T *dummy;

	if(this != 0)
	{
		dummy = this;

		while(dummy->next != 0)
			dummy = dummy->next;
	}
	else
	{
		// Error, no root
	}

	return dummy;
}

template class cLinkedList<cTile>; 
template class cLinkedList<cEntity>; 
template class cLinkedList<cLayer>;

Edit: Gah, I always forget to leave out a crucial bit of information. cLayer, cTile, and cEntity all inherit cLinkedList. They all call the functions inherited by this->ScanList(ID), or equivalent.

So basically, what am I doing wrong? As always, all replies and help is very appreciated.
Prove me wrong so I can know what's right.

Sponsor:

#2 Wooh   Members   -  Reputation: 652

Like
0Likes
Like

Posted 09 November 2011 - 09:16 PM

This doesn't look right
dummy = this;
this is a cLinkedList<T>* and dummy is T* so that will not work.

Also when working with templates you have to define all the functions in the header file.

#3 lordimmortal2   Members   -  Reputation: 129

Like
0Likes
Like

Posted 09 November 2011 - 09:33 PM

Thanks for your reply =D.

This doesn't look right

dummy = this;
this is a cLinkedList<T>* and dummy is T* so that will not work.


Then what should I change this/anything to?

Also when working with templates you have to define all the functions in the header file.


I was following this article: http://www.cplusplus...articles/14272/ and as you can see in my code, I've tried using explicit instantiation. Implicit would be the better way to do it, but I don't have many types for the template to be used right now and it produces the same errors...
Prove me wrong so I can know what's right.

#4 Wooh   Members   -  Reputation: 652

Like
0Likes
Like

Posted 09 November 2011 - 10:16 PM

Oh I didn't see the explicit instantiation. I don't know much about it so I can't say anything more about that.

What you should change depends on what are trying to do. What is it you want dummy to point to?

Checking if this is null is a bit strange. Do you want to be able to call the member functions on a null pointer or something? Normally you just assume the this pointer is not null.

#5 lordimmortal2   Members   -  Reputation: 129

Like
0Likes
Like

Posted 09 November 2011 - 10:44 PM

Oh I didn't see the explicit instantiation. I don't know much about it so I can't say anything more about that.

What you should change depends on what are trying to do. What is it you want dummy to point to?

Checking if this is null is a bit strange. Do you want to be able to call the member functions on a null pointer or something? Normally you just assume the this pointer is not null.


Well the reason I'm using the template is because cTile, cLayer, and cEntity all use linked lists for their data management and all their basic functions are exactly the same except for data types (ScanList and such). Dummy is just a pointer of type cTile/cLayer/cEntity that is used as a placeholder to check certain values as you traverse down the list.

If the pointer was null, I'd have errors so I check if the root of the linked list actually exists to avoid potential errors (would probably only occur from the programmer but meh).

Edit: Gah, I always forget to leave out a crucial bit of information. cLayer, cTile, and cEntity all inherit cLinkedList. They all call the functions inherited by this->ScanList(ID), or equivalent.
Prove me wrong so I can know what's right.

#6 rip-off   Moderators   -  Reputation: 8727

Like
0Likes
Like

Posted 10 November 2011 - 03:32 AM

It is a very unusual design to have all the objects extend linked list here. Is there a reason it must be an intrusive list, or can you not have have the objects in an external std::list<> and use a standard predicate search for finding nodes by ID?

#7 lordimmortal2   Members   -  Reputation: 129

Like
0Likes
Like

Posted 10 November 2011 - 03:07 PM

It is a very unusual design to have all the objects extend linked list here. Is there a reason it must be an intrusive list, or can you not have have the objects in an external std::list<> and use a standard predicate search for finding nodes by ID?


I'm confused. Could you please elaborate? I built this entire thing to learn how to use linked lists. I'm self-learned in programming so when it comes to standard usage of things, then I have no idea.
Prove me wrong so I can know what's right.

#8 way2lazy2care   Members   -  Reputation: 782

Like
0Likes
Like

Posted 10 November 2011 - 03:22 PM

I'm confused. Could you please elaborate? I built this entire thing to learn how to use linked lists. I'm self-learned in programming so when it comes to standard usage of things, then I have no idea.


Just quickly glancing it, it looks like you are trying to force your linked list to act like an array. Check out the STL version of list to see functions that might be good http://www.cplusplus.com/reference/stl/list/

#9 lordimmortal2   Members   -  Reputation: 129

Like
0Likes
Like

Posted 10 November 2011 - 04:42 PM


I'm confused. Could you please elaborate? I built this entire thing to learn how to use linked lists. I'm self-learned in programming so when it comes to standard usage of things, then I have no idea.


Just quickly glancing it, it looks like you are trying to force your linked list to act like an array. Check out the STL version of list to see functions that might be good http://www.cplusplus...rence/stl/list/


A linked list acts like an array in that it's a collection of a bunch of data values of a certain data type. This is how it should work, isn't it? I'm confused about how I'm forcing it to work like an array and how that would produce the template error I'm getting.
Prove me wrong so I can know what's right.

#10 Wooh   Members   -  Reputation: 652

Like
0Likes
Like

Posted 10 November 2011 - 06:48 PM

cLayer, cTile, and cEntity all inherit cLinkedList.

dummy = this;
You are here trying to assign a base class pointer to a derived class pointer. This cast is not implicit, for good reason.

I think you should reconsider your design.

#11 lordimmortal2   Members   -  Reputation: 129

Like
0Likes
Like

Posted 10 November 2011 - 07:25 PM

cLayer, cTile, and cEntity all inherit cLinkedList.

dummy = this;
You are here trying to assign a base class pointer to a derived class pointer. This cast is not implicit, for good reason.

I think you should reconsider your design.


I can always just put these functions into the three different types of classes but I'd consider that inefficient. So there's no way I can call these functions in their current form from a template class which all the other classes inherit from?
Prove me wrong so I can know what's right.

#12 Bregma   Crossbones+   -  Reputation: 5440

Like
0Likes
Like

Posted 10 November 2011 - 07:44 PM

It looks like in your design you are conflating the list node with the list itself. I think that approach will leave you unsatisfied.

Try separating concerns. Make a node a node and a list a list.
Stephen M. Webb
Professional Free Software Developer

#13 lordimmortal2   Members   -  Reputation: 129

Like
0Likes
Like

Posted 10 November 2011 - 07:50 PM

It looks like in your design you are conflating the list node with the list itself. I think that approach will leave you unsatisfied.

Try separating concerns. Make a node a node and a list a list.


The functions are given the node and then iterate through the entirety until they reach the end. These worked perfectly until I made them a template.
Prove me wrong so I can know what's right.

#14 rip-off   Moderators   -  Reputation: 8727

Like
0Likes
Like

Posted 11 November 2011 - 05:27 AM

These worked perfectly until I made them a template.

Just because they worked doesn't mean that they were a good design! =]

The functions are given the node and then iterate through the entirety until they reach the end.

Actually, that isn't true. Your functions (apart from ScanListEnd) don't really work if you call them on an arbitrary LinkedList object. The list isn't bi-directional you cannot guarantee you've searched it exhaustively.

There is no hint in the API that suggests you must call these functions on the "root" node. Indeed, in your functions you have comments saying "Start at the beginning of the list", but that is an assumption.

I recommend you replace this concept of a "head node" with a std::list<> instance. You can then write free functions to implement your search-by-id logic.

By separating the container logic from the objects themselves, you can guarantee exhaustive searches - any code that can reach the list can reach the entire list. It also means that the objects themselves don't need to worry about being part of a container. They can concentrate on being individual Tiles, Layers or Entities.

Here is an example:
template<typename T>
int FindEmptyID(std::list<T*> &list)
{
    if(list.empty())
    {
        return DEFAULT_ID; // Might be 0 or 1, or something else, I don't know
    }
    else
    {
        typename std::list<T*>::iterator i = list.begin();
        int previousId = (*i)->ID();
        ++i
        for( ; i != list.end() ; ++i)
        {
             int currentId = (*i)->ID();
             if(currentId - previousId > 1)
             {
                 return previousId + 1;
             }
             previousId = currentId;
        }
        return previousId + 1;
    }
}

template<typename T>
T * ScanListPrevious(std::list<T*> &list, int ID)
{
     T *previous = 0;
     for(typename std::list<T*>::iterator i = list.begin() ; i != list.end() ; ++i)
     {
        T *object = *i;
        if(object->ID() == ID)
        {
            return previous;
        }
        previous = object;
     }
     return 0;
}

template<typename T>
T * ScanList(std::list<T *> &list, int ID)
{
    for(typename std::list<T *>::iterator i = list.begin() ; i != list.end() ; ++i)
    {
        T *object = *i;
        if(object->ID() == ID)
        {
            return object;
        }
    }
    return 0;
}

typedef std::list<Tile *> TileContainer;
typedef std::list<Layer *> LayerContainer;
typedef std::list<Entity *> EntityContainer;
Something like that. I haven't compiled or tested the code, but I expect that it is the correct "shape". Though I'd probably recommend using std::vector over std::list if you expect to be doing lots of searching like that.

 

As an aside, you really don't want to be writing code that checks if "this" is null, unless it is an assertion perhaps. Relying on undefined behaviour like invoking a member function on a NULL pointer is a brittle way to program.

#15 lordimmortal2   Members   -  Reputation: 129

Like
0Likes
Like

Posted 12 November 2011 - 01:34 PM


These worked perfectly until I made them a template.

Just because they worked doesn't mean that they were a good design! =]

The functions are given the node and then iterate through the entirety until they reach the end.

Actually, that isn't true. Your functions (apart from ScanListEnd) don't really work if you call them on an arbitrary LinkedList object. The list isn't bi-directional you cannot guarantee you've searched it exhaustively.

There is no hint in the API that suggests you must call these functions on the "root" node. Indeed, in your functions you have comments saying "Start at the beginning of the list", but that is an assumption.

I recommend you replace this concept of a "head node" with a std::list<> instance. You can then write free functions to implement your search-by-id logic.

By separating the container logic from the objects themselves, you can guarantee exhaustive searches - any code that can reach the list can reach the entire list. It also means that the objects themselves don't need to worry about being part of a container. They can concentrate on being individual Tiles, Layers or Entities.

Here is an example:
template<typename T>
int FindEmptyID(std::list<T*> &list)
{
    if(list.empty())
    {
        return DEFAULT_ID; // Might be 0 or 1, or something else, I don't know
    }
    else
    {
        typename std::list<T*>::iterator i = list.begin();
        int previousId = (*i)->ID();
        ++i
        for( ; i != list.end() ; ++i)
        {
         	int currentId = (*i)->ID();
         	if(currentId - previousId > 1)
         	{
             	return previousId + 1;
         	}
         	previousId = currentId;
        }
        return previousId + 1;
    }
}

template<typename T>
T * ScanListPrevious(std::list<T*> &list, int ID)
{
 	T *previous = 0;
 	for(typename std::list<T*>::iterator i = list.begin() ; i != list.end() ; ++i)
 	{
        T *object = *i;
        if(object->ID() == ID)
        {
            return previous;
        }
        previous = object;
 	}
 	return 0;
}

template<typename T>
T * ScanList(std::list<T *> &list, int ID)
{
    for(typename std::list<T *>::iterator i = list.begin() ; i != list.end() ; ++i)
    {
        T *object = *i;
        if(object->ID() == ID)
        {
            return object;
        }
    }
    return 0;
}

typedef std::list<Tile *> TileContainer;
typedef std::list<Layer *> LayerContainer;
typedef std::list<Entity *> EntityContainer;
Something like that. I haven't compiled or tested the code, but I expect that it is the correct "shape". Though I'd probably recommend using std::vector over std::list if you expect to be doing lots of searching like that.

 

As an aside, you really don't want to be writing code that checks if "this" is null, unless it is an assertion perhaps. Relying on undefined behaviour like invoking a member function on a NULL pointer is a brittle way to program.


Thanks for your replies and code. Could you explain how you would use these and where I would place them? Since you got rid of them being part of cLinkedList.
Prove me wrong so I can know what's right.

#16 rip-off   Moderators   -  Reputation: 8727

Like
0Likes
Like

Posted 13 November 2011 - 04:45 PM

They are free functions. Normally they would be decalared in a header file, and implemented in a source file. However, as template functions, they must be defined in a header file, or else you would have to use explicit instantiation.

Presumably, your current code looks like this:
// In a header

class Something
{
public:
    void foo();
    void bar();
    void frobnicate();

private:
    cEntity *head;
};

// In a source file

void Something::foo()
{
    // ...

    int id = head->FindEmptyID();
    
    // Use id
}

void Something::bar()
{
    int someId = /* ... */;

    cEntity *entity = head->ScanListPrevious(someId);

    // Use *entity
}

void Something::frobnicate()
{
    int someId = /* ... */;

    cEntity *entity = head->ScanList(someId);

    // Use *entity
}
This would become:
// In a header

class Something
{
public:
    void foo();
    void bar();
    void frobnicate();

private:
    EntityContainer entities;
};

// In a source file

void Something::foo()
{
    // ...

    int id = FindEmptyID(entities);
    
    // Use id
}

void Something::bar()
{
    int someId = /* ... */;

    cEntity *entity = ScanListPrevious(entities, someId);

    // Use *entity
}

void Something::frobnicate()
{
    int someId = /* ... */;

    cEntity *entity = ScanList(entities, someId);

    // Use *entity
}





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS