On Fri, Feb 05, 2021 at 01:17:12PM -0500, Jason McKesson via Std-Proposals wrote:
> On Fri, Feb 5, 2021 at 1:09 PM Magnus Fromreide via Std-Proposals
> <std-proposals_at_[hidden]> wrote:
> >
>
> 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?

The problem I am trying to solve is when I have a number of data structures
which I wish to look up with the timing characteristics of a set the key
ain't the whole data structure and I want to be able to change the non-key
parts of the value_type.

In order to achieve this I try to generalize sets.

std::set and std::map could, to some extent(1) be expressed as specializations
of tree as follows:

template <typename Key, typename Compare = std::less<Key>,
          typename Alloc = std::allocator<Key>>
using almost_set =
    tree<const Key,
         decltype([](const auto& x){return x;}), Key, Compare, Alloc>;

template <typename Key, typename Value, typename Compare = std::less<Key>,
          typename Alloc = std::allocator<std::pair<const Key, Value>>>
using almost_map =
    tree<std::pair<const Key, Value>,
         decltype([](const auto&x){return x.first;}), Key, Compare, Alloc>;

(1)
 For almost_set, iterator and const_iterator are different types
 For almost_map, there is no mapped_type and thus no operator[] nor any at()
 member

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

No, I am trying to say that since this container don't have control of
the stored key_type and thus can't force it to be const then this is
what I have to rely on to make sure the key of a node doesn't change.

/MF