CODEWITHSUNDEEP
c++heap-memory
MathuSum Mut
MathuSum Mut

Reputation: 2825

Emulate method call on heap in C++?

Although heap memory is allocated slower than the thread call stack, it is considerably larger, allowing room for a much larger number of operations (such as massively-recursive method calls) to be performed. Although the stack can be resized, the values allowed are still comparatively minuscule (a few MBs available) relative to the heap (more than 1 GB available).

Out of curiosity, in C++ (as an example), is it possible to emulate calling a method by using the heap instead of the thread call stack?

Upvotes: 2

Views: 181

Answers (1)

Richard Hodges
Richard Hodges

Reputation: 69922

Here's a (contrived and probably overcomplicated) implementation of factorial that uses only the heap:

#include <iostream>
#include <vector>
#include <memory>
#include <numeric>
#include <typeinfo>

struct factorial
{
    struct call_concept
    {
        virtual int operator()() const = 0;
        virtual std::unique_ptr<call_concept> generate_next() const = 0;
        virtual ~call_concept() = default;
    };

    static std::unique_ptr<call_concept> generate_term(int i);

    struct terminator : call_concept
    {
        int operator()() const override { return 1; }
        std::unique_ptr<call_concept> generate_next() const override { return nullptr; }
    };

    struct fact_term : call_concept
    {
        fact_term(int i) : _i(i) {};
        int operator()() const override { return _i; }
        std::unique_ptr<call_concept> generate_next() const override {
            return generate_term(_i - 1);
        }
        int _i;
    };


    struct call
    {
        call(std::unique_ptr<call_concept> pc) : _impl(std::move(pc)) {}

        int operator()() const {
            return _impl->operator()();
        }

        int operator*(const call& r) const {
            return (*this)() * r();
        }

        std::unique_ptr<call_concept> _impl;
    };

    friend int operator*(int i, const call& r) {
        return i * r();
    }



    int operator()(int i) {

        auto pt = generate_term(i);
        std::vector<call> stack;

        while (pt) {
            auto next_term = pt->generate_next();
            stack.emplace_back(std::move(pt));
            pt = std::move(next_term);
        }

        return std::accumulate(std::begin(stack), end(stack), 1, std::multiplies<>());
    }
};

auto factorial::generate_term(int i) -> std::unique_ptr<call_concept>
{
    if (i > 1) {
        return std::make_unique<fact_term>(i);
    }
    else {
        return std::make_unique<terminator>();
    }
}

int main()
{
    auto i = factorial()(10);
    std::cout << i << std::endl;

    return 0;
}

expected results:

3628800

Upvotes: 1

Related Questions