A fixed-length array data structure that allows you to quickly use arbitrary elements? C ++

Question

I'm relatively new to C ++ and trying to choose the most appropriate data structure for a particular problem, but it's hard for me to find the answers.

I want to create a small (1000 elements) array of either ints or simple structures. At any time in my code, I will need to add and remove elements from my array, but I do not want the overhead of dynamically reallocating RAM all the time. In addition, since I will have other variables that point to the elements in my array, I do not want to renumber / reorder the elements, as this will ruin this relationship. Since I can be sure of the maximum number of elements in my array, I am happy to preallocate all the necessary operational data, but I'm not sure how to effectively track which elements become free so that I can reuse them for new elements, as necessary. 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 to use a pre-distributed 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; } } }; 

If you need to select node only call Node::alloc , passing the data and where to put the node. When you need to free it, just call node dealloc.

Nodes are highlighted on the "pages" and reused after release. This minimizes the number of calls in the memory manager and can significantly speed up the work.

In a doubly connected structure, you will never need to move an existing node while it is in memory (so no pointers will need to be configured). It is also easy to change the order of elements, for example, add the Node::moveTo(Node *before) method.

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

Answer 2

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

• use vector::reserve() to allocate enough storage for the maximum number of elements that you plan to use for the array - note that reserve() does not actually add elements to the vector. The vector will still have the same number of elements as before the reserve() call. However, it ensures that vector does not need to be redistributed when an element is added to vector , unless this additional element causes the number of elements to exceed the reservation. It also means that pointers to vector will remain stable. Items
• guarantee that they will be in a continuous memory block with addressing of elements compatible with ordinary pointer arithmetic. In other words, if you have a pointer to one element, you can get a pointer to another element using ordinary pointer arithmetic (or array indexing)

Answer 3

You are looking for a Pool Distributor . You can write your own or use Boost.Pool

Answer 4

What you are describing is essentially a fixed-sized memory pool. You did not explain why you need it. Unless you have a specific reason to keep objects in an array-like structure, you should simply select them separately through new . You do not need a pool allocator unless the profiler convinces you otherwise.

If you have a reason to store all the objects in the array, regardless of this reason, you are going to implement your own array-based pool allocator. The easiest one uses a simple linked list to track free chunks. You save the index of the first unused element, and each unused element stores the index of the next. You should not do this unless you know exactly what you are doing and why.

Answer 5

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

You can come up with vector<> . It performs dynamic allocation when necessary, but not all the time. It is an efficiently written container.

Since I can be sure of the maximum number of elements in my array, I am happy to pre-select all the necessary

When declaring your vector, you can specify the size as:

 vector<int> vi(1000); 

You can also access vi from other places.

Answer 6

std :: vector is what you should use and use smart pointers instead of source pointers.

Answer 7

Since you still want to maintain the relationship between the external variables and the internal elements of the array, yes, you cannot reorder them. However, using std :: vector will change the order of the remaining elements when deleting / adding new elements that cannot satisfy your needs.

You can combine the bool value with each element of the array that determines whether this element is used or not. Please note that you can use a bitmap if memory is important to you.

 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 . Adding or removing a node from a linked list takes constant time, while pointers to other nodes remain unchanged. That way, you can establish a “relationship” if the external variables contain a pointer to the nodes instead of the index of the array. In addition, you do not even need to pre-select 1000 elements.

Answer 8

I will add that the overhead of allocating ints / small structs is small and that if you initialize vector without elements and use vector.push_back() and vector.erase() , this will mean that you do not need to keep track of which elements are free, and which are not. You seem to be interested in efficiency, but don't forget to do something in this sequence:

• Implement a clean and easy to read solution. Use features that clearly express what you want.
• If and only if , you find that the solution has serious performance problems, start using more complex and more effective solutions.