自定义池分配器std :: list

Question

我正在编写一个与std :: list一起使用的自定义分配器.列表大小将始终限制为一个较小的数字,列表元素将在约束树搜索算法中非常频繁地分配和释放,因此我认为自定义池分配器(从堆栈中分配元素)应该提高性能.

我的问题是std :: list如何分配用于存储链接/节点的数据结构.它将使用自定义分配器来分配元素,但如果节点仍然从堆中分配,那么这将不会有太大帮助.

这是我正在实现的自定义分配器:

#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;
}

这是我打算如何使用它的一个例子.

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

编辑1:

我得到了关于std :: list如何分配数据结构的答案:

简而言之,给定分配器,我们可以简单地将allocator :: rebind :: other.allocate(1)分配给足够大的内存以容纳对象U.这是std :: list正常工作所需的魔力,因为给定std :: list(allocator()),std :: list实际上需要为Node分配内存,而不是int.因此,他们需要重新绑定到allocator():: rebind> :: other. http://www.codeproject.com/Articles/4795/C-Standard-Allocator-An-Introduction-and-Implement

但现在我仍然对一个新问题感到困惑.如何实现复制构造函数.

当我创建一个列表,如:

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

调用此复制构造函数:

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

同

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

我不知道在这个拷贝构造函数中该做什么.从示例分配器中我看到似乎没有什么必须在那里完成.但为什么？为什么它会被调用呢？

编辑2

得到了答案: 如何根据复制构造的要求,如何在C++ 11中编写有状态分配器？

Answer 1

容器使用相同的分配器为存储的对象分配节点和内存。