Разминка мозгов: свой массив на c++ без malloc

Пришла мне в голову интересная задачка: реализовать свой массив на c++.

Массивы — это одна из базовых структур, трудно себе представить сколько-нибудь сложную программу без них. Но что если попробовать реализовать массив самому? В голову сразу приходит список: будем в каждом элементе массива хранить указатель на следующий и хранить эти элементы в динамически выделяемой памяти на куче.

Слишком просто. Давайте обойдемся без кучи. Никаких malloc и new. Можно ли тогда сделать массив?

На одних глобальных переменных мы далеко не уедем. Для того чтобы реализовать идею со списком, нам все-таки нужно выделять память динамически, и если знать, как работают внутренности C на низком уровне, то решение становится понятным.

Где происходит динамическое выделение памяти кроме кучи? На стеке вызовов. Каждая вызванная функция хранит там свои локальные переменные. Вызовем функцию рекурсивно и много выделенного место на стеке. Правда, оно будет размазано по разным вызовам, но можно связать все вместе указателями, которым плевать на государственные границы структуру стека. Заметим, что все действия с массивом (списком) нужно произвести внутри рекурсивного вызова, пока стек не свернулся.

Давайте реализуем эту идею, добавив немного ООП и другого сахара, чтобы массив вел себя, как обычный. В качестве бонуса напишем сортировку пузырьком.

Gist

#include <iostream>

struct Array {
    int val;
    Array* previous;

    Array(int val, Array* previous) : val(val), previous(previous) {}

    int& operator[](size_t index) {
        if (index == 0) {
            return val;
        }
        return (*previous)[index - 1];
    }
};

void generator(size_t n, void(*payload)(Array), Array* previous = 0) {
    Array element(0, previous);
    if (n == 1) {
        payload(element);
    } else {
        generator(n - 1, payload, &element);
    }
}

size_t N;

void test(Array array) {
    for (size_t i = 0; i < N; ++i) {
        std::cin >> array[i];
    }
    for(size_t i = 0 ; i < N - 1; ++i) { 
        for(size_t j = 0 ; j < N - i - 1 ; ++j) {  
            if(array[j] > array[j+1]) {           
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp; 
            }
        }
    }
    for (size_t i = 0; i < N; ++i) {
        std::cout << array[i] << ' ';
    }
}

int main() {
    std::cin >> N;
    generator(N, test);
}