C++ Logo

STD-PROPOSALS

Advanced search

Subject: Re: [std-proposals] std::tree
From: Marcin Jaczewski (marcinjaczewski86_at_[hidden])
Date: 2021-02-05 12:32:55


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.

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 list run by std-proposals-owner@lists.isocpp.org

Standard Proposals Archives on Google Groups