Generic<Programming>:一个基于策略的basic_string的实现
Andrei Alexandrescu
翻译：汤韬（skywalker）
这个月的Generic<Programming>部分有两个有趣的主题。其中一个-讨论standard library中basic_string组件的实现（众所周知，string 是这样定义的：typedef basic_string<char> string;）,它是C++ library 中一个非常重要的部分。但是真正有意思的是，那些可供下载的代码是为了配合VC++ 6.0一起工作而特别精心制作的。VC++ 6.0是一个因具有两大对立特性而知名的编译器――它所具有的普及性以及它对generic programming的弱支持。
伴随这篇文章所实现的basic_string不是一个、两个，而是十二个有着不同权衡的实现。他们不是玩具代码，我们讨论的都是完整、高效、符合标准、具有工业级强度的实现（哦，当然，可能有bug）。你可能首先会想到这会有可怕的代码量，不过，相信我，这篇文章将会非常的有趣。
一种尺寸不会适用所有的身材
首先，大家可能会疑惑为什么要再次实现basic_string?他不是已经在standard library中实现了吗，再来实现一个basic_string是不是仅仅只具有教学价值。
众所周知，在多线程程序中使用string存在非常严重的问题。标准库会尝试在basic_string的实现中允许使用Copy-on-write。（Copy-on-write在其拥护者那里有个亲切的昵称：COW，但是在反对者眼里却成了"the mad cow"）基于COW的strings在内部使用引用计数器（reference counting），这在多线程程序中是不可用的，但是如果standard library在实现中支持多线程，那么用在单线程时，性能常常又不可接受，看来必须有所选择。
（译注：所谓Copy-on-write就是多个相同的对象会使用内存中同一份数据copy,只有当某一个对象改变自己的数据时，它才会先复制一份数据自己独享，再改动数据。这样做的好处就是在对象复制时减少了内存分配、赋值等操作。缺点就是既然多个对象使用同一份内存数据，如果不上锁，在多线程里就会出麻烦了，呵呵！！）
当在使用动态连接库的程序中用COW strings可能还会发生更多的问题-当你的程序还在拥有一份由动态库分配内存的string 的一份浅拷贝（shallow copies）时,你却释放了动态库。
大量关于使用cow strings所引起麻烦的讨论，使得大多数STL的实现都摒弃了COW的方式，而改成了可替换的优化策略（alternate optimization strategies）方式。但是"大多数"并不是"全部"，因此，当你在多线程中使用basic_string,你必须要使用non-COW方式的实现，所以你不得不放弃STL所实现的basic_string。
另一方面，COW实现方式对于相当一部分应用来讲仍然是非常有用的。试问，你可以根据自己的喜好在某种应用中使用某种确定的优化的实现方式，这样不是更好吗？"我想要一个用non-COW实现，并针对字符数在16个以下做优化的string。",或者是"我即想利用COW,又同时使用我自己的堆分配运算符。"
如何在200行代码内实现basic_string
暂且不管多个string实现的有效性，仅仅实现一个都将是一个令人畏惧的任务。在你实现的对外接口需要实现大量的成员函数和类型定义，确实不是一件容易的事。我清楚的了解这一点，是因为我先前为一个需要使用COM字符串分配算符和多线程的应用程序实现过一个basic_string接口。
当我小心翼翼按照Standard的规矩写全部的utility函数时，我注意到一个有趣的事实。大量的成员函数看上去都围绕着一组小的、核心的函数和类型-换句话说，你可以把basic_string的接口分作"core"和"utility"两个部分。"utility"部分和你的实现策略无关，而"core"在不同的实现里则有着完全不同的设计。例如，"utility"中的replace系列函数就是由resize 这个"core"函数来实现的。
这儿有一个难点："utility"部分的代码非常庞大（在我的实现里超过700行）。与此对照的，写一个"core"部分，即使是严谨、能够经受考验的代码，也是一项相对容易任务-在我的实现中代码量大致在75-250行变化。这就意味着你可以在"utility"接口下相对容易得实现不同的"core"来满足不同的需要。你只需把那庞大的代码实现一次就够了。（实际上，你甚至一次都无需写，你可以下载这篇文章所附的源代码，他们正渴望被使用呢！！）真的，只需要200行就可以实现你梦想中的basic_string。
一个基于策略的String
或许有些读过我的书的人都知道，我们最初设计的初衷就是为了――policies。当然的，当你想改变某个类中特定部分的实现，想让用户选择某个特定的实现方式，你就应该把这个部分作为一个模板变量，并为其定义一个接口。这种方式虽然并不高深，但是它确实非常有效。
标准的 basic_string声明看起来像这样：
namespace std
{
template <class E,
class T = char_traits<E>,
class A = allocator<E> >
class basic_string;
}
E 是string的字符类型（通常是char或是wchar_t），T 控制string 如何比较和复制，A就是我们大家都知道的、但从未使用的分配运算符。我们将添加第四个模板变量，负责如何精确的实现string。由于它是处理如何准确的存储string，我们把它叫做存储策略（Storage Policy）
新的string被命名为flex_string，正如你所看到的，它具有相当的灵活性、可扩展性。
template <class E,
class T = char_traits<E>,
class A = allocator<E>
class Storage = AllocatorStringStorage<E, A> >
class flex_string;
Storage 默认为AllocatorStringStorage<E, A>。这是一个非常简单、直截了当的存储策略的实现，它使用直接的eager copy方式（相对于COW）。在这种实现里，flex_string拥有一个Storage对象，并使用它所提供的类型和成员函数。
选择Storage界面的准确程度可能会变得有点不同。实质上，在用我的basic_string实现之后，我发现了一组函数，如果没有这些函数，我将不可能提供实现，并且这些函数是非冗余的。这是一个Storage policy实现必须满足的半正规的条件范式。
template <typename E, other arguments>
class StorageImpl
{
public:
typedef some_type size_type;
typedef some_type iterator;
typedef some_type const_iterator;
typedef some_type allocator_type;
StorageImpl(const StorageImpl &);
StorageImpl(const allocator_type&);
StorageImpl(const E* s, size_type len, const allocator_type& a);
StorageImpl(size_type len, E, const allocator_type&);
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
size_type size() const;
size_type max_size() const;
size_type capacity() const;
void resize(size_type, E);
void reserve(size_type);
void swap(StorageImpl&);
const E* c_str() const;
const E* data() const;
allocator_type get_allocator() const;
};
实现的非常漂亮，它相当简单（因为它没有使用allocator）。这意味着你能以一个非常小的Storage核心所定义的types和function来实现一个完整、高效的接口。
flex_string 类以'值'的方式拥有一个Storage对象。我选择私有继承是因为一些无关紧要的因素。因此，flex_string看上去象这样：
template <class E,
class T = std::char_traits<E>,
class A = std::allocator<E>,
class Storage = AllocatorStringStorage<E, A> >
class flex_string : private Storage
{
public:
typedef typename Storage::iterator iterator;
typedef typename Storage::const_iterator const_iterator;
...
// 21.3.1 construct/copy/destroy
explicit flex_string(const A& a = A())
: Storage(a)
{}
...
};
实现存储策略
ok,现在让我们进入Storage的内部，看看如何实现这些Storage。一个string拥有一个指向buff的指针。buff里保存string的长度，最大长度以及string本身。为了避免两次分配内存（一次为数据标记，一次为数据本身），可以使用一个小巧门"the struct hack":buff的最后一个元素是一个C-style的字符数组，它能够动态伸展以适应字符数的变化。SimpleStringStorage这样实现的：
template <class E, class A = std::allocator<E> >
class SimpleStringStorage
{
struct Data
{
E* pEnd_;
E* pEndOfMem_;
E buffer_[1];
};
Data* pData_;
public:
size_type size() const
{ return pData_->pEnd_ - pData_->buffer_; }
size_type capacity() const
{ return pData_->pEndOfMem_ - pData_->buffer_; }
...
};
pEnd_ 指针指向字符串的末尾，pEndOfMem指向已分配内存buff的末尾，而buffer_将被扩展来存放多个字符，作为字符串的存放空间--换句话说，Data数据结构的对象能够能够被扩展以放下更多的字符。为了达到这种灵活性，pData_ 指针实际上并不是严格的指向Data对象，一块更大内存被影射成了Data结构。这种"struct hack" 理论上不能保证100%的可移植性，但是实际应用中，它确实工作的很好。
SimpleStringStorage 还有一个小小的优化 -- 所有的empty string都共享一个静态Data实例。另一种实现是将empty strings的pData_指针初始化为zero，但是它却无法通过许多成员函数的普及化(propagated)测试。
SimpleStringStorage 之所以"simple"还因为它避开了allocator。SimpleStringStorage简单的使用new/delete运算符为其管理内存。使用passed-in allocator来为Data分配空间比看上去还要难，部分原因是因为allocator的设计（它不支持能够任意改变尺寸的对象），还有部分原因是因为编译器兼容方面的原因。你能在类模板AllocatorStringStorage中找到一个使用了Allocator的Storage策略的实现。
另一个可能的实现是在后台简单的使用std::vector。这种实现非常简洁、有效,你能获得STL的支持，这就意味着string能够非常简单的、美妙的方式重用standard library。这也就能帮助你将代码量减小到最小尺寸。你能在VectorStringStorage中看到这个实现。
上述三种实现均使用了EPO(Empty Base Optimization)。（还记得我说的"工业级强度"这句话吗？）使用EPO非常的有效是因为大多数allocators实际上都会empty class。
Exhilarated C++
ok，到目前为止，总共用了大约1300行代码，有了三种非常漂亮的basic_string的实现。平均每种433行。还不算太坏，特别是你应该想到现在已经可以非常轻松添加一个新的实现了。
如果你觉得这很有趣，这篇文章到目前为止就达到了它的目的。但是别忘了我们最开始说了包含了大量有趣的东西，现在我们又开始下一步了。
现在让我们进入SSO（small string optimization 小字符串优化）。SSO的想法就是如何以适当的方式存储small strings(不使用动态存储)。当string的尺寸变大时，才使用allocation strategy。这两种方法在字符串内共享内存来记录数据。string class 通过标记能够区别出这两种机制中的某一种。
template <class E, other parameters>
class sso_string
{
struct DynamicData { ... };
static const unsigned int maxSmallStringLen = 12;
union
{
E[maxSmallStringLen] inlineBuffer_;
DynamicData data_;
};
bool isSmall_;
...
};
当isSmall_为true是，string使用inlineBuffer_。否则使用data_。问题是，为DynamicData分配空间使用何种策略？std::vector? SimpleStringStorage? AllocatorStringStorage? 答案当然是"随便你选"
很明显，无论你使用的是何种可替换存储，SSO都是正交(orthogonal)的。因此，SmallStringOpt类拥有一个storage模板变量：
template <class E, unsigned int threshold, class Storage, typename Align = E*>
class SmallStringOpt
{
enum { temp = threshold > sizeof(Storage) ? threshold : sizeof(Storage) };
public:
enum { maxSmallString = temp > sizeof(Align) ? temp : sizeof(Align) };
private:
union
{
E buf_[maxSmallString + 1];
Align align_;
};
...implement the Storage policy...
};
buf_ 成员变量保存Storage对象或是string字符串本身。但是Align是干什么的？好了，当要处理"静态分配"(seated allocation),你就必须小心处理对齐(alignment)的问题。因为没有一个简单的办法计算出对齐的值，因此SmallStringOpt 接受一个指定的类型变量作为一个哑元变量保存。
SmallStringOpt 是如何起别对待大、小不同的字符串呢？ 在小字符串中，Buf_的最后一个元素（即buf_[maxSmallString]）存放的是maxSmallString与实际字符串尺寸之差，对于长字符串却是magic这个值。对于长度等于maxSmallString 的字符串来说，buf_[maxSmallString]等于0，刚好可作为字符串终结符。（译注：这个实现方法确实非常巧妙，buf_[maxSmallString]这个内存单元担任了双重任务，小于等于maxSmallString 时，表示这是一个小字符串，还能指示串的长度，等于0时，还作为串终结符，大于maxSmallString 时，表示一个长字符串。）
在这个类中，你会看到"数字欺骗"，casts，和底层操作（我们正在讨论优化，不是吗？），而且还有一点引人注目：那就是我们可以组合SmallStringOpt和其它三种存储策略，包括SimpleStringStorage, VectorStringStorage, 和 AllocatorStringStorage。于是现在我们有了6种basic_string的存储策略的实现--我们的努力有了成倍的回报。（呵呵，是不是非常有趣）现在有了1440行代码，平均每种实现的代码下降到了240行。
这儿是一个实例：
typedef flex_string<
char,
std::char_traits<char>,
std::allocator<char>,
SmallStringOpt<char, 16, VectorStringStorage<char, std::allocator<char> > >
> String;
它组合使用基于vector的存储策略和小于16个字符的小字符串的优化存储策略。
回到COW
不管喜欢与否，你不能忽略COW -- 因为很多人都知道温和的动物是很有价值的。为了这些好处，我们就来实现一个CowString类模板，当然，它也可以使用其它任何Storage。CowString看上去象这样：
template <class E, class Storage>
class CowString
{
struct Data
{
Storage s_;
unsigned int refs_;
};
Data* pData_;
public:
...
};
Data结构拥有一个你所选择的Storage和一个引用计数器。CowString本身仅有一个指向Data结构的指针。多个CowString可能会指向同一个Data对象。只有即将发生对字符串的改变，CowString才会生成一个属于自己的拷贝。
让我们再看下面这个：
typedef flex_string<
char,
std::char_traits<char>,
std::allocator<char>,
SmallStringOpt<char, 5,
CowString<char, AllocatorStringStorage<char, std::allocator<char> > > >
> String;
这个String使用了如下的一个存储策略：当字符数小于5时，它使用无需动态申请内存的小字符串优化方式。对于更长的字符串，则使用COW存储策略，而COW本身的存储策略却使用基于Allocator方式的实现。
CowString再次倍增了flex_string的实现策略，所以我现在有了12种方式。代码总共1860行，平均每种实现155行。如果考虑SmallStringOpt 和 CowString的使用次序，实际上应该有24种。但是在COW中使用SmallStringOpt并无任何意义，所以你总是应该在SmallStringOpt中使用CowString而不是相反。
小结
basic_string是一个结构复杂的组件。尽管如此，一个仔细设计存储策略让能够大大提升你的生产力。使用少量的策略，你就可以选择如直接的、小字符串优化的、拥有引用计数器的实现的basic_string,仅仅只需简单的给模板类赋上几个变量。
参考
[1] Herb Sutter. "Optimizations that Aren't (In a Multithreaded World)," C/C++ Users Journal, June 1999.
[2] Kevlin Henney. "From Mechanism to Method: Distinctly Qualified," C/C++ Users Journal C++ Experts Forum, May 2001 （http://www.cuj.com/experts/1905/henney.htm）
[3] Andrei Alexandrescu. Modern C++ Design (Addison-Wesley, 2001).
[4] Andrei Alexandrescu. "Traits on Steroids," C++ Report, June 2000, （http://ftp.sj.univali.br/prof/Fernando%20Montenegro/artigos/GenericProgramingCPP02.htm）
[5] Jack Reeves. "String in the Real World - Part 2," C++ Report, January 1999, （http://www.bleading-edge.com/Publications/C++Report/v9901/Column14.htm）.
原文
（http://www.cuj.com/experts/1906/alexandr.htm?topic=experts&topic=experts）
代码下载
（ftp://ftp.cuj.com/pub/2001/1906/alexandr.zip）
关于作者
Andrei Alexandrescu 是 RealNetworks 开发经理。Modern C++ Design的作者
