What are the requirements for implementing an allocator with a fancy pointer which works with STL containers?

Asked 24/5, 2022 at 1:58 Answered 25/6, 2022 at 11:13

I am attempting to implement an Allocator which allows me to use a 'fancy' pointer along the lines of boost::interprocess::offset_ptr with STL types.

As a self contained template the pointer itself works well but I am having trouble getting it to work with either std::vector or boost::containers::vector

The list of things I have implemented for the pointer are:

template<class T>
class OffsetPtr ...

constructors from T*, T&
comparisons <=, <, !=, ==, >=, >=
dereferencing operator* & operator->
assignment
pointer arithmetic ++, --, -, +, +=, -=
explicit operator bool () const;
bool operator! () const;
using iterator_category = std::random_access_iterator_tag;
conversion from OffsetPtr(T) -> OffsetPtr(const T)
rebind conversions from OffsetPtr(T) to OffsetPtr(U)
move semantics - though I think this type should actually be immovable.
pointer traits
random access iterator requirements
iterator traits
conversion between raw pointers and my fancy pointer
comparisions and conversions with nullptr and nullptr_t

The allocator implements

allocator traits

But something, possible several somethings, are still missing.

Do I need template specialisations for OffsetPtr<void> and OffsetPtr<const void> ?

No error messages have suggested this so far but I am aware that rebind() is required so that we can have void* based implementations of STL containers.

Also:

Do I really need to implement move semantics? I have always acted as though these are optional for all types.

This is related to my other question

My other question asks how do I verify that I have actually implemented traits for a concept (pre c++20) which is in theory a general question.

I have two specific issues which I am so far unable to track down. One is related to move_iterator and the other either rebind and/or use of void.

Here is an example error when trying to use std::vector:

from /foo/bar/OffsetPtrAllocatorTest.cpp:8:
/usr/include/c++/8/bits/stl_uninitialized.h: In instantiation of _ForwardIterator std::__uninitialized_copy_a(_InputIterator, _InputIterator, _ForwardIterator, _Allocator&) [with _InputIterator = std::move_iter
ator<Memory::OffsetPtr<int, long int> >; _ForwardIterator = Memory::OffsetPtr<int, long int>; _Allocator = Memory::OffsetPtrAllocator<int>]:
/usr/include/c++/8/bits/stl_vector.h:1401:35:   required from std::vector<_Tp, _Alloc>::pointer std::vector<_Tp, _Alloc>::_M_allocate_and_copy(std::vector<_Tp, _Alloc>::size_type, _ForwardIterator, _ForwardIter
ator) [with _ForwardIterator = std::move_iterator<Memory::OffsetPtr<int, long int> >; _Tp = int; _Alloc = Memory::OffsetPtrAllocator<int>; std::vector<_Tp, _Alloc>::pointer = Memory::OffsetPtr<int, long int>; st
d::vector<_Tp, _Alloc>::size_type = long unsigned int]
/usr/include/c++/8/bits/vector.tcc:74:12:   required from void std::vector<_Tp, _Alloc>::reserve(std::vector<_Tp, _Alloc>::size_type) [with _Tp = int; _Alloc = Memory::OffsetPtrAllocator<int>; std::vector<_Tp, 
_Alloc>::size_type = long unsigned int]
/foo/bar/OffsetPtrAllocatorTest.cpp:46:16:   required from here
/usr/include/c++/8/bits/stl_uninitialized.h:275:25: error: no matching function for call to __gnu_cxx::__alloc_traits<Memory::OffsetPtrAllocator<int>, int>::construct(Memory::OffsetPtrAllocator<int>&, int*, std
::move_iterator<Memory::OffsetPtr<int, long int> >::reference)
      __traits::construct(__alloc, std::__addressof(*__cur), *__first);
      ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/8/bits/stl_construct.h:61,
                 from /usr/include/c++/8/deque:62,
                 from /usr/include/cppunit/Message.h:11,
                 from /usr/include/cppunit/Exception.h:5,
                 from /usr/include/cppunit/TestCaller.h:4,
                 from /usr/include/cppunit/extensions/HelperMacros.h:9,
                 from /foo/bar/OffsetPtrAllocatorTest.cpp:8:
