编写容器以同时使用 c++11 和 pmr 分配器

tl;博士

• 必须为所有标准库容器提供一个分配器，其 a 与容器的分配器相同;否则，它将是格式错误的。
  因此，在这种情况下，需要使用 for ，或者在将分配器类型传递给 之前重新绑定分配器类型，例如：value_typevalue_typestd::pmr::polymorphic_allocator<std::string>MyContainerstd::vector

  // option 1
  MyContainer<std::string, std::pmr::polymorphic_allocator<std::string>> ctr1 = /* ... */;
  
  // option 2
  template <class T, class Allocator = std::allocator<T>>
  struct MyContainer {
      // ...
  private:
      std::vector<T, typename std::allocator_traits<Allocator>::template rebind_alloc<T>> vec_;
  };
  
  MyContainer<std::string, std::pmr::polymorphic_allocator<std::byte>> ctr1 = /* ... */;
  

• 这在您链接的视频中不是问题，因为它定义了一个用户定义的容器，因此它不是分配器感知容器并不重要。
• 实现一个可以同时处理两者并且相对容易的容器类 - 两者都满足命名要求 Allocator，因此在这种情况下需要的特殊调味只是不做任何特殊的事情 - 将它们实现为沼泽标准分配器（基本上用于与分配器的所有交互）std::polymorphic_allocatorstd::allocatorstd::allocator_traits<Alloc>
  • 这包括手动检查分配器的传播首选项（完全按照分配器要求页面上的“对容器操作的影响”表中所述实现它们）

---

1. 为什么给定的代码示例格式不正确

所有可识别分配器的容器都必须具有与容器相同的分配器。value_typevalue_type

这是标准中规定的：（强调我的）

24.2.2.5 分配器感知容器 （4） （3） 在本子句中，^（3.1）
- 表示一个分配器感知容器类，其 a 使用类型为
， [...]
如果满足容器要求，并且以下类型、语句和表达式格式正确且具有指定的语义，则类型满足分配器感知容器要求。Xvalue_typeTAXX

typename X::allocator_type

• ^（4） 结果：A
• ^（5） 任务：allocator_type：：value_type 与 X：：value_type 相同。

因此，对于可识别分配器的容器，以下语句必须始终为 true：

static_assert(
    std::same_as<
        Container::value_type,
        Container::allocator_type::value_type
    >
);

---

请注意，标准库中定义的所有容器（除了 ）都必须具有分配器感知能力。（见24.2.2.5（1）可识别分配器的容器std::array)

---

请注意，在您的示例中，该语句将不被满足：

// Hypothetical, won't compile
using Container = std::vector<std::string, std::pmr::polymorphic_allocator<std::byte>>;

// will be std::string
using ContainerValueType = Container::value_type;
// will be std::byte (std::pmr::polymorphic_allocator<std::byte>::value_type)
using AllocatorValueType = Container::allocator_type::value_type;

// would fail
static_assert(std::same_as<ContainerValueType, AllocatorValueType>);

• 因此，此版本不会是可识别分配器的容器（因为它不满足此要求）std::vector
• 但标准要求必须是可识别分配器的容器std::vector

=> 由于标准中的矛盾，这是格式不正确的。

请注意，这也与您从 gcc 收到的错误消息相匹配：

error: static assertion failed: std::vector must have the same value_type as its allocator

---

2.为什么链接的视频不是问题

您在评论中链接的 Youtube 视频（CppCon 2017：Pablo Halpern “Allocators： The Good Parts”）是关于用户定义的容器类，该类不使用任何标准库容器。

该标准没有对用户定义的容器类型施加任何规则，因此人们基本上可以在那里做任何想做的事情。

以下是演讲所讨论的课程的简短记录：

template<class Tp>
class slist {
public:
  using value_type = Tp;
  using reference = value_type&;
  // ...
  // non-template use of polymorphic_allocator
  using allocator_type = std::pmr::polymorphic_allocator<std::byte>;

  // Constructors
  // Every constructor has an variant taking an allocator
  slist(allocator_type a = {});
  slist(const slist& other, allocator_type a = {});
  slist(slist&& other);
  slist(slist&& other, allocator_type a = {});

  // ...
};

