В Scala есть интересная коллекция — Stream. Контейнер, который представляет собой список, элементы которого вычисляются (и сохраняются после этого) при первом обращении:

The class Stream implements lazy lists where elements are only evaluated when they are needed.

Мне захотелось реализовать нечто подобное на C++.

Цель

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

typedef lazy::list<int> list_type;  list_type fibonacci(int n1, int n2) {      int next = n1 + n2;      std::cout << "fibonacci(" << n1 << ", " << n2 << ") -> " << n1 << std::endl;      return list_type(n1, std::bind(&fibonacci, n2, next)); }  int main()  {      list_type list(fibonacci(0, 1));      auto res3 = std::find_if(list.begin(), list.end(), [](int v){return v > 3;});     std::cout << "first number greater 3 is " << *res3 << std::endl;     std::cout << std::endl;      auto res10 = std::find_if(list.begin(), list.end(), [](int v){return v > 10;});     std::cout << "first number greater 10 is " << *res10 << std::endl;     return 0;  }

fibonacci(0, 1) -> 0 fibonacci(1, 1) -> 1 fibonacci(1, 2) -> 1 fibonacci(2, 3) -> 2 fibonacci(3, 5) -> 3 fibonacci(5, 8) -> 5 first number greater 3 is 5  fibonacci(8, 13) -> 8 fibonacci(13, 21) -> 13 first number greater 10 is 13

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

Ограничения

Предположим, мы хотим выполнить что-то типа:

auto iter = --list.end();

Чтобы получить элемент, предшествующий end, необходимо обойти все элементы, генерируемые функцией, а это бесконечность (для примера выше). Соответственно, итератор по ленивому списку будет однонаправленный — ForwardIterator. Аналогичная ситуация будет и при получении количества элементов в списке, и при удалении последнего элемента (pop_back). Таким образом, этих методов у контейнера не будет.

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

Что же получилось?

Получился список, в который можно добавлять как элементы, так и функторы, генерирующие ленивый список, который в свою очередь может содержать элементы и функторы. Удалять можно либо первый элемент (pop_front), либо все элементы (clear). Вставка элементов осуществляется в начало или конец списка.

Итератор по списку однонаправленный, не позволяющий модифицировать элементы списка.

template< typename T, typename Allocator = std::allocator<T> > class list;

template< typename T, typename Allocator = std::allocator<T> > class list { public:     typedef list<T, Allocator> self_type;     typedef T value_type;     typedef std::function<self_type ()> func_type;     typedef __details_lazy_list::const_iterator<self_type> iterator;     typedef __details_lazy_list::const_iterator<self_type> const_iterator;      friend __details_lazy_list::const_iterator<self_type>;      list();     list(const self_type& that);     list(self_type&& that);      template<typename ... Args>     explicit list(Args&&... args)     {         push_others(std::forward<Args>(args)...);     }      void push_back(const value_type& value);     void push_back(value_type&& value);     void push_back(const func_type& func);     void push_back(func_type&& func);     void push_back(const self_type& that);     void push_back(self_type&& that);      void push_front(const value_type& value);     void push_front(value_type&& value);     void push_front(const func_type& func);     void push_front(func_type&& func);     void push_front(const self_type& that);     void push_front(self_type&& that);      void clear();      bool empty() const;      const_iterator begin() const;     const_iterator end() const;  private:     typedef std::list<value_type, Allocator> container_type;     typedef typename container_type::iterator inner_iterator;     typedef value_type const * funcs_map_key_type;     typedef std::pair<funcs_map_key_type, func_type> funcs_map_value_type;     typedef std::map<funcs_map_key_type, func_type> funcs_map_type;      void forward(const_iterator& iter) const;     void insert(inner_iterator pos, self_type&& that) const;      template<typename Arg, typename ...Args>     void push_others(Arg&& arg, Args&&... args)     {         push_back(std::forward<Arg>(arg));         push_others(std::forward<Args>(args)...);     }      template<typename Arg>     void push_others(Arg&& arg)     {         push_back(std::forward<Arg>(arg));     }      void push_others() {}      mutable container_type _cont;     mutable funcs_map_type _funcs; };

template< typename lazy_list_type > class const_iterator:     public std::iterator<std::input_iterator_tag, typename lazy_list_type::value_type> {     friend lazy_list_type; public:     typedef std::iterator<std::input_iterator_tag, typename lazy_list_type::value_type> base_type;     const_iterator();      typename base_type::reference const operator* () const;     typename base_type::pointer const operator-> () const;      const_iterator& operator++();     const_iterator operator++(int);      bool operator== (const const_iterator& that);     bool operator!= (const const_iterator& that); private:     typedef typename lazy_list_type::inner_iterator inner_iterator;      const_iterator(const lazy_list_type* owner, inner_iterator iter);      const lazy_list_type* _owner;     inner_iterator _iter; };

