在std::scoped_allocator_adaptor内使用自定义分配器与std::unordered_map

Question

我正在尝试使用一个简单的内存池分配器和std::unordered_map一起使用。我似乎已经成功地将这个相同的分配器用于std::string和std::vector。我希望unordered_map（和vector）中包含的项目也使用这个分配器，因此我已经在std::scoped_allocator_adaptor中包装了我的分配器。

简化定义集如下：

template <typename T>
using mm_alloc = std::scoped_allocator_adaptor<lake_alloc<T>>;

using mm_string = std::basic_string<char, std::char_traits<char>, mm_alloc<char>>;
using mm_vector = std::vector<mm_string, mm_alloc<mm_string>>;
using mm_map = std::unordered_map<mm_string, mm_vector, std::hash<mm_string>, std::equal_to<mm_string>, mm_alloc<std::pair<mm_string, mm_vector>>>;

初始化如下：

lake pool;
mm_map map { mm_alloc<std::pair<mm_string, mm_vector>>{pool} };

以下是 lake_alloc 和其余迭代器代码。在Clang 3.3中出现的错误是它无法将其自己的__pointer_allocator（在这种情况下，字符串到向量对的mm_alloc）与其allocator_type匹配。这是哈希映射实现中使用的内部类型。以下是部分错误输出：

