Data Structures and Algorithms for Trading

From setup to speed

In Introduction to Algorithmic Trading, you saw the building blocks of a trading application: data comes in, decisions are made, actions are sent out.

In Setting Up Your C++ Development Environment, you prepared the toolchain so your code can run consistently in Debug and Release.

Now we focus on the layer that often decides whether your application feels instant or slow: data structures and algorithms.

For trading systems, the question is not just: Can I store the data?

It is:

• Can I update it quickly?
• Can I query it quickly?
• Can I avoid unnecessary allocations?
• Can I reason about worst-case behavior?

This lesson keeps us at the foundation level. In the next lesson, Market Data Acquisition, you will connect these structures to real incoming data.

Big-O is a starting point

In trading, performance has two sides:

1. Algorithmic complexity — how work grows as data grows.
2. Real machine behavior — memory layout, cache friendliness, allocations, and branch predictability.

A theoretically nice structure can still be slow if it jumps around memory too much.

Common operations in trading code

Operation Example Desired feel Append latest price Store new tick price Very fast Read recent history Last 100 prices Cache-friendly Lookup instrument state Position for AAPL Near constant time Maintain top candidate Best spread / signal Fast update + query Remove old data Sliding window Predictable

A useful rule

Prefer data structures where your hot path does simple, predictable work.

For an intermediate C++ learner, this means getting comfortable with standard containers first, then understanding when their behavior matters.

Recent prices need efficient storage

A trading algorithm often needs the latest N observations:

• last 50 prices
• last 20 spreads
• last 100 volumes

A std::vector is cache-friendly because elements are stored contiguously. But if you constantly erase from the front, you shift many elements.

A common solution is a ring buffer:

capacity = 5
new prices overwrite the oldest slot

[101.2, 101.4, 101.3, 101.8, 101.6]
                   ^ next write wraps around

This gives fixed-size recent history with predictable updates.

```cpp
#include <iostream>
#include <vector>
#include <iomanip>

class PriceRingBuffer {
public:
    explicit PriceRingBuffer(std::size_t capacity)
        : data_(capacity), capacity_(capacity) {}

    void push(double price) {
        data_[next_] = price;
        next_ = (next_ + 1) % capacity_;
        if (size_ < capacity_) ++size_;
    }

    void printNewestOrder() const {
        std::cout << "Recent prices: ";
        for (std::size_t i = 0; i < size_; ++i) {
            std::size_t index = (next_ + capacity_ - size_ + i) % capacity_;
            std::cout << std::fixed << std::setprecision(2) << data_[index] << " ";
        }
        std::cout << "\n";
    }

private:
    std::vector<double> data_;
    std::size_t capacity_ = 0;
    std::size_t size_ = 0;
    std::size_t next_ = 0;
};

int main() {
    PriceRingBuffer prices(5);

    for (double p : {101.20, 101.40, 101.30, 101.80, 101.60, 102.10}) {
        prices.push(p);
        prices.printNewestOrder();
    }

    return 0;
}
```

You need to store the latest 1,000 prices and frequently iterate through them in order. Which container is usually the best starting point for cache-friendly sequential access?

Per-symbol state needs fast access

A trading application usually tracks state per instrument:

• current position
• average entry price
• last seen price
• current risk counters

If your algorithm receives an update for MSFT, you do not want to scan a list of all symbols to find MSFT.

For this, std::unordered_map is often a practical first choice:

• average-case O(1) lookup
• readable interface
• works well for symbol-to-state mapping

Important C++ note: if the set of symbols is known, reserving capacity can reduce rehashing.

```cpp
#include <iostream>
#include <string>
#include <unordered_map>
#include <iomanip>

struct PositionState {
    int quantity = 0;
    double avgPrice = 0.0;
};

void applyFill(PositionState& state, int qty, double price) {
    int newQuantity = state.quantity + qty;

    if (newQuantity == 0) {
        state.quantity = 0;
        state.avgPrice = 0.0;
        return;
    }

    double oldValue = state.quantity * state.avgPrice;
    double fillValue = qty * price;

    state.quantity = newQuantity;
    state.avgPrice = (oldValue + fillValue) / newQuantity;
}

int main() {
    std::unordered_map<std::string, PositionState> positions;
    positions.reserve(10);

    applyFill(positions["AAPL"], 100, 180.50);
    applyFill(positions["AAPL"], 50, 181.20);
    applyFill(positions["MSFT"], 40, 420.10);

    for (const auto& [symbol, state] : positions) {
        std::cout << symbol
                  << " qty=" << state.quantity
                  << " avg=" << std::fixed << std::setprecision(2) << state.avgPrice
                  << "\n";
    }

    return 0;
}
```

std::unordered_map always guarantees O(1) lookup in the worst case.

Avoid recomputing from scratch

Suppose you need a simple moving average over the last N prices.

A slow approach:

for every new price:
    loop over last N prices
    sum them again

That costs O(N) per update.

A faster approach stores a running sum:

when new price arrives:
    add new price
    remove oldest price if window is full
    average = sum / window_size

Now each update does constant work. This idea appears again and again in trading algorithms: store enough state so you do not repeat unnecessary work.

```cpp
#include <iostream>
#include <queue>
#include <iomanip>

class MovingAverage {
public:
    explicit MovingAverage(std::size_t window) : window_(window) {}

    double update(double price) {
        prices_.push(price);
        sum_ += price;

        if (prices_.size() > window_) {
            sum_ -= prices_.front();
            prices_.pop();
        }

        return sum_ / static_cast<double>(prices_.size());
    }

private:
    std::size_t window_;
    std::queue<double> prices_;
    double sum_ = 0.0;
};

int main() {
    MovingAverage ma(3);

    for (double price : {100.0, 101.0, 102.0, 105.0, 104.0}) {
        double avg = ma.update(price);
        std::cout << "price=" << price
                  << " moving_avg=" << std::fixed << std::setprecision(2) << avg
                  << "\n";
    }

    return 0;
}
```

Using a running sum for a fixed-size moving average makes each update run in ____ time with respect to the window size.

Answer using Big-O notation.

Some tasks need the best item quickly

Trading systems often rank things:

• strongest signal candidate
• highest priority order event
• largest exposure to review
• cheapest venue candidate

When you repeatedly need the current best item, a heap-based structure such as std::priority_queue may be useful.

Key trade-off

A priority queue is excellent for:

• inserting a candidate
• retrieving the current top candidate

But it is not ideal for:

• searching arbitrary elements
• updating an item already inside the heap
• iterating in sorted order

So the structure is powerful, but only when the access pattern matches.

How to think like a trading systems developer

Before writing a container or algorithm, ask:

1. What is the hot path?
   Which operation happens thousands or millions of times?

2. What is the access pattern?
   Append-only, random lookup, sorted traversal, top candidate, sliding window?

3. What is the update pattern?
   Insert, remove, overwrite, aggregate, expire old values?

4. What are the latency risks?
   Allocations, rehashing, front erases, unnecessary copies, repeated scans?

5. Can I reserve or pre-size?
   C++ containers often become more predictable when you reduce dynamic growth.

Practical starter mapping

Need Starting structure Recent fixed history ring buffer / vector-backed buffer Symbol state lookup std::unordered_map Sorted keys std::map or sorted vector depending on update rate Best candidate std::priority_queue FIFO processing std::queue / circular queue

The goal is not to memorize containers. The goal is to match data shape + access pattern + latency expectation.

Which statement best captures the main lesson for building low-latency C++ trading components?