On Fri, Feb 5, 2021 at 1:33 PM Marcin Jaczewski via Std-Proposals <
std-proposals_at_[hidden]> wrote:

> pt., 5 lut 2021 o 19:17 Jason McKesson via Std-Proposals
> <std-proposals_at_[hidden]> napisał(a):
> >
> > 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?
> >
>
> If I understand correctly, the goal is to have set like class that has
> a deterministically computed key,
> but this key is not included in this class directly.
>

If I'm not mistaken, you can already do that:

std::set<something, decltype([](const something& s1, const something& s2) {
return s1.getSomeAspect() < s2.getSomeAspect(); })> S;

In fact this is pretty similar to the OP's usage example for the proposed
std::tree.

Seems like a more fleshed-out motivating example is needed.


>
> Probaby 20y ago I would support a type like this but currently if we
> should add something like this it probably should be a "flat" tree.
> Because memory indirections are performance killers.
>
> Btw type like this could have interesting property. We could allow
> transferring nodes between different collections,
> even if they use different keys but have same value type.
>
>
> > >
> > > 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?
> > --
> > Std-Proposals mailing list
> > Std-Proposals_at_[hidden]
> > https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>

-- 
*Brian Bi*