Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Narcist

Template woes, iterative loop on template paramater for friend definition?

This topic is 5349 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am trying to create a generic linked list template (and no use STL list comments please..) its pretty much a standard link list, there is a linked list entry class to be inherited by any class that i want a linked list of, and then a linked list template class that is used to operate on the list. the only problem is that i want to add support for allowing an item to be in multiple linked lists at once, and preferebly by passing the number of lists as a template parameter to the LinkList entry, and the the number of this list to the link list class the problem is that because the "type" of the object is based on the template parameter i cant do a friend declaration in the entry class for every linked list class that uses it
template <typename T, U32 u32NumEntries = 1> class LinkListEntry {
private:
	friend LinkList<T, ????>; // what goes here???

	struct {
		T *m_pNext;
		T *m_pPrev;
	} LLEntry[u32NumEntries];

	T *Derived(void) {return static_cast<T*>this;}

	template <U32 u32EntryNum> void SetNext(T* pNext) 
	{ 
		LLEntry[u32EntryNum].m_pNext = pNext;
	}
	template <U32 u32EntryNum> void SetPrev(T *pPrev)
	{
		LLEntry[u32EntryNum].m_pPrev = pPrev;
	}
protected:
	LinkListEntry() {
		U32 i;
		for (i = 0; i < u32NumEntries; i++)
		{
			LLEntry[i].m_pNext = NULL;
			LLEntry[i].m_pPrev = NULL;
		}
	}
	~LinkList() {}
public:
	template <U32 u32EntryNum> T *Next(void) { return LLEntry[u32EntryNum].m_pNext; };
	template <U32 u32EntryNum> T *Prev(void) { return LLEntry[u32EntryNum].m_pPrev; };
};

template <typename T, U32 u32EntryNum> class LinkList
{
	T *m_pFirst;
	T *m_pLast;
	LinkList(const LinkList<T> &src) {}
public:
	LinkList(void) : m_pFirst(NULL), m_pLast(NULL) {};
	T *First(void) {return List.m_pFirst;};
	T *Last(void) {return List.m_pLast;};
	void AddFirst(T *pEntry);
	void AddLast(T *pEntry);
};
i would prefer to do it via template paramater as everything is known at compile time so doesnt involve any runtime overhead, the only thing stopping me is the friend declarations (and i dont want to make LinkListEntry::SetNext and LinkListEntry::SetPrev members public as i dont want anyone calling them directly, only using LinkList members so is it possible to do this?

Share this post


Link to post
Share on other sites
Advertisement
erm... maybe I''m suffering from a huge brain fart, but...

Why the heck does each entry in your linked list have... well, multiple entries?

Share this post


Link to post
Share on other sites
so that if required, an "entry" can be in multiple linked lists at once

eg what i wanted to do was



class test : public LinkListEntry<test, 2>

.
.
.

LinkList<test, 0> list1;
LinkList<test, 1> list2;

test *pT = new test;

list1.AddFirst(pT);
list2.AddLast(pT);



for example

[edited by - Narcist on November 26, 2003 5:35:02 PM]

Share this post


Link to post
Share on other sites
ya gonna love me for this but, why no ''use STL list'' comments?

Anyways, why not change the design slightly so that you pass the list number into the constructor, then the ''setNext'' and ''setPrev'' functions could take that number so they know what entry to change.

Share this post


Link to post
Share on other sites
The reason for not using STL list, is that if you have a list of pointers to objects, and the object pointer that you want to remove from the list, removing it isnt trivial, you first need to search the list for that entry, and then remove it, STL list was intended for value semantics as opposed to reference semantics

By storing the next and previous pointers inside the objects, then given a pointer to the object to remove, and knowing which list its in, removing is trivial, please note thats not a dig at STL, STL is great, just that this template is for applications where the STL list isnt suitable..


I may have to do the constructor idea if there is no solution tot his, only problem is that it probably wont be a compile time decision, but rather a run time one, i had rather hoped that i could do it in compile time as opposed to runtime as everything is known at compile time, there is no need for it to store the value in the list as its tied to the list declaration.

i thought about whether specialising the template for each case up to a suitable number would do it, but then thats basically the same as just declaring a set of LinkListEntry1, LinkListEntry2, etc etc types..

Share this post


Link to post
Share on other sites
the run time overhead of looking up which is tiny anyways, it might be annoying but i dont see how it would make a difference.

Re:STL
Now you''ve explained how you plan to use it i can see your point about the STL list not doing what you want it to.
I was going so say about using a list with boost::shared_ptr<>s in, however while that gets around the reference problem isnt doesnt do the same trick you are doing with the removeal of the objects.

Share this post


Link to post
Share on other sites
I see....

Note that you''re defining each entry as a TYPE which only has a certain number of entiries.

So that a entry which is in 1 list can''t be converted to an entry which is in 2 lists. because they are different types.

that shouldn''t be part of the template, it should be a variable.

Share this post


Link to post
Share on other sites
E&OE; uncompile, untested, syntax may need poking with a sharp stick:

#include <list>
template<typename T, typename Alloc=std::allocator<T*> >
class pointer_list<T*> : private std::list<T*, Alloc>
{
typedef std::list<T*, Alloc> base_type;
static void purge(T* obj) { delete obj; }
public:
using base_type::assign;
using base_type::back;
// etc. bring every function of the base into scope

// probably need to bring the typedefs here too

pointer_list() {}
explicit pointer_list(const Alloc& a) : base_type(a) {}
// et cetera -- forward each c-tor; there should be seven plus the default. an implied copy c-tor should be fine

// and here are the important bits:

~pointer_list() { std::for_each(begin(), end(), &purge); }
iterator erase(iterator where)
{
purge(*where);
return base_type::erase(where);
}
iterator erase(iterator first, iterator last)
{
std::for_each(first, last, &purge);
return base_type::erase(first, last);
}
// remove, remove_if, and unique will probably need to be implemented completely

};



[edited by - DrPizza on November 26, 2003 9:50:29 PM]

[edited by - DrPizza on November 26, 2003 9:50:59 PM]

Share this post


Link to post
Share on other sites
Couldn't you use STL list, and then have each Node object contain an array (or std::list) of iterators pointing to its location in all the lists? I think if you remove a STL list node by its iterator it should do it in constant time like you want. Your method might be faster though, I'm not sure... but this way you get to use the STL list and not worry as much about possible bugs .

edited - never mind... the iterator is probably unsafe to continue using after an element is deleted from the list... just pretend i didn't say anything...

[edited by - makeshiftwings on November 26, 2003 10:18:32 PM]

Share this post


Link to post
Share on other sites
C-Junkie: what do you mean? the base type LinkListEntry is never instantiated on its own, but a class is derived from it which specifies tha maximum number of lists its it in, The lists are supposed to be typesafe in that unless a Test2 class is derived from test1, a LinkList, there are no conversions to do?

DrPizza: i have already stated why i dont want to use STL List (the other reason is i dont want extra allocations for the "node" class - one of the things i plan to use this for is my memory allocater!) so i''m not sure what i''m supposed to learn from your post?

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!