英文:
Traverse binary tree with unique_ptr child
问题
我有一棵二叉树，需要使用队列进行遍历。但问题在于遍历需要“移动”对象，而我不想这样做。
这是我的例程：
struct bsp_node
{
vec4 Plane;
std::vector<polygon> Polygons;
std::unique_ptr<bsp_node> Front;
std::unique_ptr<bsp_node> Back;
};
uint32_t BSPGetIndexCount(const std::unique_ptr<bsp_node>& Tree)
{
uint32_t Result = 0;
std::queue<std::unique_ptr<bsp_node>&> BspQueue;
BspQueue.push(Tree);
uint32_t VertexIndex = 0;
while(!BspQueue.empty())
{
std::unique_ptr<bsp_node>& Node = BspQueue.front();
for(polygon Poly : Node->Polygons)
{
Result += 3;
}
BspQueue.pop();
if(Tree->Front != nullptr)
{
BspQueue.push(Tree->Front);
}
if(Tree->Back != nullptr)
{
BspQueue.push(Tree->Back);
}
}
return Result;
}
我猜这应该很简单。但无论如何，感谢你的帮助。
英文:
I have some binary tree and I need to traverse it with queue. But the issue is that traversal requires "moving" object which I don't want to do.
Here is my routine:
struct bsp_node
{
vec4 Plane;
std::vector<polygon> Polygons;
std::unique_ptr<bsp_node> Front;
std::unique_ptr<bsp_node> Back;
};
uint32_t BSPGetIndexCount(const std::unique_ptr<bsp_node>& Tree)
{
uint32_t Result = 0;
std::queue<std::unique_ptr<bsp_node>&> BspQueue;
BspQueue.push(Tree);
uint32_t VertexIndex = 0;
while(!BspQueue.empty())
{
std::unique_ptr<bsp_node>& Node = BspQueue.front();
for(polygon Poly : Node->Polygons)
{
Result += 3;
}
BspQueue.pop();
if(Tree->Front != nullptr)
{
BspQueue.push(Tree->Front);
}
if(Tree->Back != nullptr)
{
BspQueue.push(Tree->Back);
}
}
return Result;
}
I guess, it should be trivial. But thanks for the help anyway.
答案1
得分: 2
BspQueue 是一个本地变量，不能超出 Tree 的生存期。因此，你可以在那里使用裸指针。
std::queue<bsp_node*> BspQueue;
BspQueue.push(Tree.get());
// ...
bsp_node* Node = BspQueue.front();
// ...
BspQueue.push(Tree->Front.get());
英文:
BspQueue is a local variable, it cannot outlive Tree. Therefore you can use there raw pointers
std::queue<bsp_node*> BspQueue;
BspQueue.push(Tree.get());
// ...
bsp_nonde* Node = BspQueue.front().get();
// ...
BspQueue.push(Tree->Front.get());
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论