/usr/include/c++/8/ext/alloc_traits.h:82:7: note: candidate: template<class _Ptr, class ... _Args> static typename std::enable_if<std::__and_<std::is_same<typename std::allocator_traits<_Alloc>::pointer, _Ptr>,
 std::__not_<std::is_pointer<_Ptr> > >::value>::type __gnu_cxx::__alloc_traits<_Alloc, <template-parameter-1-2> >::construct(_Alloc&, _Ptr, _Args&& ...) [with _Ptr = _Ptr; _Args = {_Args ...}; _Alloc = Memory::OffsetPtrAllocator<int>; <template-parameter-1-2> = int]
       construct(_Alloc& __a, _Ptr __p, _Args&&... __args)
       ^~~~~~~~~
/usr/include/c++/8/ext/alloc_traits.h:82:7: note:   template argument deduction/substitution failed:

I get a different error when trying to use boost::container::vector:

The reason for trying boost as well is that some STL implementations have bugs meaning they don't work as they are supposed to without additional modifications. I was hoping to expose different flaws in my implementation to help understand what is wrong.

Just returned to this and I now realise that my OffsetPtr class does work with an allocator on gcc 4.8 on RHEL8 but not on gcc 9.4.0 on Ubuntu so the errors are caused by some difference between the two versions.

Returning to this again. I created a complete self contained example which fails to compile on gcc 9.4.0 (Ubuntu 20). This one also fails on 4.8 (RHEL8) though I feel I have got closer than previously by adding construct() templates to the allocator.

The error I get for this case is:

In file included from /usr/include/c++/8/bits/stl_algobase.h:67,
                 from /usr/include/c++/8/vector:60,
                 from /home/brucea/scrap/offsetptr2/main.cpp:2:
/usr/include/c++/8/bits/stl_iterator.h: In instantiation of ‘std::move_iterator<_Iterator>::reference std::move_iterator<_Iterator>::operator*() const [with _Iterator = OffsetPtr<int, long int>; std::move_iterator<_Iterator>::reference = int&&]’:
/usr/include/c++/8/bits/stl_uninitialized.h:275:61:   required from ‘_ForwardIterator std::__uninitialized_copy_a(_InputIterator, _InputIterator, _ForwardIterator, _Allocator&) [with _InputIterator = std::move_iterator<OffsetPtr<int, long int> >; _ForwardIterator = OffsetPtr<int, long int>; _Allocator = OffsetPtrAllocator<int>]’
/usr/include/c++/8/bits/stl_vector.h:1401:35:   required from ‘std::vector<_Tp, _Alloc>::pointer std::vector<_Tp, _Alloc>::_M_allocate_and_copy(std::vector<_Tp, _Alloc>::size_type, _ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::move_iterator<OffsetPtr<int, long int> >; _Tp = int; _Alloc = OffsetPtrAllocator<int>; std::vector<_Tp, _Alloc>::pointer = OffsetPtr<int, long int>; std::vector<_Tp, _Alloc>::size_type = long unsigned int]’
/usr/include/c++/8/bits/vector.tcc:74:12:   required from ‘void std::vector<_Tp, _Alloc>::reserve(std::vector<_Tp, _Alloc>::size_type) [with _Tp = int; _Alloc = OffsetPtrAllocator<int>; std::vector<_Tp, _Alloc>::size_type = long unsigned int]’
/home/brucea/scrap/offsetptr2/main.cpp:743:16:   required from here
/usr/include/c++/8/bits/stl_iterator.h:1047:16: error: invalid static_cast from type ‘const int’ to type ‘std::move_iterator<OffsetPtr<int, long int> >::reference’ {aka ‘int&&’}
       { return static_cast<reference>(*_M_current); }
                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/8/bits/ptr_traits.h: In instantiation of ‘constexpr typename std::pointer_traits<_Ptr>::element_type* std::__to_address(const _Ptr&) [with _Ptr = OffsetPtr<int, long int>; typename std::pointer_traits<_Ptr>::element_type = int]’:
/usr/include/c++/8/ext/alloc_traits.h:84:46:   required from ‘static typename std::enable_if<std::__and_<std::is_same<typename std::allocator_traits<_Alloc>::pointer, _Ptr>, std::__not_<std::is_pointer<_Ptr> > >::value>::type __gnu_cxx::__alloc_traits<_Alloc, <template-parameter-1-2> >::construct(_Alloc&, _Ptr, _Args&& ...) [with _Ptr = OffsetPtr<int, long int>; _Args = {int}; _Alloc = OffsetPtrAllocator<int>; <template-parameter-1-2> = int; typename std::enable_if<std::__and_<std::is_same<typename std::allocator_traits<_Alloc>::pointer, _Ptr>, std::__not_<std::is_pointer<_Ptr> > >::value>::type = void]’
/usr/include/c++/8/bits/vector.tcc:103:30:   required from ‘void std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int}; _Tp = int; _Alloc = OffsetPtrAllocator<int>]’
/usr/include/c++/8/bits/stl_vector.h:1091:9:   required from ‘void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = int; _Alloc = OffsetPtrAllocator<int>; std::vector<_Tp, _Alloc>::value_type = int]’
/home/brucea/scrap/offsetptr2/main.cpp:744:18:   required from here
/usr/include/c++/8/bits/ptr_traits.h:165:31: error: invalid conversion from ‘const int*’ to ‘std::pointer_traits<OffsetPtr<int, long int> >::element_type*’ {aka ‘int*’} [-fpermissive]
     { return std::__to_address(__ptr.operator->()); }
              ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

