《Effective STL》

haoji

你是否可以接受“非相等”分配器的实现定义行为，（3）你不关心把你的代码移植到那些可能从标准给予
的自由中获得好处的STL实现。简而言之，这个段落——第20.1.5节第5段，为坚持要求知道的那些人——是
标准为分配器的“I have a dream”演讲。在梦想成为现实之前，关心移植性的程序员应该把他们自己限制在
没有状态的自定义分配器。
我早先提及了分配器在分配原始内存方面类似operator new，但它们的接口不同。如果你看看operator new和
allocator<T>::allocate最普通形式的声明，就会很清楚：
void* operator new(size_t bytes);
pointer allocator<T>::allocate(size_type numObjects);
// 记住事实上“pointer”总是
// T*的typedef
两者都带有一个指定要分配多少内存的参数，但对于operator new，这个参数指定的是字节数，而对于
allocator<T>::allocate，它指定的是内存里要能容纳多少个T对象。例如，在sizeof(int) == 4的平台上，如果你要
足够容纳一个int的内存，你得把4传给operator new，但你得把1传给allocator<int>::allocate。（在operator new情
况下这个参数的类型是size_t，而在allocate的情况下它是allocator<T>::size_type。在两种情况里，它都是无符号
整数类型，通常allocator<T>::size_type是一个size_t的typedef。）关于这个差异没有什么“错误”，但是
operator new和allocator<T>::allocate之间的不同协定使应用自定义operator new的经验到开发自定义分配器的过
程变得复杂。
operator new和allocator<T>::allocate的返回类型也不同。operator new返回void*，那是C++传统的表示一个到未
初始化内存的指针的方式。allocator<T>::allocate返回一个T*（通过pointer typedef），不仅不传统，而且是有
预谋的欺诈。从allocator<T>::allocate返回的指针并不指向一个T对象，因为T还没有被构造！在STL里暗示的
是希望allocator<T>::allocate的调用者将最后在它返回的内存里构造一个或多个T对象（也许通过allocator<T>::
construct，通过uninitialized_fill或通过raw_storage_iterator的一些应用），虽然在这里没有发生vector::reserve或
string::reserve（参见条款14）。在operator new和allocator<T>::allocate之间返回类型的不同使未初始化内存的概
念模型发生了变化，而它再次使把关于实现operator new的知识应用到开发自定义分配器变得困难。
那也带来了我们对STL分配器最后的好奇——大多数标准容器从未调用它们例示的分配器。这是两个例子：
list<int> L; // 和list<int, allocator<int> >一样；
// allocator<int>从未用来
// 分配内存！
set<Widget, SAW> s; // 记住SAW是一个
// SpecialAllocator<Widget>的typedef；
// SAW从未分配内存！

haoji

