4

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.

Improve this question
2
  • 5
    Why don't you use std::vector? Commented Jul 24, 2011 at 6:34
  • 1
    Where do you have to add and remove elements? The front, the back, potentially anywhere? Conceptually, removing elements will always renumber the subsequent elements. Commented Jul 24, 2011 at 7:02

8 Answers 8

Reset to default
3

A std:vector<> seems to fit your requirements quite well:

  • use vector::reserve() to allocate enough storage for the maximum number of elements you plan for the array to have - note that reserve() doesn't actually add elements to the vector. The vector will still have the same number of elements as before the call to reserve(). However, it does guarantee that the vector will not need to perform a reallocation when an element is added to the vector unless that additional element would cause the number of element to exceed the reservation. This also means that pointers into the vector will remain stable.
  • elements are guaranteed to reside in a contiguous block of memory with addressing of the elements compatible with normal pointer-arithmetic. In other words, if you have a pointer to one element, you can get a pointer to another element using normal pointer arithmetic (or array indexing)
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Ah, I have used vectors before but found them slow to do realocation. I had not seen the reserve() functionality before so that sounds like it might do the trick. I need to remove elements at any arbitary position, not just front or back. Thanks!
Whether the "remove elements at any arbitrary position" requirement will be a problem depends on exactly what you mean by that. vector:erase() will move the elements after the erase element(s) over the locations that were erased - that may or may not be exactly what you want. vector::erase() will never perform a reallocation.
2

You're looking for a Pool allocator. You can write your own or use Boost.Pool

Improve this answer

Comments

2

What you describe is, essentially, a fixed-size memory pool. You have not explained why you need it. Unless there's a specific reason to keep your objects in an array-like structure, you should just allocate them individually via new. You don't need a pool allocator unless a profiler convinces you otherwise.

If you do have a reason to keep all your objects in an array, whatever that reason is, you are going to implement your own array-based pool allocator. The simplest one uses a simple linked list to keep track of free chunks. You keep the index of the first unused element, and each unused element keeps an index of the next one. You shouldn't do it unless you know exactly what you are doing and why.

Improve this answer

2 Comments

Yes a linked list to unused chunks sounds useful. It's hard to explain exactly what I am doing but it is part of a particle system where each particle has a pointer to one of a number of container objects. Multiple particles can point to the same container and will repeatedly swap containers. The containers are the elements that I wish to store in my array structure. Because of the way I wish to organize the data it makes more sense to store the container indexes per particle rather than storing the particle indexes per container. ie there are few containers but a large number of particles.
OK so you store container identifiers in particles, nothing wrong with that. But the identifiers need not be integer indexes in an array, they could be pointers to actual containers just as well. You could use boost::shared_ptr instead of plain pointers and stop worrying about freeing your containers.
0

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.

Improve this answer

Comments

0

I don't want the overhead of dynamically reallocating ram all the time

You can think of using vector<>. It does dynamic allocation when needed, but not all the time. It's efficiently written container.

Since I can be sure of a maximum number of elements in my array I am happy to pre-allocate all the required

While declaring your vector you can specify the size as:

vector<int> vi(1000);

You can also refer to vi from other places.

Improve this answer

Comments

0

std::vector is what you should use & use Smart Pointers instead of raw pointers.

Improve this answer

Comments

0

I will add the point that the overhead of allocating ints/small structs is small and that if you initialize a vector with no elements and use vector.push_back() and vector.erase() it will mean that you don't need to keep track of which elements are free and which are not. You seem concerned with efficiency but remember to do things in this sequence:

  1. Implement a clean and easily readable solution. Use features that express what you want clearly.
  2. If and only if you find that the solution suffers from significant performance issues, start to use more complex but more efficient solutions.
Improve this answer

Comments

0

Since you still want to maintain the relationship between external variables and internal array elements, yes, you cannot reorder them. However, using std::vector will reorder remaining elements when you remove/add new elements which cannot meet your need.

You can combine a bool value with each element in the array specifying whether that element is in use or not. Note that you can use a bitmap if memory is critical to you though.

struct CElement
{
  // specify whether this element is in use
  bool isUsed;
  int element;
}

const size_t MAX_CAPACITY = 1000;
CElement myArray[MAX_CAPACITY];

Another option is to use a linked list. Addition or removal a node from a linked list takes constant time while pointers to other nodes still remain the same. So you can establish "relationships" by having external variables hold pointer to nodes instead of array index. Also, you don't even need preallocate 1000 elements in advance.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.