C++ statically allocated double ended queue implementation

Question

STL has deque implementation, Boost deque implementation; But both of them uses the STL way of sequence containers (dynamic allocation with allocators).

I am searching for a reliable, fast and statically allocated deque implementation. Which looks something like this:

template<typename T, unsigned int S>
class StaticDeque
{
   T m_elements[S];
};

So all elements to be allocated statically.

Note1: I already have STL based solution (using custom allocators which statically allocates data for vector and deque), but I am searching for any better solution (lower execution time).

Note2: I need statically allocated memory because I handle data in a predefined (fast access) area in memory. So object will be declared like this: #pragma DATA_SECTION("fast_memory") StaticDeque<int, 10> payloads;

Answer 1

You could use Howard Hinnant's stack allocator which reuses the existing std::deque implementation with a modified allocator. You can supply any piece of memory to the allocator's constructor, including a so-called arena object which holds an array of chars on the stack. You could also use an arena object containing a statically allocated piece of memory on the heap, by a small modification of the arena class.

Note however that currently it is not a 100% static scheme because when the amount of memory that the arena object holds is exhausted, the ::operator new is being called to allocate extra memory on the heap. Maybe in C++14 with runtime sized arrays this can be mitigated. For the time being, just make sure to pre-allocate and reserve enough memory for your std::deque (based on profiling your application).

The advantage is that you can use this allocator with any STL container, and you can concentrate on the memory issues only, instead of also having to worry about getting the container correct and efficient.