C++ - Why is this implementation of fibonacci memoization using map so slow?

Question

I am trying to implement a fibonacci function in c++ using memoization. My implementation works but is extremely slow. Why is my implementation so slow? I've seen a similar implementations in javascript using an object for memoization and they were blazing fast. Is it because I used the map data structure?

#include <iostream>
#include <map>

unsigned int fib(unsigned short n, std::map<unsigned short, unsigned int> memo = {});

int main(void)
{
    for (unsigned short i = 0; i <= 50; i++)
    {
        std::cout << i << " " << fib(i) << std::endl;
    }
};

unsigned int fib(unsigned short n, std::map<unsigned short, unsigned int> memo)
{
    if (memo.find(n) != memo.end())
    {
        return memo.find(n)->second;
    }
    if (n <= 2)
    {
        return 1;
    }

    memo.insert(
        std::pair<unsigned short, unsigned int>(
            n, fib(n - 1, memo) + fib(n - 2, memo)));

    return memo.find(n)->second;
}

Answer 1

, std::map<unsigned short, unsigned int> memo)

that is a copy of a map.

You are copying your memoization map every call, then forgetting anything you added to it.

unsigned int fib(unsigned short n, std::map<unsigned short, unsigned int>* memo = nullptr);

unsigned int fib(unsigned short n, std::map<unsigned short, unsigned int>* pmemo)
{
  std::map<unsigned short, unsigned int> local;
  auto& memo = pmemo?*pmemo:local;

then pass &memo to the recursive call of fib.

This uses up a touch of extra stack space on each recursive call, but only worth worrying about if you are doing 100,000+ calls.

unsigned int fib(unsigned short n)
{
  std::map<unsigned short, unsigned int> memo = {
    {0u,0u},
    {1u,1u},
    {2u,1u},
  };
  std::vector<unsigned short> todo = {n};
  while (!todo.empty()) {
    // solved?
    if (memo.find(todo.back()) != memo.end())
    {
      todo.pop_back();
      continue;
    }

    unsigned short a = todo.back()-1;
    unsigned short b = todo.back()-2;
    auto ita = memo.find(a);
    auto itb = memo.find(b);

    // solved?
    if (ita != memo.end() && itb !=  memo.end())
    {
       memo.insert( {todo.back(), ita->second+itb->second} );
       todo.pop_back();
       continue;
    }
    todo.push_back(a);
    todo.push_back(b); // could skip this actually
  }
  return memo.find(n)->second;
}

this is an example of manually maintaining the "call stack" of things todo instead of using recursive calls.