Item 2:抛弃写“容器无关”的代码的幻想

scott meyers 著

刘未鹏译

STL建立在泛型的基础之上。数组(arrays)被泛化成为容器，并以它们所包含的对象的类型为模板参数。函数(functions)被泛化成算法，并以它们所接纳的迭代器的类型为模板参数。指针被泛化成迭代器，并以它们所指向的对象的类型为模板参数。

然而这仅仅是个开始。个别的容器类型被泛化成为序列式容器和关联式容器。相似的容器被赋予相似的泛函性(functionality，或“功能性”)。标准的“内存连续式”容器提供随机存取迭代器，标准的node-based容器提供双向迭代器。序列式容器支持push_front或push_back，关联式容器却不支持。关联式容器提供算法复杂度为对数时间的 lower_bound,upper_bound和equal_range成员函数，然而序列式容器却不提供。

很自然的，你也想加入这个泛化的行动中来，这值得赞扬，并且当你写你自己的容器、迭代器和算法时，你当然想尝试着这样做。然而有许多程序员却用错了方式——他们并不是让代码依赖于某种特定的容器，而是试图将容器的概念泛化，从而试图达到这样一种目的——当前使用某一种容器，如vector，以后又能够在不改变其它代码的前提下透明地将容器替换成其它类型（如换成deque、list等）。这也就是说，他们努力去写“ 容器无关”的代码。这种泛化虽然意图是好的，然而——几乎可以肯定的说——这是个误导。

即使是“容器无关”代码的最热心的鼓吹者不久也会意识到：试图去写能同时和序列式容器及关联式容器工作的代码几乎是没有意义的。许多成员函数只在某一种特定类型的容器中存在。例如：只有序列式容器支持push_front和push_back，只有关联式容器支持count和lower_bound，等等。即使是erase和insert这样基本的操作在不同容器类别之间都有着语义上的差别。比如，当你插入一个元素至序列式容器中时，它将会呆在你将它放置的地方。然而在关联式容器中，它会按照容器的排序方式被移至某个恰当的地点。再举个例子，在序列式容器上调用erase会返回一个新的迭代器，而在关联式容器上则什么也不返回(条款9说明了这将如何影响你的代码)。

好吧，假设你热切盼望能够写出能与大多数通常的容器如vector、list、deque一起工作的代码。显然，你的代码必须只用到它们的能力的交集(译注：假设你使用了容器A有而容器B没有的功能，则当容器A换成B时你的代码将不能工作)——这意味着你得放弃使用reserve和capacity(条款14)，因为deque和list并不提供它们。有list的到场意味着你又不能使用operator[]，你还把自己限制在双向迭代器的能力范围内——那又意味着你将不能使用需要随机存取式迭代器的算法（例如：sort,stable_sort,partial_sort,nth_element(条款31)）。

另一方面，你支持vector的愿望将push_front和pop_front踢出场外(译注：因为vector根本没有这两个操作)，如果你希望支持deque或vector，则你将不能使用splice和成员形式的sort。后者(译注：即不能使用splice和成员形式的sort)意味着在你的“泛化的序列式容器”上你不能调用任何形式的sort。

以上只是一些较为明显的事实。如果你违反其中任何一条限制，在你所要使用的所有容器中至少有一种会使你的代码通不过编译。而那些能通过编译的代码则会隐藏着更大的危险。

导致这些问题的罪魁祸首就是各种序列式容器间有关迭代器、指针、引用失效的不同协定。要写出能正确地和vector,deque,list同时工作的代码，你必须假设任何操作都会使所有的迭代器、指针、引用失效。因此，你必须假设在你所使用的任何容器上调用insert都会使它们的任何迭代器、指针、引用失效——而这不过仅仅是由于deque::insert()会使所有迭代器失效。并且由于缺少调用capacity的能力，你就必须假设vector::insert()会使指向它内部的所有指针和引用失效(条款1解释了对于deque——某些时候——在它的迭代器失效的同时指针和引用却不失效)。出于类似的原因，每次调用erase你得做同样的打算。

想要知道更多吗？你不能将容器中的数据传给C风格的接口(C-interface)。因为仅有vector支持这种行为(条款16)，你不能存储bool型别的变量，因为正如条款18所解释的，vector<bool>并不总是表现得像个vector，它也从不真的存储bool值。你不能假定list的常数时间的插入和擦除动作，因为vector和deque在这些操作上需要耗线性时间。

当所有该说的都说完了，该做的都做完了，你就只剩下了如下的这个“泛化的序列式容器”：在这个容器上，你不能调用reserve,capacity,operator[],push_front,pop_front,splice,或是任何需要接受随机存取迭代器的算法；你得假设任何insert和erase会消耗线性时间，并会使所有迭代器、指针、引用失效；你还得假设这个容器与C风格不兼容，并且不能保存bool值。这真的是你期望在程序中使用的容器吗？我怀疑不是！

如果你收敛一下野心，决定愿意放弃对list的支持，则你仍然要放弃reserve,capacity,push_front,pop_front；你仍然必须假定所有对insert和erase的调用消耗线性时间，并使所有迭代器、指针、引用失效。你仍然失掉与C风格的兼容；你仍然不能存储bool值。

