如何遍歷矢量中的所有子矢量？

可以說我有一堂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) 
    { 
    } 
}

來源

2013-05-22 Bullsfan127

如果Foo有一個Foos向量，那麼由於那裏的遞歸性質，你會得到一個堆棧溢出。你確定它不是Bar的矢量嗎？ –

@ChristopherBales是正確的，這個DataStructure實際上實現了一個Tree ... – Exceptyon

發佈的代碼是非法的，並且不能用g ++和通常的選項（包括'-D_GLIBCXX_CONCEPT_CHECKS -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC'進行編譯，這會變成很多未定義的行爲轉化爲硬錯誤）。 –

使用遞歸：

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 
     } 
    } 
}

來源

2013-05-22 15:04:16 Exceptyon

-1：聰明，但遞歸很少在生產級代碼中佔有一席之地。 –

@JohnDibling完全取決於要求。實際上，這通常是一種很好的（生產級別）解決方案。 – leemes

如果您的評論是在BFS和DFS訂單中不訪問這些點。由於遞歸的性質，兩者都是DFS。遞歸*是* DFS。你的代碼中的第二點只是*訪問子節點之後，也稱爲「回溯」。 BFS通常使用隊列而不是堆棧（在使用遞歸實現時隱式使用）。 – leemes

使用隊列：

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(); 
}

來源

2013-05-22 15:23:04 andre

遞歸解決方案更簡單。 –

@JamesKanze遞歸通常會提供更簡單的解決方案，但如果您沒有堆棧空間，則總會有程序崩潰的風險。 – andre

如果你沒有必要的堆，那麼程序崩潰會有風險。如果發生程序錯誤，程序崩潰的風險很大，如果您選擇的解決方案更復雜，則更有可能發生程序錯誤。 –

你Foo對象形成樹形數據結構。您可以表示從根到某個節點的任何路徑，作爲std::stack<Foo*>以跟蹤您在樹中的位置。使用這個想法和深度優先搜索，您可以在不使用遞歸的情況下訪問所有Foo對象。

來源

2013-05-22 15:37:30

如何遍歷矢量中的所有子矢量？

回答

相關問題