Strange performance observed with memoized function

I was toying around with something that uses Euclid's algorithm to computed the GCD of two numbers. I implemented the standard one-liner as usual, and it worked fine. It's used in a algorithm that computes a series and calls gcd() several times per element as n gets larger. I decided to see if I could do better by memoizing, so here is what I tried:

size_t const gcd(size_t const a, size_t const b) {
  return b == 0 ? a : gcd(b, a % b);
}

struct memoized_gcd : private std::unordered_map<unsigned long long, size_t> {
  size_t const operator()(size_t const a, size_t const b) {
    unsigned long long const key = (static_cast<unsigned long long>(a) << 32) | b;
    if (find(key) == end()) (*this)[key] = b == 0 ? a : (*this)(b, a % b);
    return (*this)[key];
  }
};

//std::function<size_t (size_t, size_t)> gcd_impl = gcd<size_t,size_t>;
std::function<size_t (size_t, size_t)> gcd_impl = memoized_gcd();

I call the chosen function through the std::function instance later. Interestingly, when for example n = 10,000, the calculation runs in 8 sec on this computer, and with the memoized version it's close to a minute, everything else being equal.

Have I missed something obvious? I am using key as an expedient so that I don't need to specialize std::hash for the hash map. The only things I can think of are maybe that the memoized version doesn't get the TCO and gcd() does, or that calling through the std::function is slow for the functor (even though I use it for both), or perhaps that I'm retarded. Gurus, show me the way.

Notes

I've tried this on win32 and win64 with g++ 4.7.0 and linux x86 with g++ 4.6.1 and 4.7.1.

I also tried a version with a std::map<std::pair<size_t, size_t>, size_t> that had comparable performance to the unmemoized version.