title: Custom pool allocator std::list
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>This is the custom allocator I'm implementing:</p>
  
  <pre><code>#include &lt;algorithm&gt;
  #include &lt;cassert&gt;
  
  template &lt;class Tp, std::size_t N&gt;
  class PoolStackAllocator {
  
  public:
      typedef Tp value_type;
      typedef value_type* pointer;
      typedef const value_type* const_pointer;
      typedef value_type&amp; reference;
      typedef const value_type&amp; const_reference;
      typedef std::size_t size_type;
      typedef std::ptrdiff_t difference_type;
  
      template&lt;typename U&gt;
      struct rebind {
          typedef PoolStackAllocator&lt;U, N&gt; other;
      };
  
      inline explicit PoolStackAllocator() : data_size_(0) {}
  
      template &lt;class U, std::size_t M&gt;
      inline explicit PoolStackAllocator(const PoolStackAllocator&lt;U, M&gt;&amp; other) : data_size_(other.data_size_) {
          typename PoolStackAllocator&lt;U&gt;::const_pointer i = other.data_;
          typename PoolStackAllocator&lt;U&gt;::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 &amp;r; }
      inline const_pointer address(const_reference r) { return &amp;r; }
  
      inline pointer allocate(size_type n){
          assert(n == 1);
          assert(data_size_ &lt; 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 &lt;class T, class U, std::size_t N&gt;
  inline bool operator==(const PoolStackAllocator&lt;T, N&gt;&amp; a, const PoolStackAllocator&lt;U, N&gt;&amp; b){
      return &amp;a == &amp;b;
  }
  
  template &lt;class T, class U, std::size_t N&gt;
  inline bool operator!=(const PoolStackAllocator&lt;T, N&gt;&amp; a, const PoolStackAllocator&lt;U, N&gt;&amp; b){
      return &amp;a != &amp;b;
  }
  </code></pre>
  
  <p>And this is an example of how I intend to use it.</p>
  
  <pre><code>typedef std::forward_list&lt;Alien, PoolStackAllocator&lt;Alien, 25&gt;&gt; Aliens;
  </code></pre>
  
  <h2>Edit 1:</h2>
  
  <p>I got an answer on how std::list allocates the data structures:</p>
  
  <blockquote>
    <p>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.
    <a href="http://www.codeproject.com/Articles/4795/C-Standard-Allocator-An-Introduction-and-Implement" rel="nofollow noreferrer">http://www.codeproject.com/Articles/4795/C-Standard-Allocator-An-Introduction-and-Implement</a></p>
  </blockquote>
  
  <p>But now I'm still puzzled with a new question. How to implement the copy constructor.</p>
  
  <p>When I create a list like:</p>
  
  <pre><code>std::forward_list&lt;int, PoolStackAllocator&lt;int&gt;&gt; ints;
  </code></pre>
  
  <p>This copy constructor gets called:</p>
  
  <pre><code>template &lt;class Tp, std::size_t N&gt;
  class PoolStackAllocator {
     ...
     template &lt;class U, std::size_t M&gt;
     inline explicit PoolStackAllocator(const PoolStackAllocator&lt;U, M&gt;&amp; other);
     ...
  }
  </code></pre>
  
  <p>with</p>
  
  <pre><code>U = int
  Tp = std::_Fwd_list_node&lt;int&gt;
  </code></pre>
  
  <p>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?</p>
  
  <h2>Edit 2</h2>
  
  <p>Got the answer from:
  <a href="https://stackoverflow.com/questions/24278803/how-can-i-write-a-stateful-allocator-in-c11-given-requirements-on-copy-constr">How can I write a stateful allocator in C++11, given requirements on copy construction?</a></p>