5
\$\begingroup\$

The following is an implementation of a tree in C++ designed for keys which do not have an order (otherwise a std::map could be used). T is a key type and H is a hash for T.

#include <iostream>
#include <memory>
#include <utility>
#include <unordered_map>

template<typename T, typename H>
class tree;

template<typename T, typename H>
class tree : public std::unordered_map<T, std::shared_ptr<tree<T, H>>, H> { };

template<typename T, typename H>
std::ostream& operator<<(std::ostream& s, const tree<T, H> &t);

template<typename T, typename H>
std::ostream& operator<<(std::ostream& s, const tree<T, H> &t)
{
    for(auto i : t) {
        s << i.first << std::endl;
        s << *i.second << std::endl;
    }
    return s;
}
\$\endgroup\$
2
  • \$\begingroup\$ What is the usecase for this? I have a suspicion that a custom container built on top of unordered_map might be more fitting. It seems rather odd to have a recursive map that never terminates. Have you considered a trie? I suspect it might fit what you're trying to do better. \$\endgroup\$
    – Corbin
    Commented Apr 21, 2014 at 0:39
  • \$\begingroup\$ My first use is minimax on some games. As to the recursion, it terminates when an unordered_map is empty. \$\endgroup\$ Commented Apr 21, 2014 at 1:58

1 Answer 1

4
\$\begingroup\$

At least as it stands right now, quite a bit of your code accomplishes nothing.

template<typename T, typename H>
class tree;

template<typename T, typename H>
class tree : public std::unordered_map<T, std::shared_ptr<tree<T, H>>, H> { };

When the declaration immediately precedes the definition like this, the declaration isn't really accomplishing anything--the definition by itself will do the same, so we can consolidate this down to just:

template<typename T, typename H>
class tree : public std::unordered_map<T, std::shared_ptr<tree<T, H>>, H> { };

Likewise, your declaration of the stream insertion operator:

template<typename T, typename H>
std::ostream& operator<<(std::ostream& s, const tree<T, H> &t);

...can be eliminated with no loss. For these declarations to be meaningful/helpful, you'd do something like putting them in a header, with the definitions in a separate file. For most purposes, the class definitions need to be in a header as well though, so the utility of the class declarations may be open to some question. There are cases such things are used (e.g., <iosfwd> contains just "forward" declarations of the iostreams classes) but they're not very widely used (e.g., when was the last time you wrote code that used #include <iosfwd>?)

Another obvious issue is that you're publicly deriving from a standard container. The standard containers aren't really intended to be used as base classes, so this usage is somewhat fragile. Public derivation means it's trivial to assign the address of Tree object to a pointer an unordered_map. If the object is destroyed this way, you get undefined behavior because the base class doesn't declare its dtor as virtual.

// Note that we don't have a cast or anything like that indicate that we're doing 
// something dangerous here.
std::unordered_map<T, H> *base = new Tree<T, H>;
// ...
delete base; // undefined behavior here.

...and there's basically nothing you can do from inside the class to prevent a user from doing this--by using public inheritance, you've told the world (and the compiler) that this usage should be perfectly fine, so the compiler doesn't require an explicit cast to do the conversion.

\$\endgroup\$
1
  • \$\begingroup\$ Okay, I had assumed that I needed to declare the class and function to use them in a recursive fashion, but after testing I see it's not the case with gcc. Two the second point I can see that it would be more useful to put a reasonable interface on tree<T, H>. Thanks \$\endgroup\$ Commented Apr 26, 2014 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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