Jump to content

  • Log In with Google      Sign In   
  • Create Account


Generic Datatypes --Are Templates the Way to Go?


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
12 replies to this topic

#1 Vincent_M   Members   -  Reputation: 523

Like
1Likes
Like

Posted 17 August 2013 - 01:38 PM

I developed my own linked list for C++ that has a few features in it that I like over STL lists. The idea is that I have this abstract LinkedItem class, which holds pointers to the previous and next element in the linked list. Then, I have the LinkedList class that manages this class. LinkedList is able to add and remove elements, and more importantly, get an element from a specific index. LinkedItem also contains a virtual method, GetType(), that returns a literal string, and LinkedList contains a "key" field, which is also a string. When LinkedItem is subclassed, GetType() should be overridden to return some other unique string, such as "item_definition", "character_definition", "map_character", etc. and LinkedList instances with the matching key will allow only LinkedItem subclasses with the matching type to be added to the list. That way, it's guaranteed. I think templates might be an even smarter way to go, but I'm not sure how to use them yet...

 

Here is another example:

LinkedItem and LinkedList also also subclassed by DictionaryItem and Dictionary, respectively. DictionaryItem provides an additional "name" field, and when Dictionary attempts to add a DictionaryItem to the list, it'll check the name field against items currently in the list to make sure it's unique (checking duplicates can be turned off, though).

 

Then, I have the last subclassed pair: UniqueItem and UniqueList. When an item is successfully placed into the list, a unique number, called "primaryKey", is generated, and stored in that item.

 

I have all three classes working, but a lot of casting is required to make it work... I plan on using these three classes, mainly Dictionary, as an abstract class where I can override my ValidateAdd method to implement further code for the situation. But then, if I was to use GetItem() to retrieve anything, it'd return abstract datatypes depending on the base class that implemented them.

 

For example:

LinkedItem *GetItem(int index); // implemented by LinkedList
DictionaryItme *GetItem(string name); // implemented by Dictionary

If I were to make a Dictionary subclass called CharacterController, that managed a list subclassed DictionaryItem's called Character, then GetItem(int) and GetItem(string) would return LinkedItem and DictionaryItem pointers of the actual Character instance actually there. I could write wrapper methods, but that seems messy.

 

Would templates work for this situation?

 



Sponsor:

#2 plainoldcj   Members   -  Reputation: 594

Like
2Likes
Like

Posted 17 August 2013 - 02:29 PM

Okay, this is an paradigm for implementing containers that I recently came across:

struct list_item { list_item *prev, *next; };
struct list {
list_item* head; // list of list_items
void add(list_item* item);
list_item* get(void);
};

To have a list of objects of type, say, my_widget, you derive from list_item:

struct my_widget : list_item { /* inherits prev, next pointers */ };

Additionally, you derive from list to hide casting:

struct my_widget_list : list {
// note how my_widget_list acts as a filter
void add(my_widget* item) { list::add((list_item*)item); }
my_widget* get() { return (my_widget*)list::get(); /* safe cast, only my_widgets in the list! */ }
};

Okay, great! But you certainly don't want to write a XXX_list class for every possible type XXX by hand. Luckily these classes can

be easily generated with templates:

template<class T>
struct concrete_list : list {
void add(T* item) { list::add((list_item*)item); }
T* get() { return (T*)list::get(); }
};

Okay, the code has probably some errors in it, but you get the idea how to hide the casting

and get pointers to derived types.

 

By the way, list implementations like these are often(?) called intrusive lists.

So you can ask Google how other people solved this.



#3 rdragon1   Crossbones+   -  Reputation: 1135

Like
2Likes
Like

Posted 17 August 2013 - 02:38 PM

Yes, these are "intrusive lists" and I would use caution when deriving from a type to add 'next' and 'prev' pointers to your object. What do you do when you want the object to be in more than one list? Also, how do you keep code from looking confusing - going this route, if you add an object to a list, you have to remember you're implicitly removing it from any list it was in previously.



#4 King Mir   Members   -  Reputation: 1788

Like
0Likes
Like

Posted 17 August 2013 - 04:42 PM

First of all as rdragon1 points out, that's a rather poor design for a list. Usually list containers are implemented as a bunch of nodes that contain the element held. The element type can vary, so this requires a class template.

Secondly, it sounds like it would be more fitting for CharacterController to contain a Dictionary, but have it's own methods that cast the dictionary elements to the proper type.

