Command pattern queue ordered by time?

Question

I'm changing some code to use the command pattern and will store command objects in a queue. The commands will need to be executed at specific times and so I will iterate over the list once per second to find commands to execute.

There will be a time associated with each command object and I will check this time against the current time (within a small threshold). So I'll need to remove the command object from the list if its time matches and then execute it. Generally there will be under 10 commands at any given time. What collection data structure should I use and how do I remove command objects while iterating the list?

Answer 1

I think you want to use a priority queue. This is a container that lets you pull the highest priority item. In your case, "higher priority" is "happens first".

C++ models a priority queue as the priority_queue container adapter. This means that there's some other container inside of it that does the actual storage. This container is usually either vector or deque. (Random-access iterators are required.) It defaults to vector. So you can just declare:

std::priority_queue<T, vector<T>, Compare> queue;

where T is your element and Compare is a function that compares two T elements and returns true if the first is lower priority than the second. If you have operator < defined for your type T, it gets even simpler:

std::priority_queue<T> queue;

• To put an item in the queue: queue.push(item);
• To get the highest-priority element: queue.top()
• To remove the top item of the queue: queue.pop();

Note that pop() does not return the removed element; it just removes and destructs it.

Answer 2

An alternative to Mike's solution is to use ordered map, which in case of STL is simply a map. You can keep time as a key and command as value. Depending on your case it may be more convenient than queue.

If two commands are allowed for the execution at the same time then you shall use multimap.

multimap<time_t, Command> schedule;

schedule.insert(pair<time_t, Command>(123456, formatHDDCommand));