Rebinding the allocator for the Nodes of a LinkedList?

[Catfish666]

I am coding a singly-linked list container.
Of course, internally it uses Node<T>.

Question: what is the correct way to use the allocator given by the user?
I ask, because I've read this on the rival C++ Reference:

std::list<T, A> allocates nodes of some internal type Node<T>, using the allocator std::allocator_traits<A>::rebind_alloc<Node<T>>, which is implemented in terms of A::rebind<Node<T>>::other if A is an std::allocator

http://en.cppreference.com/w/cpp/memory/allocator

The above doesn't seem right to do, because then what should pointer and const_pointer be?

using pointer = std::allocator_traits<Alloc>::pointer;
using const_pointer = std::allocator_traits<Alloc>::const_pointer;

// but we're using Alloc<Node<T>> not Alloc<T>
// so maybe do this?

using pointer = value_type *;
using const_pointer = const value_type *;

Thanks.

[Cubbi]

Look at implementations, for example, libc++ http://llvm.org/svn/llvm-project/libcxx/trunk/include/list

the member typedef pointer is allocator_traits<Alloc>::pointer

but the type of the pointer members of each node is
allocator_traits<__node_base_allocator>::pointer where __node_base_allocator is allocator_traits<Alloc>::rebind_alloc<__node_base>

