I am writing a custom distributor to be used with std :: list. The size of the list will always be limited to a small number, and the list items will be distributed and freed very often in the search algorithm of the constraint tree, and therefore I think that the user pool allocator (which selects items from the stack) should improve performance.
My question is how std :: list allocates data structures used to store links / nodes. He will use a custom allocator to distribute the elements, but then this will not help much if the nodes are still allocated from the heap.
This is a custom allocator that I am 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;
Change 1:
I got an answer on how std :: list allocates data structures:
In short, given a allocator, we can simply do allocator :: rebind :: other.allocate (1) to allocate memory large enough to hold an U object. This is the magic necessary for std :: list to work properly, since this std: : list (allocator ()), std :: list should actually allocate memory for Node, not int. Thus, they need to reinstall instead of allocator () :: rebind> :: other. http://www.codeproject.com/Articles/4795/C-Standard-Allocator-An-Introduction-and-Implement
But now I'm still puzzled by a new question. How to implement copy constructor.
When I create a list like:
std::forward_list<int, PoolStackAllocator<int>> ints;
This copy constructor is 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); ... }
from
U = int Tp = std::_Fwd_list_node<int>
I do not know what to do in this copy constructor. From the example of dispensers, I saw that nothing should be done. But why? Why is it called?
Edit 2
Got a response from: How can I write a stateful allocator in C ++ 11, given the requirements for building a copy?