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

[François Dumont]

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. We could just use the non-const pointers everywhere, which 
> would make things much simpler!

I just reproduced the current code approach on the const_iterator, I 
though it was more consistent that const_iterator was storing a 
const_pointer. But for the _Rb_tree_const_piterator we can indeed just 
store an allocator pointer. I'll give it a try.


>
> The const_iterator stores a const_pointer, and returns a const-pointer 
> from operator->(), so maybe _Rb_tree_const_piterator should take the 
> allocator's const_pointer as its template argument, instead of the 
> non-const ValPtr. So the trait would take two pointer types, but the 
> const one would only be used for the const iterator:
>
> template<typename _ValPtr, typename _CValPtr>
>   struct _Rb_tree_node_traits
>   {
>     using _Node_base = _Rb_tree_pnode_base<_ValPtr>;
>     using _Node_type = _Rb_tree_pnode<_ValPtr>;
>     using _Header_t = _Rb_tree_pheader<_Node_base>;
>     using _Iterator_t = _Rb_tree_piterator<_ValPtr>;
>     using _Const_iterator_t = _Rb_tree_const_piterator<_CValPtr>;
>   };
>
> Would that work? I can experiment with that if you like.

Seems contradictory with the previous proposal to store allocator 
pointer in const_iterator. I prefer to experiment with the latter 
approach so feel free to experiment any other approach.


>
>         Is there a plan to deprecate it ?
>
>
>     No, although I think that would be possible. Nothing in the
>     allocator requirements ever uses that type or cares what it is, as
>     long as it's convertible to  'const_void_pointer', and 'pointer'
>     is convertible to 'const_pointer'.
>
>         And if not, should not alloc traits const_pointer be per
>         default a rebind of pointer for const element_type like in the
>         __add_const_to_ptr you made me add ? I can try to work on a
>         patch for that if needed.
>
>
>     No, allocator_traits is defined correctly as the standard
>     requires. If an allocator A defines a 'A::const_pointer' typedef,
>     then that is used. If not, then
>     'allocator_traits<A>::const_pointer' defaults to rebinding the
>     non-const 'allocator_traits<A>::pointer' type.
>
Indeed, I hadn't look close enough.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20241021/78d217b6/attachment-0001.htm>