C ++ - быстрее понижать дочерние элементы дерева-узла?

Question

У меня есть простая иерархическая древовидная структура с базовым классом 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), и каждый раз будет создаваться новый векторный объект.

Есть ли лучший способ сделать это?

Answer 1

Вам действительно нужно скопировать вектор? Если вам это не нужно, вы можете написать итератор, который будет вызываться при запросе элемента пользователем, т. Е. Оператор *.

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

Надеюсь, это проясняет, что я имел в виду.

Answer 2

Может быть, вы можете превратить 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>;

Answer 3

Как отмечает Джеймс МакНеллис в своих комментариях ниже, следующее небезопасно (он более категоричен). Я бы не стал использовать это сам, хотя я не знаю, почему именно это вызвало бы неопределенное поведение - возможно, мне следует задать это в вопросе

---

Поскольку вы храните указатели в массиве и предполагаете, что можете изменить тип возвращаемого значения вашей функции, вы можете сделать это следующим образом:

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