c++ - Data structures for traversable memory pool -

I am implementing a memory pool in C ++ with the following constraints:

• To promote allocated cache reuse elements must be in linear time in order of their memory address.
• Delete the elements (memory block) and make them memory pool.

Allocation and deallocation are often during a real time program runtime, so there is a need to be as fast as possible.

I have implemented one of these allocated elements for free, by using two linked lists as slots, so far this memory pool has been implemented. It works, but of course it is very slow, because once an element is either free or allocated, the element should be removed from one list and the other should be added, which is linear. I would like to do it fast

What data structure can I use to make it as efficient as possible (D) allocation? I was thinking of using the red-black tree (or similar balance BST) to store allocated elements and the priority queue for free elements. This will lead to O (log n) allocation and delocation.

Any advice about how I can improve this design? Can I use other data structures?

Edit : I should make it clear that these data structures are for storage only and memory blocks are already allocated before accessing memory addresses is. Fixed memory Memory blocks with a memory pool, continuous time operation can be obtained as follows. :

• Identify each memory block from your index in the pool (memory block address can be easily obtained from this code from block_address = base_address +) index * block_size , and vice versa).
• There is a data structure for metadata (to keep track of allocated and free blocks), one that works with the requirements, is a fixed size array in which each There is an item corresponding to memory block (identified by the same index). Embedded in that array are two (double) linked lists (one for one more free blocks for allocated). Since these linked lists do not overlap, they can use the same prev = / code> and next pointers.

How it fixes the requirements:

Linear Time Traveler : Memory blocks are defined as part of their index (either metadata A free / allocated flag is probably useful in that case), or both of linked lists, depending on requirements.

Continuous time allocation : Allocation of memory blocks means getting the first list from the free list, and taking it into the allocated list (finally eg.) Of the link To remove the first item from the list, and to attach an item at the end of the linked list, both time continuous time operations (the index of a list is handled and / or at the end, an index is handled - the circulars of the lists can help) .

Continuous time deallocation : Removing a memory block is to identify the metadata item related to its respective index, and transfer it from the allotted list in the free list (eg eg .) Obtaining an item in an index from one object, removing items from the (doubled) linked list, and adding an item at the end of the list listed at one link, all the continuous time operations.