Hello!

I have, once more, stumbled over the fact that std::tree doesn't exist.

std::tree is normally used in the implementation of std::set and std::map
but it is very useful on it's own. It's member methods are the same as the
ones std::set provides but it gives a lot more flexibility in the choice of
the key_type.

template <typename ValueType,
          typename KeyFromValue,
          typename KeyType = decltype((KeyFromValue()(ValueType()))),
          typename KeyComp = std::less<void>,
          typename Alloc = std::allocator<ValueType>>
struct tree;

This class is already present in most implementations of the
standard library (libstdc++: bits/stl_tree.h ; libc++: __tree ;
DinkumWare: xtree) since it is used as a base in the implementation of
std::map and std::set.

The Tony Table pretty much screams about why this template is needed:

After:
        struct something { ... type getSomeAspect(); ... };

        tree<something,
             decltype([](const auto& x){ return x.getSomeAspect(); })> aTree;

Before:
        struct something { ... type getSomeAspect(); ... };

        // Eh... I don't really know how to do this... maybe a sorted vector?
        // I suppose there is something in boost.

Now, the obvious drawback to this is that if the value the key extractor
(KeyFromValue) returns changes during the lifetime of an element then
the container suffers undefined behavior. My feeling here is that the
utility of the class outweighs the danger.

The name tree comes from stlport where this class existed in a more primitive
form and was named "tree".

One could imagine letting the iterator and const_iterator have the same type
if ValueType is const-qualified. I think this would be a mistake since it
introduces a special case where none is really needed.



Now, if the idea of std::tree feels like a good idea then the idea of
std::unordered_tree follows naturally and I suppose it should be added
as well.

Is this something that should be pursued further?

/MF