C++ - faster downcasting children of a tree-node?

Question

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?

Drakosha · Answer 1 · 2011-01-26T19:48:15.560

4

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.

edited Jan 26 '11 at 19:48

answered Jan 26 '11 at 16:19

Drakosha

11,925
4
39
52

I think the custom iterator is the best approach here. – James McNellis Jan 26 '11 at 16:27
This would be interesting. Sorry I'm not very proficient with iterator. How would I go about doing it? – huy Jan 26 '11 at 16:35

score 1 · Answer 2 · answered Jan 26 '11 at 16:20

1

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

answered Jan 26 '11 at 16:20

Philipp

48,066
12
84
109

This is indeed very clever. Never thought of it. But why a `Boost.PtrCointainer`? – huy Jan 26 '11 at 16:32
hmm I think about it again, in that case how do I declare a Node variable? – huy Jan 26 '11 at 16:55

score 0 · Answer 3 · edited May 23 '17 at 12:13

0

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

edited May 23 '17 at 12:13

Community

1
1

answered Jan 26 '11 at 16:18

Daniel Gehriger

7,339
2
34
55

isn't that undefined behavior? – Philipp Jan 26 '11 at 16:21
You cannot `reinterpret_cast` the `vector` that way. – James McNellis Jan 26 '11 at 16:25
Why? A pointer to `Node` is the same size as a pointer to `DepartmentNode`, so if he is *sure* that his vector really only includes `DepartmentNode`s, then it's ok. – Daniel Gehriger Jan 26 '11 at 16:26
@James: yes, sorry, I didn't realize he returns by value. But if he returned a pointer, than it would be fine. – Daniel Gehriger Jan 26 '11 at 16:28
1

@Daniel: It doesn't matter whether you return by value or by pointer: you can't use a `vector` as if it were a `vector`. They could have different representations in memory, they could be optimized differently by the compiler, or the compiler might insert runtime checks to assert if you try to do this. The only type with which you can use a `vector` is `vector` (or any const/volatile-qualified version of that type or as an array of `char`, though that isn't a particularly useful thing to do.). – James McNellis Jan 26 '11 at 16:36
@James: ok, I take your word for it. I wouldn't use my approach myself (as `reinterpret_cast` is a red flag), but I am surprised to hear that the memory layout of `vector` should differ from `vector` (we're storing pointers, not the actual objects). The runtime checks seem to be the final argument, although I also have to think hard to find any check that could cause a problem. In a way, @Philipp's templated solution produces the same result, just w/o an explicit cast. -- But I'll be deleting my answer unless someone sees some value in it. – Daniel Gehriger Jan 26 '11 at 16:41

C++ - faster downcasting children of a tree-node?

3 Answers3

Linked