创作一个同时使用C++11和PMR分配器的容器

esyap4oy  于 2023-07-01  发布在  其他
关注(0)|答案(2)|浏览(91)

如何正确地创建一个同时使用C11和C17多态分配器的容器?以下是我目前所拥有的(作为通用样板模板):

说明:我已经包含了两个字段,res_显示了如何直接从容器管理动态内存,而字段vec_用于演示分配器如何向下传播。我从巴勃罗Halpern的演讲Allocators: The Good Parts中学到了很多,但他主要谈论pmr分配器,而不是c++11。

演示

#include <cstdio>
#include <vector>
#include <memory>
#include <memory_resource>

template <typename T, typename Allocator = std::allocator<T>>
struct MyContainer {

    auto get_allocator() const -> Allocator {
        return vec_.get_allocator();
    }

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

    MyContainer(T val, Allocator allocator = {})
        : MyContainer(allocator)
    {
        res_ = std::allocator_traits<Allocator>::allocate(allocator, sizeof(T));
        std::allocator_traits<Allocator>::construct(allocator, res_, std::move(val));
    }

    ~MyContainer() {
        Allocator allocator = get_allocator();
        std::allocator_traits<Allocator>::destroy(allocator, std::addressof(res_));
        std::allocator_traits<Allocator>::deallocate(allocator, res_, sizeof(T));
        res_ = nullptr;
    }

    MyContainer(const MyContainer& other, Allocator allocator = {})
        : MyContainer(allocator)
    {
        operator=(other);
    }

    MyContainer(MyContainer&& other) noexcept
        : MyContainer(other.get_allocator())
    {
        operator=(std::move(other));
    }

    MyContainer(MyContainer&& other, Allocator allocator = {})
        : MyContainer(allocator)
    {
        operator=(std::move(other));
    }

    auto operator=(MyContainer&& other) -> MyContainer& {
        if (other.get_allocator() == get_allocator()) {
            std::swap(*this, other);
        } else {
            operator=(other); // Copy assign
        }
    }

    auto operator=(const MyContainer& other) -> MyContainer& {
        if (other != this) {
            std::allocator_traits<Allocator>::construct(get_allocator(), std::addressof(vec_), vec_);
            std::allocator_traits<Allocator>::construct(get_allocator(), std::addressof(res_), other);
        }
        return *this;
    }
    
private:
    std::vector<T, Allocator> vec_; // Propagation
    T* res_ = nullptr;
};

int main() {
    MyContainer<std::string, std::pmr::polymorphic_allocator<std::byte>> ctr1 = std::string{"Hello World!"};

    MyContainer<double> ctr2 = 2.5;
}

然而,即使这样也不能按计划工作,因为vector期望其值类型与分配器的值类型相匹配:

