добавление функциональности в полиморфное дерево в C ++

Question

У меня есть полиморфное дерево, и я пытаюсь добавить функциональность, например, сравнивать два узла без использования RTTI, как dynamic_cast. Подход, который я использую, - это шаблон посетителей.

Проблема, с которой я столкнулся, заключается в том, что шаблон посетителя не позволяет мне работать с какими-либо параметрами или получать типы возврата из функций.

Например, если я хочу написать посетителя, который сравнивает два узла

class AbstractDispatch{
    public:
        virtual void visit(NodeFoo &operand) = 0;
        virtual void visit(NodeBar &operand) = 0;
        //...for all types.
};

class CompareVisitor{
    public: 
        void visit(NodeFoo &operand) override;
        //...
};

class SetVisitor{
    public: 
        void visit(NodeFoo &operand) override;
        //...
};

void CompareVisitor::visit(NodeFoo &operand){
    //compare operand to what?
    //get result of comparison how?
}

void SetVisitor::visit(NodeFoo &operand){
    //set operand to what?
}

Моя текущая идея - добавить другие функции и члены в классы посетителей. Это позволило бы мне сделать что-то вроде этого:

Base *object = new NodeFoo();
CompareVisitor compare;
compare.set_parameters(NodeFoo(/* */));
object->accept(compare);
bool result = compare.get_result();

Я мог бы установить параметры посетителя сравнения и обойти дерево, проверяя его на наличие узлов и выполняя другие подобные операции.

Другим решением было бы сохранить информацию о типе узла в узле и выполнить проверку get_type () для безопасного приведения.

dynamic_cast медленно, но если иерархия типа узла предельно проста, может ли она быть быстрее? Есть ли лучшие шаблоны проектирования для выполнения чего-то подобного?

Answer 1

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

class Node{...}
class NodeFoo : public Node {...}
class NodeBar : public Node {...}

class visitor{
  public:
    void visit( const NodeFoo& node ){
      //First node: store relevant comparison information to private variables
      if( foo == nullptr ){
        foo = &node;
      }
      //Other nodes: Compare to the stored data and store comparison result
      else {
        ...
      }
    }
    void visit( const NodeBar& node ){
      ...
    }
    bool result() const{ return result; };
  private:
    bool result = false;
    //variables for comparison, could be this simple but also a variant type
    // or plain Node*
    NodeFoo* foo = nullptr;
    NodeBar* bar = nullptr;
}

Вы могли бы использовать его как

Node node1;
Node node2;
Visitor v;
node1.accept( v );
node2.accept( v );
v.result();

Конечно, это очень простая реализация,Вы можете использовать обычный Node * для хранения первого узла, если предположите, что все посещенные узлы имеют одинаковый тип.Вы также можете использовать тип варианта или сохранить тип в виде строки ... (тип известен по выполненной функции посещения)

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

Answer 2

Это можно сделать с двойным visit (= два виртуальных вызова), если вы разрешите CompareVisitor иметь состояние. Я не думаю, что есть способ обойти это, учитывая API вашего посетителя.

#include <iostream>
#include <string>
#include <vector>
#include <memory>

struct FooNode;
struct BarNode;

struct Visitor
{
    virtual void visit(FooNode&)=0;
    virtual void visit(BarNode&)=0;
};
struct Node{
    virtual void accept(Visitor& v) = 0;
};
struct FooNode: public Node{
    virtual void accept(Visitor& v) override { v.visit(*this);}
    const char* print(){return "FooNode";}    
};
struct BarNode: public Node{
    virtual void accept(Visitor& v) override { v.visit(*this);}    
    const char* print(){return "BarNode";}    

};

using ret_type=std::string;
//Feel free to specialize or overload
//Or create comparator class that allows partial specializations
template<typename Left, typename Right>
ret_type compare(Left &left, Right& right){

    return std::string(left.print()) + "<=>" + right.print() + '\n';
}

//Compares (visited) and (rightNode)
class RightCompareVisitor : public Visitor {
public:
    RightCompareVisitor(Node& right):rightNode(right){}
    void visit(FooNode &left) override
    {
        visitRightNode(left);
    }
    void visit(BarNode &left) override
    {
        visitRightNode(left);
    }
    ret_type getRes() { return std::move(result);}
private:
    template<typename Left>
    void visitRightNode(Left& left){
        struct CompareVisitor: Visitor
        {
            ret_type& result;
            Left& left;

            CompareVisitor(ret_type& result, Left& left):result(result), left(left){}

            void visit(FooNode &right) override final{
                result = compare(left, right);
            }
            void visit(BarNode &right) override final{
                result = compare(left, right);                  
            }        
        };
        CompareVisitor v(result, left);
        rightNode.accept(v);
    }
    ret_type result;
    Node& rightNode;
};

//If you add this then you can always just use 'compare' to compare any two 
//nodes.
template<>
ret_type compare<Node,Node>(Node& left, Node& right){
    RightCompareVisitor rC{right};
        left.accept(rC);
    return rC.getRes();
}

int main()
{

    std::vector<std::unique_ptr<Node>> nodes;
    nodes.emplace_back(std::make_unique<FooNode>());
    nodes.emplace_back(std::make_unique<BarNode>());
    nodes.emplace_back(std::make_unique<FooNode>());

    for(auto&& left : nodes)
        for(auto&& right: nodes)
            std::cout<<compare(*left,*right);
}

Добавьте const s, где вы хотите. Если вы хотите, чтобы RightCompareVisitor использовался повторно, используйте указатели для узлов.

Выход:

FooNode<=>FooNode    
FooNode<=>BarNode    
FooNode<=>FooNode    
BarNode<=>FooNode    
BarNode<=>BarNode    
BarNode<=>FooNode    
FooNode<=>FooNode    
FooNode<=>BarNode    
FooNode<=>FooNode