5
\$\begingroup\$

I've done this simple c++ assignment. The homework was "Design a Tree class that allows insertion of nodes and visit of the graph".

What do you think of the style/design I used? I chose to store in the STL container the pointers of sub trees.

Is it memory efficient?

Is it sufficiently readable?

Did I chose the right STL container?

Thanks a lot for any tips about problems or bad practices!

What do you think of the style/design I used? I chose to store in the STL container the pointers of sub trees.

Is it memory efficient?

Is it sufficiently readable?

Did I chose the right STL container?

Thanks a lot for any tips about problems or bad practices!

#include <set> 
#include <deque> 
#include <iostream>
  using namespace std;

template < typename T >
class Tree {

struct compare {
  bool operator()(const Tree * t1,
    const Tree * t2) const {
    return t1 -> GetContent() < t2 -> GetContent();
  }
};

typedef typename std::multiset < Tree * , typename Tree::compare > NodeSet;

private:
  NodeSet children;
T content;

public:

  Tree& AppendNode(const T& node) {
    Tree *t = new Tree(node);
    AttachTree(t);
    return *t;
  }
void Clear() {
  typename NodeSet::iterator it = children.begin();
  while (children.end() != it) {
    children.erase( *it);
    delete *it;
    it++;
  }

}
const T& GetContent() const {
  return content;
}
Tree(const T& root) {
  content = root;
}
void AttachTree(Tree* t) {
  children.insert(t);
}
void Visit(std::deque <T>& exp) const {
  exp.push_back(content);
  typename NodeSet::iterator it = children.begin();
  while (it != children.end()) {
    (*it) -> Visit(exp);
    it++;
  }
}
Tree() {}
Tree(Tree & c) {
  c.DeepCopyTo(this);
}
T & operator = (const Tree & b) {
  b.DeepCopyTo(this);
}
~Tree() {
  Clear();
}
void DeepCopyTo(Tree* dest) const {
  dest -> content = content;
  typename NodeSet::iterator it = children.begin();
  while (it != children.end()) {
    Tree* t = new Tree();
    (*it)->DeepCopyTo(t);
    dest->AttachTree(t);
    it++;
  }
}

 };

https://ideone.com/62Ggwu

\$\endgroup\$
3
\$\begingroup\$

Use using keyword to define your type instead of typedef

C++11 introduced type alias which can be used to define your own type and it's compatible with templates, so instead of:

typedef typename std::multiset < Tree * , typename Tree::compare > NodeSet;

you'll get this:

using NodeSet = std::multiset < Tree * , Tree::compare >;

Consider using range-based for loop instead of while loop with iterator

I think that it will result in simplier and more readable code, for example Visit function will look like this:

void Visit(std::deque <T>& exp) const {
  exp.push_back(content);
  for (const auto& child : children)
        child->Visit(exp);
}

Unnecessary erase call in Clear function

The following call:

children.erase( *it);

is unnecessary - multiset childern will be erased automatically.

Reconsider memory management

Currently it's possible to add new child to existing Tree by calling function

void AttachTree(Tree* t)

which expects pointer to existing Tree object as argument. It means that Tree is not repsonsible for creation of children. By the other hand, in destructor the Clear function is called which deletes all the children, which means that Tree takes responsibility for deletion of children. This might lead to undefined behaviour. Consider the following code:

Tree<int>* t1 = new Tree<int>(1);
{
    Tree<int> t2(2);
    t2.AttachTree(t1);
    {
        Tree<int> t3(3);
        t3.AttachTree(t1);
        std::cout << "1. t1 content: " << t1->GetContent() << "\n";
    } // t3 desctructor is called, which means that t1 has been deleted
    std::cout << "2. t1 content: " << t1->GetContent() << "\n"; // t1 doesn't exist anymore - what's the result of t1->GetContent() ?
} // t2 desctructor is called and t1 will be deleted again
std::cout << "3. t1 content: " << t1->GetContent() << "\n"; // t1 doesn't exist anymore - what's the result of t1->GetContent() ?
\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for the review!! What's the easiest way to deal with the last issue? \$\endgroup\$ – Surfer on the fall Jun 7 '17 at 5:53
  • \$\begingroup\$ What about simply rewriting attach method to force a deep copy? \$\endgroup\$ – Surfer on the fall Jun 7 '17 at 5:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.