[PATCH] Add fancy pointer support in std::map/set

[Jonathan Wakely]

On Mon, 4 Nov 2024 at 21:34, François Dumont <frs.dumont@gmail.com> wrote:
>
>
> On 04/11/2024 19:45, Jonathan Wakely wrote:
> > On Mon, 4 Nov 2024 at 18:30, François Dumont <frs.dumont@gmail.com> wrote:
> >>
> >> On 21/10/2024 06:56, François Dumont wrote:
> >>
> >>
> >> On 17/10/2024 23:11, Jonathan Wakely wrote:
> >>
> >>
> >>
> >> On Thu, 17 Oct 2024 at 21:39, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
> >>>
> >>>
> >>> On Thu, 17 Oct 2024 at 20:52, François Dumont <frs.dumont@gmail.com> wrote:
> >>>> Here is an updated version that compiles, I think, all your feedbacks. It's much cleaner indeed.
> >>>
> >>> Thanks, I'll take a look tomorrow.
> >>>
> >>>> It's also tested in C++98/17/23.
> >>>>
> >>>> I'm surprised that we do not need to consider potential allocator::const_pointer.
> >>> Do you mean consider the case where Alloc::const_pointer is not the same type as rebinding 'pointer' to a const element type?
> >> Yes, exactly.
> >>
> >>
> >>> We don't need to consider that because we never get a 'const_pointer' from the allocator, and we never need to pass a 'const_pointer' to the allocator. The allocator's 'allocate' and 'deallocate' members both work with the 'pointer' type, so we only need to use that type when interacting with the allocator. For all the other uses, such as _Const_Node_ptr, what we need is a pointer-to-const that's compatible with the allocator's pointer type. It doesn't actually matter if it's the same type as allocator_traits<Alloc>::const_pointer, because we don't need
> >>
> >> Sorry, I sent the email before finishing that thought!
> >>
> >> ... we don't need to pass a const_pointer to anything, we only need it for the container's own purposes.
> >>
> >> But thinking about it some more, do we even need a const-pointer for the container?  Currently the const_iterator stores a const-pointer, and some members like _M_root() and _M_leftmost() return a const-pointer. But they don't need to. The nodes are all pointed to by a non-const _Base_ptr, none of the storage managed by the container is const.
> >>
> >> Except _M_impl._M_header in a const context.
> >>
> >> Using const_cast would result in a similar UB that you fixed on _GLIBCXX_DEBUG containers, no ?
> > We only use a pointer to _M_header for the past-the-end iterator,
> > which is not dereferenceable. It's OK to do the const_cast, it's not
> > OK to write something through that pointer/reference if the object is
> > really const. But you can't write through a past-the-end pointer
> > anyway.
> >
> One last question then to complete this work, is it fine to change
> _Rb_tree_const_iterator::_M_node to _Base_ptr ? No abi issue in doing so ?

I thought I'd sent a reply to this question, but I don't see it in the
archives, sorry.

So changing from _Const_Base_ptr to _Base_ptr? Yes, I think that's OK.