std::unordered_map 使用自定义分配器/本地分配器无法编译

Question

我有一个非常简单的 custom/local 分配器。我的目标是使用堆栈上的数组作为内存的分配部分。它似乎在 std::vector 中工作，但是当我尝试将其插入 std::unordered_map 时，它无法编译。 gcc 7.4.0 的错误消息非常难以理解。大致如下：

hashtable_policy.h:2083:26: error: no matching function for call to
‘MonotonicIncreasingAllocator<std::pair<const int, std::string>, 500>::
MonotonicIncreasingAllocator(std::__detail::_Hashtable_alloc<MonotonicIncreasingAllocator
<std::__detail::_Hash_node<std::pair<const int, std::string>, false>, 500> >::
__node_alloc_type&)’
   
    __value_alloc_type __a(_M_node_allocator());

Clang 7.1.0 更易于管理。从 error: no matching conversion for functional-style cast from 'const std::_Hashtable . . . 之类的错误滚动，我发现：

hashmap_custom_alloc.cpp:11:5: note: candidate constructor not viable: no known conversion from
    'MonotonicIncreasingAllocator<std::__detail::_Hash_node<std::pair<const int,
    std::__cxx11::basic_string<char> >, false>, [...]>' to 'const
    MonotonicIncreasingAllocator<std::__detail::_Hash_node_base *, [...]>' for 1st argument
  MonotonicIncreasingAllocator(const MonotonicIncreasingAllocator& rhs) = default;
  ^

让这个 std::__detail::_Hash_node_base 位变得更清楚一点。这是代码，unordered_map 声明都不编译：

#include <array>
#include <stdexcept>
#include <unordered_map>
#include <vector>

template<class T, std::size_t max_size>
class MonotonicIncreasingAllocator
{
public:
    MonotonicIncreasingAllocator() : _index{0} {}

    using type = MonotonicIncreasingAllocator<T, max_size>;
    using other = MonotonicIncreasingAllocator<T, max_size>;

    using value_type = T;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using propagate_on_container_move_assignment = std::true_type;
    using is_always_equal = std::true_type;
        
    template<class U> 
    using rebind = MonotonicIncreasingAllocator<U, max_size>;

    T* allocate(std::size_t n)
    {
        T* r = _data.begin() + _index;
        _index += n;
        return r;
    }

    constexpr void deallocate(T* p, std::size_t n)
    {
        throw std::runtime_error("MontonicIncreasingAllocator can never deallocate()!");
    }

private:
    std::size_t _index;
    std::array<T, max_size> _data;
};

int main()
{
    using namespace std;

    using key = int;
    using value = string;
    using item = pair<key, value>;

    using alloc = MonotonicIncreasingAllocator<item, 500>;
    alloc a0;
    alloc a1;
    vector<item, alloc> v0(a0);
    vector<int, alloc> v1;
    // unordered_map<key, value, hash<key>, equal_to<key>, alloc> m; // doesn't compile
    // unordered_map<key, value, hash<key>, equal_to<key>, alloc> m(500, a1); // doesn't compile

    return 0;
}

Answer 1

类型 T 的分配器必须可重新绑定到类型 U 的分配器——这就是为什么有 rebind 模板的原因。

为此，您必须提供一种从类型 U 到类型 T 的转换构造方法，例如从 MonotonicIncreasingAllocator<U, ...>& 构造的构造函数，例如：

template <typename U>
MonotonicIncreasingAllocator( const MonotonicIncreasingAllocator<U, max_size>& )

您可能会立即注意到一个问题：array<U,max_size> 不一定能复制到 array<T,max_size>；因此，您需要重新考虑您的分配器设计。^[1]

由于遗留原因，C++“分配器”模型是可复制的。此要求使得很难使用本身包含状态而不是间接指向状态的分配器。

注意： 这可能对 vector 有效的原因是类型 T 的分配器不会在 vector<T>，因为它只需要分配 T 的 n 个实例。对于更复杂的数据结构，如 map、set、unordered_map 等，情况并非如此——因为可能存在对象节点或内部使用的其他连续序列。

^[1] 有状态分配器直接存储在使用它们的容器中。这意味着 vector<T,MonotonicIncreasingAllocator<T,N>> 现在还将存储分配器本身，包含一个 array<T,N>，直接在 vector class 内部，除了它自己的数据——这是浪费。使用此分配器复制甚至移动容器将是一项非常昂贵的操作。

此外，通过将数据直接存储在分配器内部，转换构造需要整个内部 std::array 对象的副本，这意味着重新绑定构造一个 new 对象指的是与正在反弹的分配器不同的单调结构——这并不理想。

您应该查看 std::pmr::polymorphic_allocator 中使用的架构以获得更好的灵感。 std::pmr::polymorphic_allocator 持有一种数据类型：一个 std::memory_resource 指针，这使得重新绑定变得很便宜，并且这个分配器的存储也很便宜。 memory_resource 是类型不明确的并通过间接传递，这允许分配器在重新绑定后使用并引用相同的内存池。

Answer 2

正如@Human-Compiler 在他的回答中所说的那样，不应该将分配的数据与分配器耦合。解决方案相当简单：从所需的栈上数组传入一个指针。您不必为在该线程和其他地方发现的所有分配器包装器废话而烦恼。在 SOLID 术语中，数据作为依赖项注入到分配器中。

我仍然觉得重新绑定界面非常好奇。我们坚持的显然是糟糕的设计。除了编写 struct rebind { other... 古老的别名之外， 还必须提供来自反弹类型的复制构造函数 。后者 几乎没有记录，如果有的话。

#include <array>
#include <unordered_map>
#include <vector>

struct SharedArray 
{
    uint8_t* data;
    uint64_t index;
};
template<class T>
class MonotonicIncreasingAllocator
{
public:
    MonotonicIncreasingAllocator(SharedArray& a) : _data{a} {}

    template<class U>
    MonotonicIncreasingAllocator(const MonotonicIncreasingAllocator<U>& rhs)
     : _data{const_cast<MonotonicIncreasingAllocator<U>&>(rhs).data()} {}

    using type = MonotonicIncreasingAllocator<T>;
    using other = MonotonicIncreasingAllocator<T>;

    using value_type = T;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using propagate_on_container_move_assignment = std::true_type;
    using is_always_equal = std::true_type;
    
    template<class U> 
    using rebind = MonotonicIncreasingAllocator<U>;

    T* allocate(std::size_t n)
    {
        T* r = _data.data + _data.index;
        _data.index += n * sizeof(T);
        return r;
    }

    constexpr void deallocate(T* p, std::size_t n)
    {
        return;
    }

    SharedArray& data()
    {
        return _data;
    }


private:
    SharedArray& _data;
};

int main()
{
    using namespace std;

    using key = int;
    using value = string;
    using item = pair<key, value>;
    std::array<uint8_t, 4096> arr; // allocate enough, here but a page
    SharedArray sharr;
    sharr.index = 0;
    sharr.data = arr.begin();

    using alloc = MonotonicIncreasingAllocator<item>;
    alloc a0(sharr);
    alloc a1(sharr);
    vector<item, alloc> v0(a0);
    unordered_map<key, value, hash<key>, equal_to<key>, alloc> m(500, a1);

    return 0;
}

std::unordered_map 使用自定义分配器/本地分配器无法编译

std::unordered_map with custom allocator / local allocator does not compile

c++

allocation