Data Structures

Sequential containers in C++ store elements in a linear order, where each element is positioned relative to the one before or after it. They’re designed for efficient iteration, fast access, and are typically used when element order matters, such as in time-based data.

The most commonly used sequential containers in the STL are:

• std::vector: dynamic array with contiguous memory
• std::deque: double-ended queue with fast insertions/removals at both ends
• std::array: fixed-size array on the stack
• std::list / std::forward_list: linked lists

In quantitative finance, sequential containers are often at the heart of systems that process tick data, historical time series, price paths, and rolling windows. When processing millions of data points per day, the choice of container directly impacts latency, memory usage, and cache performance.

1. std::vector: The Workhorse

std::vector is a dynamic array container in C++. It’s one of the most performance-critical tools in a quant developer’s toolbox — especially for time-series data, simulation paths, and numerical computations.

🧠 Stack vs Heap: The Memory Model

In C++, memory is managed in two primary regions:

🔸 A std::vector behaves as follows:

• The vector object itself (pointer, size, capacity) lives on the stack.
• The elements it stores live in a dynamically allocated heap buffer.

💡 Consequences:

• You can create a std::vector of size 1 million without stack overflow.
• But heap allocation is slower than stack and can cause fragmentation if misused.
• When passed by value, only the stack-held metadata is copied (until you access elements).

📦 Contiguous Memory Layout

A std::vector stores all its elements in a single, contiguous block of memory on the heap — just like a C-style array.

Why this matters:

• CPU cache efficiency: Memory is prefetched in blocks — sequential access is blazing fast.
• Enables pointer arithmetic, SIMD (Single Instruction Multiple Data), and direct interfacing with C APIs.

💥 For quants: When you’re processing millions of floats/doubles (e.g., price histories, simulation paths), contiguous memory layout can be a 10× performance multiplier vs pointer-chasing containers like std::list.

⏱ Time Complexity

⚠️ When capacity is exhausted, std::vector reallocates, usually doubling its capacity and copying all elements — which invalidates pointers and iterators.

💻 Example: Using std::vector for Rolling Average on Price Time Series

#include <vector>
#include <numeric>  // for std::accumulate

int main() {
    // Simulated price time series (e.g. 1 price per second)
    std::vector<double> prices;

    // Simulate appending tick data
    for (int i = 0; i < 10'000'000; ++i) {
        prices.push_back(100.0 + 0.01 * (i % 100)); // Fake tick data
    }

    // Compute rolling average over the last 5 prices
    size_t window_size = 5;
    std::vector<double> rolling_avg;

    for (size_t i = window_size; i < prices.size(); ++i) {
        double sum = std::accumulate(prices.begin() + i - window_size, prices.begin() + i, 0.0);
        rolling_avg.push_back(sum / window_size);
    }

    // Print the last rolling average
    std::cout << "Last rolling avg: " << rolling_avg.back() << std::endl;

    return 0;
}

🧠 Key Points:

• std::vector<double> stores prices in contiguous heap memory, enabling fast iteration.
• push_back appends elements efficiently until capacity needs to grow.
• Access via prices[i] or iterators is cache-friendly.
• This method is fast but not optimal for rolling computations — a future section will show how std::deque or a circular buffer improves performance here.

2. std::deque: Double-Ended Queue

std::deque stands for “double-ended queue” — a general-purpose container that supports efficient insertion and deletion at both ends. Unlike std::vector, which shines in random access, std::deque is optimized for dynamic FIFO (first-in, first-out) or sliding window patterns.

🧠 Stack vs Heap: Where Does Data Live?

• Like std::vector, the std::deque object (its metadata) lives on the stack.
• The underlying elements are allocated on the heap — but not contiguously.

💡 Consequences:

• You can append or prepend large amounts of data without stack overflow.
• Compared to std::vector, memory access is less cache-efficient due to fragmentation.

📦 Contiguous Memory? No.

Unlike std::vector, which stores all elements in one continuous memory block, std::deque allocates multiple fixed-size blocks (typically 4KB–8KB) and maintains a map (array of pointers) to those blocks.

Why this matters:

• Appending to front/back is fast, since it just adds blocks.
• But access patterns may be less cache-friendly, especially in tight loops.

⏱ Time Complexity

⚠️ Internally more complex: uses a segmented memory model (think: mini-arrays linked together via pointer table).