这个怪癖对list和所有标准关联容器都是真的（set、multiset、map和multimap）。那是因为这些是基于节点的
容器，即，这些容器所基于的数据结构是每当值被储存就动态分配一个新节点。对于list，节点是列表节点。
对于标准关联容器，节点通常是树节点，因为标准关联容器通常用平衡二叉搜索树实现。
想一会儿可能怎么实现list<T>。list本身由节点组成，每个节点容纳一个T对象和到list中后一个和前一个节点
的指针：
template<typename T, // list的可能
typename Allocator = allocator<T> > // 实现
class list{
private:
Allocator alloc; // 用于T类型对象的分配器
struct ListNode{ // 链表里的节点
T data:
ListNode *prev;
ListNode *next;
};
...
};
当添加一个新节点到list时，我们需要从分配器为它获取内存，我们要的不是T的内存，我们要的是包含了一
个T的ListNode的内存。那使我们的Allocator对象没用了，因为它不为ListNode分配内存，它为T分配内存。现
在你理解list为什么从未让它的Allocator做任何分配了：分配器不能提供list需要的。
list需要的是从它的分配器类型那里获得用于ListNode的对应分配器的方法。按照协定，分配器得提供完成那
个工作的typedef，否则将会很难办。那个typedef叫做other，但它不那么简单，因为other是嵌入一个叫做
rebind的结构体的typedef，rebind自己是一个嵌入分配器的模板——分配器本身也是模板！
请不要试图考虑最后那句话。取而代之的是，看看下段代码，然后直接阅读后面的解释。
template<typename T> // 标准分配器像这样声明，
class allocator { // 但也可以是用户写的
public: // 分配器模板
template<typename U>
struct rebind{
typedef allocator<U> other;

haoji

}
...
};
在list<T>的实现代码里，需要确定我们持有的T的分配器所对应的ListNode的分配器类型。我们持有的T的分
配器类型是模板参数Allocator。在本例中，ListNodes的对应分配器类型是：
Allocator::rebind<ListNode>:ther
和我保持一致。每个分配器模板A（例如，std::allocator，SpecialAllocator，等）都被认为有一个叫做rebind的
内嵌结构体模板。rebind带有一个类型参数，U，并且只定义一个typedef，other。 other是A<U>的一个简单名
字。结果，list<T>可以通过Allocator::rebind<ListNode>:ther从它用于T对象的分配器（叫做Allocator）获取对
应的ListNode对象分配器。
这或许对你有意义，或许不。（如果你注视它足够长时间了，它会，但你可能还必须注视一会儿。我知道我
必须。）作为一个可能想要写自定义分配器的STL用户，你其实不需要知道它怎样工作。你需要知道的是如
果你选择写分配器并让标准容器使用它们，你的分配器必须提供rebind模板，因为标准容器认为它在那里。
（为了调试的目的，知道T对象的基于节点的容器为什么从未从T对象的分配器获取内存也是有帮助的。）
哈利路亚！我们最后完成了对分配器特质的检查。因此，如果你想要写自定义分配器，让我们总结你需要记
得的事情。
● 把你的分配器做成一个模板，带有模板参数T，代表你要分配内存的对象类型。
● 提供pointer和reference的typedef，但是总是让pointer是T*，reference是T&。
● 决不要给你的分配器每对象状态。通常，分配器不能有非静态的数据成员。
● 记得应该传给分配器的allocate成员函数需要分配的对象个数而不是字节数。也应该记得这些函数返回
T*指针（通过pointer typedef），即使还没有T对象被构造。
● 一定要提供标准容器依赖的内嵌rebind模板。
写你自己的分配器时你必须做的大部分事情是重现大量样板代码，然后修补一些成员函数，特别是allocate和
deallocate。我建议你从Josuttis的样例allocator网页[23]或Austern的文章《What Are Allocators Good For?》[24]的
代码开始，而不是从头开始写样板。
一旦你消化了本条款中的信息，你将知道很多关于分配器不能做的事情，但是那或许不是你想要知道的。相
反，你或许想知道分配器能做什么。那有权成为一个丰富的主题，一个我称为“条款11”的主题。

haoji

Center of STL Study
——最优秀的STL学习网站
条款11：理解自定义分配器的正确用法
你用了基准测试，性能剖析，而且实验了你的方法得到默认的STL内存管理器（即allocator <T>）在你的STL
需求中太慢、浪费内存或造成过度的碎片的结论，并且你肯定你自己能做得比它好。或者你发现allocator<T>
对线程安全采取了措拖，但是你只对单线程的程序感兴趣，你不想花费你不需要的同步开销。或者你知道在
某些容器里的对象通常一同被使用，所以你想在一个特别的堆里把它们放得很近使引用的区域性最大化。或
者你想建立一个相当共享内存的唯一的堆，然后把一个或多个容器放在那块内存里，因为这样它们可以被其
他进程共享。 恭喜你！这些情况正好对应于一种适合于自定义分配器解决的方案。
例如，假定你有仿效malloc和free的特别程序，用于管理共享内存的堆，
void* mallocShared(size_t bytesNeeded);
void freeShared(void *ptr);
并且你希望能把STL容器的内容放在共享内存中。没问题：
template<typename T>
class SharedMemoryANocator {
public:
...
pointer allocate(size_type numObiects, const void *localityHint = 0)
{
return static_cast<pointer>(mallocShared(numObiects * sizeof(T)));
}
void deallocate(pointer ptrToMemory, size_ type numObjects)
{
freeShared(ptrToMiemory);
}
...
};
allocate里的pointer类型、映射和乘法的更多信息参见条款10。

haoji

你可以像这样使用SharedMemoryAllocator：
// 方便的typedef
typedef vector<double, SharedMemoryAllocator<double> >
SharedDoubleVec;
...
{ // 开始一个块
SharedDoubleVec v; // 建立一个元素在
// 共享内存中的vector
... // 结束这个块
}
在紧挨着v定义的注释里的词语很重要。v使用SharedMemoryAllocator，所以v分配来容纳它元素的内存将来自
共享内存，但v本身——包括它的全部数据成员——几乎将肯定不被放在共享内存里，v只是一个普通的基于
堆的对象，所以它将被放在运行时系统为所有普通的基于堆的对象使用的任何内存。那几乎不会是共享内
存。为了把v的内容和v本身放进共享内存，你必须做像这样的事情：
void *pVectorMemory = // 分配足够的共享内存
mallocShared(sizeof(SharedDoubleVec)); // 来容纳一个
// SharedDoubleVec对象
SharedDoubleVec *pv = // 使用“placement new”来
new (pVectorMemory) SharedDoubleVec; // 在那块内存中建立
// 一个SharedDoubleVec对象；
// 参见下面
// 这个对象的使用（通过pv）
...
pv->~SharedDoubleVec(); // 销毁共享内存
// 中的对象
freeShared(pVectorMemory); // 销毁原来的
// 共享内存块
我希望那些注释让你清楚是怎么工作的。基本上，你获得一些共享内存，然后在里面建立一个用共享内存为
自己内部分配的vector。当你用完这个vector时，你调用它的析构函数，然后释放vector占用的内存。代码不很
复杂，但我们在上面所做的比仅仅声明一个本地变量要苛刻得多。除非你真的要让一个容器（与它的元素相
反）在共享内存里，否则我希望你能避免这个手工的四步分配/建造/销毁/回收的过程。

