考虑到复制构造的要求,如何在C++ 11中编写有状态分配器？

Question

据我所知,对于与STL容器一起使用的分配器的要求在C++ 11标准的第17.6.3.5节的表28中列出.

我对其中一些要求之间的相互作用感到有些困惑.给定一个类型X是类型分配器T,一类Y是"相应的allocator类"的类型U,实例a,a1和a2中 X,和实例b的Y,表说:

1. 表达式仅在分配的存储可以被解除分配时a1 == a2评估,反之亦然.truea1a2

2. 表达式X a1(a);格式正确,不会通过异常退出,之后a1 == a也是如此.

3. 表达式X a(b)格式正确,不会通过异常退出,然后退出a == b.

我读到这一点时说,所有分配器必须是可复制构造的,使得副本可以与原件互换.更糟糕的是,跨类型边界也是如此.这似乎是一个非常繁重的要求; 据我所知,它使大量类型的分配器变得不可能.

例如,假设我有一个我想在我的分配器中使用的freelist类,以便缓存释放的对象.除非我遗漏了某些东西,否则我无法在分配器中包含该类的实例,因为大小或对齐的T和U可能不同,因此freelist条目不兼容.

我的问题:

1. 我的解释是否正确？

2. 我在一些地方读到C++ 11改进了对"有状态分配器"的支持.考虑到这些限制,情况如何？

3. 你有什么建议可以做我想做的事吗？也就是说,如何在分配器中包含特定于分配类型的状态？

4. 一般来说,分配器周围的语言似乎很草率.(例如,表28的序言假设它a是类型X&,但某些表达式重新定义a.)此外,至少GCC的支持是不符合的.分配器周围的这种奇怪的原因是什么？它只是一个不经常使用的功能吗？

Answer 1

分配器的平等并不意味着它们必须具有完全相同的内部状态,只是它们必须能够释放分配给任一分配器的内存.十字型分配器的平等a == b于分配器a型的X和分配器b类型的Y如表28定义为"相同a == Y::template rebind<T>::other(b)".换句话说,a == b如果分配的内存a可以由重新绑定b到a的实例化的分配器解除分配value_type.

您的freelist分配器无需释放任意类型的节点,您只需要确保分配的内存FreelistAllocator<T>可以被释放FreelistAllocator<U>::template rebind<T>::other.鉴于这FreelistAllocator<U>::template rebind<T>::other与FreelistAllocator<T>大多数理智的实现中的类型相同,这很容易实现.

简单的例子(Coliru的现场演示):

template <typename T>
class FreelistAllocator {
    union node {
        node* next;
        typename std::aligned_storage<sizeof(T), alignof(T)>::type storage;
    };

    node* list = nullptr;

    void clear() noexcept {
        auto p = list;
        while (p) {
            auto tmp = p;
            p = p->next;
            delete tmp;
        }
        list = nullptr;
    }

public:
    using value_type = T;
    using size_type = std::size_t;
    using propagate_on_container_move_assignment = std::true_type;

    FreelistAllocator() noexcept = default;
    FreelistAllocator(const FreelistAllocator&) noexcept {}
    template <typename U>
    FreelistAllocator(const FreelistAllocator<U>&) noexcept {}
    FreelistAllocator(FreelistAllocator&& other) noexcept :  list(other.list) {
        other.list = nullptr;
    }

    FreelistAllocator& operator = (const FreelistAllocator&) noexcept {
        // noop
        return *this;
    }

    FreelistAllocator& operator = (FreelistAllocator&& other) noexcept {
        clear();
        list = other.list;
        other.list = nullptr;
        return *this;
    }

    ~FreelistAllocator() noexcept { clear(); }

    T* allocate(size_type n) {
        std::cout << "Allocate(" << n << ") from ";
        if (n == 1) {
            auto ptr = list;
            if (ptr) {
                std::cout << "freelist\n";
                list = list->next;
            } else {
                std::cout << "new node\n";
                ptr = new node;
            }
            return reinterpret_cast<T*>(ptr);
        }

        std::cout << "::operator new\n";
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }

    void deallocate(T* ptr, size_type n) noexcept {
        std::cout << "Deallocate(" << static_cast<void*>(ptr) << ", " << n << ") to ";
        if (n == 1) {
            std::cout << "freelist\n";
            auto node_ptr = reinterpret_cast<node*>(ptr);
            node_ptr->next = list;
            list = node_ptr;
        } else {
            std::cout << "::operator delete\n";
            ::operator delete(ptr);
        }
    }
};

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

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

Answer 2

1)我的解释是否正确？

你是对的,你的自由列表可能不适合分配器,它需要能够处理多种尺寸(和对齐)以适应.这是解决自由列表的问题.

2)我在一些地方读到C++ 11改进了对"有状态分配器"的支持.考虑到这些限制,情况如何？

与出生相比,它没有那么多改进.在C++ 03中,标准只推动实现者提供可支持非平等实例和实现者的分配器,从而有效地使有状态分配器成为非可移植的.

3)你对如何做我想做的事有什么建议吗？也就是说,如何在分配器中包含特定于分配类型的状态？

您的分配器可能必须是灵活的,因为您不应该确切地知道应该分配哪些内存(以及哪些类型).此要求对于将您(用户)与使用分配器的某些容器(如std::list,std::set或)的内部隔离是必要的std::map.