<source>:67:31:   required from 'struct MyContainer<std::__cxx11::basic_string<char>, std::pmr::polymorphic_allocator<std::byte> >'
<source>:72:74:   required from here
/opt/compiler-explorer/gcc-13.1.0/include/c++/13.1.0/bits/stl_vector.h:438:64: error: static assertion failed: std::vector must have the same value_type as its allocator
  438 |       static_assert(is_same<typename _Alloc::value_type, _Tp>::value,
      |

我还漏掉了什么我是否应该根据分配器的传播特性进行不同的传播(通用容器需要这样做吗)?

eulz3vhy

eulz3vhy1#

tl;dr

  • 所有标准库容器都必须有一个分配器,其value_type与容器的value_type相同;否则它将是病态的。

因此在这种情况下,需要为MyContainer使用std::pmr::polymorphic_allocator<std::string>,或者在将分配器类型传递给std::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 = /* ... */;
  • 在您链接的the video中,这不是问题,因为它定义了一个用户定义的容器,所以它不是一个分配器感知的容器也没关系。
  • 实现一个可以同时处理std::polymorphic_allocatorstd::allocator的容器类相对容易--它们都满足指定的需求Allocator,所以在这种情况下所需要的特殊酱料只是不做任何特殊的事情--将它们实现为一个标准的分配器(基本上使用std::allocator_traits<Alloc>来处理与分配器的所有交互)
  • 这包括手动检查分配器的传播首选项(完全按照Allocator需求页面上的“Influence on container operations”表中的描述实现它们)

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

所有为allocator-aware container的容器必须有一个分配器,其value_type与容器的value_type相同。
本标准规定:(强调我的)
24.2.2.5 Allocator-aware containers(4)
(3)在本款中,
(3.1)- X表示具有Tvalue_type的分配器感知容器类,其使用A类型的分配器,
[...]如果X满足容器要求,并且以下类型、语句和表达式格式良好并具有指定的语义,则类型X满足可识别分配器的容器要求。
typename X::allocator_type

  • (4)结果:A
  • (5)任务:allocator_type​::​value_typeX​::​value_type相同。

所以下面的语句对于allocator-aware容器必须始终为真:

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

请注意,标准库中定义的所有容器(std::array除外)都必须是分配器感知的。(参见24.2.2.5(1)Allocator-aware容器)
请注意,在您的示例中,该语句将不满足:

// 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 Video(CppCon 2017:巴勃罗Halpern“分配器: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_type被硬编码为std::pmr::polymorphic_allocator<std::byte>,因此allocator_type::value_type通常不会匹配slist::value_type(除了两者都是std::byte的情况);
所以这个容器在大多数情况下不能满足allocator-aware container的要求。
但也没有要求它这样做。
=>格式良好
注意:如果一个人通过了,那将是病态的。slist<>到一个函数,该函数要求其参数必须是一个分配器感知的容器。- 但是只要避免定义几乎一致的容器就没有问题。

3.如何写一个可以和任何分配器一起工作的容器

注意,std::pmr::polymorphic_allocator满足指定的需求Allocator,就像std::allocator一样。
(All用于标准容器的分配器必须满足该要求)
因此,支持这两种分配器的技巧就是不做任何特殊的事情--像对待任何其他分配器一样对待std::pmr::polymorphic_allocator,因为它就是这样。(基本上所有内容都使用std::allocator_traits<Alloc>
请注意,这也意味着您应该遵守std::allocator_traits<Allocator>::propagate_on_container_copy/container_move_assignment/container_swap值。
这对于polymorphic_allocator意味着分配器在复制/移动/交换容器时不应该**传播。
因为这样做可能会导致令人惊讶的生命周期问题-例如参见this answer
(Of当然,应该始终尊重这些,而不仅仅是polymorphic_allocator s)

oxf4rvwz

oxf4rvwz2#

我花了最后一天的时间收集了所有关于分配器的资源,并提出了一个通用的设计。我会把它写在这里,也许有人会发现它很有用。

泛型类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;
}

注意事项:

一般形状:

  • 容器接受分配器类型模板参数,这必然意味着使用不同分配器类型的容器将是完全不同的类型(这意味着它们根本不能相互移动/复制/交换)。
  • 所有的资源管理(分配/释放内存+构造/销毁对象)都必须通过分配器接口std::allocator_traits<Allocator>来完成。你永远不能直接使用allocator->allocate(),因为std::allocator_traits甚至为std::allocator<T>(默认分配器)提供了默认值,这些默认值在类型中不一定可用!
  • 分配器的私有继承允许空基优化,因此无状态分配器不会占用空间(注意stl容器有时将分配器存储在sentinel节点/未占用的数据部分)。这需要一个非常量分配器&通过get_alloc_()中的static_cast可检索;

分配器传播:

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

  • move:如果propagate_on_container_move_assignment::value为true,则B.allocator将被移动分配给a.allocator
  • copy:如果propagate_on_container_copy_assignment::value为true,则B.allocator将被复制到a.allocator
  • swap:如果propagate_on_container_swap::value为true,则a.allocator将与b.allocator交换

构造函数

  • 构造函数通常可以很容易地通过赋值操作符和委托构造函数来实现,后者占用了可选的分配器参数。
  • 移动操作符需要是双重的,因为在某些情况下,移动不能是noexcept(在分配器不同的情况下,移动赋值操作符需要将数据复制到可能抛出的新内存竞技场)。只有当分配器是相同的(运行时检查)或者分配器被故意复制(在这种情况下,我们知道它是相同的)时,才可能执行Noexcept move。

移动赋值

看看霍华德·欣南特的精彩answer在这里。

  • 问题:容器元素由一个容器分配,在移动后由另一个容器释放。如果不同的分配器在一个元素上执行分配/解除分配,这就是正式的UB!
  • 如果分配器从一开始就相同,或者我们知道其他的.allocator传播给我们(可以在编译时检查,alloc_traits::propagate_on_container_move_assignment::value为true),这是没有问题的,我们可以移动。
  • 但是如果分配器不匹配,并且其他的.allocator没有传播,我们必须使用分配器将构造的所有元素复制到新的内存竞技场。

副本分配

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

swap

  • Swap必须永远不会抛出(根据标准总是noexcept),因此我们不能做花哨的复制(因为这会分配/构造可能抛出的东西)。这意味着只有当分配器相同或在swap(alloc_traits::propagate_on_container_swap)上传播时,才有可能真正交换。
  • 我们可以选择在这里Assert(就像libstdc++所做的那样),但这可能会阻碍有经验的用户确保他的两个分配器相互工作,所以我的想法是让用户自己定义好容器。
  • 包括ADL发现的朋友交换,以便我们符合惯用的 * 非限定 * 交换原则。
  • 需要一个内部函数swap_data(),它只交换容器的内部,而不交换分配器,因为分配器是有条件交换的。

noexcept

  • 除非标准中有定义(§23.2.1[容器.要求.概述]第8节和第10节),否则Swap始终为no。Swap将 * 假定 * 使用noexcept通过对成员字段的非限定交换调用来交换内部成员字段。
  • 只有当propagate_on_container_move_assignment::valueis_nothrow_move_assignable<allocator_type>::value的计算结果都为true时,移动赋值运算符才可以标记为noexcept(因为分配器也被移动到了case中的新对象)。
  • 拷贝分配/构造永远不能保证noexcept,因为它分配和构造新元素,即请求系统内存并调用构造函数。理论上只有当容器仍然为空时才可以是noexcept,但C++不支持运行时检查。
  • 移动构造函数只能是noexcept,如果我们知道分配器是相同的,我们可以noexcept移动元素,因此我们包括一个扩展的移动ctor,它不能保证,因为它需要一个分配器参数离开默认的移动ctor noexcept。扩展的移动对象可以是no,除非分配器比较相等,但C++不支持运行时检查。

异常安全,copy & swap:

  • copy & swap -习惯用法不能在stl兼容的分配器感知容器中使用,因为该习惯用法预见到基于复制/移动构造函数实现赋值操作符。但是,分配器传播特性在复制/移动分配之间可能不同,因此需要将它们分开。但是,对于move_assign_()-方法中不包括分配器的字段,仍然可以实现复制和交换。
  • 只能给出基本的异常安全性(这是stl容器的标准)。

未解决问题:

  • 从理论上讲,一个对象是用某个分配器复制/移动构造的,然后马上从另一个对象切换到一个传播分配器,这可能吗?(潜在优化点)。
  • 是否有必要包括一个额外的分支来检查自我分配(注:该分支将被复制ctor重复,因为它委托给operator=(&))?
  • 在noexcept move的情况下,由于我们委托给operator=(&&),因此我们在运行时分配器相等时可能效率低下。可以直接调用move_assign_吗?
  • 如果分配器无论如何传播或比较总是相等,则具有扩展移动构造函数的noexcept移动看起来是有条件可能的。
  • 在其他核心数据也存储分配器(例如,分配器102)的情况下,核心数据102可以被配置为存储分配器104。是一个stl-container),我们可以将分配器推到叶子节点,并从那里检索它以保存缓存。要做到这一点,容器层次结构中的分配器必须始终匹配(我必须进一步研究这一点,以确保上面的实现是这样的!)

也许有人能帮我回答最后几个问题!

版本1

我添加了改变了的东西,浮现在脑海中:

  • cppreference说明noexcept函数可以调用抛出异常的函数。我用这个来委托给扩展的移动ctor,而不会失去优化(为了简洁):

注意,函数上的noexcept规范不是编译时检查;它仅仅是程序员通知编译器函数是否应该抛出异常的一种方法。

  • 我调整了资源分配。以前我只有一个空的assign()函数,但是ofc需要实现。
  • 修复了一些开销:--在销毁的情况下为res指针置空--无论如何传播分配器时,在移动构造时检查分配器相等性。
  • 修复bug:我注意到我不能从构造函数委托给赋值,因为这将检查传播特性(这允许使用一个分配器构造然后立即从另一个对象传播分配器的奇怪行为)
  • 我现在也使用了copy & swap习惯用法来进行复制赋值,它摆脱了额外的free_res_()函数并增加了异常安全性。我将不得不再次检查,但我认为分配现在有很强的异常安全性。
  • 使用C++20特性no_unique_address作为一种更优雅的方式来处理空分配器类型的分配器存储。

来源:

相关问题