patterncppMinor
Tree implementation for unordered keys
Viewed 0 times
unorderedkeysforimplementationtree
Problem
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
#include
#include
#include
template
class tree;
template
class tree : public std::unordered_map>, H> { };
template
std::ostream& operator &t);
template
std::ostream& operator &t)
{
for(auto i : t) {
s << i.first << std::endl;
s << *i.second << std::endl;
}
return s;
}Solution
At least as it stands right now, quite a bit of your code accomplishes nothing.
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:
Likewise, your declaration of the stream insertion operator:
...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., `
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.
...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.
template
class tree;
template
class tree : public std::unordered_map>, 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
class tree : public std::unordered_map>, H> { };Likewise, your declaration of the stream insertion operator:
template
std::ostream& operator &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., `
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 `?)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 *base = new Tree;
// ...
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.
Code Snippets
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>
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);// 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.Context
StackExchange Code Review Q#47752, answer score: 4
Revisions (0)
No revisions yet.