C++ 标准分配器：简介与实现
4.91/5 (24投票s)
介绍分配器概念，以及实现一个策略驱动的分配器模板类
引言
在大多数 C++ 教学中，STL 分配器是最容易被忽略的主题之一。它们很少被显式使用，无论是通过直接的客户端代码，还是通过直接构造一个在容器中使用的分配器。你可能唯一会注意到“分配器”这个词的地方，是当你使用 STL 容器类时，会疑惑那个最后的参数 (Allocator) 到底是什么。
在本文中，我将解释分配器的目的，什么算作标准的 C++ 分配器，如何实现一个分配器，以及可能的用法和扩展。
C++ 标准的目的
根据 [Josuttis 1999] 的描述，
....分配器最初作为 STL 的一部分引入，用于处理 PC 上各种指针类型（如 near、far 和 huge 指针）的棘手问题。现在，它们可以作为使用特定内存模型的底层技术解决方案，例如共享内存、垃圾回收和面向对象数据库，而无需更改接口。然而，这种用法相对较新，尚未被广泛采用……分配器代表了一种特殊的内存模型，并被用作一种抽象，将使用内存的需求转化为对内存的原始调用。它们提供了一个分配、创建、销毁和释放对象的接口。通过分配器，容器和算法可以根据元素的存储方式进行参数化。例如，你可以实现使用共享内存的分配器，或者将元素映射到持久数据库的分配器……
事实上，[C++] 中关于分配器信息非常少。它们都归结为两个部分：20.1.5 分配器要求 [lib.allocator.requirements]，和 20.4.1 默认分配器 [lib.default.allocator]。事实上，最重要的一点是 20.1.5.1，
该库描述了一套标准的分配器要求，分配器是封装分配模型信息的对象。这些信息包括指针类型、指针差值类型、分配模型中对象大小的类型，以及其内存分配和释放原语。所有容器 (_lib.containers_) 都根据分配器进行参数化。
在 20.4.1 中提供的 std::allocator 是 [C++] 对所有 C++ 编译器实现强制要求的唯一预定义且必需的分配器。
C++ 标准定义
标准要求分配器定义指向 T 的指针类型 (pointer)、指向 T 的常量指针类型 (const_pointer)、T 的引用类型 (reference)、指向 T 的常量引用类型、T 本身类型 (value_type)、可以表示分配模型中最大对象大小的无符号整型 (size_type)，以及可以表示分配模型中任意两个指针之差的有符号整型 (difference_type)。
标准接着要求一个模板类 rebind 成员，它应该遵循 20.1.5.3 的以下段落：
上面表格中的模板类成员 rebind 实际上是一个模板typedef：如果名称Allocator绑定到SomeAllocator<T>，那么Allocator::rebind<U>::other就与SomeAllocator<U>是相同的类型。
简而言之，给定 allocator<T>，我们可以简单地通过 allocator::rebind<U>::other.allocate(1) 来分配足够容纳 U 类型对象的内存。这是 std::list 正确工作所必需的魔法，因为给定 std::list<int>(allocator<int>())，std::list 实际上需要分配 Node<int> 的内存，而不是 int 的内存。因此，它们需要重新绑定到 allocator<int>()::rebind<Node<int> >::other。
接下来，我们需要提供一个函数来简单地返回给定对象的地址 (address)。
以下是分配器的核心：一个用于为 n 个 T 类型对象分配内存但**不构造对象**的函数 (allocate(n,u)，其中 u 是对其他内存模型的提示)，以及一个用于释放 n 个 T 类型对象的函数 (deallocate(p, n))。在此调用之前，对象必须已被销毁。
如前所述，allocate 和 deallocate 仅仅是底层的内存管理，不参与对象的构造和析构。这意味着关键字 new 和 delete 的默认用法不适用于这些函数。正如任何中级 C++ 程序员应该知道的，以下代码。
A* a = new A;
delete a;
实际上是由编译器1解释为
// assuming new throws std::bad_alloc upon failure
A* a = ::operator new(sizeof(A));
a->A::A();
if ( a != 0 ) { // a check is necessary for delete
a->~A();
::operator delete(a);
}
分配器的目的是2分配原始内存而不构造对象，并且仅仅释放内存而不必销毁它们，因此直接使用 operator new 和 operator delete 比使用关键字 new 和 delete 更受青睐。
在此之后，还有用于执行复制构造 (construct(p, t)) 和销毁 (destroy(p)) 对象，以及获取可以有意义地传递给 allocate 的最大值的函数 (max_size)，复制构造函数和默认构造函数，以及相等性检查运算符 (== 和 !=)。
一个示例分配器
下面是一个符合 C++ 标准的分配器的定义和实现。
template<typename T>
class Allocator {
public :
// typedefs
typedef T value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
public :
// convert an allocator<T> to allocator<U>
template<typename U>
struct rebind {
typedef Allocator<U> other;
};
public :
inline explicit Allocator() {}
inline ~Allocator() {}
inline explicit Allocator(Allocator const&) {}
template<typename U>
inline explicit Allocator(Allocator<U> const&) {}
// address
inline pointer address(reference r) { return &r; }
inline const_pointer address(const_reference r) { return &r; }
// memory allocation
inline pointer allocate(size_type cnt,
typename std::allocator<void>::const_pointer = 0) {
return reinterpret_cast<pointer>(::operator new(cnt * sizeof (T)));
}
inline void deallocate(pointer p, size_type) {
::operator delete(p);
}
// size
inline size_type max_size() const {
return std::numeric_limits<size_type>::max() / sizeof(T);
}
// construction/destruction
inline void construct(pointer p, const T& t) { new(p) T(t); }
inline void destroy(pointer p) { p->~T(); }
inline bool operator==(Allocator const&) { return true; }
inline bool operator!=(Allocator const& a) { return !operator==(a); }
}; // end of class Allocator
这是分配器的基本实现，它应该与你编译器供应商提供的绝大多数 std::allocator 相似。然而，对于经验丰富的读者来说，可以立即发现一个潜在的错误。&r 只有在 T 没有重载 operator & 时才能工作，并且 T 必须返回对象的地址。否则，用户将无法可靠地获取 T 类型对象的地址。
将分配器分解为策略和特性的3
为了解决上述地址问题（双关语），我们有逻辑地允许 T 的创建者实际提供获取 T 类型对象正确地址的方法。遵循 STL 的类似设计，我们可以创建一个 Trait 类来提供这种方法。当我们识别出应该提升到 Trait 类中的逻辑设计时，我们应该提出以下设计。
template<typename T>
class ObjectTraits {
public :
// convert an ObjectTraits<T> to ObjectTraits<U>
template<typename U>
struct rebind {
typedef ObjectTraits<U> other;
};
public :
inline explicit ObjectTraits() {}
inline ~ObjectTraits() {}
template <typename U>
inline explicit ObjectTraits(ObjectTraits<U> const&) {}
// address
inline T* address(T& r) { return &r; }
inline T const* address(T const& r) { return &r; }
inline void construct(T* p, const T& t) { new(p) T(t); }
inline void destroy(T* p) { p->~T(); }
}; // end of class ObjectTraits
如上所述，我们还将 construct/destroy 包含进来，因为对象的构造/析构方式应该由 T 的特性来定义。然而，请注意，construct/destroy 并不总是被容器在内存分配之后调用，也不在容器内存释放之前调用。这是因为容器不构造对象，它们构造的是对象的副本2。因此，construct/destroy 不会成为检查对象构造/析构的可靠方法。
有了 ObjectTraits，如果 T 的创建者决定 construct、destroy 或重载 operator &，他可以为自己的目的进行完整的模板特化 ObjectTraits。
在特性之后，我们还可以将实际的内存分配/释放代码抽象成一个策略本身。
template<typename T>
class StandardAllocPolicy {
public :
// typedefs
typedef T value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
public :
// convert an StandardAllocPolicy<T> to StandardAllocPolicy<U>
template<typename U>
struct rebind {
typedef StandardAllocPolicy<U> other;
};
public :
inline explicit StandardAllocPolicy() {}
inline ~StandardAllocPolicy() {}
inline explicit StandardAllocPolicy(StandardAllocPolicy const&) {}
template <typename U>
inline explicit StandardAllocPolicy(StandardAllocPolicy<U> const&) {}
// memory allocation
inline pointer allocate(size_type cnt,
typename std::allocator<void>::const_pointer = 0) {
return reinterpret_cast<pointer>(::operator
new(cnt * sizeof (T)));
}
inline void deallocate(pointer p, size_type)
{ ::operator delete(p); }
// size
inline size_type max_size() const {
return std::numeric_limits<size_type>::max();
}
}; // end of class StandardAllocPolicy
// determines if memory from another
// allocator can be deallocated from this one
template<typename T, typename T2>
inline bool operator==(StandardAllocPolicy<T> const&,
StandardAllocPolicy<T2> const&) {
return true;
}
template<typename T, typename OtherAllocator>
inline bool operator==(StandardAllocPolicy<T> const&,
OtherAllocator const&) {
return false;
}
分配策略决定了内存分配/释放的工作方式，可以分配的 T 类型对象的最大数量，以及用于确定其他分配器之间是否可以互换分配和释放内存的相等性检查。
通过一个简单的特性和分配策略的完成，我们现在可以构建一个可扩展的分配器接口。
template<typename T, typename Policy =
StandardAllocPolicy<T>, typename Traits = ObjectTraits<T> >
class Allocator : public Policy, public Traits {
private :
typedef Policy AllocationPolicy;
typedef Traits TTraits;
public :
typedef typename AllocationPolicy::size_type size_type;
typedef typename AllocationPolicy::difference_type difference_type;
typedef typename AllocationPolicy::pointer pointer;
typedef typename AllocationPolicy::const_pointer const_pointer;
typedef typename AllocationPolicy::reference reference;
typedef typename AllocationPolicy::const_reference const_reference;
typedef typename AllocationPolicy::value_type value_type;
public :
template<typename U>
struct rebind {
typedef Allocator<U, typename AllocationPolicy::rebind<U>::other,
typename TTraits::rebind<U>::other > other;
};
public :
inline explicit Allocator() {}
inline ~Allocator() {}
inline Allocator(Allocator const& rhs):Traits(rhs), Policy(rhs) {}
template <typename U>
inline Allocator(Allocator<U> const&) {}
template <typename U, typename P, typename T2>
inline Allocator(Allocator<U, P,
T2> const& rhs):Traits(rhs), Policy(rhs) {}
}; // end of class Allocator
// determines if memory from another
// allocator can be deallocated from this one
template<typename T, typename P, typename Tr>
inline bool operator==(Allocator<T, P,
Tr> const& lhs, Allocator<T,
P, Tr> const& rhs) {
return operator==(static_cast<P&>(lhs),
static_cast<P&>(rhs));
}
template<typename T, typename P, typename Tr,
typename T2, typename P2, typename Tr2>
inline bool operator==(Allocator<T, P,
Tr> const& lhs, Allocator<T2, P2, Tr2> const& rhs) {
return operator==(static_cast<P&>(lhs),
static_cast<P2&>(rhs));
}
template<typename T, typename P, typename Tr, typename OtherAllocator>
inline bool operator==(Allocator<T, P,
Tr> const& lhs, OtherAllocator const& rhs) {
return operator==(static_cast<P&>(lhs), rhs);
}
template<typename T, typename P, typename Tr>
inline bool operator!=(Allocator<T, P, Tr> const& lhs,
Allocator<T, P, Tr> const& rhs) {
return !operator==(lhs, rhs);
}
template<typename T, typename P, typename Tr,
typename T2, typename P2, typename Tr2>
inline bool operator!=(Allocator<T, P, Tr> const& lhs,
Allocator<T2, P2, Tr2> const& rhs) {
return !operator==(lhs, rhs);
}
template<typename T, typename P, typename Tr,
typename OtherAllocator>
inline bool operator!=(Allocator<T, P,
Tr> const& lhs, OtherAllocator const& rhs) {
return !operator==(lhs, rhs);
}
注意对策略和特性的使用是公有继承，而不是将它们作为成员数据。这使得每个分配器实例都可以拥有自己的内存管理模型（通过策略），并可以利用编译器可能提供的 EBCO（空基类优化），因为在大多数情况下，特性会是一个空类。
Allocator 类的用法非常简单，如下所示：
std::vector<int, Allocator<int> > v;
内存分配跟踪策略实现
前面列出的分配器执行最基本的内存管理。在现有工作模型的基础上，我们实际上可以对内存管理进行性能分析，例如，通过以下内存分配跟踪策略：
template<typename T, typename Policy = StandardAllocPolicy<T> >
class TrackAllocPolicy : public Policy {
private :
typedef Policy AllocationPolicy;
public :
// convert an TrackAllocPolicy<T> to TrackAllocPolicy<U>
template<typename U>
struct rebind {
typedef TrackAllocPolicy<U,
typename AllocationPolicy::rebind<U>::other> other;
};
public :
inline explicit TrackAllocPolicy():total_(0), current_(0), peak_(0) {}
inline ~TrackAllocPolicy() {}
inline explicit
TrackAllocPolicy(TrackAllocPolicy const& rhs):Policy(rhs),
total_(rhs.total_), current_(rhs.current_), peak_(rhs.peak_) {}
template <typename U>
inline explicit
TrackAllocPolicy(TrackAllocPolicy<U> const& rhs):Policy(rhs),
total_(0), current_(0), peak_(0) {}
// memory allocation
typename AllocationPolicy::pointer
allocate(typename AllocationPolicy::size_type cnt,
typename std::allocator<void>::const_pointer hint = 0) {
typename AllocationPolicy::pointer p =
AllocationPolicy::allocate(cnt, hint);
this->total_ += cnt;
this->current_ += cnt;
if ( this->current_ > this->peak_ ) {
this->peak_ = this->current_;
}
return p;
}
inline void deallocate(typename AllocationPolicy::pointer p,
typename AllocationPolicy::size_type cnt) {
AllocationPolicy::deallocate(p, cnt);
this->current_ -= cnt;
}
// get stats
inline typename AllocationPolicy::size_type
TotalAllocations() { return this->total_; }
inline typename AllocationPolicy::size_type
CurrentAllocations() { return this->current_; }
inline typename AllocationPolicy::size_type
PeakAllocations() { return this->peak_; }
private :
// total allocations
typename AllocationPolicy::size_type total_;
// current allocations
typename AllocationPolicy::size_type current_;
// peak allocations
typename AllocationPolicy::size_type peak_;
}; // end of class TrackAllocPolicy
// determines if memory from another
// allocator can be deallocated from this one
template<typename T, typename Policy, typename T2, typename Policy2>
inline bool operator==(TrackAllocPolicy<T, Policy> const& lhs,
TrackAllocPolicy<T2, Policy2> const& rhs) {
return operator==(static_cast<Policy&>(lhs),
static_cast<Policy&>(rhs));
}
template<typename T, typename Policy, typename OtherAllocator>
inline bool operator==(TrackAllocPolicy<T,
Policy> const& lhs, OtherAllocator const& rhs) {
return operator==(static_cast<Policy&>(lhs), rhs);
}
此分配策略仅添加跟踪功能，并建立在另一个/实际的内存分配策略之上，第二个模板参数决定了该策略。
类的用法也同样简单：
std::vector<int, Allocator<int, TrackAllocPolicy<int> > > v;
小型对象分配器
另一种可能的分配策略实现可能是优化小型对象的分配。频繁地从自由存储区分配/释放小型对象有时会损害应用程序的性能。解决办法是一次性分配一大块内存，并在需要时将其分配给应用程序。释放的小型对象会返回到该内存块，并在稍后重新使用。
由于 Loki5 有一个已完成的 Small Object Allocator 类，那么将其改编为我们的分配器是合乎逻辑的。
template<typename T, std::size_t numBlocks = 64>
class SmallObjectAllocPolicy {
public :
// typedefs
typedef T value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
public :
// convert an SmallObjectAllocPolicy<T> to SmallObjectAllocPolicy<U>
template<typename U>
struct rebind {
typedef SmallObjectAllocPolicy<U, numBlocks> other;
};
public :
inline explicit SmallObjectAllocPolicy() {}
inline ~SmallObjectAllocPolicy() {}
inline explicit SmallObjectAllocPolicy(SmallObjectAllocPolicy const&) {}
template <typename T2, std::size_t N2>
inline explicit
SmallObjectAllocPolicy(SmallObjectAllocPolicy<T2, N2> const&) {}
// memory allocation
inline pointer allocate(size_type cnt,
typename std::allocator<void>::const_pointer = 0) {
return reinterpret_cast<T*>(allocator_.Allocate(sizeof(T) * cnt));
}
inline void deallocate(pointer p, size_type cnt) {
allocator_.Deallocate(p, sizeof(T) * cnt);
}
// size
inline size_type max_size() const {
return std::numeric_limits<size_type>::max() / sizeof(T);
}
private:
static Loki::SmallObjAllocator allocator_;
}; // end of class SmallObjectAllocPolicy
// optimized for single small object,
// hence chunk size and max object size is small
// otherwise using free store
template<typename T, std::size_t numBlocks>
Loki::SmallObjAllocator SmallObjectAllocPolicy<T,
numBlocks>::allocator_(numBlocks * sizeof(T), sizeof(T));
// determines if memory from another allocator
// can be deallocated from this one
template<typename T, std::size_t N>
inline bool operator==(SmallObjectAllocPolicy<T, N> const&,
SmallObjectAllocPolicy<T, N> const&) {
return true;
}
template<typename T, std::size_t N, typename T2, std::size_t N2>
inline bool operator==(SmallObjectAllocPolicy<T,
N> const&, SmallObjectAllocPolicy<T2, N2> const&) {
return false;
}
template<typename T, std::size_t N, typename OtherAllocator>
inline bool operator==(SmallObjectAllocPolicy<T,
N> const&, OtherAllocator const&) {
return false;
}
如果你想了解 Loki 的 SmallObjAllocator 的工作原理，请务必查看 Loki 提供的代码，或购买 [Alexandrescu 2001]。
使用 SmallObjectAllocator 也很简单。
std::list<int, Allocator<int, SmallObjectAllocPolicy<int, 64> > > vTest;
如果你看过 Loki 的 SmallObjAllocator，你会注意到它最适合单次固定大小的分配（对于不同大小的分配，它们实际上会创建不同的内部分配器）。因此，它不太适合 std::vector 或其他类似容器，这些容器会分配一块内存（且大小各异）。
当然，如果你事先知道你的结构的最大大小，你也可以这样做：
std::vector<int> v;
v.reserve(10);
或者，如果你想摆脱动态内存分配，你可以声明一个提供固定大小数组的分配器，尽管通过 std::vector 将分配器作为构造函数参数的方式，你最终会得到一个不必要的临时对象。（尽管如此，代码已包含在源代码中，并且仅在你事先知道大小并使用 reserve 函数的情况下才有效）
解决多线程问题
起初，我希望 Allocator 类中包含自定义的线程策略，因为例如 SmallObjectAllocator 使用共享内存池来提供对象 T。多个线程使用 SmallObjectAllocator<T, N> 可能会导致内部内存池跟踪状态不一致。除了任何形式的互斥锁/锁在 Allocator 中不起作用（感谢 Sean Kent 指出这一点），即使在 SmallObjectAllocator<T, N> 中也是如此，因为它们仍然是不同的实例，但共享同一个静态 Loki::SmallObjAllocator。唯一可能的解决方案是在 Loki::SmallObjAllocator 的包装器中执行锁/互斥锁，甚至是在 Loki::SmallObjAllocator 自身中。
因此，此实现本身实际上不是线程安全的（至少在 SmallObjectAllocator 的情况下）。
结论
分配器概念是一种非常强大的封装内存管理模型的方法，它不触及重载 new 和 delete 运算符，而有些人认为这样做是坏的或邪恶的。通过分配器，你可以将内存跟踪、针对特定对象的优化内存管理模型等集成到你的容器中。如果你围绕分配器设计和构建了你的框架，那么可能性将是巨大的。
当然，不要陷入“万能锤”综合症，或者有些人称之为“当你有一把锤子时，其他东西都看起来像钉子”。有些设计不适合插入分配器，尽管这样做造成的危害不大（除了可能增加构建时间和依赖性），但也没有带来太多好处。
脚注
1 描述于 [Lippman 1996]，第 5 章，构造和复制的语义。
2 在 STL 容器中，不需要通过默认构造函数进行对象构造，因为容器中的数据仅仅是插入的实际数据的副本（使用复制构造函数创建）。
3 策略类分配器的原始想法和实现应归功于 Sean Kent。请注意，这里描述的版本与他的原始版本存在相似之处和差异。
4 请参阅 Henrik Stuart 的 模板特化 - 入门调查，以获得关于模板特化的精彩介绍和解释。
5 记住 下载 Loki 库。
参考文献
- [Josuttis 1999]: Nicolai M. Josuttis, The C++ Standard Library: A Tutorial and Reference Addison-Wesley Pub Co 1999
- [C++]: C++ 标准，1998
- [Lippman 1996]: Stanley B. Lippman, Inside the C++ Object Model Addison-Wesley Pub Co, 1996
- [Alexandrescu 2001]: Andrei Alexandrescu, Modern C++ Design: Generic Programming and Design Patterns Applied. Addison-Wesley Pub Co, 2001
历史
- 2003 年 8 月 19 日：上传初始版本。