C++ - faster downcasting children of a tree-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; }
}

and I have a couple of subclasses of Node:

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

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

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

Is there any better way to do this?

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

Hope it clarifies what i meant.

Maybe you can turn Node into a template?

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

As James McNellis points out in his comments below, the following is unsafe (he is more categoric). I wouldn't use it myself, even though I don't know why exactly it would trigger undefined behavior -- maybe I should ask this in a question

Since you are storing pointers in the array, and assuming you can change the return type of your function, then you could do it like this:

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