CODEWITHSUNDEEP
c++memory-managementallocator
gerum
gerum

Reputation: 1134

Implementing a custom allocator with fancy pointers

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.

Upvotes: 1

Views: 750

Answers (2)

Artyer
Artyer

Reputation: 40791

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

Upvotes: 2

Evg
Evg

Reputation: 26282

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.

Upvotes: 1

Related Questions