SmartList

I need a method of having an array which knows where its empty spots are.
I have a few ideas for it, but is there anything I should google?

Well, you need to define what an empty spot is. You need to decide on the performance characteristics: do you need constant-time access to all the empty spots, or just the first? etc.

Once you've done that, I can perhaps help you choose a data structure for it.

At anytime, without any knowledge of what exists in the array, I wish to be able to simply Push() into an array, have the array determine a free slot and stick it in there OR ReAllocate and set up extra free values then add it.

My first conclusion was to simply use 2 arrays
Array<_TY> m_pData;
Array<UINT> m_pFree;

Then anytime data is removed from m_pData, that index will be pushed in m_pFree. I in fact implimented this once and called it a ManagedArray, but it was a bit ugly.

I figure this is a newbie approach to the problem and I assume somewhere deep in a computer science text I could find the proper solution.

How about a std::list? You don't have indexed access, but it allows constant-time insertion and removal at any given place.
Or a simple std::vector. Removal from a random place is linear time, but pushing is constant time unless the vector has to reallocate, in which case it's linear.
Another option is std::deque. Removal is again linear, but you can push at both ends with constant time.
Or perhaps a std::set. Removal and addition both log(n), with no indexed access, but instead lookup of elements based on their own value.

What exactly is it that you want to do with that thing?

A dynamic unit pool.
Size with an estimate and quickly resized when necessary accompanied by no lookup for free slots when new units are added. It would be nice to keep the array collapsed when a unit deletes as to speed up iteration through it.

Sounds like a job for a linked list with a memory pool custom allocator. You can use a normal linked list now and add the custom allocator when profiling shows it's necessary.

That was my first guess, to use a single-linked list.
On its most basic level it is very easy to impliments.

Each element in the list holds the points to the next item in the list but this pose's a problem as far as I know.

A list with 15 elements in it, I wish to delete element 10, now some link in the list is pointing to an invalid element.

I suppose the solution would be to have each element store the last and next so if I delete 10, it can go to the last and set its next to 10's next before 10 is removed...

Em I on the right track here or did I totaly miss the point of the linked-list?


What do you mean by a memory pool custom allocator?


Also, I'm sure std::list is faster and I'm sure there is a boost library for this but I need to learn how to do it myself from scratch at least as much as I can. Learning is more fun than using, I'd rather fail a million times and see my mistakes than use std:: and be without knowledge.

That's why you use a double-linked list. In a dll a node has pointers to both the previous and next node. Adding a node nn after a given node gn looks like this:

Code:

---

nn = new node(data);
nn->next = gn->next;
nn->previous = gn;
gn->next->previous = nn;
gn->next = nn;

---

Now you've inserted an element into the list and adjusted the links. Deleting works the other way round. Suppose you want to delete dn:

Code:

---

dn->next->previous = dn->previous;
dn->previous->next = dn->next;
delete dn;

---

You just need to take special care for the first and last elements, because they also adjust the head and tail pointers of the linked list controller, and because their next and previous pointers might be null. (There are circular lists which never have null pointers, but they are for very specialized applications.)

Based on this information, it shouldn't be too hard for you to implement a linked list. The experience is certainly worth it. However, I would strongly recommend against using this list in your actual engine.


Custom allocators - all standard library containers, such as std::list, can be supplied an allocator. An allocator is a small object that is used by the container instead of calls to new and delete, so that the programmer can choose his own way of giving the container memory. The default allocator just calls new and delete, but you could, for example, write one that uses a memory pool. (Boost provides a memory pool implementation. Memory pools are anything but trivial, so I recommend you don't try to write your own.)

So thats wut a double linked list is... Very cool.
I can see why it isn't very optimized for a game engine, many dereferencing. I will however begin writing my own, experience. Plus I bet in Computer Science they'll make me do it anyway, so why not get a heads up :)


Exactly what is a memory pool?
Its pure definition.

From I can gather it is a class which manages pre-allocated memory and hands it off when necessary, thus less calls to new and delete.

They most certainly make you do it in CompSci. Here at my university they make us do it in a subject called Algorithms & Datastructures I (as opposed to II). Highly interesting subject, covering simple search algorithms (insertion sort, selection sort, merge sort, quick sort, heap sort, and bucket sort), various data types (linear sequential lists (std::vector), linear linked lists (std::list), binary trees of various kinds (std::map)), search algorithms (linear and binary search), various other trees (B-trees, B*-strees), tries (data structures for string lookup), hashing and hash maps, some very simple graph problems and optimization problems.

AlgoDat II is about various advanced text search algorithms (VERY interesting topic), randomized algorithms, external algorithms (those working on data masses too large to fit into RAM), more optimizing, more graphing and some geometric algorithms.

A memory pool manager is an object that allocates a large block of memory and hands parts of it out in a manner optimized for a very specific application. This is done because the default new and delete, being written to be generic, are not efficient for various applications, such as allocating many small objects of the same size.

Oh! I cannot wait. Learning about stuff I enjoy is such a joy and I find some of my most barriers on my lack of the computer science knowledge.

See game programming is my goal, that feels like its been embedded into me as my life went on.


So a custom memory pool actually replaces the use of new and delete?
It totally re-writes them or allocates one large chunk but then becomes the allocater for an application?

There are various ways of applying a memory pool. Replacing new and delete is possible, but rarely desireable, because it's quite a big action to take. Also, the new ones would have to be just as generic as the old ones.
Replacing new and delete for a single class is also possible, and makes a lot of sense. However, this is not applicable to containers.

Containers simple don't use new and delete. They instead use an allocator object that you, as the programmer, can replace. The allocator object decides how to deal out memory.

Yes but it just doesn't decide...
How are its decisions made, where did it get the memory from initially.

The decisions are made by the author of the allocator. Including where the initial memory comes from. It probably comes from calling operator new, malloc, or some OS-specific allocation function like VirtualAlloc. It might even be a memory area returned by mapping a file to memory, or a device. (If you wrote a device driver in C++ using the STL.)

Ahhh, okay I won't need to tamper with memory pools for awhile yet. :)


Is there a such thing as Quad-Linked Lists??

Perhaps a 1D Array with items can point up, down, next, prev

I suppose that you could find a use for them in some geometric systems. Perhaps level maps. Quad-trees are used a lot in 2d games.

Well Quad-Tree are used very nicely in breaking up terrain to provide an easy frustum culling, collision culling engine, all in 3D especially. I have that all going.
BSP tree's are good for objects and what not that cannot fit nicely in your quad-tree.


I asked about a quad-linked list cause on GameDev someone proposed the problem of how to manage a game like Tetris Attack. If you've never played, it is somewhat like tetris except you can swap individual block pieces around up, down, left, right and all it takes is 3 blocks of one type to eliminate them.

I figured in my head the solution would be simple, a linked-list which knows wuts above it, below it, beside it on either side. The process of manuevering around blocks would be a sintch.
I should remake Tetris attack, probably take only a few days....

Yeah, that sounds viable. Largest problem is knowing your position in the overall grid, you have to track that separately.