определение итераторов для общего дерева

Question

определение итераторов для общего дерева

У меня есть этот класс под названием «Узел». Я подумывал переименовать его в «Дерево», но любое имя имеет такой же смысл. Этот класс реализует контейнер универсального дерева. Каждый узел может иметь любое количество детей. Основное определение заголовка класса выглядит следующим образом:

template<class Elem>
class Node
{
public:
Node();
~Node();
Node(const Elem& value);
Node(const Node& rNode);
const Elem& operator*() const;
Elem& operator*();
Elem* operator->();
void operator=(const Elem& rhs);
Node* addChild(const Elem& value);
Node* addChild(Node childNode);
Node* addChild(Node* pChildNode);
HRESULT removeNode(DFSIterator<Node>& iter);

template <class Node, class List, class Iter> friend class DFSIterator;

private:
bool hasChild() const;

Node* m_pParentNode;
Elem m_value;
std::vector<Node*> m_childList;
static std::set<Node*> sNodeSet;
};

Определение заголовка моего DFSIterator:

template<class Item,
class List = std::vector<Item*>,
class Iter = typename std::vector<Item*>::iterator>
class DFSIterator
{
public:
DFSIterator(Item& rRootNode);
~DFSIterator();
DFSIterator* begin();
DFSIterator* operator++();
Item& operator*() const;
Item* operator->() const;
bool operator!=(const DFSIterator& rhs) const;
bool isDone() const;
operator bool() const {return !isDone();}

private:
template <class Node> friend class Node;

void initChildListIterator(Item* currentNode);

bool m_bIsDone;
Item* m_pRootNode;
Item* m_pCurrentNode;
ChildListIterator<Item>* m_pCurrentListIter;
std::map<Item*, ChildListIterator<Item, List, Iter>*>  m_listMap;
};

Item псевдоним итератора для Node<Elem>,

У меня проблема в том, что я хочу определить итераторы для этого дерева, которые пользователь может объявлять аналогично контейнерам STL. Я думал, что помещая утверждения типа как typedef DFSIterator<Node<Elem>> dfs_iterator; будет работать нормально. Но всякий раз, когда я добавляю эти утверждения в заголовок, я получаю следующую ошибку error C2512<Item>: no appropriate default constructor available. Везде, где я пытаюсь пойти и использовать это.

Так что сейчас, чтобы объявить итератор, я должен сделать что-то вроде DFSIterator<Node<DataMap>> dfsIter = rRootNode.begin(); или же DFSIterator<Node<DataMap>> dfsIter(rNode); если я не хочу начинать с корневого узла дерева. То, что я хочу сделать, это что-то вроде Node<DataMap>::dfs_iterator it = rRootNode.begin(), Есть ли способ сделать это, что мне не хватает?

Примечание: я хочу изменить несколько других вещей об этой реализации. Я действительно не хочу, чтобы пользователь передавал элемент узла методу addChild (). Я бы предпочел, чтобы пользователь передал итератор, указывающий на узел.

1

c++generic-programming templates tree

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Если вы определяете dfs_iterator внутри Node, то вы можете использовать его в основном так, как вы описали:

template<class Elem>
class Node
{
public:
typedef Node<Elem> Item;

template<
class List = std::vector<Item*>,
class Iter = typename std::vector<Item*>::iterator
> class dfs_iterator;

.
.
.
};

template<class Elem>
template<class List, class Iter>
class Node<Elem>::dfs_iterator
{
public:

.
.
.
};

и использовать

Node<DataMap>::dfs_iterator<> it = rRootNode.begin();

Единственное отличие состоит в том, что, поскольку dfs_iterator является шаблоном, вы должны указать параметры шаблона, даже если они оба могут быть по умолчанию.

1