Implementing a custom allocator with fancy pointers

Question

I'm trying to implement my own allocator, which should work with STL containers and use a custom fancy pointer implementation.

I'm pretty sure, that my classes fulfill all requirements (according to cppreference) but my implementation doesn't compile for std::list because there is no conversion from my fancy pointer to a normal pointer.

A minimal example which shows the problem, (but is obviously not my real implementation):

fancy_ptr.h:

#include <cstddef>

template<typename T>
class FancyPtr {
    T *ptr;

    FancyPtr(T *ptr, bool) : ptr(ptr) {};   //Bool to be non standart

public:
    using element_type = T;

    FancyPtr(std::nullptr_t n) : FancyPtr() {};

    template<class S>
    operator FancyPtr<S>() {
        return {ptr};
    }

    T &operator*() { return *ptr; }

    T &operator[](size_t n) { return ptr[n]; }

    T *operator->() { return ptr; }

    bool operator==(const FancyPtr &other) { return ptr == other.ptr; };

    static FancyPtr pointer_to(element_type &r) { return FancyPtr(&r, false); };
};

TrivialAllocator.h:

#include "fancy_ptr.h"

template<typename T>
class TrivialAllocator {
public:
    using pointer = FancyPtr<T>;
    using value_type = T;

    TrivialAllocator() = default;

    template<typename Other>
    TrivialAllocator(const TrivialAllocator<Other> &other) {};

    template<typename Other>
    TrivialAllocator(TrivialAllocator<Other> &&other) {};

    TrivialAllocator(TrivialAllocator &alloc) = default;

    pointer allocate(size_t n) { return pointer::pointer_to(*new T[n]); }

    void deallocate(pointer ptr, size_t n) { delete[] &*ptr; };

    bool operator==(const TrivialAllocator &rhs) const { return true; };

    bool operator!=(const TrivialAllocator &rhs) const { return false; };
};

main.cpp:

#include "TrivialAllocator.h"
#include <list>

int main() {
    struct Test {};
    using AllocT = std::allocator_traits<TrivialAllocator<long double>>;
    static_assert(std::is_same_v<FancyPtr<long double>,std::pointer_traits<AllocT::pointer>::pointer>);
    static_assert(std::is_same_v<FancyPtr<Test>, std::pointer_traits<AllocT::pointer>::rebind<Test>>);


    std::list<long double, AllocT::allocator_type> list;
}

The static assertions are ok.

Can anybody tell me what I have to to to get this working?

PS: I know that operator-> is in something like a conversion operator, but the underlying problem is that std::list seem not to save my fancy pointers, but raw pointers.

Marciano

Thanks for the hint, I add some assertions which show that the type are correct ( at least in my understanding). – Marciano

Are you using GCC? – Visby

I tried gcc and clang, same result. – Marciano

Ok I musst specify that I test with Clang and GCC, but in both cases with libstdc++. Its working with libc++. – Marciano

What versions of the library was used? – Monochord

GCC 10.2, libc++ 11.0, clang 11.0. The latest versions in arch linux, why? – Marciano

Answer 1

After some digging into the problem, I guess this is simply impossible due to libstdc++ internal limitations. This is a known old bug, "Node-based containers don't use allocator's pointer type internally":

Container nodes are linked together by built-in pointers, but they should use the allocator's pointer type instead. Currently I think only std::vector does this correctly. ...

It should work with Clang and libc++ (use -stdlib=libc++ command line option) with a couple of fixes:

1. FancyPtr<void>::pointer_to(...) should be a valid member function. Now it is not, because void& does not exist.
2. FancyPtr should provide operator!=(...) member function.

These fixes are needed to make your code at least compilable. Whether it will work correctly is out of scope of this answer.

Visby

There are some minor bug in the code, but nothing critical. Is it known if they will ever fix that issue, because the bug report exists for 7 years already? – Marciano

@gerum, I didn't find anything specific about the status of this bug. One problem is that fixing this bug will break ABI, and from the practical point of view this might be a (much) more serious problem than the bug itself. – Visby

Answer 2

Your class does not fulfil all the requirements.

Your pointer type must be a Cpp17RandomAccessIterator (operator++, operator+=, operator+, operator--, operator-, operator-=, operator!=, operator<, operator>=, operator<=)

Your FancyPtr<void> (which would be std::allocator_traits<TrivialAllocator<T>>::void_pointer) does not compile because of the operator[] and pointer_to(void&) (void_pointer and const_void_pointer don't need to be random access iterators)

You can't convert from a pointer to a void_pointer (You need to change your conversion operator to return {static_cast<S*>(ptr);}, or have the static_cast on a constructor of void_pointer)

You can't convert from your pointer type to bool which is one of the requirements for NullablePointer.

Your allocators's allocate and deallocate shouldn't call constructors or destructors.

However, even after making it a valid pointer type for an allocator, you still run into issues with how libstdc++ and libc++ deals with pointers. At some points in the code, there is a cast from FancyPtr<ListNode> to FancyPtr<ListNodeBase>, where ListNode derives from ListNodeBase. This is not part of the requirements of a pointer type, but is used by the implementation of std::list in those standard libraries anyways. You allow this by having operator FancyPtr<T> for any T, which is used. The standard libraries may be able to fix this by converting to a void pointer then to the base class, if the node classes are standard layout.

libstdc++ also internally uses raw T* pointers everywhere, so there are points where it implicitly tries to convert from T* to FancyPtr<T>. Unfortunately, the only way to support this would be to have a public FancyPtr(T*) constructor and a conversion to a raw pointer operator T*(). libstdc++ could fix this without breaking ABI by using p ? std::pointer_traits<pointer>::pointer_to(*p) : pointer(nullptr) to convert a T* p to a fancy pointer, and std::to_address for the reverse.

Microsoft's STL's std::list has no problems with a valid pointer type.

Here is a example implementation of a fancy pointer type that fulfils the requirements and has the workarounds for the 2 standard library implementations mentioned here: https://godbolt.org/z/vq9cvW

Giagiacamo

Thanks for listing all the missing requirements, but the core of the problem is, that the list saves the wrong pointer type. That has 2 disadvantages: 1. It is a additional requirement compared to the standard (minor problem) 2. The pointers of my allocator has to be saved as FancyPtr because they save additional, required information which will be lost if they are converted to a raw pointer. – Marciano

@Marciano How are you implementing pointer_to if you have to store extra information that is lost when you do &*fancy_ptr? – Giagiacamo

With a exhaustive search through the internal buffers. My implementation use mmap to save the data in a file, so this works only until the program will be restarted. – Marciano