Segmented Deque

The standard library provides a std::deque (double-ended queue) which is a dynamic array of arrays.

It supports:

• O(1) push_front() and push_back()
• Efficient, O(1) amortized random access
• Constant-time amortized resizing in both directions

But unlike std::vector, it doesn't reallocate the entire buffer when growing:

• It allocates fixed-size blocks (like 512 or 1024 elements)
• It maintains an array of pointers to those blocks (a block map)
• Growing at the front or back simply adds another block

Why Not Just Use std::vector?

std::vector supports only back-side growth. Growing from the front means full data movement, resulting in O(n) time complexity.

In real-world use (e.g. sliding windows, buffered ingestion, undo stacks), we often want to grow in both directions.

That's where deque shines:

• Fast, scalable insertions/removals at both ends
• No data copying when growing

Your Task

Implement a simplified std::deque-like structure with:

• Fixed-size blocks (e.g. 4 elements each)
• A central array that holds pointers to these blocks
• push_back() and pop_front() operations
• Dynamically allocate new blocks as needed

> You don't need to support arbitrary indexing or full std::deque API --- just build the core concept of segmented growth!

Implement a simplified deque structure using segmented memory blocks.

#include <vector>

template <typename T, std::size_t BLOCK_SIZE = 4>
class SegmentedDeque {
private:

    // Data structures here

public:
    SegmentedDeque() {
        // TODO: Initialize data structures
    }

    void push_back(T val) {
        // TODO: Push to back
    }

    void pop_front() {
        // TODO: Pop from front
    }

    T& front() {
        // TODO: Return front element
    }

    bool empty() const {
        // TODO: Check if empty
    }
};