В конце статьи есть ссылка на репозиторий, где можно взять реализацию с юнит-тестами.

Шаблонные параметры.

T — тип хранимых элементов

Allocator — аллокатор, используемый для размещения элементов.

Внутренние типы

Методы

Методы push_front и push_back принимают функтор, генерирующий элементы, значение хранимого элемента или другой объект типа self_type.

Конструкторы

Как это работает

Внутри используются два стандартных контейнера — std::list для хранения значений и std::map для хранения функторов. Функтор должен возвращать ленивый список, т.е. self_type. Это позволяет, во-первых, рассчитать при необходимости сразу несколько элементов, а во-вторых, не заботиться о случае, когда нет следующего значения — закончилась последовательность, в этом случае можно просто вернуть пустой контейнер.

С добавлением нового элемента все просто — он сразу добавляется во внутренний список.

При добавлении функтора проверяется, есть ли функтор, ассоциированный с элементом, после которого он добавляется (push_back). Если функтора нет, то переданный функтор добавляется в map, а в качестве ключа берется указатель на предыдущий элемент. При добавлении в начало, в пустой контейнер или после элемента, с которым уже есть ассоциированный функтор, просто вызывается метод функтора operator(), и значения из полученного контейнера вставляются в нужное место (в начало или конец), в map добавляются новые функторы, если они есть в возвращенном контейнере.

Можно было бы хранить в списке пару "значение — функтор", но мне кажется, что в процессе работы количество функторов будет существенно меньше количества вычисленных элементов, и затраты памяти в случае хранения пар будут выше.
Опять же, так как предполагаю, что количество функторов не будет очень большим, то нет особой разницы, что использовать — map или unordered_map. Единственное, что при использовании map затраты памяти будут чуть меньше, мне так кажется.

Когда инкрементируется итератор, то проверяется наличие функтора для текущего элемента, если он есть, то возвращаемое им значение добавляется в контейнер, а функтор удаляется. После этого инкрементируется итератор на внутренний список. Если функтора нет или он вернул пустой контейнер, то просто производится переход к следующему элементу во внутреннем списке.

Зачем все это?

К реализации такого списка меня подтолкнула задача Water Pouring, представленная в лекции по языку Scala. Суть в следующем: есть несколько стаканов фиксированного объема, кран, из которого можно наполнить любой стакан (мы можем наполнить стакан только полностью), и раковина, куда можно вылить содержимое стаканов. Наполняя, опустошая и переливая воду из одного стакана в другой, нужно получить заданное количество воды в одном из стаканов. Решение — последовательность действий для получения такого состояния.

Например, есть два стакана объемом 3 и 5 литров, мы хотим получить 4 литра.

Будем рассматривать текущее количество воды в каждом из стаканов как состояние. Из каждого состояния можно получить новый набор возможных состояний, применив одну из возможных операций: наполнить, вылить, перелить. Из каждого набора состояний можно получить новый набор. Чтобы не зациклиться, будем отдельно хранить полученные состояния и отбрасывать их при получении набора новых состояний.

В каждом наборе состояний будем смотреть, есть ли искомое состояние — стакан с искомым уровнем воды.

Нам понадобятся возможные варианты воздействия на текущее состояние. Каждый вариант перемещения воды будет наследовать интерфейс imove:

class imove { public:     virtual state operator()(const state& cur) const = 0;     virtual std::unique_ptr<imove> clone() const = 0;     virtual std::string to_string() const = 0;     virtual ~imove() {} };

Метод to_string нужен только для вывода информации на экран.

Для этой задачи возможны следующие типы перемещения:

class fill: public imove { public:     fill(unsigned glass, unsigned capacity);     state operator()(const state& cur) const override;     std::unique_ptr<imove> clone() const override;     std::string to_string() const override; protected:     const unsigned _glass;     const unsigned _capacity; };  fill::fill(unsigned glass, unsigned capacity) :     _glass(glass),     _capacity(capacity) {}  state fill::operator()(const state& cur) const {     assert(cur.size() > _glass);     state next(cur);     next[_glass] = _capacity;     return next; } std::unique_ptr<imove> fill::clone() const {     return std::unique_ptr<imove>(new fill(_glass, _capacity)); } std::string fill::to_string() const {     return "fill(" + std::to_string(_glass) + ")"; }

class empty: public fill { public:     empty(unsigned glass);     std::unique_ptr<imove> clone() const override;     std::string to_string() const override; };  empty::empty(unsigned glass) :     fill(glass, 0) {}  std::unique_ptr<imove> empty::clone() const {     return std::unique_ptr<imove>(new empty(_glass)); }  std::string empty::to_string() const {     return "empty(" + std::to_string(_glass) + ")"; }

