个人中心
gpt4 book ai didi

c++ - 自定义池分配器 std::list

转载 作者：可可西里 更新时间：2023-11-01 18:39:32 25 4
gpt4 key购买 nike

<分区>

我正在编写一个与 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 如何分配数据结构的答案:

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

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

当我创建一个列表时:

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

得到答案: How can I write a stateful allocator in C++11, given requirements on copy construction?

25 4 0
文章推荐： android - Qt 升级后 QPushButton 有重复的文本
文章推荐： c++ - "plugin verification data mismatch"while loading plugin for qt5 project
文章推荐： c++ - 使用 spdlog 从库中记录
文章推荐： c++ - 如何为 Qt 应用程序提供脚本支持？
可可西里
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com