请注意，被硬编码为 ，因此通常不匹配（除非两者都是allocator_typestd::pmr::polymorphic_allocator<std::byte>allocator_type::value_typeslist::value_typestd::byte);

因此，此容器在大多数情况下都不满足分配器感知容器的要求。
但它也没有要求这样做。
=> 格式正确

^{注意：如果将 slist<> 传递给一个要求其参数必须是分配器感知容器的函数，则格式不正确。- 但是，只要避免这种情况，定义几乎符合要求的容器就没有问题。}

---

3. 如何编写一个与任何分配器一起使用的容器

请注意，满足命名要求 Allocator，与此完全相同。
（所有打算与标准容器一起使用的分配器都必须满足该要求）std::pmr::polymorphic_allocatorstd::allocator

因此，支持两者的诀窍就是不做任何特别的事情 - 像对待任何其他分配器一样对待它，因为它就是这样。（基本上用于所有东西）std::pmr::polymorphic_allocatorstd::allocator_traits<Alloc>

请注意，这也意味着您应该尊重 / / 值。
这意味着分配器在复制/移动/交换容器时不应传播。
因为这样做会导致令人惊讶的生命周期问题 - 例如，请参阅此答案。std::allocator_traits<Allocator>::propagate_on_container_copycontainer_move_assignmentcontainer_swappolymorphic_allocator

（当然，这些应该始终得到尊重，而不仅仅是为了s）polymorphic_allocator

我花了最后一天的时间收集了我找到的有关分配器的任何资源，并提出了一个通用设计。我会在这里发布它，有人可能会觉得它有帮助。

通用的类似 stl 的分配器感知容器实现

演示

#include <cstdio>
#include <vector>
#include <memory>
#include <memory_resource>
#include <type_traits> /* is_nothrow_swappable */


template <typename T, typename Allocator = std::allocator<T>>
struct MyContainer {
    using allocator_type = Allocator;
    using alloc_traits = typename std::allocator_traits<Allocator>;

    auto get_allocator() const -> Allocator& {
        return allocator_;
    }

    MyContainer(Allocator allocator = {})
        : vec_{ allocator }
    {}

    MyContainer(T val, Allocator allocator = {})
        : MyContainer(allocator)
    {
        res_ = alloc_traits::allocate(allocator_, sizeof(T));
        alloc_traits::construct(allocator_, res_, std::move(val));
    }

    ~MyContainer() {
        if (res_) {
            alloc_traits::destroy(allocator_, res_);
            alloc_traits::deallocate(allocator_, res_, sizeof(T));
        }
    }

    MyContainer(const MyContainer& other, Allocator allocator = {})
        : MyContainer(allocator)
    {
        // Copy resource
        res_ = alloc_traits::allocate(allocator_, sizeof(T));
        alloc_traits::construct(allocator_, res_, *other.res_);
        // Copy types with value semantics
        vec_ = other.vec_;
    }

    MyContainer(MyContainer&& other) noexcept
        : MyContainer(std::move(other), other.get_allocator())
    {}

    MyContainer(MyContainer&& other, Allocator allocator = {})
        : MyContainer(allocator)
    {
        // Move resource
        res_ = std::move(other.res_);
        other.res_ = nullptr;
        // Move types with value semantics
        vec_ = std::move(other.vec_);
    }

    auto operator=(MyContainer&& other) noexcept(
            std::conjunction_v<alloc_traits::propagate_on_container_move_assignment,
            std::is_nothrow_move_assignable<Allocator>>) -> MyContainer&
    {
        if constexpr(std::disjunction_v<
            typename alloc_traits::propagate_on_container_move_assignment,
            typename alloc_traits::is_always_equal>)
        {
            MyContainer tmp{ std::move(other), allocator_ };
            swap_data_(tmp);
            allocator_ = std::move(other.allocator_);
        } else {
            if (allocator_ != other.allocator_) {
                // Must copy
                MyContainer tmp{ other, allocator_ };
                swap_data_(tmp);
            } else {
                MyContainer tmp{ std::move(other), allocator_ };
                swap_data_(tmp);
            }
        }
        return *this;
    }

    auto operator=(const MyContainer& other) -> MyContainer& {
        // copy construct from other with our allocator
        MyContainer tmp(other, allocator_);
        swap_data_(tmp);
        if constexpr (alloc_traits::propagate_on_container_copy_assignment::value) {
            allocator_ = other.allocator_;
        }
        return *this;
    }

