Archived

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

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

This topic is 5131 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
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
quote:
DrPizza: i have already stated why i dont want to use STL List

The initial reason you gave was, and here I quote:
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

The list I showed you doesn't suffer from that limitation -- it destroys objects for you, rather than making you do it yourself.

As such, it completely invalidates your initial complaint.

quote:
(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!)

(a) You're going to need extra allocations if you want a list. If you don't want extra allocations, use a fixed-size array, and forget any pretence of it being a list.
(b) Why do you need your own memory allocator?

quote:
so i'm not sure what i'm supposed to learn from your post?

How to use std::list and address the reason you gave for, er, not using std::list.

[edited by - DrPizza on November 27, 2003 9:27:52 AM]

Share this post


Link to post
Share on other sites
Okay so i have sat down and tried to understand your version

as far as i can tell, it just uses an iterator to tell where in the list to delete, however where do i get that iterator from?
i would presumably need to search the list for it in the first place, or have everything keep track of iterators to objects instead of pointers to them. However, as far as i understand it an insert and delete operation invalidates all iterators, so that wouldnt work.

a thorough explanation of why STL list isnt suitable :-

say i have a class A, lots of people are creating and using class A's, each person calls a function to create one, that creates it and adds it to a linked list, and returns the pointer, they can use the pointer to do whatever they want with A
now when it comes to destroy a, it needs to be removed from the linked list, under STL, that means somewhere, the list needs to be searched for the pointer to A.

now by including the next and previous pointers inside the object itself, the list never needs to be searched, instead it just needs to be unlinked which is easy enough as we have direct access to the previous and next pointers.

(a) You're going to need extra allocations if you want a list. If you don't want extra allocations, use a fixed-size array, and forget any pretence of it being a list.

I dont need extra allocations for my list, there is a single allocation for the object, there doesnt need to be a second allocation for a block just to store a pointer to my "object" and the pointers to the next and the previous item in the list.

(b) Why do you need your own memory allocator?

a) because i can?
b) so that i can do complete, efficient memory tracking with file and linenumber support, time of allocation etc, so i can customize allocation where needed, so i can add electric fence/bounds checker type support if required.



[edited by - Narcist on November 27, 2003 10:58:59 AM]

Share this post


Link to post
Share on other sites
quote:
narcist: i would presumably need to search the list for it in the first place, or have everything keep track of iterators to objects instead of pointers to them. However, as far as i understand it an insert and delete operation invalidates all iterators, so that wouldnt work.


Different containers have different restrictions. Removing an element of the std::list only invalidates the iterator that identified that element. Nothing else. It''s good to learn all the differences, although the normal documentation doesn''t usually compare them. I''d recommend ''Effective STL'' by Scott Meyers.

Share this post


Link to post
Share on other sites
quote:
Okay so i have sat down and tried to understand your version

To little effect, apparently.

quote:
as far as i can tell, it just uses an iterator to tell where in the list to delete, however where do i get that iterator from?

No, you''ve completely misunderstood the purpose.

The principle problem with using a std::list to contain pointers is that operations which remove elements don''t delete what the pointers point to. Similarly, destroying the list entirely doesn''t delete any pointed-at elements.

What my code does is redress these issues. The destructor deletes each element in the list, and the list members which remove list elements also delete the element they''re about to remove.

quote:
i would presumably need to search the list for it in the first place, or have everything keep track of iterators to objects instead of pointers to them. However, as far as i understand it an insert and delete operation invalidates all iterators, so that wouldnt work.

Then you''re pretty ignorant of the guarantees a list offers. The only operation that invalidates list iterators is erasing the entry the iterator refers to. Insertions invalidate no iterators at all, removals invalidate only iterators referring to the removed element.

quote:
say i have a class A, lots of people are creating and using class A''s, each person calls a function to create one, that creates it and adds it to a linked list, and returns the pointer, they can use the pointer to do whatever they want with A
now when it comes to destroy a, it needs to be removed from the linked list, under STL, that means somewhere, the list needs to be searched for the pointer to A.

But that''s no problem -- the function just returns an iterator. They can then use the iterator to do whatever they want with the object. When they want to destroy the object, it needs to be removed from teh list, so they can simply pass the iterator to the complementary function to their "create object and add it to a list" function -- a "destroy object and remove it from a list" function.

quote:
now by including the next and previous pointers inside the object itself, the list never needs to be searched, instead it just needs to be unlinked which is easy enough as we have direct access to the previous and next pointers.

This can be achieved with a normal list and an iterator instead of a raw pointer.

