Ленивый список в C++


    В 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 — аллокатор, используемый для размещения элементов.

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


    Тип Описание
    value_type T
    self_type собственный тип
    func_type тип функтора, используемого для генерации элемента. Функтор возвращает объект self_type.
    iterator константный forward итератор
    const_iterator константный forward итератор

    Методы


    Метод Описание
    push_front вставка в начало
    push_back вставка в конец
    empty проверка, является ли контейнер пустым
    clear удалить все элементы
    pop_front удалить первый элемент

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

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


    Сигнатура Описание
    list(); Создает пустой контейнер
    template<typename ... Args> explicit list(Args&&... args) Cоздает контейнер и помещает в него переданные элементы.
    Могут быть переданы значения следующих типов:
    value_type
    func_type
    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 нужен только для вывода информации на экран.

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

    Наполнить стакан - fill
    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) + ")";
    }


    Вылить воду из стакана - empty
    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) + ")";
    }


    Перелить из одного стакана в другой - pour
    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 используется для генерации элементов ленивого списка.

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

    Для получения возможных перемещений используется функция create_moves
    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)

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

    Ссылки


    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 9

      +6
      Хорошая идея и реализация. Ещё бы это подружить со стремлением С++ к диапазонам https://ericniebler.github.io/std/wg21/D4128.html
      То есть ваш список это же перемешанные в кучу данные и ленивые генераторы. Их можно более менее вписать в ленивые диапазоны, которые не владеют данными, если отделить хранение в обычный std::list/vector/set/… .
        +3
        Спасибо, за хорошую оценку и идею относительно диапазонов.

        То есть ваш список это же перемешанные в кучу данные и ленивые генераторы.

        Да, можно и так сказать. То, что я написал можно переписать как адаптор к некоторой коллекции. Я посмотрю, что из себя представляют диапазоны. Возможно, получится развить идею.
    • UFO just landed and posted this here
        +3
        А вот, кстати, рискую так же отхватить, но… стойте!..

        Соглашусь с тем, что С++ становится костылём, если пытаться копировать в нём чисто функциональные фишки. На мой взгляд, это так же, как писать игры на lisp — можно и даже полезно как языковое упражнение… но язык для этого не предназначен и для реальных задач лучше использовать технологии, привычно играющие в соответствующей предметной области (та же скала, например)… Ну, или нужно приводить весьма веские аргументы (кроме "просто прикольно") для обоснования использования конкретного языка в конкретном множестве задач.

        … всё, закончил. Теперь можете бить.

        П.С.: Кстати, сама статья прикольная и интерфейс класса вышел изящный. Автор молодец — но с учётом сказанного выше.
          +1
          Да не за что вас бить-то. Функциональная парадигма поддерживается частично в С++, но она не основная и не единственная, поэтому логично что он проиграет чисто функциональному языку в изяществе кода.
        0
        boost::function_input_iterator ?
          0
          boost::function_input_iterator не контейнер, а ленивый список — контейнер. Т.е. вычисленные значения остаются в нем и к ним можно обращаться без повторного вычисления. А так идеи похожи.

        Only users with full accounts can post comments. Log in, please.