⚙️ What’s Under the Hood?

A simplified mental model:

cppCopierModifierT** block_map;   // array of pointers to blocks
T* blocks[N];    // actual blocks on the heap

• Each block holds a fixed number of elements.
• deque manages which block and offset your index points to.

✅ Strengths

• Fast insertion/removal at both ends (O(1)).
• No expensive shifting like vector.
• Stable references to elements even after growth at ends (unlike vector).

⚠️ Trade-offs

• Not contiguous → worse cache locality than vector.
• Random access is constant time, but slightly slower than vector[i].
• Slightly higher memory overhead due to internal structure (block map + block padding).

📈 Quant Finance Use Cases

• Rolling windows on tick or quote streams (e.g. sliding 1-minute buffer).
• Time-based buffers for short-term volatility, VWAP, or moving averages.
• Event-driven systems where data is both consumed and appended continuously.

Example:

std::deque<double> price_buffer;
// push_front for new tick, pop_back to discard old

💬 Typical Interview Questions

1. “How would you implement a rolling average over a tick stream?”
   • A good answer involves std::deque for its O(1) append/remove at both ends.
2. “Why not use std::vector if you’re appending at the front?”
   • Tests understanding of std::vector‘s O(n) front-insertion cost vs deque‘s O(1).
3. “Explain the memory layout of deque vs vector, and how it affects performance.”
   • Looks for awareness of cache implications.

💻 Code Example: Rolling Average with std::deque

cppCopierModifier#include <iostream>
#include <deque>
#include <numeric>

int main() {
    std::deque<double> price_window;
    size_t window_size = 5;

    for (int i = 0; i < 10; ++i) {
        double new_price = 100.0 + i;
        price_window.push_back(new_price);

        // Keep deque size fixed
        if (price_window.size() > window_size) {
            price_window.pop_front();  // Efficient O(1)
        }

        if (price_window.size() == window_size) {
            double avg = std::accumulate(price_window.begin(), price_window.end(), 0.0) / window_size;
            std::cout << "Rolling average: " << avg << std::endl;
        }
    }

    return 0;
}

🧠 Summary: deque vs vector

3. std::array: Fixed-Size Array

std::array is a stack-allocated, fixed-size container introduced in C++11. It wraps a C-style array with a safer, STL-compatible interface while retaining zero overhead. In quant finance, it’s ideal when you know the size at compile time and want maximum performance and predictability.

🧠 Stack vs Heap: Where Does Data Live?

• std::array stores all of its data on the stack — no dynamic memory allocation.
• The container itself is the data, unlike std::vector or std::deque, which hold pointers to heap-allocated buffers.

💡 Consequences:

• Blazing fast allocation/deallocation — no malloc, no heap overhead.
• Extremely cache-friendly — everything is packed in a single memory block.
• But: limited size (you can’t store millions of elements safely).

📦 Contiguous Memory? Yes.

std::array maintains a true contiguous layout, just like a C array. This enables:

• Fast random access via arr[i]
• Compatibility with C APIs
• SIMD/vectorization-friendly memory layout

⏱ Time Complexity

⚙️ What’s Under the Hood?

Conceptually:

cppCopierModifiertemplate<typename T, std::size_t N>
struct array {
    T elems[N];  // Inline data — lives on the stack
};

• No dynamic allocation.
• No capacity concept — just a fixed-size C array with better syntax and STL methods.

✅ Strengths

• Zero runtime overhead — allocation is just moving the stack pointer.
• Extremely fast access and iteration.
• Safer than raw arrays — bounds-safe with .at() and STL integration (.begin(), .end(), etc.).

⚠️ Trade-offs

• Fixed size — can’t grow or shrink at runtime.
• Risk of stack overflow if size is too large.
• Pass-by-value is expensive (copies all elements) unless using references.

📈 Quant Finance Use Cases

• Grids for finite difference/PDE solvers: std::array<double, N>
• Precomputed factors (e.g., Greeks at fixed deltas)
• Fixed-size historical feature vectors for ML signals
• Small matrices or stat buffers in embedded systems or hot loops

// Greeks for delta hedging
std::array<double, 5> greeks = { 0.45, 0.01, -0.02, 0.005, 0.0001 };

💬 Typical Interview Questions

