0

我有一个简单的层次结构树结构，其基类 Node 表示一个节点。一个节点可以是另一种特定类型（子类化）。

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)，并且每次调用时都会创建新的向量对象。

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

4

3 回答 3

4

你真的需要复制向量吗？如果您不需要，您可以编写一个迭代器，该迭代器将在用户请求该项目时进行转换，即在 operator* 上。

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-26T16:19:07.860 回答
1

也许你可以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-26T16:20:37.290 回答
0

正如 James McNellis 在下面的评论中指出的那样，以下内容是不安全的（他更明确）。我自己不会使用它，即使我不知道它究竟为什么会触发未定义的行为——也许我应该问这个问题

由于您将指针存储在数组中，并假设您可以更改函数的返回类型，那么您可以这样做：

const vector<DepartmentNode*>* FacultyNode::getDepartments() {
  vector<Node*> tmp = this->getChildren();
  return reinterpret_cast<vector<DepartmentNode*>*>(&tmp);
}
于 2011-01-26T16:18:52.330 回答