如果你放弃序列式容器，然后争取让你的代码能和不同的关联式容器一同工作，情况并不会变得更好一些——写同时支持set和map的代码近乎不可能。因为sets存储单独的对象，而maps存储一对对象。甚至写同时支持set和multiset(或是map和multimap)的代码都是艰难的。因为只接受一个值的insert成员函数在set/map和它们的兄弟multiset/multimap身上具有不同的返回值型别。你还必须避免作出对“到底有多少个值的拷贝存在于容器中”的假定。你不能调用operator[]——因为它只在map中存在。

面对事实吧——不值得这样做！不同的容器是处于两个不同世界的东西，有各自的规则，有不同的强大之处和弱点。它们并非被设计为可互换的。你对此无能为力。如果你去尝试，你只不过是在冒险，而且注定经不起考验。

当你意识到你所选择的容器是不理想的，你得去使用别的类型的容器时，黎明就到来了。你现在知道了，当你改变所使用的容器时，你不只是要改正编译器给你诊断出的错误，你还需要检查使用新容器的所有代码，看看在新容器的性能特征和iterator,pointer,reference失效的规则之下还有什么需要改变的。如果你从vector转而使用别的容器，你得确认你已经不再依赖于vector的C风格兼容的内存分配形式。如果你从别的容器转向vector，你得确认你没有使用它来存储bool值。

鉴于有时你必须得改变容器，你可以使这种改变更容易一些，通常，经过包装，包装，再包装。最简单的方法之一，是对容器和迭代器使用typedefs的自由形式，因此将下面的代码：

class Widget{...};

vector<Widget> vw;

Widget bestWidget;

... //give bestWidget a value

vector<Widget>::iterator i= //find a Widge with the

find(vw.begin(),vw.end(),bestWidget);//same value as bestWidget

取代为：

class Widget{...};

typedef vector<Widget> WidgetContainer;

typedef WidgetContainer::iterator WCIterator;

WidgetContainer cw;

Widget bestWidget;

...

WCIterator i=find(cw.begin(),cw.end(),bestWidget);

这使改变容器的类型变得相当容易。当只是给容器加一个自定义配置器时(这样的改变不会改变容器的iterator/pointer/reference失效规则),这会显得特别方便。

class Widget{...};

template<typename T> //see Item 10 for why this

SpecialAllocator{...}; //needs to be a template

typedef vector<Widget,SpecialAllocator<Widget> > WidgetContainer;

typedef WidgetContainer::iterator WCIterator;

WidgetContainer cw; //still works

Widget bestWidget;

...

WCIterator i=find(cw.begin(),cw.end(),bestWidget); //still works

如果这些对你并不代表什么，你也得感激它们能为你省下的工作，举个例子，如果你有个型别为：

map<string,vector<Widget>::iterator,CIStringCompare>

//CIStringCompare is "case-insensitive string compare;"

//Item 19 describes it

的对象，你想用const_iterator遍历map，你真的想拼写下面的代码？

map<string,vector<Widget>::iterator,CIStringCompare>::const_iterator

如果你要用到不止一次呢？一旦你用STL一段时间后，你会意识到typedef是你的朋友。

一个typedef只是为其他的型别起一个别名。所以这只是提供纯粹字面上的包装。一个typedef并不阻止客户端做(或依赖)他们已经能做(或依赖)的。如果想要避免将你对容器的选择暴露给客户端，你需要更强力的措施——class。

当你用一个容器替换现有容器时，为了限制所要改动的代码的量，你可以将容器隐藏在class内部，并限制从class的接口显露出的容器相关（container-specific）的信息的量。例如，如果你需要创建一个顾客列表(customer list)，不要直接用list(指STL容器的list)。你可以创建一个新的CustomerList类，将list作为它的私有成员隐藏起来。

class CustomerList{

private:

typedef list<Customer> CustomerContainer;

typedef CustomerContainer::iterator CCIterator;

CustomerContainer customers;

public: //limit the amount of list-specific

... //infomation visible through this interface

};

起初，这看起来可能有些莫名其妙——毕竟一个customer list也是一个list，不是么？好吧，或许，再后来你会发现你并不需要像你预期的那样频繁地从顾客列表中部增加或删减消费者，但是你开始需要快速标识出你的顾客中的前20%(可能是消费量最大的)--这正是nth_lement算法特定的任务(条款31)，然而nth_element需要随机存取迭代器，所以它不能和list合作(译注：list的迭代器是双向的却不是随机的)，在这种情况下你的customer "list"最好用一个vector或deque来实现。

当你考虑了这种变化后，你还得检查CustomerList的每个成员函数和友员函数以考察它们所受到的影响(因底部容器的性能因素和iterator/pointer/reference失效性)，作出可能需要的相应的改变。但是如果你将CustomerList的实现细节封装得很好，则CustomerList内部容器的变化对客户端的影响就会很小。你不能写出容器无关(container-independent)的代码，但你的客户或许可以(译注：在上例中，如果CustomerList封装得够好的话)。