Что делает этот код C++11 (памятка)?

Question

Я нашел статью, которая содержит этот код:

template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)>
memoize(std::function<ReturnType (Args...)> func)
{
    std::map<std::tuple<Args...>, ReturnType> cache;
    return ([=](Args... args) mutable {
            std::tuple<Args...> t(args...);
            if (cache.find(t) == cache.end())                
                cache[t] = func(args...);
            return cache[t];
    });
}

Можете ли вы объяснить это, пожалуйста? Я не могу понять многие вещи здесь, но самое странное, что кэш локальный, а не статический, но, возможно, я ошибаюсь и...

Answer 1

Это простая реализация напоминания в C++1x.

memoize Функция возвращает закрытие. Возвращаемое значение - это функция, состояние которой отличается от того, что передается через аргументы (в данном случае cache переменная).

[=] бит в анонимной функции указывает, что возвращаемая функция должна взять копию всех локальных переменных. cache переменная не является статической, потому что она предназначена для совместного использования через вызовы возвращаемой функции.

Таким образом, каждый вызов memoize вернет другую функцию со своей cache, Последующие вызовы к определенному закрытию возвращаются memoize будет вставлять / извлекать значения из этого замыкания cache,

Вы можете думать об этом как о чем-то, эквивалентном более старой версии ООП:

template <typename ReturnType, typename... Args>
class Memoize
{
    std::map<std::tuple<Args...>, ReturnType> cache;
public:
    ReturnType operator() (Args... args)
    {
        std::tuple<Args...> t(args...);
        if (cache.find(t) == cache.end())                
            cache[t] = func(args...);
        return cache[t];
    }
};

Answer 2

Кеш встроен в саму лямбду и локальный для нее.

Поэтому, если вы создадите две лямбды, у каждой будет свой кеш.

Это отличный способ реализовать простой кэш, так как таким образом используемая память очищается, как только лямбда выходит из области видимости, и у вас нет взрыва памяти.

Answer 3

"Этот простой фрагмент кода" также может запоминать рекурсивные функции, при условии, что он вызывается должным образом. Здесь я приведу полный пример:

#include <functional>
#include <iostream>
#include <tuple>
#include <map>

template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)> memoize(std::function<ReturnType (Args...)> func) {
  std::map<std::tuple<Args...>, ReturnType> cache;
  return ([=](Args... args) mutable {
          std::tuple<Args...> t(args...);
          if (cache.find(t) == cache.end())
             cache[t] = func(args...);
          return cache[t];
  });
}

std::function<int (int)> f;
int fib(int n) {
  if  (n < 2) return n;
  return f(n-1) + f(n-2);
}

std::function<int (int, int)> b;
int binomial(int n, int k) {
  if (k == 0 || n == k) return 1;
  return b(n-1, k) + b(n-1, k-1);
}

int main(void) {
  f = memoize(std::function<int (int)>(fib));
  std::cout << f(20) << std::endl;
  b = memoize(std::function<int (int, int)>(binomial));
  std::cout << b(34,15) << std::endl;
}

Answer 4

Чтобы процитировать из блога, где вы нашли это, чуть ниже кода:

... знак равенства [=] означает "захватить локальные переменные в окружающей области видимости по значению", что необходимо, потому что мы возвращаем лямбда-функцию, а локальная переменная исчезнет в этот момент.

Так, cache копируется в возвращаемый объект функции, как если бы он был членом.

(Обратите внимание, что этот простой фрагмент кода не запомнит рекурсивную функцию. Реализация комбинатора с фиксированной запятой в C++0x оставлена ​​читателю в качестве упражнения.)

Answer 5

Добро пожаловать в удивительный мир лексического обзора. Его можно использовать для создания целых типов с открытыми и закрытыми членами. На функциональных языках это часто единственный способ сделать это.

Я предлагаю вам прочитать http://mark-story.com/posts/view/picking-up-javascript-closures-and-lexical-scoping, которая посвящена Javascript, но C++0x добавляет те же понятия и (почти тоже самое) поведение на C++.