您仍然可以将这些分配器与简单容器一起使用,例如std::vector或std::deque.

是的,这是一项昂贵的要求.

4)一般来说,分配器周围的语言似乎很草率.(例如,表28的序言表示假设a是类型X&,但是某些表达式重新定义了a.)此外,至少GCC的支持是不符合的.分配器周围的这种奇怪的原因是什么？它只是一个不经常使用的功能吗？

一般而言,标准不容易阅读,不仅仅是分配器.你必须要小心.

要谨慎,gcc不支持allocators(它是一个编译器).我猜你说的是libstdc ++(gcc附带的标准库实现).libstdc ++很旧,因此它是为C++ 03量身定制的.它已经适应了C++ 11,但还不完全一致(例如,仍然使用Copy-On-Write作为字符串).原因是libstdc ++非常注重二进制兼容性,C++ 11所需的一些更改会破坏这种兼容性; 因此,必须仔细介绍它们.

Answer 3

我读到这一点时说,所有分配器必须是可复制构造的,使得副本可以与原件互换.更糟糕的是,跨类型边界也是如此.这似乎是一个非常繁重的要求; 据我所知,它使大量类型的分配器变得不可能.

如果分配器是一些内存资源的轻量级句柄,那么满足要求是微不足道的.只是不要尝试将资源嵌入单个分配器对象中.

例如,假设我有一个我想在我的分配器中使用的freelist类,以便缓存释放的对象.除非我遗漏了某些内容,否则我无法在分配器中包含该类的实例,因为T和U的大小或对齐可能不同,因此freelist条目不兼容.

[allocator.requirements]第9段:

分配器可以约束可以实例化的类型以及construct可以调用其成员的参数.如果某个类型不能与特定分配器一起使用,则分配器类或调用construct可能无法实例化.

您的分配器可以拒绝为除给定类型之外的任何内容分配内存T.这将阻止它在基于节点的容器中使用,例如std::list需要分配自己的内部节点类型(不仅仅是容器value_type),但它可以正常工作std::vector.

这可以通过防止分配器被反弹到其他类型来完成:

class T;

template<typename ValueType>
class Alloc {
  static_assert(std::is_same<ValueType, T>::value,
    "this allocator can only be used for type T");
  // ...
};

std::vector<T, Alloc<T>> v; // OK
std::list<T, Alloc<T>> l;   // Fails

或者您只能支持适合的类型sizeof(T):

template<typename ValueType>
class Alloc {
  static_assert(sizeof(ValueType) <= sizeof(T),
    "this allocator can only be used for types not larger than sizeof(T)");
  static_assert(alignof(ValueType) <= alignof(T),
    "this allocator can only be used for types with alignment not larger than alignof(T)");

  // ...
};

1. 我的解释是否正确？

不是完全.

2. 我在一些地方读到C++ 11改进了对"有状态分配器"的支持.考虑到这些限制,情况如何？

C++ 11之前的限制更糟糕!

现在清楚地说明了分配器在复制和移动时如何在容器之间传播,以及当分配器实例被可能与原始数据不等的不同实例替换时,各种容器操作如何表现.如果没有这些说明,如果你用有状态的分配器交换了两个容器,就不清楚应该发生什么.

3. 你有什么建议可以做我想做的事吗？也就是说,如何在分配器中包含特定于分配类型的状态？

不要将它直接嵌入到分配器中,单独存储它并让分配器通过指针引用它(可能是智能指针,具体取决于你如何设计资源的生命周期管理).实际的allocator对象应该是一些外部内存源的轻量级句柄(例如竞技场,游戏池或管理空闲列表的东西).共享相同源的Allocator对象应该相等,即使对于具有不同值类型的分配器也是如此(见下文).

我还建议你不要尝试支持所有类型的分配,如果你只需要支持它.

4. 一般来说,分配器周围的语言似乎很草率.(例如,表28的序言说假设a是X&类型,但是有些表达式重新定义了a.)

是的,正如您在https://github.com/cplusplus/draft/pull/334上报道的那样(谢谢).

此外,至少GCC的支持是不符合要求的.

它不是100%,而是将在下一个版本中.

分配器周围的这种奇怪的原因是什么？它只是一个不经常使用的功能吗？

是.并且有许多历史包袱,并且很难指定广泛有用.我的ACCU 2012演示文稿有一些细节,如果读完之后我会非常惊讶你认为你可以让它变得更简单;-)

关于分配器何时比较相等,请考虑:

MemoryArena m;
Alloc<T> t_alloc(&m);
Alloc<T> t_alloc_copy(t_alloc);
assert( t_alloc_copy == t_alloc ); // share same arena
Alloc<U> u_alloc(t_alloc);
assert( t_alloc == u_alloc ); // share same arena
MemoryArena m2
Alloc<T> a2(&m2);
assert( a2 != t_alloc ); // using different arenas

分配平等的含义是,物体可以释放彼此的记忆,因此,如果您分配一些内存t_alloc,并(t_alloc == u_alloc)是true,那么就意味着你可以使用解除分配内存u_alloc.如果它们不相等,u_alloc就无法释放来自的记忆t_alloc.

如果你只有一个freelist,其中任何内存都可以添加到任何其他freelist,那么也许所有的allocator对象都会相互比较.