haoji

在这个例子里，无疑你已经注意到代码忽略了mallocShared可能返回一个null指针。显而易见，产品代码必须
考虑这样一种可能性。 此外，共享内存中的vector的建立由“placement new”完成。如果你不熟悉placement
new，你最喜欢C++课本应该可以告诉你。如果那个课本碰巧是《More Effective C++》，你将发现这个玩笑在
条款8兑现。
作为分配器作用的第二个例子，假设你有两个堆，命名为Heap1和Heap2类。每个堆类有用于进行分配和回收
的静态成员函数：
class Heap1 {
public:
...
static void* alloc(size_t numBytes, const void *memoryBlockToBeNear);
static void dealloc(void *ptr);
...
};
class Heap2 { ... }; // 有相同的alloc/dealloc接口
更进一步认为你想在不同的堆里联合定位一些STL容器的内容。同样没有问题。首先，你设计一个分配器，
使用像Heap1和Heap2那样用于真实内存管理的类：
template<typenameT, typename Heap>
class SpecificHeapAllocator {
public:
pointer allocate(size_type numObjects, const void *localityHint = 0)
{
return static_cast<pointer>(Heap::alloc(numObjects * sizeof(T),
localityHint));
}
void deallocate(pointer ptrToMemory, size_type numObjects)
{
Heap::dealloc(ptrToMemory);
}
...
};

haoji

然后你使用SpecificHeapAllocator来把容器的元素集合在一起：
vector<int, SpecificHeapAllocator<int, Heap1 > > v; // 把v和s的元素
set<int, SpecificHeapAllocator<int Heap1 > > s; // 放进Heap1
list<Widget,
SpecificHeapAllocator<Widget, Heap2> > L; // 把L和m的元素
map<int, string, less<int>, // 放进Heap2
SpecificHeapAllocator<pair<const int, string>,
Heap2> > m;
在这个例子里，很重要的一点是Heap1和Heap2是类型而不是对象。STL为用不同的分配器对象初始化相同类
型的不同STL容器提供了语法，但是我将不让你看它是什么。那是因为如果Heap1和Heap2是对象而不是类
型，那么它们将是不等价的分配器，那就违反了分配器的等价约束，在条款10有详细说明。
因为这些例子演示的，分配器在许多情况里有用。只要你遵循相同类型的所有分配器都一定等价的限制条
件，你将毫不费力地使用自定义分配器来控制一般内存管理策略，群集关系和使用共享内存以及其他特殊的
堆。

haoji

Center of STL Study
——最优秀的STL学习网站
条款12：对STL容器线程安全性的期待现实一些
标准C++的世界是相当保守和陈旧的。在这个纯洁的世界，所有可执行文件都是静态链接的。不存在内存映
射文件和共享内存。没有窗口系统，没有网络，没有数据库，没有其他进程。在这种情况下，当发现标准没
有提到任何关于线程的东西时你不该感到惊讶。你对STL的线程安全有的第一个想法应该是它将因实现而不
同。
当然，多线程程序是很普遍的，所以大部分STL厂商努力使他们的实现在线程环境中可以正常工作。但是，
即使他们做得很好，大部分负担仍在你肩上，而理解为什么会这样是很重要的。STL厂商只能为你做一些可
以减少你多线程的痛苦的事情，你需要知道他们做了什么。
在STL容器（和大多数厂商的愿望）里对多线程支持的黄金规则已经由SGI定义，并且在它们的STL网站[21]上
发布。大体上说，你能从实现里确定的最多是下列内容：
● 多个读取者是安全的。多线程可能同时读取一个容器的内容，这将正确地执行。当然，在读取时不能
有任何写入者操作这个容器。
● 对不同容器的多个写入者是安全的。多线程可以同时写不同的容器。
就这些了，那么让我解释你可以期望的是什么，而不是你可以确定的。有些实现提供这些保证，但是有些
不。
写多线程的代码很难，很多程序员希望STL实现是完全线程安全的。如果是那样，程序员可以不再需要自己
做并行控制。毫无疑问这将带来很多方便，但这也非常难实现。一个库可能试图以下列方式实现这样完全线
程安全的容器：
● 在每次调用容器的成员函数期间都要锁定该容器。
● 在每个容器返回的迭代器（例如通过调用begin或end）的生存期之内都要锁定该容器。
● 在每个在容器上调用的算法执行期间锁定该容器。（这事实上没有意义，因为，正如条款32所解释
的，算法没有办法识别出它们正在操作的容器。不过，我们将在这里检验这个选项，因为它的教育意
义在于看看为什么即使是可能的它也不能工作。）
现在考虑下列代码。它搜寻一个vector<int>中第一次出现5这个值的地方，而且，如果它找到了，就把这个值
改为0。

