Блог

Я заинтересован в использовании range-v3 для построения и запроса линейных структур данных quadtree. Я смог успешно использовать range-v3 для построения линейной структуры данных quadtree, используя существующие представления в библиотеке. Я рад возможности выразить логику запроса в виде адаптера представления, поскольку вы можете выполнять итерации по узлам в quadtree, используя RandomAccessIterator производного диапазона, что удобно помогает отделить поведение запроса от структуры quadtree.

Мой адаптер просмотра имеет единственный аргумент: определяемую пользователем функцию лямбда-предиката, которая используется для оценки узла и определения того, следует ли вводить или выводить. Включение приводит к оценке дочерних узлов, тогда как выход приводит к посещению следующего родственного узла (или, возможно, следующего родственного узла родительского узла) до тех пор, пока либо конечный узел не будет успешно оценен, либо мы «выйдем» через корневой узел. (Вы можете думать об этом как о шаблоне DFS.)

Таким образом, мы можем определить этот диапазон в терминах RandomAccessIterator (из производного диапазона) и Sentinel (в отличие от другого итератора).

Вот некоторый урезанный код, который показывает общую структуру. (Мои извинения, если отсутствуют данные / структура элемента):

 template<typename Rng, typename Fun>
class quadtree_query_view
  : public ranges::view_adaptor<quadtree_query_view<Rng, Fun>, Rng>
{
    friend ranges::range_access;

    using base_iterator_t = ranges::iterator_t<Rng>;

    ranges::semiregular_t<Fun> fun;
    uint tree_depth;

    struct query_termination_adaptor : public ranges::adaptor_base
    {
        query_termination_adaptor() = default;
        query_termination_adaptor(uint tree_depth) : tree_depth(tree_depth) {};

        uint tree_depth;

        uint end(quadtree_query_view constamp;) {
            return tree_depth;
        }
    };

    struct query_adaptor : public ranges::adaptor_base
    {
        query_adaptor() = default;
        query_adaptor(ranges::semiregular_t<Fun> constamp; fun) : fun(fun) {};

        ranges::semiregular_t<Fun> fun;

        bool exited = false;
        uint current_node_depth = 0;

        base_iterator_t begin(quadtree_query_view constamp; rng) {
            return ranges::begin(rng.base());
        }

        // TODO: implement equal?
        // TODO: implement empty?

        auto read(base_iterator_t constamp; it) const 
        {
            return *it; // I'm not concerned about the value returned by this range yet.
        }

        CONCEPT_REQUIRES(ranges::RandomAccessIterator<base_iterator_t>())
        void next(base_iterator_tamp; it ){
            if (fun(*it)) { // Step in
                // Advance base iterator (step in)
                // Increment current_node_depth
            } else {  // Step out
                // Advance base iterator (step out)
                // Set "exited = true" if stepping out past root node.
                // Decrement current_node_depth
            }
        }
    };

public:
    quadtree_query_view() = default;

    quadtree_query_view(Rngamp;amp; rng, uint tree_depth, Fun fun)
      : quadtree_query_view::view_adaptor{std::forward<Rng>(rng)}
      , tree_depth(tree_depth)
      , fun(std::move(fun))
    {}

    query_adaptor begin_adaptor() const {
        return {std::move(fun)};
    }

    query_termination_adaptor end_adaptor() const {
        return {tree_depth};
    }
};
  

Я пытаюсь выяснить последние несколько шагов для завершения этой реализации:

• Мой диапазон не удовлетворяет Range концепции из-за того, что WeaklyEqualityComparable требование не реализовано для моей пары итератор / дозорный. Каков наилучший способ для этого?

• Нужно ли мне реализовывать equal метод-член для query_adaptor ? Чему соответствуют два аргумента итератора?

• Я предполагаю, что мне нужно реализовать empty метод-член для query_adaptor . Это то, куда пойдет логика критериев завершения запроса? На основании документации аргумент segment должен быть типом, связанным с sentinel. Это тот же тип, который возвращается query_termination_adaptor::end() , например, a uint ? Или это должен быть другой тип?

Спасибо за любые идеи, которыми вы можете поделиться. Я действительно в восторге от того, что диапазоны будут включены в C 20!

Ах.

Я смог решить свою проблему с помощью default_sentinel . Поскольку query_adaptor предполагается начинать с корневого узла и выполнять итерации в одном направлении, я могу удалить end_adaptor и query_termination_adaptor все вместе. Мне нужно было только реализовать bool equal(default_sentinel) const { ... } метод для адаптера, где я могу определить, соблюдены ли критерии завершения запроса.

Я все еще не уверен, почему попытка реализовать пользовательский тип sentinel вызвала у меня проблему. Однако он не предоставлял никаких дополнительных функций по сравнению с default_sentinel , кроме владения tree_depth .