1. “What’s the difference between std::array, std::vector, and C-style arrays?”
   • Tests understanding of memory layout, allocation, and safety.
2. “When would you prefer std::array over std::vector?”
   • Looking for “when size is known at compile time and performance matters.”
3. “What’s the risk of using large std::arrays?”
   • Looking for awareness of stack overflow and memory constraints.

💻 Code Example: Option Grid for PDE Solver

int main() {
    constexpr std::size_t N = 5; // e.g. 5 grid points in a discretized asset space
    std::array<double, N> option_values = {100.0, 101.5, 102.8, 104.2, 105.0};

    // Simple finite-difference operation: delta = (V[i+1] - V[i]) / dx
    double dx = 1.0;
    for (std::size_t i = 0; i < N - 1; ++i) {
        double delta = (option_values[i + 1] - option_values[i]) / dx;
        std::cout << "delta[" << i << "] = " << delta << std::endl;
    }

    return 0;
}

🧠 Summary: std::array vs vector/deque

4. std::list / std::forward_list: Linked Lists

std::list and std::forward_list are the C++ STL’s doubly- and singly-linked list implementations. While rarely used in performance-critical quant finance applications, they are still part of the container toolkit and may shine in niche situations involving frequent insertions/removals in the middle of large datasets — but not for numeric data or tight loops.

🧠 Stack vs Heap: Where Does Data Live?

• Both containers are heap-based: each element is dynamically allocated as a separate node.
• The container object itself (head pointer, size metadata) is on the stack.
• But the actual elements — and their pointers — are spread across the heap.

💡 Consequences:

• Extremely poor cache locality.
• Each insertion allocates heap memory → slow.
• Ideal for predictable insertion/removal patterns, not for numerical processing.

📦 Contiguous Memory? Definitely Not.

Each element is a node containing:

• The value
• One (std::forward_list) or two (std::list) pointers

So memory looks like this:

[Node1] → [Node2] → [Node3] ...   (or doubly linked)

💣 You lose any benefit of prefetching or SIMD. Iteration causes pointer chasing, leading to cache misses and latency spikes.

⏱ Time Complexity

⚙️ What’s Under the Hood?

Each node contains:

• value
• next pointer (and prev for std::list)

So conceptually:

Node {
    T value;
    Node* next; // and prev, if doubly linked
};

• std::list uses two pointers per node.
• std::forward_list is lighter — just one pointer — but can’t iterate backward.

✅ Strengths

• Efficient insertions/removals anywhere — no element shifting like vector.
• Iterator-stable: elements don’t move in memory.
• Predictable performance for queue-like workloads with frequent mid-stream changes.

⚠️ Trade-offs

• Terrible cache locality — each node is scattered.
• No random access — everything is via iteration.
• Heavy memory overhead: ~2×–3× the size of your data.
• Heap allocation per node = slow.

📈 Quant Finance Use Cases (Rare/Niche)

• Managing a priority-sorted list of limit orders (insert/delete in mid-stream).
• Event systems where exact insertion position matters.
• Custom allocators or object pools in performance-tuned engines.

Usually, in real systems, this is replaced by:

• std::deque for queues
• std::vector for indexed data
• Custom intrusive lists if performance really matters

💬 Typical Interview Questions

1. “What’s the trade-off between std::vector and std::list?”
   • Looking for cache locality vs insert/delete performance.
2. “How would you store a stream of operations that require arbitrary insert/delete?”
   • Tests knowledge of when to use linked lists despite their cost.
3. “Why is std::list usually a bad idea for numeric workloads?”
   • Looking for insight into heap fragmentation and CPU cache behavior.

💻 Code Example: Linked List of Events

#include <iostream>
#include <list>

struct TradeEvent {
    double price;
    double quantity;
};

int main() {
    std::list<TradeEvent> event_log;

    // Simulate inserting trades
    event_log.push_back({100.0, 500});
    event_log.push_back({101.2, 200});
    event_log.push_front({99.5, 300});  // Insert at front

    // Iterate through events
    for (const auto& e : event_log) {
        std::cout << "Price: " << e.price << ", Qty: " << e.quantity << std::endl;
    }

    return 0;
}

🧠 Summary: std::list / std::forward_list

Unless you need fast structural changes mid-stream, these containers are rarely used in quant systems. But it’s important to know when and why they exist.