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?

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.

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.

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.

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.

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.

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.