c++
标准库中的Allocator有一个复杂而低层次的接口[注1]。和new与delete不同，它们将内存分配与对象构造解耦。和malloc与free不同，它们要求你明确正在分配的内存的数据类型和对象数目。
通常，这不成为问题。Allocator拥有低层次的接口是因为它们是低层次的概念：它们通常隐藏在容器类内部，而不属于普通用户的代码。然而，有时你可能不得不关心Allocator：当你自己写一个新的容器类的时候。Allocator比new/delete难用多了，因此，更容易发生错误。如果你写的代码不得不使用Allocator，如何确保代码正确？运行期的测试不能证明不存在错误，只能证明错误的存在。尽管如此，测试还是很重要－－你越快发现bug，它就越早被修正。
所有的标准容器类都接受一个Allocator类作为其模板参数；这个参数有一个默认值，比如std::vector<int>是vector<int,std:: Allocator<int> >的简写。如果我们写了一个有额外正确性检查的alocator类，那就可以用它代替std::Allocator<int>来作为vector的第二模板参数。如果没有bug的话，vector的行为将会和以前一样。(当然，除了额外的检查将使它变慢。)
测试
我们想检查什么种类的错误？最重要的是：
l 当deallocate()一块内存时，归还了与分配时相同的字节数。（和malloc与free不同，Allocator不为自己记录这些信息。）
l 正deallocate()的内存，其类型与分配时相同。(虽然 Allocator将内存分配与对象构造解耦了，但内存仍然是为某个特定数据类型分配的。)
l 当在一块内存中写入数据时，我们不会越界。
l 从不试图在同一位置构造两个对象，并且也不会试图销毁同一对象两次。
l 当deallocate()一块内存时，确保先销毁了其中的所有对象。
在Debugging Allocator背后的主意很简单[注2]：每当allocate()一块内存时，多分配一些，并在最初几个字节中记录一些额外信息。用户看不到这块debug区域；我们传给用户的指针指向在此之后的内存。当传回给我们一个指向我们分配的内存块的指针时，我们可以减小其值以查看debug区域，并确认内存块是被正确使用的。
这样的设计有两个隐藏问题。首先，不可能相当可移植地实现它。我们必须保持对齐：假设用户数据的地址需要对齐，我们保留了一些字节而还要维持对齐。我们如何知道该加多少？理论上，我们无法知道；语言没有提供判断对齐要求的机制。(也许这将会增加到未来的标准中)。实践中，它不是一个严重的可移植性议题：在double word上对齐所有东西，在目前绝大部分平台上都足够好了，并且在要求更严格的平台上作相应修改也很容易。
第二问题是，在这个设计里，有一部分错误很容易检查，而其它的就不行了。用户通过allocate()获得一块内存，并把它传给deallocate()，于是，这个设计很容易检查allocate()和deallocate()是被一致使用的。不幸的是，很难检验construct()和destory()是被一致使用的。
问题是通常传给construct()和destory()的参数不是从allocate()返回的指针。如果写下a.construct(p,x)，那么p必须指向通过a分配出的内存块内部－－是指向内部，而不是指向（其开头）。也许用户通过p1 = a.allocate(1000)分配了足够1000个元素的内存。这种情况下，我们不知道construc()的第一个参数是p1，p1 + 5，还是p1 + 178。我们无法找到需要的Debugging信息，因为没法找到分配出的内存块的开始地址。
这个问题有两个可能的解决方案，但都不是工作得很好。首先，明显，我们可以放弃所有的Debugging信息都一定要放在内存块开始处的主意。但是，这不怎么能行，因为我们将不得不将我们的信息与用户数据混合存储。这会破坏指针的运算法则：用户无法在不知道我们的Debugging信息的情况下从一个元素步进到下一个元素。另外一个选择是，我们可以另外维护一个额外的数据结构：比如，我们可以维护一个保存活动对象信息的std::set，用户每用construct()创建一个对象，就在set中增加一个地址，用户每用destory()销毁一个对象就移除这个地址。
这个技术简单而优雅，而它不能工作的理由很微妙。问题是用户不是必须使用相同的Allocator来创建和销毁对象：用户只需要使用一个等价的Allocator。思考一下下面的一系列操作：
l 用户用a1.construct(p,x)创建了一个新对象。
l 用户用a2.destroy()销毁对象。
这个序列是合法的，但是维护活动对象列表的Allocator会指出它是一个错误：我们将新的对象加入到a1的活动对象列表中，而当用a2销毁对象时将找不到它。
可以通过在所有给定的Allocator的拷贝间共享列表来绕过这个问题吗？也许吧，但是我们将会陷入定义上的问题。如果：
然后a1和a2应该共享相同的活动对象列表吗？(答案看起来可能是“不”，那么再my_Allocator<int>(a2)时怎么办？) 我们也陷入实现上问题：在幕后被共享的对象需特别处理，尤其是在有并发问题时。
因为这些问题，我已经简单地放弃了在construct()和destory()上作实质性检查的主意。这个版本的Debugging Allocator只在它们的参数上作最小程度的检查，并不试图确保destory()的参数被构造过，或这个对象只销毁一次。
这个Debugging Allocator的主要目的是确保allocate()和deallocate()被一致使用。当分配内存时，我们在每块内存开始处保留了两个word的内存，并在其中记录了内存块中元素的数目，和一个起源于类型的hash码(从类型的名字，特别是如typeid(T).name()所给出的)。然后我们在内存块结束的地方还保留了另外一个word，并存入了hash码的另一个拷贝作为哨兵。然后当deallocate()内存块时，我们检查已经储存的元素数目与传入的参数相同，已及两个hash码都是正确的。我们调用assert()以便一个不一致的行为将导致程序失败。
这没有给予我们所期望的所有检查，但它让我们确保传给deallocate()的内存是这个Allocator分配的，并且是对相同的类型进行的分配和归还，数目也是一致的。它也对越界给予了有限的保护：在任一方向的越界一个的错误都会覆盖哨兵，而这个错误将会在归还时被检测到。
写一个Allocator adaptor产生了两个新的问题。第一是我们不能对正在适配的东西作任何假设。我们不能想当然地认为Allocator::pointer的类型是T *，也不能认为可以将东西放入未初始化的内存中（即使是内建数据类型的东西，如char和int）。我们必须虔诚地使用construct()和destroy()。虽然讨厌，但只要加些注意就行了。
那么一个普通的模板参数怎么样？我们可能想写：
typedef typename A::template rebind<void>::other A2;
问题是A2的value_type是void，而Allocator内部的一些东西对void是不成立的。例如，有一个reference的typedef，而void &是没有意义的；它会导致编译错误。默认的Allocator有一个特化，std::Allocator<void>。没有理由地，我们也需要一个特化。
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef typename Allocator::const_pointer const_pointer;
typedef typename Allocator::value_type value_type;
template <class U> struct rebind {
typedef typename Allocator::template rebind<U>::other A2;
typedef debug_Allocator<A2, typename A2::value_type> other;
};
public: // constructor, destructor, etc.
: alloc(a.alloc), hash_code(0)
// Generalized copy constructor.
template <class A2, class T2>
: alloc(a.alloc), hash_code(0)
public: // Member functions.
// The only interesting ones
// are allocate and deallocate.
pointer allocate(size_type n, const void* = 0);
void deallocate(pointer p, size_type n);
pointer address(reference x) const { return a.address(x); }
const_pointer address(const_reference x) const {
return a.address(x);
}
void construct(pointer p, const value_type& x);
void destroy(pointer p);
size_type max_size() const { return a.max_size(); }
{ return x.alloc == y.alloc; }
{ return x.alloc != y.alloc; }
private:
typedef typename Allocator::template rebind<char>::other
typedef typename Allocator::template rebind<std::size_t>::other
// calculate the hash code, and store it in this->hash_code.
// Only used in the constructor.
const char* hash_code_as_bytes()
{ return reinterpret_cast<const char*>(&hash_code); }
// Number of bytes required to store n objects of type value_type.
size_type data_size(size_type n)
{ return n * sizeof(value_type); }
// Number of bytes allocated in front of the user-visible memory
// block. Must be large enough to store two objects of type
// size_t, and to preserve alignment.
size_type padding_before(size_type)
{ return 2 * sizeof(std::size_t); }
// Number of bytes from the beginning of the block we allocate
// until the beginning of the sentinel.
size_type sentinel_offset(size_type n)
{ return data_size(n) + padding_before(n); }
// Number of bytes in the sentinel.
size_type sentinel_size()
{ return sizeof(std::size_t); }
// Size of the area we allocate to store n objects,
size_type total_bytes(size_type n)
{ return data_size(n) + padding_before(n) + sentinel_size(); }
};
// Specialization when the value type is void. We provide typedefs
// (and not even all of those), and we save the underlying Allocator
// so we can convert back to some other type.
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef typename Allocator::const_pointer const_pointer;
typedef typename Allocator::value_type value_type;
template <class U> struct rebind {
typedef typename Allocator::template rebind<U>::other A2;
typedef debug_Allocator<A2, typename A2::value_type> other;
};
template <class A2, class T2>
private:
};
// Noninline member functions for debug_Allocator. They are not defined
// for the void specialization.
(size_type n, const void* = 0) {
assert(n != 0);
// Allocate enough space for n objects of type T, plus the debug
// info at the beginning, plus a one-byte sentinel at the end.
typedef typename char_alloc::pointer char_pointer;
typedef typename size_alloc::pointer size_pointer;
char_pointer result = char_alloc(alloc).allocate(total_bytes(n));
// Store the size.
size_pointer debug_area = size_pointer(result);
size_alloc(alloc).construct(debug_area + 0, n);
// Store a hash code based on the type name.
size_alloc(alloc).construct(debug_area + 1, hash_code);
// Store the sentinel, which is just the hash code again.
// For reasons of alignment, we have to copy it byte by byte.
typename char_alloc::pointer sentinel_area =
result + sentinel_offset(n);
const char* sentinel = hash_code_as_bytes();
{
int i = 0;
try {
for ( ; i < sentinel_size(); ++i)
ca.construct(sentinel_area + i, sentinel[i]);
}
for (int j = 0; j < i; ++j)
ca.destroy(&*(sentinel_area + j));
throw;
}
}
// Return a pointer to the user-visible portion of the memory.
pointer data_area = pointer(result + padding_before(n));
return data_area;
}
(pointer p, size_type n) {
assert(n != 0);
// Get a pointer to the space where we put the Debugging information.
typedef typename char_alloc::pointer char_pointer;
typedef typename size_alloc::pointer size_pointer;
char_pointer cp = char_pointer(p);
size_pointer debug_area = size_pointer(cp - padding_before(n));
// Get the size request and the hash code, and check for consistency.
size_t stored_n = debug_area[0];
size_t stored_hash = debug_area[1];
assert(n == stored_n);
assert(hash_code == stored_hash);
// Get the sentinel, and check for consistency.
char_pointer sentinel_area =
char_pointer(debug_area) + sentinel_offset(n);
const char* sentinel = hash_code_as_bytes();
assert(std::equal(sentinel, sentinel + sentinel_size(),
sentinel_area));
size_alloc(alloc).destroy(debug_area + 0);
size_alloc(alloc).destroy(debug_area + 1);
for (size_type i = 0; i < sentinel_size(); ++i)
char_alloc(alloc).destroy(sentinel_area + i);
// Release the storage.
char_alloc(alloc).deallocate(cp - padding_before(n), total_bytes(n));
}
value_type& x)
{
assert(p);
}
{
assert(p);
a.destroy(p);
}
const char* name = typeid(value_type).name();
for ( ; *name != " "; ++name)
hash_code = hash_code * (size_t) 37 + (size_t) *name;
注：
[1] Matt Austern. "The Standard Librarian: What Are Allocators Good For?" c/c++ Users Journal c++ Experts Forum, December 2000, <www.cuj.com/experts/1812/austern.htm>.
[2] This Debugging Allocator is based on the one in the SGI library, <www.sgi.com/tech/stl>. The original version was written by Hans-J. Boehm.
