Custom pool allocator std::list [duplicate]

Question

I'm writing a custom allocator to be used with std::list. The list size will always be bounded to a small number and the list elements will be allocated and deallocated very frequently within a constraint tree search algorithm and thus I think a custom pool allocator (that allocates elements out of the stack) ought to improve performance.

My question is how does std::list allocated the data structures used to store the links/nodes. It will use the custom allocator to allocate the elements but then that wouldn't really help much if the nodes are still allocated from the heap.

This is the custom allocator I'm implementing:

#include <algorithm>
#include <cassert>

template <class Tp, std::size_t N>
class PoolStackAllocator {

public:
    typedef Tp value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;

    template<typename U>
    struct rebind {
        typedef PoolStackAllocator<U, N> other;
    };

    inline explicit PoolStackAllocator() : data_size_(0) {}

    template <class U, std::size_t M>
    inline explicit PoolStackAllocator(const PoolStackAllocator<U, M>& other) : data_size_(other.data_size_) {
        typename PoolStackAllocator<U>::const_pointer i = other.data_;
        typename PoolStackAllocator<U>::const_pointer end = other.data_ + data_size_;
        pointer j = data_;
        while (i != end){
            *j++ = Tp(*i++);
        }

        j = data_ + data_size_;
        pointer* k = free_;
        pointer end_ = data_ + 25;
        while (j != end_){
            *k++ = j++;
        }
    }

    inline pointer address(reference r) { return &r; }
    inline const_pointer address(const_reference r) { return &r; }

    inline pointer allocate(size_type n){
        assert(n == 1);
        assert(data_size_ < N);
        return free_[data_size_++];
    }

    inline void deallocate(Tp* p, size_type n){
        assert(n == 1);
        free_[--data_size_] = p;
    }

    inline size_type max_size(){
        return 1;
    }

private:
    size_type data_size_;
    value_type* free_[N];
    value_type data_[N];
};

template <class T, class U, std::size_t N>
inline bool operator==(const PoolStackAllocator<T, N>& a, const PoolStackAllocator<U, N>& b){
    return &a == &b;
}

template <class T, class U, std::size_t N>
inline bool operator!=(const PoolStackAllocator<T, N>& a, const PoolStackAllocator<U, N>& b){
    return &a != &b;
}

And this is an example of how I intend to use it.

typedef std::forward_list<Alien, PoolStackAllocator<Alien, 25>> Aliens;

Edit 1:

I got an answer on how std::list allocates the data structures:

In short, given allocator, we can simply do allocator::rebind::other.allocate(1) to be allocating memory large enough to hold an object U. This is the magic required for std::list to work properly, since given std::list(allocator()), std::list actually needs to allocate memory for Node, and not int. Thus, they need to rebind to allocator()::rebind >::other instead. http://www.codeproject.com/Articles/4795/C-Standard-Allocator-An-Introduction-and-Implement

But now I'm still puzzled with a new question. How to implement the copy constructor.

When I create a list like:

std::forward_list<int, PoolStackAllocator<int>> ints;

This copy constructor gets called:

template <class Tp, std::size_t N>
class PoolStackAllocator {
   ...
   template <class U, std::size_t M>
   inline explicit PoolStackAllocator(const PoolStackAllocator<U, M>& other);
   ...
}

with

U = int
Tp = std::_Fwd_list_node<int>

I don't know what to do in this copy constructor. From the example allocaters I've seen it seems that nothing must be done there. But why? Why does it get called then?

Edit 2

Got the answer from: How can I write a stateful allocator in C++11, given requirements on copy construction?

Answer 1

the container uses the same allocator to allocate nodes and memory for the stored objects.