Generic Datatypes --Are Templates the Way to Go?

Started by
11 comments, last by Vincent_M 10 years, 8 months ago

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
Advertisement

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.

MeAndVR

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.

This topic is closed to new replies.

Advertisement