c++ - 带有自定义分配器/本地分配器的 std::unordered_map 无法编译

Question

我有一个非常简单的自定义/本地分配器。我的目标是使用堆栈上的数组作为内存的分配部分。它似乎在 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 类型的分配器必须可重新绑定(bind)到 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> 上没有反弹, 因为它只需要分配 n T 的实例.对于更复杂的数据结构，如 map，情况并非如此。 , set , unordered_map等——因为可能有对象的节点或内部使用的其他连续序列。

[1] 有状态分配器直接存储在使用它们的容器中。这意味着 vector<T,MonotonicIncreasingAllocator<T,N>>现在还将存储分配器本身，其中包含 array<T,N> ，直接在 vector 内类，除了它自己的数据——这是浪费的。使用此分配器复制甚至移动容器将是一项极其昂贵的操作。
此外，通过将数据直接存储在分配器内部，转换构造需要整个内部 std::array 的拷贝。对象，这意味着重新绑定(bind)构造了一个新对象，该对象引用了与被重新绑定(bind)的分配器不同的单调结构——这并不理想。
您应该查看 std::pmr::polymorphic_allocator 中使用的架构。以获得更好的灵感。 std::pmr::polymorphic_allocator保留 1 种数据类型:a std::memory_resource指针，这使得重新绑定(bind)便宜，并且这个分配器的存储便宜。 memory_resource是类型不明确的并通过间接传递，这允许分配器在被重新绑定(bind)后使用和引用相同的内存池。