Introduction to the topics data structures, algorithms and complexity / computability in C++

Caution - this tutorial is a theory-loaded one - we will discuss a bit of the basics about data structures, algorithms and complexity - all that especially in context with C - so let's get started with the data structures in C

Lists, Dictionaries and Queues

We begin with some basic data structures we already used without going much into the topics; those two are std::vector (basically lists) and std::map (basically dicts).

Lists and Vectors

Let us begin with the std::vector we already use those data types for the different voices. The complexity is almost O(1) or worst case scenario O(n). For a std::vector, accessing a random item is its "superpower." Because a vector stores its elements in a contiguous block of memory, it doesn’t need to traverse the list like a chain. Thus, the complexity for accessing any item in the list is O(1) - so constant.

Dictionaries and maps

Let us continue with the dictionary (or better map) in C++ . We use std::map to assign the different keys to a certain frequency. Unlike std::vector, which is built on a contiguous array, a std::map is typically implemented as a Red-Black Tree (a type of self-balancing binary search tree). This structural difference completely changes how it handles data.

For std::map, adding, removing, and even searching for an item all share the same complexity: Logarithmic Time O(\log n).

Why O(\log n)?

In a balanced tree, every time you make a "move" (comparing your key to the current node), you effectively rule out half of the remaining possibilities.If you have 8 elements, it takes at most 3 steps ($2^3 = 8$).If you have 1,024 elements, it takes at most 10 steps ($2^{10} = 1024$).If you have 1,000,000 elements, it only takes about 20 steps.

Queues, Deques and Stacks

While vectors are great for random access, sometimes we need a structure that strictly manages the order of processing. In C++, this is typically handled by std::queue.A queue follows the FIFO (First-In, First-Out) principle. Imagine a literal line at a grocery store: the first person to get in line is the first one to leave. In your synth project, a queue (specifically a thread-safe ring buffer) is essential for passing MIDI messages or audio samples between the UI thread and the high-priority audio callback thread. Complexity: For std::queue, both adding an element (push) and removing the front element (pop) are $O(1)$. Deques are double ended queues where you can add remove any element from both sides of the queue.

data structure

Access

Search

Insert (Average)

std::vector

O(1)

O(n)

O(1) (amortized at end)

std::map

O(log(n))

O(log(n))

O(log(n))

std::list

O(n)

O(n)

O(1)

std::deque

O(1)

O(n)

O(1) (at ends)

Crafting a custom data type

Now after itching on the surface of the topic we now want go deeper and create our own data structure the (audio) ring buffer. We make use of the standard template library and create our own implementation of a ring buffer…​

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#ifndef AUDIO_RING_BUFFER_H
#define AUDIO_RING_BUFFER_H

#include <atomic>
#include <cstddef>

/**
 * @brief A Single-Producer Single-Consumer (SPSC) Ring Buffer.
 * Designed for passing audio samples from the Audio Thread to the UI.
 */
template <typename T, size_t Size>
class AudioRingBuffer {
private:
    T buffer[Size] = {0};
    // Atomic index to prevent race conditions between threads
    std::atomic<size_t> writeIndex{0};

public:
    AudioRingBuffer() = default;

    /**
     * @brief Writes a single sample to the buffer.
     * Called by the "Producer" (Audio Thread).
     */
    void write(T sample) {
        size_t currentWrite = writeIndex.load(std::memory_order_relaxed);
        buffer[currentWrite] = sample;

        // Ensure the sample is written before the index is updated
        writeIndex.store((currentWrite + 1) % Size, std::memory_order_release);
    }

    /**
     * @brief Reads a sample at a specific relative index.
     * Called by the "Consumer" (UI/Renderer).
     */
    T read(size_t index) const {
        return buffer[index % Size];
    }

    /**
     * @brief Returns the current write position.
     * Use acquire semantics to ensure we see the most recent writes.
     */
    size_t getWritePointer() const {
        return writeIndex.load(std::memory_order_acquire);
    }

