我有一棵树，其节点存储 -1 或非负整数，即顶点的名称。每个顶点在树中最多出现一次。以下函数是我的代码中的瓶颈：
版本 A：
void node_vertex_members(node *A, vector<int> *vertexList){
if(A->contents != -1){
vertexList->push_back(A->contents);
}
else{
for(int i=0;i<A->children.size();i++){
node_vertex_members(A->children[i],vertexList);
}
}
}
版本 B：
void node_vertex_members(node *A, vector<int> *vertexList){
stack<node*> q;
q.push(A);
while(!q.empty()){
int x = q.top()->contents;
if(x != -1){
vertexList->push_back(x);
q.pop();
}
else{
node *temp = q.top();
q.pop();
for(int i=temp->children.size()-1; i>=0; --i){
q.push(temp->children[i]);
}
}
}
}
出于某种原因，版本 B 的运行时间明显长于版本 A，这是我没有预料到的。编译器可能在做什么比我的代码聪明得多？换句话说，我在做什么这么低效？让我感到困惑的是，如果我在将孩子的内容放入堆栈之前尝试检查版本 B 是否为 -1，它会显着减慢（几乎 3 倍）。作为参考，我在 Cygwin 中使用带有 -O3 选项的 g++。
更新：
我能够使用以下代码（版本 C）匹配递归版本：
node *node_list[65536];
void node_vertex_members(node *A, vector<int> *vertex_list){
int top = 0;
node_list[top] = A;
while(top >= 0){
int x = node_list[top]->contents;
if(x != -1){
vertex_list->push_back(x);
--top;
}
else{
node* temp = node_list[top];
--top;
for(int i=temp->children.size()-1; i>=0; --i){
++top;
node_list[top] = temp->children[i];
}
}
}
}
明显的缺点是代码长度和幻数（以及相关的硬限制）。而且，正如我所说，这仅匹配版本 A 的性能。我当然会坚持使用递归版本，但现在我很满意它基本上是 STL 开销咬我。