(technically there are a few more steps, the member pointers are actually
pointer_traits<void_pointer>::rebind<__list_node<_Tp, void_pointer> >::other - don't ask me why - but the straight-up allocator_traits<__node_base_allocator>::pointer is also used internally to work with pointers to nodes)

[Catfish666]

@ Cubbi: your suggestion is not clear to me; is it that I should go ahead and use std::allocator_traits<Alloc>::pointer anyway?

If so, isn't there a danger that the pointer types might be incompatible?

If clarifications are needed, my implementation currently looks like this.

template <typename T, typename A = std::allocator<T>>
class singly_linked_list
{
    class node;
    class sll_iterator;
    class sll_const_iterator;

    // ...

    using value_type        = T;
    using reference         = value_type &;
    using const_reference   = const value_type &;
    using iterator          = sll_iterator;
    using const_iterator    = sll_const_iterator;
    using difference_type   = std::iterator_traits<iterator>::difference_type;
    using size_type         = std::size_t;

    using pointer           = value_type *; // ???
    using const_pointer     = const value_type *; // ???

    // ...

    class node
    {
    public:

        value_type  data;
        node *      next = nullptr;

        node() = default;

        explicit node(const value_type &data):
            data(data)
        {
        }
    };

    class sll_iterator:
        public std::iterator<std::forward_iterator_tag, value_type>
    {
        // synopsis (begin)

    private:

        node *ptn = nullptr; ///< Pointed-To Node

    public:

        explicit sll_iterator(node *);

        sll_iterator() = default;
        sll_iterator(const sll_iterator &) = default;
        sll_iterator & operator = (const sll_iterator &) = default;
        ~sll_iterator() = default;

        bool            operator == (const sll_iterator &) const; // ???
        bool            operator != (const sll_iterator &) const; // ???
        reference       operator *  () const;
        pointer         operator -> () const;
        sll_iterator &  operator ++ ();
        sll_iterator    operator ++ (int);

        // synopsis (end)

        explicit sll_iterator(node *ptn):
            ptn(ptn)
        {
        }

        // ...

        pointer operator -> () const
        {
            return &ptn->data;
        }

        // ...
    };

    // ...
};

[JLBorges]

Does this help clarify matters?

#include <memory>
#include <type_traits>

template < typename T, typename Alloc = std::allocator<T> > struct slist
{
    struct node { T value ; node* next ; /* ... */  };
    
    // allocator we would use to allocate nodes
    using slist_allocator = typename Alloc::template rebind<node>::other ;
    
    // 'pointer' to node (compatible with the allocator we would use to allocate nodes)
    using pointer_to_node = typename slist_allocator::pointer ;
    
    // an allocator that is compatible (yields compatible pointers etc.)
    // with the allocator we would use to allocate nodes
    using compatible_allocator = typename slist_allocator::template rebind<T>::other ;

    // 'pointer' to T (compatible with the allocator we would use to allocate nodes)
    using compatible_pointer_to_T = typename std::allocator_traits<compatible_allocator>::pointer ;
    
    // 'pointer to T (compatible with Alloc)
    using pointer = typename std::allocator_traits<Alloc>::pointer ;
    
    // the IS (library-wide requirements)requires that the type of compatible_allocator must be Alloc
    static_assert( std::is_same< Alloc, compatible_allocator >::value,
                   "allocator Alloc does not conform to the library-wide requirements for allocators" ) ;
                   
    // therefore:
    static_assert( std::is_same< pointer, compatible_pointer_to_T >::value,
                   "allocator Alloc does not conform to the library-wide requirements for allocators" ) ;
                   
    // ...               
};

template struct slist<int> ;

int main()
{
}

http://coliru.stacked-crooked.com/a/d11e0f17d68f071b

[Catfish666]

@ JLBorges: if, in your code, slist_allocator would be used to allocate the node's, then why use the pointer type from Alloc instead of simply T* to point to T?

[JLBorges]

> why use the pointer type from Alloc instead of simply T* to point to T?

All that we can be sure of is that the pointer type from Alloc would have the semantics of a pointer.

However, we would not want to hard-code that it is a (dumb) pointer.

#include <memory>
#include <type_traits>
#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/allocator.hpp>

template < typename T, typename Alloc = std::allocator<T> > struct slist
{
    struct node { T value ; node* next ; /* ... */  };
    
    // allocator we would use to allocate nodes
    using slist_allocator = typename Alloc::template rebind<node>::other ;
    
    // 'pointer' to node (compatible with the allocator we would use to allocate nodes)
    using pointer_to_node = typename slist_allocator::pointer ;
    
    // an allocator that is compatible (yields compatible pointers etc.)
    // with the allocator we would use to allocate nodes
    using compatible_allocator = typename slist_allocator::template rebind<T>::other ;

    // 'pointer' to T (compatible with the allocator we would use to allocate nodes)
    using compatible_pointer_to_T = typename std::allocator_traits<compatible_allocator>::pointer ;
    
    // 'pointer to T (compatible with Alloc)
    using pointer = typename std::allocator_traits<Alloc>::pointer ;
    
    // the IS (library-wide requirements)requires that the type of compatible_allocator must be Alloc
    static_assert( std::is_same< Alloc, compatible_allocator >::value,
                   "allocator Alloc does not conform to the library-wide requirements for allocators" ) ;
                   
    // therefore:
    static_assert( std::is_same< pointer, compatible_pointer_to_T >::value,
                   "allocator Alloc does not conform to the library-wide requirements for allocators" ) ;
                   
    // ...  
    
};

namespace interprocess = boost::interprocess ;

using my_allocator_type = interprocess::allocator< int, interprocess::managed_shared_memory::segment_manager > ;

template struct slist< int, my_allocator_type > ;

int main()
{
    using pointer = slist< int, my_allocator_type >::pointer ;
    
    std::cout << "slist< int, my_allocator_type >::pointer is int* (pointer to int): " 
              << std::boolalpha << std::is_same<pointer,int*>::value << '\n' ;

    std::cout << "slist< int, my_allocator_type >::pointer is a (dumb) pointer: " 
              << std::is_pointer<pointer>::value << '\n' ;
    
    std::cout << "nevertheless, if we dereference it, we would get a reference to int: "
              << std::is_same< decltype( *std::declval<pointer>() ), int& >::value << '\n' ;    
}

clang++ -std=c++11 -stdlib=libc++ -O2 -Wall -Wextra -pedantic-errors -pthread main.cpp -lsupc++ && ./a.out
slist< int, my_allocator_type >::pointer is int* (pointer to int): false
slist< int, my_allocator_type >::pointer is a (dumb) pointer: false
nevertheless, if we dereference it, we would get a reference to int: true

http://coliru.stacked-crooked.com/a/81dad24eaf6967f7

EDIT: C++11, should have used std::allocator_traits<>::rebind_alloc<> to rebind.

[Cubbi]

I just logged in to bring up segmented storage as an example...