Is it OK to use a std::map on the audio thread?

I’m building a midi sequencer that works as a tracktion_engine::Plugin. Inside the applyToBuffer() function, I locate an array of MidiMessages, find one that matches the time index, and then swap it into the midi buffer. It looks something like this:

void SequencerPlugin::applyToBuffer(const te::AudioRenderContext& context)
    if (const auto eventArray = getEvents())    // type: std::shared_ptr<const std::vector<Event>>
        for (auto event : *eventArray)
            if (event->getTimeIndex() <= context.playhead.getPosition())

(Note: There are a lot of things that probably look fishy about this code, but please bare with me for the moment. I’ve been very careful to ensure that allocation, de-allocation and locking never happen inside this function, even though it might not seem so in the simplified code I’ve typed out here.)

My question is: would it be a Bad Idea to use a std::map<double, Event> as a container, rather than a std::vector<Event>?

I would want to do this because:

  • It would mean that all off the events would be sorted by time index, and the audio thread could locate the right ones without having to iterate over the whole array.
  • It would make some other parts of my code a lot neater (i.e. the parts where I am populating the Events, not shown here).

Again, the audio thread would only have access to a std::shared_ptr<const std::map<double, Event>>, so it could only read from the map, never alter it.

I’m asking this question because I know that iterating over a map is a lot slower than iterating over an array, and I’m wondering if it’s a bad idea to do this from the audio thread.

You are free to use a read only std::map in your audio thread.
The only forbidden stuff in the audio thread is allocating
Depending on the number of items a sorted vector could be faster given the cache size.
Only measurement will let you know

Have a look at std::unordered_map as well


Since you mention iteration, you should be mindful of iterator invalidation rules. std::vector is (potentially) invalidated on insertion, std::map on removal (if the iterator points to the item you just removed, for example). Since you cannot lock on the audio thread to read, you have to come up with a scheme to update your data structures such that you can read them and mutate them without blocking or invalidating pointers/iterators.

std::map is a binary tree which will underperform binary search through a sorted vector past a certain bound (depends on your data/application). You should benchmark to find out.

Another data structure that is useful for event scheduling is an interval tree, which can be implemented with std::map or by rolling your own tree structure. It will provide efficient (algorithmically) range queries, which is useful for figuring out which events to handle in an audio block.

If you do use the STL, you probably want std::multimap. std::map would not allow multiple events at the same time point.

1 Like