    size_t getSize() const { return Size; }
};

#endif
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

#include <SDL2/SDL.h>
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>

#include "Oscillator.h"
#include "Envelope.h"
#include "Filter.h"
#include "Voice.h"
#include "AudioRingBuffer.h"

// Global pre-allocated Ring Buffer for the Oscilloscope (2048 samples)
AudioRingBuffer<float, 2048> scopeBuffer;

class SynthEngine {
public:
    // std::vector is great for iterating through active voices in the audio thread.
    // However, adding/removing voices requires a Mutex (SDL_LockAudio) to be safe.
    std::vector<Voice*> voices;
    LowPassFilter filter;
    SquareOsc lfo;

    float masterVolume = 0.15f;
    float syncMultiplier = 2.5f;

    SynthEngine() : lfo(0.5f, 1.0f, 44100.0f) {
        filter.setCutoff(0.8f);
    }

    ~SynthEngine() {
        for (auto v : voices) delete v;
    }

    // This is the High-Priority Audio Thread
    static void AudioCallback(void* userdata, Uint8* stream, int len) {
        SynthEngine* engine = static_cast<SynthEngine*>(userdata);
        float* buffer = reinterpret_cast<float*>(stream);
        int length = len / sizeof(float);

        for (int i = 0; i < length; i++) {
            float mixedSample = 0.0f;

            // Process all active voices stored in the std::vector
            for (auto it = engine->voices.begin(); it != engine->voices.end(); ) {
                Voice* v = *it;

                // Real-time update of the Hard Sync frequency
                v->setSlaveFrequency(v->masterOsc->getFrequency() * engine->syncMultiplier);

                mixedSample += v->getNextSample();

                // If Envelope is finished, remove the voice from the vector
                if (v->env.getState() == OFF) {
                    delete v;
                    it = engine->voices.erase(it);
                } else {
                    ++it;
                }
            }

            // Global FX Chain
            float filtered = engine->filter.process(mixedSample);
            float finalSample = filtered * engine->masterVolume;

            buffer[i] = finalSample;

            // PUSH to the custom lock-free structure for the UI to see
            scopeBuffer.write(finalSample);
        }
    }
};

