fixed length array data structure which allows quick reuse of arbitrary elements? C++

Question

I am relatively new to c++ and am trying to choose the most appropriate data structure for a specific problem but am finding it difficult to find answers.

I wish to create a small (1000 elems max) array of either ints or simple structs. At any time in my code I will need to add and remove elements from my array but I don't want the overhead of dynamically reallocating ram all the time. Also since I will have other variables which point to elements in my array I don't want to renumber/reorder the elements since that will screw up this relationship. Since I can be sure of a maximum number of elements in my array I am happy to pre-allocate all the required ram but I am not sure how to efficiently track which elements become free so that I can re-use them for new elements as needed. Is there an obvious data structure for this type of problem? Thanks in advance.

Answer 1

I think the best approach in this case is using a preallocated doubly-linked list...

// Untested code... just to give the idea

struct Node
{
    int data;
    Node *prev, *next;

    static Node *first, *last, *free;

    // Allocates a new node before the specified node or
    // at the end of the list if before is NULL
    static Node *alloc(int data, Node *before)
    {
        // Check the free list first
        Node *n = free;
        if (!n)
        {
            // There are no free nodes... allocate a bunch of them
            Node *page = new Node[1000];
            for (int i=0; i<999; i++)
            {
                page[i].next = &page[i+1];
            }
            page[999].next = NULL;
            n = free = &page[0];
        }

        // Update the free list
        free = n->next;

        // Link the new node to neighbors
        n->next = before;
        n->prev = before ? before->prev : last;
        if (n->prev) n->prev->next = n; else first = n;
        if (n->next) n->next->prev = n; else last = n;

        // Initialize it
        n->data = data;

        return n;
    }

    // Deallocates a node, placing it in the free list for reuse
    static dealloc(Node *n)
    {
        if (n)
        {
            // Remove from double chain
            if (n->next) n->next->prev = n->prev; else last = n->prev;
            if (n->prev) n->prev->next = n->next; else first = n->next;

            // Add to free list
            n->next = free; free = n;
        }
    }
};

When you need to allocate a node just call Node::alloc passing the data and where to put the node. When you need to free it just call node dealloc.

Nodes are allocated in "pages" and reused after deallocation. This minimizes the number of calls to the memory manager and can speed up things considerably.

The doubly-linked structure will never need to move an existing node while it's in memory (so no pointers will need to be adjusted). It's also easy to reorder elements for example adding a Node::moveTo(Node *before) method.

The drawback of this approach is that to access the nth element given the index is an O(n) operation.