On Fri, Feb 5, 2021 at 1:09 PM Magnus Fromreide via Std-Proposals
<std-proposals_at_[hidden]> wrote:
>
> 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.

That's not how a Tony Table works. A Tony Table compares the
implementation of something before the feature and after it. They're
not applicable for cases of "implement the feature to have the
feature."

You should instead focus on explaining why you want a tree that isn't
a set/map. Your post here just sort of assumes that this is a thing
that is desired. I mean, you say that it "gives a lot more flexibility
in the choice of the key_type", but you don't explain what you're
supposed to do with that flexibility. That is, when do you need it?
What problems can be better solved with the feature than without it?

>
> 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.

Are you saying that you want a `set` with a non-`const` key type?