    auto swap(MyContainer& other) noexcept -> void {
        // UB in case propagate_on_container_swap is true and allocators are not the same
        // However no assert triggered as this could be weirdly intended by a knowing user
        swap_data_(other);
        if constexpr (alloc_traits::propagate_on_container_swap) {
            swap(allocator_, other.allocator_); // Swap always noexcept
        }
    }

    friend auto swap(MyContainer& lhs, MyContainer& rhs) -> void {
        lhs.swap(rhs);
    }
    
private:

    auto swap_data_(MyContainer& other) noexcept {
        // TBAA information for compiler optimization will not be lost unless
        // unqualified swap uses XOR swap semantics.
        swap(other.res_, res_);
        swap(other.vec_, vec_);
    }

    std::vector<T, Allocator> vec_; // To model propagation
    T* res_ = nullptr;
#ifdef _MSC_VER
    [[msvc::no_unique_address]]
#else
    [[no_unique_address]]
#endif
    Allocator allocator_;
};

int main() {
    // MyContainer<int, std::pmr::polymorphic_allocator<int>> ctr1 = 5;
    MyContainer<std::string, std::pmr::polymorphic_allocator<std::string>> ctr1 = std::string{"Hello World!"};
    MyContainer<double> ctr2 = 2.5;
}

笔记：

一般形状：

• 容器采用分配器类型模板参数，这必然意味着使用不同分配器类型的容器将完全是不同的类型（这意味着它们根本无法相互移动/复制/交换）。
• 所有资源管理（分配/释放内存 + 构建/销毁对象）都必须通过 分配器接口 完成。你永远不能直接使用 allocator->allocate（） 作为默认值，即使是 （默认分配器） 在类型中不一定可用！std::allocator_traits<Allocator>std::allocator_traitsstd::allocator<T>
• 来自分配器的私有继承允许空基础优化，因此无状态分配器不会占用空间（注意：STL-Containers 有时会将分配器存储在 Sentinel 节点/未占用的数据部分中）。这需要一个非常量分配器&，以便通过 static_cast in 进行检索get_alloc_();

分配器传播：

不幸的是，分配器有一个自定义点，允许它们在移动、复制和交换这三个操作中传播到其他容器，事后看来，这只会造成伤害，但如果我们想符合 stl，我们需要考虑以下情况：

• move： b.allocator 将在 true 的情况下将 move 分配给 a.allocatorpropagate_on_container_move_assignment::value
• copy： 如果为 true，b.allocator 将被复制到 a.allocatorpropagate_on_container_copy_assignment::value
• 交换：如果为 true，a.allocator 将与 b.allocator 交换propagate_on_container_swap::value

构造 函数

• 构造函数通常可以很容易地通过赋值运算符和委托构造函数来实现，这会吞噬可选的分配器参数。
• 移动 ctor 需要双重，因为在某些情况下，move 不能是 noexcept （如果分配器不同，移动分配运算符需要将数据复制到新的内存领域，这可能会抛出）。Noexcept 只有在分配器相同（运行时检查）或分配器被故意复制（在这种情况下，我们知道它是相同的）时才有可能移动。

移动分配

在这里查看霍华德·辛南特（Howard Hinnant）的精彩回答。

• 问题：容器元素由一个容器分配，移动后由另一个容器解除分配。如果不同的分配器对一个元素执行分配/取消分配，则正式称为 UB！
• 如果分配器从一开始就是相同的，或者我们知道other.alloator传播给我们（可以在编译时检查，是真的），这没问题，我们可以移动。alloc_traits::propagate_on_container_move_assignment::value
• 但是，如果分配器不匹配并且 other.allocator 没有传播，我们必须使用我们的分配器将构造的所有元素复制到新的内存领域。

复制分配

• 如果计算结果为 true，则首先复制分配器。alloc_traits::propagate_on_container_copy_assignment::value
• 然后，从另一个容器复制分配所有元素。

交换

