C ++ Недвоичное дерево: получение дерева оставляет коллекцию (вопрос производительности)

Question

У меня есть недвоичные древовидные структуры, такие как:

struct Node
{
    Node*              pa_;
    std::vector<Node*> children_;

    std::vector<Node*> GetLeaves()
};

По листьям дерева я понимаю узлы дерева без дочерних элементов.Метод, который обеспечивает сбор листьев дерева, выглядит следующим образом:

    std::vector<Node*> Node::GetLeaves()
    {
        std::vector<Node*> ret;
        if(!children_.size())
        {
            ret.push_back(this);
        }
        else
        {
            for (auto child : children_)
            {
                auto child_leaves = child->GetLeaves()
                ret.insert( ret.end(),
                            child_leaves.begin(),
                            child_leaves.end() );
            }
        }
        return std::move(ret);
    }

Не скажем, что у всего дерева может быть сотни листьев.

Использование вектора в качестве контейнера для листьев означает, что при вставке в возвращаемую коллекцию происходит много перераспределения памяти.

Вопрос: использование std :: list вместо std :: vector нежелательно?

спасибо заранее

Answer 1

Исключение рекурсии исключит некоторые операции копирования и позволит вам просто создать один список:

std::vector<Node*> Node::GetLeaves()
{
    if (children_.empty())
    {
      return std::vector<Node*>(this, 1);
    }
    std::vector<Node*> ret;
    std::stack<Node*> nodes;
    nodes.push(this);
    while (!nodes.empty())
    {
      Node* parent = nodes.top();
      nodes.pop();
      for (auto node : parent->children_)
      {
        if (node->children_.empty())
        {
          ret.push_back(node);
        }
        else
        {
          nodes.push(node);
        }
      }
    }
    return ret;
}

Если вы хотите изменить порядок обхода, вы можете изменить stack на queue.