can I implement this queue without dynamic allocation

[sbaratheon]

Hi

I'd like to implement a queue for messages:

• I have a base Message class, which is inherited by subclasses which contains further data for a particular purpose (e.g. a TimeMessage object)
• The queue should be able to store a Message object or any subclass (and any combination thereof).
• The queue can have a fixed size (e.g. 5 Messages or Message subclasses)

I think this could be done via dynamic allocation and the passing of pointers. At a high level, it would work like this (and I appreciate that the below has all sorts of issues - I have just typed out quickly to show what I am trying to do):

#include <iostream>

using namespace std;

class Message
{
    protected:
        int mMsgCode;
        
    public:
        Message(int msgCode) : mMsgCode(msgCode) {}
        
        int getMsgCode()
        {
            return mMsgCode;
        }
        
        virtual void serialiseMe()
        {
            cout << "msgCode: " << mMsgCode << endl; 
        }
};

class TimeMessage : public Message // just an example, there might be many other subclasses
{
    private:
        unsigned int mTm;
        
    public:
        TimeMessage(int msgCode, unsigned int tm) : Message(msgCode)   
        {
            mTm = tm;
        }
        
        unsigned int getTime()
        {
            return mTm;
        }
        
        virtual void serialiseMe() override
        {
            Message::serialiseMe();
            cout << "Time: " << mTm <<endl;
        }
};

class MessageQueue
{
    private:
        static const int QUEUE_SZ = 2;
        Message *pMessages[QUEUE_SZ];
        
    public:
        void addMessage(Message msg)
        {
            pMessages[0] = new Message(msg.getMsgCode());
        }
        
        void addTimeMessage(TimeMessage tMsg)
        {
            pMessages[1] = new TimeMessage(tMsg.getMsgCode(), tMsg.getTime());
        }
        
        Message* getMessage(size_t messageN)
        {
            return pMessages[messageN];
        }
        
};

int main()
{
   MessageQueue queue;
   queue.addMessage( Message(33) );
   queue.addTimeMessage(TimeMessage (44, 595949239));
   
   queue.getMessage(0)->serialiseMe(); // msgCode: 33
   queue.getMessage(1)->serialiseMe(); // msgCode: 44 // call serialiseMe() of TimeMessage by polymorphism
                                                          //Time: 595949239
   
   
   return 0;
}

The key issue with the above which I am trying to solve is to avoid dynamic allocation (which is generally discouraged on embedded platforms). Is there any way in which I can have this type of functionality without dynamic allocation (i.e. adding Messages or subclass Messages to the queue and relying on polymorphism)?

Thanks

[gfvalvo]

What platform? The Arduino cores for most non-AVR processor support the C++ STL.

[sbaratheon]

gfvalvo:
What platform? The Arduino cores for most non-AVR processor support the C++ STL.

Hi
I'm using a SAMD21 microcontroller. Are there any features of the C++ STL which would help me here?
Thanks

[anon57585045]

Well, 'queue' of course.

[jimLee]

How much RAM do you have? SAMD21 can have up to 32k. If you have that much.. Go for it.

-jim lee

[PieterP]

You cannot create arrays of polymorphic objects of mixed types. Therefore, a common approach is to use an array of pointers to base type, and store the actual objects elsewhere, usually on the heap.

They don't have to be stored on the heap, though, you could have your main queue of pointers and then one array of each derived type, allocated in advance. Obviously, this doesn't scale well if you have many different derived types.

Another solution would be to use a queue of std::variants (type-safe unions). Creating a variant does not require dynamic allocation. The downside is that you'll have to use std::visit ... This is a different kind of runtime polymorphism, it's less user friendly than inheritance with virtual functions.

Assuming you know the size of your largest message, you could use a custom allocator that operates in blocks of this size, possibly on a pre-allocated buffer in order to prevent fragmentation. This buffer can be your queue at the same time: allocate raw storage for N times the maximum element size and then use placement new to create the elements in your queue.

The latter is probably the best solution. However, an std::queue of std::unique_ptr will probably work fine, and is much easier to implement, leaving less room for error.
std::queue uses std::deque for storage (by default), which usually allocates memory in fixed-sized chunks. If your messages have similar sizes, allocating them on the heap is probably fine as well. You might get some limited fragmentation, but it won't be as bad as concatenating hundreds of strings, and you have enough RAM, it'll be fine. I'd try this first, and if you notice fragmentation issues, you can always write a more specific solution later. It all depends on the application, of course, in many hobby projects, dynamic allocation is not an issue. The problem is that it is not deterministic, so in critical applications, it is simply not done, because you cannot formally prove that fragmentation won't be an issue.

The code you posted above leaks memory. You should almost never use new directly, and raw pointers should never be owning pointers. Use an array of std::unique_ptr for the storage of your queue instead of raw pointers.

Pieter