Разминка мозгов: свой массив на 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); }