class pour: public imove { public:     pour(unsigned from, unsigned to, unsigned capacity_to);     state operator()(const state& cur) const override;     std::unique_ptr<imove> clone() const override;     std::string to_string() const override; protected:     const unsigned _from;     const unsigned _to;     const unsigned _capacity_to; };  pour::pour(unsigned from, unsigned to, unsigned capacity_to) :     _from(from),     _to(to),     _capacity_to(capacity_to) {}  state pour::operator()(const state& cur) const {     assert((cur.size() > _from) && (cur.size() > _to));     assert(_capacity_to >= cur[_to]);     unsigned amount = std::min(cur[_from], _capacity_to - cur[_to]);     state next(cur);     next[_from] -= amount;     next[_to] += amount;     return next; }  std::unique_ptr<imove> pour::clone() const {     return std::unique_ptr<imove>(new pour(_from, _to, _capacity_to)); }  std::string pour::to_string() const {     return "pour(" + std::to_string(_from) + ", " + std::to_string(_to) + ")"; }

Также нужно хранить информацию о новом состоянии, а именно состояние и набор перемещений, приведших к нему. За это будет отвечать класс path:

class path { public:     path(const state& initial_state);     path(const path& that);      void extend(imove_ptr move);     const state& end_state() const;     std::string to_string() const;     bool empty() const; private:     std::list<imove_ptr> _history;     state _end_state; };

И собственно класс, который использует ленивый список и вышеперечисленные вспомогательные классы для нахождения решения:

typedef std::list<path> paths_list;  class water_pouring { public:     water_pouring(std::initializer_list<unsigned> capacities);      path solve(unsigned target); private:     typedef lazy::list<paths_list> list_of_paths_type;     list_of_paths_type extend(const paths_list& paths);      const std::vector<unsigned> _capacities;     const std::vector<imove_ptr> _posible_moves;     const state _initial;     std::set<state> _explored_states;     list_of_paths_type _paths; };

Класс имеет два публичных метода — конструктор, который принимает емкости стаканов, и метод, возвращающий путь достижения требуемого состояния.

Приватный метод extend используется для генерации элементов ленивого списка.

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

std::vector<imove_ptr> create_moves(const std::vector<unsigned>& capacities) {     std::vector<imove_ptr> moves;     for (size_t i = 0; i < capacities.size(); ++i)     {         moves.emplace_back(new empty(i));         moves.emplace_back(new fill(i, capacities[i]));         for (size_t j = 0; j < capacities.size(); ++j)         {             if (i != j)                 moves.emplace_back(new pour(i, j, capacities[j]));         }     }     return moves; }

Метод water_pouring::extend:

water_pouring::list_of_paths_type water_pouring::extend(const paths_list& paths) {     paths_list next;     for (auto& cur_path: paths)     {         for (auto move: _posible_moves)         {             state next_state = (*move)(cur_path.end_state());              if (_explored_states.find(next_state) == _explored_states.end())             {                 path new_path(cur_path);                 new_path.extend(move);                 next.push_back(new_path);                 _explored_states.insert(next_state);             }         }     }      if (next.empty())         return list_of_paths_type();      return list_of_paths_type(next, std::bind(&water_pouring::extend, this, next)); }

Метод water_pouring::solve:

path water_pouring::solve(unsigned target) {     paths_list::const_iterator solution;     auto it = std::find_if(         _paths.begin(),         _paths.end(),         [target, &solution](const paths_list& paths) -> bool {             solution = std::find_if(                 paths.begin(),                 paths.end(),                 [target](const path& p) -> bool {                     auto it = std::find(                             p.end_state().begin(),                             p.end_state().end(),                             target);                     return it != p.end_state().end();                 });             return solution != paths.end();         });      if (it != _paths.end())         return *solution;      return path(state({0})); }

Собственно, для поиска решения используется функция std::find_if, а в качестве предиката — лямбда функция, просматривающая пути на наличие необходимого состояния. Лямбда захватывает по ссылке solution, чтобы лишний раз не проходиться по списку решений, на которые будет указывать итератор it в случае, если решение было найдено.

В итоге программа выведет следующее решение:

fill(1) pour(1, 0) empty(0) pour(1, 0) fill(1) pour(1, 0) --> (3, 4)

Придумать другую задачу, где мог бы пригодиться "ленивый" список, я не смог. Надеюсь, идея кому-нибудь приглянется.

Ссылки

• Исходный код lazy_list
• Исходный код решения Water Pouring на C++
• Исходный код решения Water Pouring на Scala
• Курс лекций Functional Programming Principles in Scala в рамках которого была расмотрена и задача Water Pouring
• Для юнит тестов использовал фреймворк Catch

ссылка на оригинал статьи https://habrahabr.ru/post/277737/