#5 Ravyne   Crossbones+   -  Reputation: 5695

Like
3Likes
Like

Posted 17 August 2013 - 04:57 PM

If this is an educational exercise, go ahead and learn about implementing things with templates. If its a practical one, the standard template library almost certainly has everything you need, and if it doesn't have *exactly* what you need, you can probably build what you want by combining containers, and perhaps sprinkling in a few other standard library features.

 

On a related note to that last part, the reason you see your custom list as having more features that are more desirable is because its just doing too much. From your description, its part list, part dictionary (like std::map), and has something to do with translating abstract types to concrete ones.

 

It sounds to me like what you want is a std::map (add/remove elements, look up an element by a name). If all the types you want to put in the list share a common base class, then you can do something like std::map<std::string, base_class*> and be done with it. If you want things in the list that don't share a common base type, you might first consider whether they really should and make one, or decide they shouldn't in which case you want some kind of intermediate class that can point to different types and handle all the type conversions. Even if that's what you want, separating the different concerns (item lookup from all this type conversion) into different classes is way better than mashing them all together in one class.



#6 Ryan_001   Prime Members   -  Reputation: 1098

Like
0Likes
Like

Posted 17 August 2013 - 04:59 PM

Boost has intrusive containers: http://www.boost.org/doc/libs/1_54_0/doc/html/intrusive.html.  They have their uses but I usually prefer the standard containers for most things.  They're generally most useful when you want an item to belong to multiple lists, or if the items are large, or have special construction, destruction, copying, or moving constraints that renders them unusable to normal containers.



#7 rip-off   Moderators   -  Reputation: 6876

Like
2Likes
Like

Posted 18 August 2013 - 07:29 AM

I would consider all the things you've mentioned as downsides compared to the standard containers. Having to derive from a given superclass is something I like to avoid. The "get type" idea sounds brittle and pushes what could be compile time checks to runtime string comparisons. Providing a "get by index" member function means you probably are trying to use linked lists where a dynamic array would be more appropriate. The dictionary appears to be a case of using linked lists where a sorted list, sorted tree or hashing data structure would be more appropriate. There seems to be a lot of inheritance for no real reason.

 

To directly answer your question, yes templates would be the recommended way to do this. This kind of code is party why templates were added to the language.

 

It is fun to write your own containers as a learning experience. But I would not recommend using them. I would recommend you try build your game on top of the standard containers instead. You should be able to implement CharacterController easily in terms of std::vector<> and/or std::map<>, if you simply want to be able to look characters up by name and "index".



#8 Vincent_M   Members   -  Reputation: 523

Like
0Likes
Like

Posted 18 August 2013 - 02:18 PM

I think the concrete_list is something along the lines of what I was originally aiming for, but there were quite a few good points brought up about using standard containers over building my own intrusive ones.

 

The reason I wanted my own type of lists is mainly due to std::list iterators. Having to declare an iterator every time I want to get to a specific element is just plain annoying. It takes like 3 or 4 lines of code to get to that specific element I already know I want. I've thought about vectors since I'd be able to refer to my elements by index, but then everything's aligned in memory. Although memory alignment has its benefits, adding elements to a vector could cause the entire array to relocate in memory to ensure everything is memory-aligned. This can be slow when adding data --especially larger elements.

 

Honestly, though, the current code base uses an old version of LinkedList called Collection and CollectionItem which did everything that Dictionary does. Just about everything was built on top of the use Collection and CollectionItem. Back then, Collection wasn't inherited either; it was used as a field per class and had wrappers to add, remove, clear and get everything. Lots of redundant code...

 

I'll try my luck with map and see how it works for me. Looks like it'll be my heavy hitter for most things.



#9 King Mir   Members   -  Reputation: 1788

Like
0Likes
Like

Posted 18 August 2013 - 11:17 PM

The reason I wanted my own type of lists is mainly due to std::list iterators. Having to declare an iterator every time I want to get to a specific element is just plain annoying. It takes like 3 or 4 lines of code to get to that specific element I already know I want. I've thought about vectors since I'd be able to refer to my elements by index, but then everything's aligned in memory. Although memory alignment has its benefits, adding elements to a vector could cause the entire array to relocate in memory to ensure everything is memory-aligned. This can be slow when adding data --especially larger elements.

