What I want to achieve is the following:
#include "tree.h"
#include <iostream>
int main() {
Tree<std::string>* tA = new Tree<std::string>("A");
Tree<std::string>* tB = new Tree<std::string>("B", tA);
Tree<std::string>* tC = new Tree<std::string>("C", tA);
Tree<std::string>* tD = new Tree<std::string>("D", tB);
Tree<std::string>* tE = new Tree<std::string>("E", tB);
Tree<std::string>* tF = new Tree<std::string>("F", tB);
for (auto cur : *tA) {
std::cout << "traversed from " << (cur->parent ? cur->parent->val : "NULL") << " to " << cur->val << std::endl;
}
// std::next(std::next(tF->begin()));
return 0;
}
And here is my implementation.
#ifndef TREE_H
#define TREE_H
#include <iterator>
#include <stack>
#include <vector>
#include <iostream>
template <typename T>
class Tree {
public:
class iterator {
public:
using iterator_category = std::forward_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
public:
iterator() = default;
iterator(Tree<T>* const root);
Tree<T>* operator*() const;
iterator& operator++();
bool operator!=(iterator const& other) const;
Tree<T>* cur;
private:
std::stack<Tree<T>*> s_;
};
public:
Tree() = default;
Tree(T const& val, Tree<T>* parent = NULL);
void* operator new(size_t size);
iterator begin();
iterator end();
T val;
Tree<T>* const parent = NULL;
private:
std::vector<Tree<T>*> children_;
};
template <typename T>
Tree<T>::iterator::iterator(Tree<T>* const root)
: cur(root) {}
template <typename T>
Tree<T>* Tree<T>::iterator::operator*() const {
return cur;
}
template <typename T>
typename Tree<T>::iterator& Tree<T>::iterator::operator++() {
if (cur == NULL) {
throw std::out_of_range("No more nodes for traversal");
}
for (auto& child : cur->children_) {
s_.push(child);
}
if (s_.empty()) {
cur = NULL;
} else {
cur = s_.top(); s_.pop();
}
return *this;
}
template <typename T>
bool Tree<T>::iterator::operator!=(Tree<T>::iterator const& other) const {
return cur != other.cur;
}
template <typename T>
Tree<T>::Tree(T const& val, Tree<T>* const parent)
: val(val), parent(parent) {
if (parent) {
parent->children_.push_back(this);
}
}
template <typename T>
void* Tree<T>::operator new(size_t size) {
void* p = ::new Tree<T>();
return p;
}
template <typename T>
typename Tree<T>::iterator Tree<T>::begin() {
return iterator(this);
}
template <typename T>
typename Tree<T>::iterator Tree<T>::end() {
return iterator();
}
#endif
User should be able to directly modify val
(hence it is public). However, they shouldn't be able to modify any parent/children relationship. Therefore I try to make parent
a const
pointer, but I cannot make children
a list of const
pointers because anything inside a std::vector
must be assignable. I am considering exposing a GetChildren()
method which returns a const std::vector
, but that would be inconsistent with how I dealt with parent
. Can anyone show a good way to resolve this?
General reviews are welcome. More specifically, I want to know
- Is this a good and correct use of pointers?
- Is the interface well designed?
- Are there any
const
that I missed?
g++ main.cc -o tree -std=c++17 -Wall -static -O3 -m64 -lm
. This is a general tree (can have multiple children). \$\endgroup\$