C ++ - 更快的向下转换树节点的子节点？ [英] C++ - faster downcasting children of a tree-node?

问题描述

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

I have a simple hierarchy tree structure with a base class Node representing a node. A node could be of another specific type (subclassing).

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

我有几个子类 ：

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

说我知道教师节点的所有孩子都是 DepartmentNode 类型，以保存开发人员的工作我打算做类似

Say I know that all children of a faculty node is of DepartmentNode type, to save the developer's work I intended to do something like

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;
}

但是这将需要 code>，每次调用都会创建一个新的向量对象。

But that would take O(n), and new vector object will be created every time call is made.

有更好的方法吗？

推荐答案

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

Do you really need to copy the vector? In case you don't have to, you can write an iterator which will cast when the user requests the item, i.e. on 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.
  // ...
};

希望它澄清我的意思。

这篇关于C ++ - 更快的向下转换树节点的子节点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！