quote:
I dont need extra allocations for my list, there is a single allocation for the object, there doesnt need to be a second allocation for a block just to store a pointer to my "object" and the pointers to the next and the previous item in the list.

But you will need multiple allocations so that each element can store its position in an arbitrary number of lists -- your current mechanism by which you limit the number of lists an element can be in seems frankly bizarre.

quote:
a) because i can?

That doesn''t appear immediately obvious.

quote:
b) so that i can do complete, efficient memory tracking with file and linenumber support, time of allocation etc,

I''m not sure why any of those things need a custom memory allocator.

quote:
so i can customize allocation where needed,

Wouldn''t it be prudent to determine the need first and then write the allocator?

quote:
so i can add electric fence/bounds checker type support if required.

Your platform has no pre-existing support for such a thing?

Share this post


Link to post
Share on other sites
quote:
Original post by DrPizza
quote:
Okay so i have sat down and tried to understand your version

To little effect, apparently.



Well sorry my STL and Template understanding is still somewhat rusty, i have been programming in C for about 10 years, and only done a little C++ about 3-4 years ago, I am now making a concentrated effort to try and re-learn C++ and learn STL for the first time

quote:
No, you''ve completely misunderstood the purpose.

The principle problem with using a std::list to contain pointers is that operations which remove elements don''t delete what the pointers point to. Similarly, destroying the list entirely doesn''t delete any pointed-at elements.

What my code does is redress these issues. The destructor deletes each element in the list, and the list members which remove list elements also delete the element they''re about to remove.



But how does that work where the item is in multiple lists, and may change lists regularly?

Wouldnt i have to store an iterator per list its in? not just a single iterator to refer to the object?

quote:
But you will need multiple allocations so that each element can store its position in an arbitrary number of lists -- your current mechanism by which you limit the number of lists an element can be in seems frankly bizarre.


in what way bizarre? It means after creation memory allocation is very minimal, and i prefer to keep my runtime memory allocation to a minimum, searching the heap for a free memory block is hardly a quick operation.

quote:
I''m not sure why any of those things need a custom memory allocator.


Because i will simply store the information in the memory block header? rather than having to do something clunky like "bolt it on the side" involving hashtables or some other such nastyness to assosciate the memory block with the info.

quote:
Wouldn''t it be prudent to determine the need first and then write the allocator?


Because from past experience i know it will be needed, and i would rather design it in from the ground up than bolt it on afterwords?

quote:
Your platform has no pre-existing support for such a thing?


I know of no platform that does have extensive electric fence/bounds checker support, hence why the products have been so successful and made their makers much money, things like having the ability to allocate the block either left or right aligned within the page to catch either buffer overruns or buffer underruns, of being able to flag memory read only where possible etc

Share this post


Link to post
Share on other sites
quote:
Well sorry my STL and Template understanding is still somewhat rusty, i have been programming in C for about 10 years, and only done a little C++ about 3-4 years ago, I am now making a concentrated effort to try and re-learn C++ and learn STL for the first time

Do you not feel that the best way to learn it might be to use it?

quote:
But how does that work where the item is in multiple lists, and may change lists regularly?

It wouldn''t, but it wasn''t designed to solve that issue; it was designed to redress your complaint concerning storing pointers in std::list.

Wouldnt i have to store an iterator per list its in? not just a single iterator to refer to the object?

quote:
in what way bizarre?

The number of lists an object can be stored in is now part of its type. That''s bizarre.

quote:
It means after creation memory allocation is very minimal, and i prefer to keep my runtime memory allocation to a minimum, searching the heap for a free memory block is hardly a quick operation.

But since you''ve clearly not profiled your application then how do you know this is a bottleneck?

quote:
Because i will simply store the information in the memory block header? rather than having to do something clunky like "bolt it on the side" involving hashtables or some other such nastyness to assosciate the memory block with the info.

Hmmm, no, that still doesn''t explain why you need to write your own allocator.

quote:
Because from past experience i know it will be needed, and i would rather design it in from the ground up than bolt it on afterwords?

You don''t know it''ll be needed until you profile to determine the need. Even if you determine a need, writing an allocator may not be the best approach -- it may be more effective to change where you perform allocations. And if you write your code properly, bolting it on afterwards is just as easy and effective as putting it in in the first place.

quote:
I know of no platform that does have extensive electric fence/bounds checker support, hence why the products have been so successful and made their makers much money, things like having the ability to allocate the block either left or right aligned within the page to catch either buffer overruns or buffer underruns, of being able to flag memory read only where possible etc

That''s odd. I know of several.

Share this post


Link to post
Share on other sites
quote:
Original post by DrPizza
Do you not feel that the best way to learn it might be to use it?



