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

本当にベクトルをコピーする必要がありますか？必要がない場合は、ユーザーがアイテムを要求したとき、つまり演算子*でキャストするイテレーターを作成できます。

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 に答える