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

Question

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

我对其中一些要求之间的相互作用感到有些困惑。给定X类型为T类型的分配器，Y类型为U类型的“相应分配器类”，a实例为a1，a2和X，b为Y实例，表中说：

1. 表达式a1 == a2仅在true分配的存储可以由a1解除分配时评估为a2，反之亦然。
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

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 2

分配器的平等并不意味着它们必须具有完全相同的内部状态，只是它们必须能够释放分配给任一分配器的内存。 a == b类型的分配器a和X类型的分配器b的分配器Y的交叉类型相等在表28中定义为“与a == Y::template rebind<T>::other(b)相同”。换句话说，如果由a == b分配的内存可以通过重新绑定a实例化到Qazxswpoi的b的分配器来释放a。

你的freelist分配器不需要能够解除分配任意类型的节点，你只需要确保value_type分配的内存可以被FreelistAllocator<T>解除分配。鉴于在大多数理智的实现中FreelistAllocator<U>::template rebind<T>::other与FreelistAllocator<U>::template rebind<T>::other的类型相同，这很容易实现。

简单的例子（FreelistAllocator<T>）：

Live demo at Coliru

Answer 3

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

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

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

[allocator.requirements]第9段：

分配器可以约束可以实例化的类型以及可以调用其

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;
}

成员的参数。如果某个类型不能与特定分配器一起使用，则分配器类或对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)

1. 我的解释是否正确？

不是完全。

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

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

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

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

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

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

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

是的，正如你在

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)");

  // ...
};

报道的那样（谢谢）。

此外，至少GCC的支持是不符合要求的。

它不是100％，而是将在下一个版本中。

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

是。并且有许多历史包袱，并且很难指定广泛有用。我的https://github.com/cplusplus/draft/pull/334有一些细节，如果读完之后我会非常惊讶你认为你可以让它变得更简单;-)

---

关于分配器何时比较相等，请考虑：

ACCU 2012 presentation

分配器等式的含义是对象可以释放彼此的内存，所以如果你从

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的记忆。

如果您只有一个空闲列表，其中任何内存可以添加到任何其他空闲列表，那么也许您的所有分配器对象将相互比较相等。