• 交换绝不能抛出（根据标准，除非始终是无），因此我们不能做花哨的复制东西（因为这会分配/构造可以抛出的东西）。这意味着只有当分配器相同或在交换 （） 上传播时，才有可能真正进行交换。alloc_traits::propagate_on_container_swap
• 我们可以选择在这里断言（就像 libstdc++ 所做的那样），但这可能会阻碍有经验的用户确保他的两个分配器相互协作，所以我的看法是将其留给用户来定义他的容器。
• 包括 ADL 发现的好友交换，以便我们符合惯用的不合格交换原则。
• 需要一个内部函数 swap_data（），它只交换容器的内脏，而不使用分配器，因为分配器是有条件交换的。

不除了

• 交换始终为 no，除非标准定义 （§23.2.1[container.requirements.general] 第 8 节和第 10 节） 。Swap 可能会使用 noexcept move 通过对成员字段的非限定交换调用来交换内部成员字段。
• 仅当 和 的计算结果均为 true 时，才能将移动赋值运算符标记为 noexcept （因为分配器也会移动到新对象以防万一）。propagate_on_container_move_assignment::valueis_nothrow_move_assignable<allocator_type>::value
• 复制分配/构造永远无法保证，因为它分配和构造新元素，即请求系统内存并调用构造函数。理论上可以 除非容器仍为空，否则为 no，但 C++ 不支持运行时检查。noexcept
• 移动构造函数只能是 no，除非我们知道分配器是相同的并且我们可以移动元素，因此我们包含一个扩展的 move ctor 不能保证这一点，因为它需要分配器参数才能保留默认的 move ctor 。扩展移动 ctor 可以是 no，除非分配器比较相等但 C++ 不支持运行时检查。noexceptnoexcept

异常安全、复制和交换：

• copy & swap - 惯用语不能用于符合 stl 的 allocater 感知容器，因为该惯用语预见到基于 copy/move 构造函数实现赋值运算符。但是，复制/移动分配之间的分配器传播特征可能不同，因此需要将它们分开。但是，仍然可以对 -method 中不包括分配器的字段实现复制和交换。move_assign_()
• 只能给出基本的例外安全性（这是 stl 容器的标准）。

未解决的问题：

• 从理论上讲，一个对象是否有可能使用某个分配器进行复制/移动构造，然后立即从另一个对象切换到传播分配器？（潜在优化点）。
• 是否有必要包含一个额外的分支来检查自分配（注意：当它委托给 operator=（&） 时，复制 ctor 会重复该分支）？
• 由于我们委托给 operator=（&&），因此在 noexcept move 的情况下，我们在分配器相等性上运行时调度可能效率低下。也许直接打电话给move_assign_？
• noexcept 如果分配器无论如何都传播或比较始终相等，则带有扩展移动构造函数的移动看起来有条件地可能。
• 如果其他核心数据也存储了分配器（例如，是一个 stl-container），我们可以将分配器推送到叶子并从那里检索它以保存缓存。为此，容器层次结构中的分配器必须始终匹配（我必须对此进行更多研究，以确保上述实现就是这种情况！

也许有人可以帮助我解决最后一个问题！

修订版 1

我添加了我想到的改变的东西：

• cppreference 表示 noexcept 函数可能会调用引发异常的函数。我用它来委托给扩展的移动 ctor 而不会丢失优化（为了简洁）：

请注意，函数的 noexcept 规范不是编译时 检查;它只是程序员通知编译器的一种方法 函数是否应引发异常。

• 我固定了资源分配。以前我只有一个空的 assign（） 函数，但这需要实现。
• 修复了一些开销： -- 在销毁时将 res 指针清空 -- 在移动构造时检查分配器是否相等，当分配器无论如何都传播时。
• 修复错误：我注意到我无法从构造函数委托给分配，因为这将检查传播特征（这允许使用一个分配器构建然后立即从另一个对象传播分配器的奇怪行为）
• 我现在也使用复制和交换习语进行复制分配，它摆脱了额外的功能并增加了异常安全性。我将不得不再次检查，但我认为分配现在具有很强的异常安全性。free_res_()
• 使用 C++ 20 功能作为解决空分配器类型的分配器存储的更优雅的方法。no_unique_address

来源：

• AllocatorAwareContainer：propagate_on_container_XXX默认值的介绍和陷阱
• 当涉及分配器时，是否有类似于复制和交换习语的东西？
• libstdc++ 向量
• libc++ 向量