Sounds like a use case for std::deque. It has an index operator, and in blocks of continuous memory, so it has most of the benefits of a vector (like good cache performance), but it won't reallocate the whole thing when it grows in size.

#10 Matt-D   Crossbones+   -  Reputation: 1405

Like
3Likes
Like

Posted 19 August 2013 - 10:23 AM

The reason I wanted my own type of lists is mainly due to std::list iterators. Having to declare an iterator every time I want to get to a specific element is just plain annoying. It takes like 3 or 4 lines of code to get to that specific element I already know I want. I've thought about vectors since I'd be able to refer to my elements by index, but then everything's aligned in memory. Although memory alignment has its benefits, adding elements to a vector could cause the entire array to relocate in memory to ensure everything is memory-aligned. This can be slow when adding data --especially larger elements.

 

I would still consider using std::vector, see: Bjarne Stroustrup: Why you should avoid Linked Lists.

The cache benefits of std::vector using contiguous memory are so massive that they may in practice outweigh the benefits provided by the lists, EVEN when inserting/removing elements in the middle. It's a trade-off; what's your relative access-to-modification ratio? It's worth checking the performance with profiler (ideally, avoid synthetic benchmarks, and test with your actual gameplay, e.g., using automated replay feature (assuming you have that in your engine)).

 

See “Software Development for Infrastructure” for more details and the graph mentioned in the video.

We should prefer sequential access of compact structures, not thoughtlessly use linked structures, and avoid general memory allocators that scatter logically related data. We must measure to avoid being blind-sided by unexpected phenomena. Our systems are too complex for us to guess about efficiency and use patterns.

 

 

 

 



#11 iMalc   Crossbones+   -  Reputation: 2176

Like
1Likes
Like

Posted 20 August 2013 - 03:58 AM

LinkedList is able to add and remove elements, and more importantly, get an element from a specific index.

That's rather unfortunate that you have done that, because giving a linked-list the ability to access items by index is generally regarded as a design blunder.

It turns any innocent loop using such functionality into a Schlemiel the Painter's algorithm.

 

LinkedItem and LinkedList also also subclassed by DictionaryItem and Dictionary, respectively. DictionaryItem provides an additional "name" field, and when Dictionary attempts to add a DictionaryItem to the list, it'll check the name field against items currently in the list to make sure it's unique (checking duplicates can be turned off, though).

Generally this is a further mistake. using a linked-list for dictionary-based lookup causes every lookup to be O(n), which get slow very quickly as the number of items increases. It again leads to more occurrences of Schlemiel the Painter's algorithm.

 

There is a very good reason that the standard library does not do any of this. It totally kills performance for any half decent usage of the container. For containers where key-based lookups are required, you want such an operation to be at most O(sqrt n), and ideally O(1). Typically O(log n) is chosen.
As much as you have a personal attachment to these features that you believe are useful, or even needed, you do need to accept that your implementation will be vastly inferior to the standard C++ library. Your best bet is to spend more time understanding the standard library containers, and come to a better appreciation of just how brilliant they really are.

 

Would templates work for this situation?

Templates are the solution to making a container generic.
 


"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

#12 DareDeveloper   GDNet+   -  Reputation: 726

Like
0Likes
Like

Posted 20 August 2013 - 05:02 AM

Unlike everybody else at Gamedev I am one of those guys who want to use both templates and inheritance at once so that I can replace the generic ItemContainer with different implementations and see how well they perform.

 

Many people have said that it doesn't make sense to do it.

Probably they are right when you can afford to invest time in reading the documentation and doing the math (as opposed to using trial and error).

 

What I'd like to add is that you will probably run into problems when you try to use both static and dynamic polymorphism in C++.

If you decide to still go for it ... maybe because you worked with another language that way and liked keeping things generic ... you should know that it might not be possible to work that way in C++.


Given enough eyeballs, all mysteries are shallow.

ProcGames.com


#13 Vincent_M   Members   -  Reputation: 523

Like
0Likes
Like

Posted 21 August 2013 - 01:21 AM

I have decided against using LinkedList/Item, etc. Many good points were brought up, and it's totally convinced me that vector and map are by far, the best solutions. Looking up by index is indeed a slow, iterative process, and the STL seems to do what is needed. It turns out that this Collection system I started using two years ago is a bad habit, and now that I have time to implement map over CollectionItem/Dictionary, things are coming along well! In fact, it seems that using map has even cut down the amount of wrapper code I need to write every time I use a map.






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