c++ - 如何遍历向量中的所有子向量？

Question

可以说我有一堂Foo。它包含一个 Foo 类型的向量。如何编写一个循环来迭代 foo 中的向量并不断迭代子向量，直到我们达到向量中的一个为空的级别

class Foo
{
  Foo();
  std::vector<Foo> foos;
}

我可以这样做来迭代它，但是如何递归地迭代原始向量内的 foo 对象中的向量，直到达到向量为空的级别？

Foo f;
if( !f->foos.empty() )
{

   std::vector<Foo>::const_iterator itr;

   for ( itr = f.foos.begin(); itr!=f.foos.end(); ++itr )
   {
   }
}

Answer 1

使用递归：

class Foo
{
    Foo();
    std::vector<Foo> foos;

    void iterate()
    {
        std::vector<Foo>::const_iterator itr;

        for ( itr = foos.begin(); itr!=foos.end(); ++itr )
        {
            // do stuff  breadth-first
            (*itr).iterate();
            // do stuff  depth-first
        }
    }
}

Answer 2

使用队列：

std::deque<Foo> q;
q.push_back(f);
while (!q.empty()) {
    Foo curr = q.back();

    typedef std::vector<Foo>::iterator iter;
    iter end = curr.foos.end();
    for(iter it = curr.foos.begin(); it != end; ++it) {
        if(!it->empty()) {
            q.push_back(*it);
            continue;
        }
        // do stuff with *it
    }

    q.pop_back();
}

Answer 3

您的Foo对象形成树形数据结构。您可以表示从根到某个节点的任何路径，std::stack<Foo*>以跟踪您在树中的位置。使用这个想法和深度优先搜索，您可以在Foo不使用递归的情况下进行访问所有对象的操作。