int main(int argc, char* argv[]) {
    if (SDL_Init(SDL_INIT_AUDIO | SDL_INIT_VIDEO) < 0) return 1;

    SDL_Window* window = SDL_CreateWindow("C++ Hard Sync Synth",
        SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, 800, 400, SDL_WINDOW_SHOWN);
    SDL_Renderer* renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED);

    // std::map: Perfect for translating keys to MIDI notes at the UI level
    std::map<SDL_Keycode, int> keyMap = {
        {SDLK_a, 60}, {SDLK_s, 62}, {SDLK_d, 64}, {SDLK_f, 65},
        {SDLK_g, 67}, {SDLK_h, 69}, {SDLK_j, 71}, {SDLK_k, 72}
    };

    SynthEngine engine;

    SDL_AudioSpec ds;
    ds.freq = 44100;
    ds.format = AUDIO_F32SYS;
    ds.channels = 1;
    ds.samples = 1024;
    ds.callback = SynthEngine::AudioCallback;
    ds.userdata = &engine;

    if (SDL_OpenAudio(&ds, NULL) < 0) return 1;
    SDL_PauseAudio(0);

    bool running = true;
    SDL_Event e;

    std::cout << "--- HARD SYNC SYNTH READY ---" << std::endl;
    std::cout << "A-K: Play Notes | UP/DOWN: Adjust Hard Sync | ESC: Quit" << std::endl;

    while (running) {
        while (SDL_PollEvent(&e)) {
            if (e.type == SDL_QUIT) running = false;

            if (e.type == SDL_KEYDOWN && e.key.repeat == 0) {
                if (e.key.keysym.sym == SDLK_ESCAPE) running = false;

                if (keyMap.count(e.key.keysym.sym)) {
                    int note = keyMap[e.key.keysym.sym];
                    float freq = 440.0f * pow(2.0f, (note - 69) / 12.0f);

                    SDL_LockAudio(); // Protect std::vector from concurrent access
                    Voice* newVoice = new Voice(freq, 1.0f, 44100.0f, note);
                    newVoice->setSlaveFrequency(freq * engine.syncMultiplier);
                    engine.voices.push_back(newVoice);
                    SDL_UnlockAudio();
                }

                if (e.key.keysym.sym == SDLK_UP) {
                    engine.syncMultiplier += 0.2f;
                    std::cout << "Sync Multiplier: " << engine.syncMultiplier << std::endl;
                }
                if (e.key.keysym.sym == SDLK_DOWN) {
                    engine.syncMultiplier = std::max(1.0f, engine.syncMultiplier - 0.2f);
                    std::cout << "Sync Multiplier: " << engine.syncMultiplier << std::endl;
                }
            }

            if (e.type == SDL_KEYUP) {
                if (keyMap.count(e.key.keysym.sym)) {
                    int note = keyMap[e.key.keysym.sym];
                    SDL_LockAudio();
                    for (auto v : engine.voices) {
                        if (v->note == note) v->env.triggerOff();
                    }
                    SDL_UnlockAudio();
                }
            }
        }

        // --- UI RENDERING (Uses the AudioRingBuffer) ---
        SDL_SetRenderDrawColor(renderer, 20, 20, 25, 255);
        SDL_RenderClear(renderer);

        SDL_SetRenderDrawColor(renderer, 0, 255, 204, 255); // Neon Cyan

        // Get the current write pointer from the audio thread
        size_t writePos = scopeBuffer.getWritePointer();

        // We draw 800 samples from the buffer
        for (int x = 0; x < 799; x++) {
            // Read samples relative to the current write position (last 800 samples)
            // This prevents the "jumping" effect of a static buffer
            float s1 = scopeBuffer.read(writePos + x - 800);
            float s2 = scopeBuffer.read(writePos + x + 1 - 800);

            int y1 = 200 - (int)(s1 * 150);
            int y2 = 200 - (int)(s2 * 150);
            SDL_RenderDrawLine(renderer, x, y1, x + 1, y2);
        }

        SDL_RenderPresent(renderer);
        SDL_Delay(16); // Target ~60 FPS
    }

    SDL_CloseAudio();
    SDL_DestroyRenderer(renderer);
    SDL_DestroyWindow(window);
    SDL_Quit();

    return 0;
}

This custom ring buffer is a perfect bridge between pure theory and practical synth development. In audio programming, we often can’t use std::vector or std::map directly inside the audio callback because they might allocate memory, which triggers a system call and risks an audio glitch (a "priority inversion").

Your implementation uses Atomics, which is the secret sauce for lock-free concurrency. Let’s break down the "how" and "why" of this structure to wrap up the Data Structures section before hitting Algorithms.

The Anatomy of the Audio Ring Buffer

A ring buffer (or circular buffer) treats a fixed-size array as if it were connected end-to-end. When the writeIndex reaches the end of the array, it wraps back to the beginning using the modulo operator (%).

Why std::atomic?

In a multi-threaded synth, the Audio Thread (Producer) and the GUI Thread (Consumer) are running simultaneously. If we used a regular size_t, one thread might see a partially updated value, leading to a crash or "garbage" audio data. std::atomic ensures that the index update is "atomic" (all-or-nothing) and visible across different CPU cores.

Memory Barriers (Acquire/Release)

You’ll notice std::memory_order_release and std::memory_order_acquire in the code. These aren’t just for show; they are Memory Barriers:

  • Release: Tells the CPU: "Make sure all my data writes (the audio samples) are finished before you update the index."

  • Acquire: Tells the CPU: "Before I read the index, make sure I have the latest data associated with it."