Exactly, and first of all i want to learn templates, how they work etc, how to put them together, to the level where i can understand STL's implementation, THEN i can use it..



quote:
The number of lists an object can be stored in is now part of its type. That's bizarre.


I dont really understand what your getting at, the baseclass type was purely a means to inherit a linkled list framework into the object, eg to save me adding m_pNext, m_pPrev, GetNext and SetNext members to a class that i want to keep track of.

quote:
But since you've clearly not profiled your application then how do you know this is a bottleneck?


Because previous games i have worked on it has been a problem, so there is a multiple memory arena system we use at work due to this. It has turned out to work so well that i wish to introduce the same thing in my own projects.


quote:
Hmmm, no, that still doesn't explain why you need to write your own allocator.


Then how would you assosciate the information with the memory block so it can be freed on delete without using a hashtable or a map to "tack it on"?

quote:
odd. I know of several.


Windows doesnt, Xbox doesnt, PS2 doesnt, PS1 doesnt (and malloc could only be called once there), DOS didnt and that covers my platform experience

not to the level, where a non valid page is tacked on before and after the allocation, and you can choose whether your allocation is tail or head aligned within that block.



and this has gone completely OT..






[edited by - Narcist on November 28, 2003 1:29:18 PM]

Share this post


Link to post
Share on other sites
quote:
Exactly, and first of all i want to learn templates, how they work etc, how to put them together, to the level where i can understand STL''s implementation, THEN i can use it..

These steps are not necessary to learn how to use the Standard Library. They''re necessary to learn how to write a standard library implementation, but that should probably come after you''ve gained familiarity with it, not before.

quote:
I dont really understand what your getting at, the baseclass type was purely a means to inherit a linkled list framework into the object, eg to save me adding m_pNext, m_pPrev, GetNext and SetNext members to a class that i want to keep track of.

The base class takes an unsigned 32-bit integer as a template parameter, and uses that parameter to determine how many next/previous pairs it must store. Because the size is a template parameter it becomes part of the type of the class. This seems frankly perverse. It means that two otherwise identical classes (the only difference being the number of lists they can be in) have incompatible types; you can''t convert from one to the other.

quote:
Because previous games i have worked on it has been a problem, so there is a multiple memory arena system we use at work due to this. It has turned out to work so well that i wish to introduce the same thing in my own projects.

i.e. you don''t.

quote:
Then how would you assosciate the information with the memory block so it can be freed on delete without using a hashtable or a map to "tack it on"?

One way that springs to mind would be to write a custom operator new that takes extra arguments (line number, file name) and prepends them to the blocks it requests from the real allocator.

quote:
Windows doesnt, Xbox doesnt, PS2 doesnt, PS1 doesnt (and malloc could only be called once there), DOS didnt and that covers my platform experience

Electric Fence runs on about a half dozen platforms, and converting it to run on Win32 shouldn''t take more than a few hours (converting mmap()/mprotect() to VirtualAlloc()/VirtualProtect()). The GPL shouldn''t be a problem, as it''d only be used in debug builds, presumably.

And of course DOS doesn''t have such a thing. DOS has no paging in the first place.

Share this post


Link to post
Share on other sites
*sigh* this thread is going nowhere

you seem to have the attitude that i shouldnt ever try to implement anything myself.

I asked a simple question to start with which i have since managed to work out a solution to myself (create the "list" template inside the "entry" template, where i can quite happily make it a friend while still retaining type safety) You have offered no advice towards that instead deciding to argue on my "design", and basically saying i should never create anything myself, instead i should work around other peoples designs trying to shoehorn stuff to fit.

At no point did I say my list was a completely generic use anywhere list, its by no means intended to be a "container" class and at no point did i ever say it was, it was purely intended to do exactly what i wanted from a list that i would completely understand what was going on in the background at ALL times, there would be no extra memory used, no extra allocations used, and if there was a situation where i would need to use std::list for something, it wouldnt stop that being used

Oh and as to your use VS write STL comment, so your basically proposing a view where you are to use something without ever understanding HOW it works? Sorry but i dont fancy being a sheep, blindly using a library without ever understanding what is going on in the background. Personally i would prefer to start off with small templates, gradually learning and understanding and building up in complexity in the LANGUAGE before i am proficient with that aspect of the language to use and understand a library. at that point will i feel confident enough to use the library in anything time critical.

Please note, i am not saying STL is slow, i quite happily use it in small non critical tools all the time where speed of development and ease of maintainabilty are far more important than how quick it runs, just that i''m not confident in my abilities in using it enough to be able to choose the most optimal means of doing something.

Share this post


Link to post
Share on other sites