Gabrielgabriela answered 24/5, 2022 at 1:58 Comment(0)

Do I need template [specializations] for OffsetPtr<void> and OffsetPtr<const void>

§16.4.4.6.2 Allocator Completeness Requirements states:

If X is an allocator class for type T, X additionally meets the allocator completeness requirements if, whether or not T is a complete type:

(1.1) X is a complete type, and

(1.2) all the member types of allocator_traits<X> other than value_type are complete types.

Yes, you need a specialization (it's required if OffsetPtrAllocator<void> denoted X X::pointer is OffsetPtr<void>, since, as established it needs to be a complete type [through allocator_traits<X>::pointer]) because void& (reference to 'void') is invalid since void is an incomplete type that cannot be completed (cf: §6.8.2.14 Fundamental types).

Do I really need to implement move semantics?

As far as I understand: your allocator needs a move constructor to be standard compliant. (cf: §16.4.4.6 Cpp17Allocator requirements)
let T, U: cv-unqualified object type.
let X: Allocator<T>
let Y: Allocator<U>
let a: lvalue of type X
let b: lvalue of type Y

X u(std::move(a));
X u = std::move(a);
// Postconditions: The value of a is unchanged and is equal to u.
// Throws: Nothing.
X u(std::move(b));
// Postconditions: u is equal to the prior value of X(b).
// Throws: Nothing.

For the template instantiation errors: in template <class T> struct OffsetPtr the member functions returning T& would be invalid with T = void for the aforementioned reason.

Hope this helps.

Insouciant answered 8/6, 2022 at 21:34 Comment(3)

The allocator completeness requirements are only relevant if the container is supposed to be used with an incomplete type (a rather rare use case). "your allocator needs a move constructor to be standard compliant.": The question seems to be asking what the requirement on the fancy pointer class are, not the requirements on the allocator class. – Sporran 9/6, 2022 at 0:5

That said, I think a specialization for void and const void is still required to remove the reference-returning member functions. According to the requirements void_pointer and const_void_pointer do not need to be RandomAccessIterator, only NullablePointer. eel.is/c++draft/library#allocator.requirements.general-92 – Sporran 9/6, 2022 at 0:9

That would be helpful but it turns out my issue is a difference between compiler versions and/or platforms. I Just returned to this and I now realise that my OffsetPtr class does work with an allocator on gcc 4.8 on RHEL8 but not on gcc 9.4.0 on Ubuntu so the errors are caused by some difference between the two versions. – Gabrielgabriela 10/6, 2022 at 13:22

I made some changes to pass the compiler, but it still fails at the run time caused by some internal logic error, I believe. And how to make it run correctly is beyond the scope of this answer.

Online Demo

It seems you're mixing up const T* and T * const. The former refers to a pointer to an object of type const T, and you can't change the object's value through the pointer, but you can change the pointer itself, like pointing to other objects. The latter is vice versa.

So what would you need here?
Suppose you have a const OffsetPtr<int>, it should behave just the same as a pointer of type int* const. And since it's unnecessary to add a const qualifier when returning by value, when you try to get the raw pointer, the function should be like

T* get() const;

It's similar to T& and const T&.

I recommend you to use free functions but not member functions to overload operators. Because of the requirements of LegacyRandomAccessIterator (Or Cpp17RandomAccessIterator for C++20 and later) include the support for n + a, which a of type OffsetPtr is the second parameter, but things look good here.

Ok, back to your origin questions.

Do I need template specialisations for OffsetPtr<void> and OffsetPtr<const void>?

Yes, it's necessary for fulfilling the requirement of an Allocator.(void_pointer and const_void_pointer). And as comments say, under very rare circumstances, the compilation will fail.).

Do I really need to implement move semantics? I have always acted as though these are optional for all types.

Nope. There are no corresponding requirements for Allocator. The move constructor and move assignment operator is auto-generated for OffsetPtrAllocator by the compiler here. You don't have to worry about it, actually.

static_assert(std::is_move_constructible_v<OffsetPtrAllocator<int>>);
static_assert(std::is_move_assignable_v<OffsetPtrAllocator<int>>);

If you disable the move constructor, you can't directly move a container, but you can move the elements inside.

template <typename T>
class OffsetPtrAllocator
{
    OffsetPtrAllocator(OffsetPtrAllocator&&) = delete;
    OffsetPtrAllocator& operator=(OffsetPtrAllocator&&) = delete;
}

  std::vector<int,OffsetPtrAllocator<int> > v;
//   std::vector<int,OffsetPtrAllocator<int> > v1 = std::move(v); // fail
  std::vector<int,OffsetPtrAllocator<int> > v2(
      std::make_move_iterator(v.begin()),
      std::make_move_iterator(v.end())
  );

As to GCC 4.8, it still fails. I believe it's an internal "bug", (not very sure), since it's assuming the std::allocator_traits<TrivialAllocator<T>>::pointer can be implicitly converted from int. Source code here. You can bypass this limitation by declaring a non-explicit constructor with a raw pointer parameter.

Final Demo, compiled under both GCC 4.8 and 9.4.

Since the mentioned bug still exists in GCC, maybe this code only works for std::vector.

Gilding answered 25/6, 2022 at 11:13 Comment(15)

I'm not convinced this problem is limited by an ICE. Otherwise boost interprocess wouldn't compile. – Gabrielgabriela 26/6, 2022 at 10:42

The null pointer exception appears to come from vector::capacity subjecting trying subject two null pointers from each other. If I define the difference of two null pointers to be zero this does not happen. This is somewhat surprising but would appear to be one of the missing requirements. However this is contrary to the standard - #55748142 – Gabrielgabriela 26/6, 2022 at 11:15

re the first comment I meant a compiler bug not an internal compiler error. – Gabrielgabriela 26/6, 2022 at 11:35

@Bruce Would you mind providing an example using a standard container with boost's offset_ptr allocator? I'm not familiar with boost and maybe there's some trick to bypass limitation. Also, this commit in GCC 9.4 which replaces the 0 to pointer(), and its commit message may explain something. It's not a requirement for allocator::pointer to be initialized from a 0. – Gilding 26/6, 2022 at 13:47

I don't go deep into your implementation, which is not part of this question. Maybe it's because you don't not correctly initialize the begin and end pointer so that they become null? The link you paste seems a C problem..., in C++, it's totally valid – Gilding 26/6, 2022 at 13:56

You are correct on that point at least. According to https://mcmap.net/q/1146633/-subtraction-of-two-nullptr-values-guaranteed-to-be-zero - you can also add 0 to a null pointer validly. – Gabrielgabriela 27/6, 2022 at 6:30

I can't add anything more to the question as adding the real code made it reach the character limit. I'll see if I can add something via godbolt – Gabrielgabriela 27/6, 2022 at 6:36

Actually this might be a good example to use - code.woboq.org/boost/boost/libs/intrusive/example/… – Gabrielgabriela 27/6, 2022 at 6:49

Its a very good example! It fails to compile in the same way as my code! – Gabrielgabriela 27/6, 2022 at 6:52

I have no idea what your example looks like...But it does compile, like this, if you create the allocator in advance and pass it as an argument of the constructor of std::vector. And it'll fail to compile if directly constructed. I'll take a look – Gilding 27/6, 2022 at 11:40

Ah, I see. boost source code. It accepts a raw pointer without explicit specifier so that the implicit conversion is allowed. – Gilding 27/6, 2022 at 12:8

But I still argue this is not a part of the standard requirement... – Gilding 27/6, 2022 at 12:15

There was a bug in my move assignment operator. Clearly my unit test suite was not thorough enough. I believe I have everything working now. – Gabrielgabriela 28/6, 2022 at 8:37

Do you think my answer helpful to you? Would you mind accepting my answer? – Gilding 30/6, 2022 at 10:24

I will award the bounty as you helped me solve my problem. However, I think I will tidy up the question and add my own answer linking to a fully tested and working minimal implementation on github and trying explaining the requirements in more detail. – Gabrielgabriela 30/6, 2022 at 21:28

Hot tags

Godot Unity Godot Help Programming Godot 4.X GUI GDScript 3D 2D Physics CSharp Godot 3.X VR XR Projects C++

Recommended topics

Hot tags