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;

So what's your question? Basically you want a cyclic buffer with two indices that mark the current ends of the queue. — , Apr 21 '13 at 18:37
You could make your own ring buffer with put front and put back funcions easily. A stl deque has lots of overhead to deal with dinammicaly linked lists. — Felipe Lavratti, Apr 22 '13 at 00:02
See [this question](http://stackoverflow.com/questions/16117304/why-is-kfifo-h-so-full-of-define-statements) and [kfifo.h](https://git.kernel.org/cgit/linux/kernel/git/stable/linux-stable.git/tree/include/linux/kfifo.h). The design goals of a typical template library don't always fit with *embedded* application. See [STL+embedded](http://stackoverflow.com/questions/3853382/stl-in-embedded-enviornment). This doesn't mean you can not use C++ in an embedded environment. Just like it is not always wise to use the *C* **X11** graphics library in an embedded *C* situation, not all C++ code fits. — artless noise, Apr 22 '13 at 01:20
FYI *Boost.Fusion* `deque` is probably not what you want. [Boost.Container `deque`](http://www.boost.org/doc/libs/1_53_0/doc/html/boost_container_header_reference.html#header.boost.container.deque_hpp) is boost equivalent. — Bartek Banachewicz, Apr 22 '13 at 11:24
@James, yes but it should support STL syntax (begin, end, iterators, reverse iterators, ...) — Yousf, Apr 24 '13 at 10:41

score 2 · Answer 1 · edited Jan 21 '15 at 19:05

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.

C++ statically allocated double ended queue implementation

1 Answers1