lib/c++/v1/__hash_table:848:53: error: no matching conversion for functional-style
      cast from 'const allocator_type' (aka 'const std::__1::scoped_allocator_adaptor<krystal::krystal_alloc<std::__1::pair<std::__1::basic_string<char,
      std::__1::char_traits<char>, std::__1::scoped_allocator_adaptor<krystal::krystal_alloc<char, krystal::lake> > >, std::__1::vector<std::__1::basic_string<char,
      std::__1::char_traits<char>, std::__1::scoped_allocator_adaptor<krystal::krystal_alloc<char, krystal::lake> > >,
      std::__1::scoped_allocator_adaptor<krystal::krystal_alloc<std::__1::basic_string<char, std::__1::char_traits<char>,
      std::__1::scoped_allocator_adaptor<krystal::krystal_alloc<char, krystal::lake> > >, krystal::lake> > > >, krystal::lake> >') to '__pointer_allocator' (aka
      'std::__1::scoped_allocator_adaptor<krystal::krystal_alloc<std::__1::__hash_node<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>,
      std::__1::scoped_allocator_adaptor<krystal::krystal_alloc<char, krystal::lake> > >, std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>,
      std::__1::scoped_allocator_adaptor<krystal::krystal_alloc<char, krystal::lake> > >, std::__1::scoped_allocator_adaptor<krystal::krystal_alloc<std::__1::basic_string<char,
      std::__1::char_traits<char>, std::__1::scoped_allocator_adaptor<krystal::krystal_alloc<char, krystal::lake> > >, krystal::lake> > > >, void *> *, krystal::lake> >')
    : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
                                                    ^~~~~~~~~~~~~~~~~~~~~~~

在其哈希映射内部结构中，GCC 4.7.1 给我返回了类似的错误信息，所以显然我做错了什么，但这是我第一次尝试STL中的分配器，我感到很困惑。

以下是自定义分配器，它是一个简单的实现，其中存在一些漏洞，但该版本在包含几兆字节数据的向量和字符串的测试用例中运行良好。

#include <cstddef>
#include <memory>
#include <scoped_allocator>

class lake {
    const size_t block_size_;
    mutable std::vector<std::unique_ptr<uint8_t[]>> blocks_;
    mutable uint8_t *arena_, *pos_;

    static constexpr const size_t DefaultBlockSize = 48 * 1024;

    void add_block(size_t of_size) const {
        blocks_.emplace_back(new uint8_t[of_size]);
        pos_ = arena_ = blocks_.back().get();
    }

    inline void add_block() const { add_block(block_size_); }

public:
    lake(const size_t block_size)
    : block_size_ {block_size}
    {
        add_block();
    }
    lake() : lake(DefaultBlockSize) {}

    void* allocate(size_t n) const {
        if (pos_ + n - arena_ > block_size_) {
            if (n > block_size_)
                add_block(n); // single-use large block
            else
                add_block();
        }

        auto result = pos_;
        pos_ += n;
        return result;
    }

    void deallocate(void* p, size_t n) const {
    }
};


template <typename T, typename Alloc>
class krystal_alloc {
    const Alloc* allocator_;

public:
    using value_type = T;
    using size_type = size_t;
    using difference_type = ptrdiff_t;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;

    template <typename U>
    struct rebind { typedef krystal_alloc<U, Alloc> other; };

    krystal_alloc() : allocator_{ new Alloc() } {} // not used
    krystal_alloc(const Alloc& alloc) : allocator_{ &alloc } {}

    pointer address(reference v) {
        return 0;
    }

    const_pointer address(const_reference v) {
        return 0;
    }

    size_type max_size() const {
        return static_cast<size_type>(-1) / sizeof(value_type);
    }

    pointer allocate(size_type n) {
        return static_cast<pointer>(allocator_->allocate(sizeof(T) * n));
    }

    void deallocate(pointer p, size_type n) {
        allocator_->deallocate(p, n);
    }
};

template <typename T, typename Alloc, typename U>
inline bool operator==(const krystal_alloc<T, Alloc>&, const krystal_alloc<U, Alloc>) { return true; }

template <typename T, typename Alloc, typename U>
inline bool operator!=(const krystal_alloc<T, Alloc>&, const krystal_alloc<U, Alloc>) { return false; }


// -- standard usage
template <typename T>
using lake_alloc = krystal_alloc<T, lake>;

- zenmumbler

---

你为自定义类型专门定制了std::hash和std::equal_to吗？ - sehe

只有一个问题，如果您手动定义嵌套分配器，为什么要使用scoped_allocator_adaptor？难道不是它的整个重点在于您一次性定义分配器吗？ - Konrad Rudolph

Konrad，到目前为止我找到的所有示例都明确指定了每个级别的分配器，但我很可能忽略了某些内容。例如，查看Bjarne在http://www.stroustrup.com/C++11FAQ.html#scoped-allocator中的解释。 - zenmumbler

Seth，我没有为我的basic_string模板化版本进行特殊化。但是，将Key恢复为普通的std :: string会产生相同的错误。 - zenmumbler

@KonradRudolph，不行。如果每个嵌套容器都没有使用作用域分配器，则不会将分配器传递到下一层嵌套对象。mm_string可以只使用lake_alloc<char>，因为char无论如何都不支持使用分配器构造，但是mm_vector和mm_map必须使用作用域分配器。 - Jonathan Wakely

Answer 1

我相信基本的错误在于您的krystal_alloc缺少一个“转换构造函数”：

template <class U>
    krystal_alloc(const krystal_alloc<U, Alloc>& u)
        : allocator_(u.allocator_) {}

我不确定我是否正确地实现了它，这只是我的最佳猜测。您需要一个友好的声明才能使其正常工作：

template <class U, class A> friend class krystal_alloc;

此外，我建议您在unordered_map的分配器中将key_type添加“const”：

using mm_map = std::unordered_map<mm_string, mm_vector, std::hash<mm_string>,
                              std::equal_to<mm_string>,
                              mm_alloc<std::pair<const mm_string, mm_vector>>>;

我认为你可以在内部容器中使用 lake_alloc 代替 mm_alloc。你的示例两种写法都可以编译通过，但我没有测试运行时的表现。

- Howard Hinnant

---

谢谢Howard，确实是这个问题。我正在尝试将作用域分配器删除，因为在这种情况下似乎并不需要。对于其他人，我应该在这里查找：http://www.cplusplus.com/reference/memory/allocator_traits/，并找到Howard所说的东西。 - zenmumbler