haoji

vector<int> v;
vector<int>::iterator first5(find(v.begin(), v.end(), 5)); // 行1
if (first5 != v.end()){ // 行2
*first5 = 0; // 行3
}
在多线程环境里，另一个线程可能在行1完成之后立刻修改v中的数据。如果是那样，行2对first5和v.end的检
测将是无意义的，因为v的值可能和它们在行1结束时的值不同。实际上，这样的检测会产生未定义的结果，
因为另一线程可能插在行1和行2之间，使first5失效，或许通过进行一次插入操作造成vector重新分配它的内在
内存。（那将使vector全部的迭代器失效。关于重新分配行为的细节，参见条款14。）类似的，行3中对*first5
的赋值是不安全的，因为另一个线程可能在行2和行3之间执行，并以某种方式使first5失效，可能通过删除它
指向（或至少曾经指向）的元素。
在上面列举的锁定方法都不能防止这些问题。行1中begin和end调用都返回得很快，以至于不能提供任何帮
助，它们产生的迭代器只持续到这行的结束，而且find也在那行返回。
要让上面的代码成为线程安全的，v必须从行1到行3保持锁定，很难想象STL实现怎么能自动推断出这个。记
住同步原语（例如，信号灯，互斥量，等等）通常开销很大，更难想象实现怎么在程序没有明显性能损失的
情况下做到前面所说的——以这样的一种方式设计——让最多一个线程在1-3行的过程中能访问v。
这样的考虑解释了为什么你不能期望任何STL实现让你的线程悲痛消失。取而代之的是，你必须手工对付这
些情况中的同步控制。 在这个例子里，你可以像这样做：
vector<int> v;
...
getMutexFor(v);
vector<int>::iterator first5(find(v.begin(), v.end(), 5));
if (first5 != v.end()) { // 这里现在安全了
*first5 = 0; // 这里也是
}
releaseMutexFor(v);
一个更面向对象的解决方案是创建一个Lock类，在它的构造函数里获得互斥量并在它的析构函数里释放它，
这样使getMutexFor和releaseMutexFor的调用不匹配的机会减到最小。这样的一个类（其实是一个类模板）基
本是这样的：
template<typename Container> // 获取和释放容器的互斥量

haoji

class Lock { // 的类的模板核心；
public: // 忽略了很多细节
Lock(const Containers container)
: c(container)
{
getMutexFor(c); // 在构造函数获取互斥量
}
~Lock()
{
releaseMutexFor(c); // 在析构函数里释放它
}
private:
const Container& c;
};
使用一个类（像Lock）来管理资源的生存期（例如互斥量）的办法通常称为资源获得即初始化，你应该能在
任何全面的C++教材里读到它。一个好的开端是Stroustrup的《The C++ Programming Language》[7]，因为
Stroustrup普及了这个惯用法，但你也可以转到《More Effective C++》的条款9。不管你参考了什么来源，记
住上述Lock是被剥离到最原始的本质的。一个工业强度的版本需要很多改进，但是那样的扩充与STL无关。
而且这个最小化的Lock已经足够看出我们可以怎么把它用于我们一直考虑的例子：
vector<int> v;
...
{ // 建立新块；
Lock<vector<int> > lock(v); // 获取互斥量
vector<int>::iterator first5(find(v.begin(), v.end(), 5));
if (first5 != v.end()) {
*first5 = 0;
}
} // 关闭块，自动
// 释放互斥量
因为Lock对象在Lock的析构函数里释放容器的的互斥量，所以在互斥量需要释放是就销毁Lock是很重要的。
为了让这件事发生，我们建立一个里面定义了Lock的新块，而且当我们不再需要互斥量时就关闭那个块。这
听上去像我们只是用关闭新块的需要换取了调用releaseMutexFor的需要，但是这是错误的评价。如果我们忘
记为Lock建立一个新块，互斥量一样会释放，但是它可能发生得比它应该的更晚——当控制到达封闭块的末