替换 std::allocator 可以让 std::set 与 void* 一起使用并单独使用 copy/dealloc 函数吗？

Question

我正在解决一些试图与现代系统通信的遗留代码的问题。具体来说，C++11 版本的 STL（如果您提出的解决方案适用于 C++03，则加分，如果解决方案仅适用于 C++17，则减分，但我仍然对我可以将其用作升级参数的情况感兴趣。

我的函数传递了一个 void* 数组和三个函数指针，这些函数指针用于比较、复制和释放每个 void 指针中的数据（对于任何给定的调用，void 指针都是相同的数据类型） .简而言之，我拥有使这些 void* 看起来像对象的所有部分，但它们实际上不是对象。

在我的函数中，我想为 std::set 和 std::map 使用一些库来处理这些数据（还有我们自己的代码库中的其他一些库，但是 set 和 map 是很好的起点). void* 需要像值对象一样对待——即，当我执行 mySet.insert(x) 时，应该分配一个新指针（我有办法查询指针的大小）然后调用copy 函数将 x 的内容复制到集合中。

TL;DR：任何人都知道一种编写自定义分配器的方法，该分配器将与 std::set 一起用于其 copy/dealloc 指令未包含在复制构造函数中的类型？

---------问题结束（剩下的是我已经尝试过的东西）--------

显然，我可以将这四个东西打包成一个 class：

class BundleStuffTogether {
    BundleStuffTogether(void *data, CompareFunc compare, CopyFunc copy, DeallocFunc dealloc);
    // And create the rest of class accordingly, storing the values, 
    // and with destructor calling dealloc, copy constructor calling
    // copy, etc.
};

如果可以的话，我想避免分配 class。我不希望集合中每个条目的内存开销都需要 4x 大小（很多指针都指向少量数据，因此相对大小很大）。

我正在考虑使用 std::set 并创造性地填补这两个空白。我可以传递比较函数指针作为集合和映射的比较对象。这很简单。较难的部分是分配、解除分配和复制。

我一直在尝试编写一个自定义分配器，当我在测试中直接调用它时，我实际上得到了一个工作，但是当我将它插入 std::set 时，事情就崩溃了。我确实创建了一个 class 只是为了保留 void* 以便能够对分配器进行模板特化（详情如下）。

我的第一个技巧是创建这个 class:

class Wrapper {
     public: void *_ptr;
};
// which allows for this, given "void *y":
Wrapper *wrap = static_cast<Wrapper*>(&y);

这为我提供了可用于模板专业化的特定类型。使用它，我尝试为 Wrapper 创建一个成功的 std::allocator 类型专业化。这对 Wrapper 本身有效，但当我试图为自定义专业化提供额外的字段来存储函数时，它就崩溃了——分配器必须比较相等。

然后我 克隆了 std::allocator 并创建了我自己的 MyAllocator 模板 class —— 与 std::allocator 完全相同的代码 —— 并且然后为 Wrapper 创建了一个模板专业化。然后我给了主模板和我的专业化操作 void* 所需的函数，所以现在它们比较相等。

作为分配器，这是成功的！我直接使用分配器测试了许多变体，并且它有效。但是当我把它插入 std::set 时它就崩溃了。该集合不直接分配我的 class。它分配包含我的 class... 的节点，并且节点假设我的 class 有一个复制构造函数。叹息我认为与 std::set 的约定是它将使用 "construct" 方法在其自己的节点中实际构造 Wrapper 对象，但显然不是不是这样的。

所以现在我卡住了。 C++17 报告说它甚至已经弃用了我一直押注的 "construct" 和 "destroy" 方法，所以向前看，看起来根本没有办法插入自定义构造函数.

除了我一开始的 BundleStuffTogether 解决方案之外，还有谁能提出解决方案吗？我的下一个最佳想法是将 std::set 本身核心化并重写其内部结构，如果可以避免的话，我真的不想走那条路。

Answer 1

没有。分配器概念中没有允许 "copy" 函数的部分。这是 STL 的 non-starter。您唯一真正的希望是分配一个包装器 class。但是，如果你很狡猾，你可以缩小尺寸，方法是让每个实例都有一个指向 pseudo-type.

的指针

struct WrapperType {
  using compare_t = int(void*,void*);
    using copy_t    = void*(void*);
    using free_t    = void(void*);

    compare_t* _compare;
    copy_t*    _copy;
    free_t*    _free;
};
struct Wrapper {
    void*      _data;
    WrapperType* _type;

    explicit Wrapper(void* data, WrapperType* type) noexcept : _data(data), _type(type) {}
    Wrapper(Wrapper&& other) noexcept : _data(other._data), _type(other._type) {}
    Wrapper& operator=(Wrapper&& other) noexcept 
    {reset(); _data=other.release(); _type=other._type; return *this;}
    ~Wrapper() noexcept {reset();}
    void reset() noexcept {_type._free(_data); _data=nullptr;}
    void* release() noexcept {void* data=_data; _data=nullptr; return data;}
    boolean operator<(const Wrapper&other) noexcept {
        assert(_type==other._type);
        return _type._compare(_data, other._data)<0;
    }
};

noexcept 在这里对移动构造函数和移动赋值运算符非常有用。对于这些，C++ 库通常会使用它们。否则，C++ 库通常会更喜欢复制版本。

Answer 2

首先 - 我个人避免使用自定义分配器，因为我觉得它们不太合适。这不是一个很好的理由，您可能会得到 allocator-based 对您问题的回答，但我不会。（参见 Andrei Alexandrescu 在 CppCon 2015 中关于此事的演讲：std::allocator is to allocation what std::vector is to vexation）。

其次 - 如果您担心内存开销 - 您真的不应该使用 std::set，它有很多内存开销。它也很慢。

但即使忽略它 - 您可以通过不为每个设置项实例保留函数的副本来避免您提到的开销。毕竟 - 它们对所有对象都是一样的；所以您可以执行以下操作之一：

为 3 个指针设置静态变量，并确保在使用指针之前设置它们。如果您可以确保您永远不会同时使用具有不同功能的此类对象，那么这应该有效。
让每个实例都持有对另一个 class 的引用（= 单个指针），其中另一个 class 持有 3 个函数指针。您需要管理 3-pointer-holding class 的单个公共实例的生命周期，但这应该不会太糟糕。

替换 std::allocator 可以让 std::set 与 void* 一起使用并单独使用 copy/dealloc 函数吗？

Can replacing the std::allocator allow std::set to work with void* and separate copy/dealloc functions?

c++

stl

stdset

c++11