I have a list: std::list<MyType*>*

MyType is an abstract class and I want to process every list item which is meets the condition, but the list can contains elements which are also type of std::list and I want to process them as well. It can has multiple depths.

I prefer to process it in iterative way, but recursive solutions is also good. Unfortunately I do not know how should I do it yet.

For example a list looks like this:

Root std::list elements:
    Type_A -> int
    Type_B -> std::list
        Type_C -> int
        Type_B -> std::list
            Type_A -> int
            Type_C -> int
        Type_A -> int
        Type_A -> int
        Type_D -> std::list
            Type_A -> int
            Type_A -> int
        Type_A -> int

As you can see Type_A is a scalar type, no problem. Type_B is also a list, I have to process Type_B elements. Type_B also can have std::list items, I have to process them as well, etc.

Code Example:

void MyFunc(std::list<MyType*>* &statements)
{
    std::list<MyType*>::iterator it;
    for (it = statements->begin(); it != statements->end();   it)
    {
        if ((*it)->GetType() == _expectedType) // this type also has a list
        {
            std::list<MyType*>* statementList = dynamic_cast<ExpectedType*>(*it)->GetStatementList();
            std::list<Statement*>::iterator it2 = statementList->begin();
            // do some iterative or recursive process
    }
}

CodePudding user response：

I guess you could use polymorphism and let each node in your tree process itself, something like this:

class MyType
{
  virtual void visit(Environment& env) const = 0;
};

class MyListType : public MyType
{
  std::list<std::unique_ptr<MyType>> _elements;
  void visit(Environment& env) const  override
  {
    for (const auto& node : _elements)
      node->visit(env);
  }
};

class MyLeafType : public MyType
{
  void visit(Environment& env) const  override
  {
    // whatever
  }
};

CodePudding user response：

You can use the visitor pattern

class Type_A;
class Type_B;
class Type_C;
class Type_D;

struct MyType_Visitor {
    virtual void visit(Type_A & a) = 0;
    virtual void visit(Type_B & b) = 0;
    virtual void visit(Type_C & c) = 0;
    virtual void visit(Type_D & d) = 0;
};

class MyType {
public:
    virtual ~MyType() = default;
    virtual void accept(MyType_Visitor & visitor) = 0;
    // existing members
}

class Type_A : public MyType {
public:
    void accept(MyType_Visitor & visitor) override {
        visitor.visit(*this); // calls void visit(Type_A & a)
    }
    // existing members
};

class Type_B : public MyType {
    std::list<MyType *> children;
public:
    void accept(MyType_Visitor & visitor) override {
        visitor.visit(*this); // calls void visit(Type_B & b)
        for (MyType * child : children) {
            child->accept(visitor); // also visit all the children
        }
    }
    // existing members
};

class Type_C : public MyType {
public:
    void accept(MyType_Visitor & visitor) override {
        visitor.visit(*this); // calls void visit(Type_C & c)
    }
    // existing members
};

class Type_D : public MyType {
    std::list<MyType *> other_things;
public:
    void accept(MyType_Visitor & visitor) override {
        visitor.visit(*this); // calls void visit(Type_D & d)
        for (MyType * thing : other_things) {
            thing->accept(visitor); // also visit all the children
        }
    }
    // existing members
};

This then allows you to define different behaviours for different situations, e.g.

class PrintVisitor : public MyType_Visitor {
    void visit(Type_A & a) override {
        std::cout << "Type_A -> int" << std::endl;
    }
    void visit(Type_B & b) override {
        std::cout << "Type_B -> std::list" << std::endl;
    }
    void visit(Type_C & c) override {
        std::cout << "Type_C -> int" << std::endl;
    }
    void visit(Type_D & d) override {
        std::cout << "Type_D -> std::list" << std::endl;
    }
}

class MeetsConditionVisitor : public MyType_Visitor {
    void visit(Type_A &) override { /* only care about B */ }
    void visit(Type_B & b) override {
        if (/* b specific something */) {
           // stuff
        }
    }
    void visit(Type_C &) override { /* only care about B */ }
    void visit(Type_D &) override { /* only care about B */ }
}

CodePudding user response：

If potentially any of the subclasses can have children, then you could have a virtual member function to expose that.

class MyType {
public:
    virtual ~MyType() = default;
    virtual const std::list<MyType*> & children() {
        // default -> no children
        static const std::list<MyType*> empty;
        return empty;
    }
    // existing members
}

class Type_B : public MyType {
    std::list<MyType*> stuff;
public:
    const std::list<MyType*> & children() override { return stuff; }
}

class Type_D : public MyType {
    std::list<MyType*> things;
public:
    const std::list<MyType*> & children() override { return things; }
}

void MyFunc(const std::list<MyType*> & statements)
{
    for (auto * item : statements)
    {
        // stuff before visiting children
        MyFunc(item->children());
        // other stuff after visiting children
    }
}