C++ - 更快地向下转换树节点的子节点？

我有一个简单的层次结构树结构，其基类Node表示一个节点。节点可以是其他特定类型（子类）。C++ - 更快地向下转换树节点的子节点？

class Node { 
    vector<Node*> childs; 
    // simple node manipulation methods 
    const vector<Node*>& getChildren() { return childs; } 
}

和我有Node几个子类：

class FacultyNode : public Node; ... 
class DepartmentNode : public Node; ...

说我也知道，一个教员节点的所有孩子DepartmentNode类型，以节省开发者的工作，我打算做类似的东西

vector<DepartmentNode*> FacultyNode::getDepartments() { 
    vector<Node*> tmp = this->getChildren(); 

    vector<DepartmentNode*> a; 
    a.reserve(tmp.size()); 
    for (int i = 0; i < tmp.size(); i++) { 
    a.push_back(static_cast<DepartmentNode*>(tmp[i])); 
    } 
    return a; 
}

但会采取O(n)，新矢量对象将被创建每次调用。

有没有更好的方法来做到这一点？

来源

2011-01-26 huy

正如詹姆斯麦克奈利斯在下面的评论中指出的，以下是不安全的（他更加分类）。我不会用它自己，虽然我不知道到底为什么它会引发未定义行为 - 也许我应该ask this in a question

既然你存储的指针数组中，并假设你可以改变你的功能的返回类型，那么你可以这样做：

const vector<DepartmentNode*>* FacultyNode::getDepartments() { 
    vector<Node*> tmp = this->getChildren(); 
    return reinterpret_cast<vector<DepartmentNode*>*>(&tmp); 
}

来源

2011-01-26 16:18:52

是不是那个未定义的行为？ – Philipp 2011-01-26 16:21:11

你不能``reinterpret_cast`这个`矢量`的方式。 – 2011-01-26 16:25:47

为什么？指向`Node`的指针与指向`DepartmentNode`的指针的大小相同，所以如果他确信*其矢量真的只包含`DepartmentNode`，那么就没关系。 – 2011-01-26 16:26:24

你真的需要复制矢量吗？如果你不需要，你可以编写一个迭代器，当用户请求该项目时，即在操作符*上，该迭代器将投射。

MyIterator FacultyNode::getDepartmentsBegin() { 
    vector<Node*>& tmp = this->getChildren(); 
    return MyIterator(tmp.begin()); 
} 
MyIterator FacultyNode::getDepartmentsEnd() { 
    vector<Node*>& tmp = this->getChildren(); 
    return MyIterator(tmp.end()); 
} 

struct MyIterator { 
    vector<DepartmentNode*>::iterator m_it; 

    MyIterator(vector<DepartmentNode*> it) : m_it(it) {} 

    Department * operator*() { return (Department*)*it; } 

    void operator++() { m_it++; } 

    // in the same way, forwarding to m_it, implement other needed iterators. 
    // ... 
};

希望能够阐明我的意思。

来源

2011-01-26 16:19:07 Drakosha

也许你可以把Node变成模板？

template<typename T> 
class Node { 
    vector<T*> childs; // I think a Boost.PtrContainer would be better 
    // simple node manipulation methods 
    const vector<T*>& getChildren() { return childs; } 
} 
class FacultyNode : public Node<DepartmentNode>;

来源

2011-01-26 16:20:37 Philipp

C++ - 更快地向下转换树节点的子节点？

回答

相关问题