I had a quick go at replacing the vector class this evening with a non-STL equivalent. The obvious route to go for is a linked list, so that’s what I created - a template class representing a doubly-linked list with both sequential access and simulated random access.
Random access is simulated by iterating along the list until the correct index is reached, which gives me bounds checking for free. Sequential access is wrapped up inside the class and hidden away, and is handled by an “iterator” member variable. It can be repositioned to the start or end of the list or moved to a random index, from where it can be moved up or down the list of items.
I got the class finished and plugged it into the code (after some tinkering). It didn’t work. One of the main problems with it is the internal iterator pointer - if one iterative function calls another, the iterator gets moved around and nothing works. I knew it wasn’t an ideal solution when I wrote it, and had the nagging feeling that it wasn’t going to work, but this obvious problem didn’t become apparent until I actually watched the code in a debugger.
I can see two ways out of this. The easiest way is to move the iterator code into a separate class, which will mean I can have as many iterators as I want (I’m thinking of something like .NET’s “GetEnumerator()” function). However, this doesn’t solve the basic problems of a linked list. Although I use a lot of sequential access in Woopsi, a significant amount of code uses random access of the gadget vectors. Linked lists aren’t designed for random access.
What would be better is a standalone implementation of the vector that just supplies the features that Woopsi uses. First question, then - what is a vector? The Wikipedia article and the description on cplusplus.com suggest that the vector is really nothing more than a dynamic array, or an array that can resize itself. This is typically achieved by allocating a fixed size to start off with (16 elements, say), then allocating a larger array if the original array fills up (32 elements - the original array plus 16 more), copying from one to the other, and finally freeing the original memory. It offers less memory fragmentation than a linked list and true random access, but the resize operation is much more expensive. Insert and remove operations anywhere but at the end of the array are similarly more costly.
I think I’m going to go for the second option - a dynamic array class. It might even be possible to abuse the DMA hardware further and get it to help out with the resize.