分类： C/C++
2009-09-19 11:54:02
STL是基于泛型思想的，数组泛化为container，并根据它们所包含的对象类型而进行参数化。函数泛化为algorithms，并根据它们所使用的iterators类型而进行参数化。指针泛化为iterators，并根据它们所指向的对象类型而进行参数化。
但这只是个开始。单个container类型泛化为序列容器（sequence container）和关联容器（associative container），相似的container具有相似的功能。标准的连续内存container（见Item 1）提供了随机存取iterators；而标准的基于结点的container（见Item 1）提供了双向iterators。Sequence containers支持push_front和（或）push_back，而Associative containers则不支持。Associative containers提供了操作复杂度为时间的（译注：这是我的理解，不知道对不对）对数的lower_bound，upper_bound和equal_range成员函数，而Sequence containers则不提供。
随着整个这样的泛化过程的进行，很自然地我们也想加入进来。这种情绪是值得赞赏的，而且你在写自己的container、iterators和algorithms时，你当然也想要追求这种泛化过程。可惜的是，很多程序员是以一种不同的方式来进行的。
通常，他们不是在他们的软件中实现一个特定类型的container，而是试图泛化一个container（比如说，一个vector）的概念以便于使用，仍然保留了将来可以替代它的选择（比如一个deque或是一个list）——所有的这一切不用改变使用这个container的代码。换句话说，他们力图编写与container无关的代码。
这种类型的泛化，尽管是一种出于善意的考虑，终究还是走错了方向。即使是最为热心于写与container无关的代码的提倡者，很快他就会认识到，力图去写一个可以让Sequence containers和Associative containers同时运作的软件几乎是没有意义的。
许多的成员函数是只存在于一类container中的。例如，只有Sequence containers支持push_front或push_back，而只有Associative containers支持count和 lower_bound等等。即使是像insert和erase这种具有基本特征和语义的操作，也是随着container类型的不同而不同的。例如，当你插入一个对象到一个Sequence containers中时，它是处于插入位置的。但当你插入一个对象到一个Associative containers中时，container将把这个对象移动到一个按这个对象在container中的索引顺序排列的位置。另一个例子是，以一个iterators为输入的这种erase操作，在一个Sequence containers中调用时返回一个新的iterators，但在Associative containers中调用时则什么也不返回（Item 9给了一个例子，解释了这将会怎样影响你所写的代码）。
接着我们假定你很想写这样的代码，它可以使用最为常用的Sequence containers，如vector、deque和list。很明显，你必须要编程实现它们的功能的交集，这意味着不能使用reserve或capacity（见Item 14），因为deque和list没有提供这样的成员函数。list的存在也意味着你要放弃operator[]，而且你要将自己的代码限制到双向iterators的所提供的能力。反过来说，这意味着你必须将你的代码不能使用要求随机存取iterators的algorithms，这些algorithms包括sort， stable_sort，partial_sort和nth_element （见Item 31）。
另一方面来说，你想要vector不使用push_front和pop_front，并且vector和deque不能使用splice和sort形式的成员函数。上述两种限制中，后者意味着在你的泛化了的Sequence containers中将没有sort形式的调用。
这是明显的情形，如果你违犯了上述的任何一条限制，你的代码会因为你想使用的至少其中一个container而不能编译通过。将要编译的代码将会有更多的隐患。
主犯是应用于不同的Sequence containers，使得iterators、指针和引用失效的规则是不同的。为了使所写的代码同vector、deque和list正确地运作，你必须假定对于任何一个使得在这样的任何一个container里的iterators、指针或是引用失效的操作，在你正在使用的container里也是失效的。从而你必须假定每一个对insert的调用总是失效的，因为deque::insert使得所有的iterators失效，而且由于缺乏调用capacity的能力，必须认为vector::insert操作使所有的指针和引用失效（Item 1解释了deque在某些时候是很独特的，它会让它的iterators失效而不使它的指针和引用实效）。同样的原因可以得出一个结论，必须认为每一个对erase的调用将使一切东西失效。
还想要更多的例子？好的，你不能传递container里的数据给C的接口，因为只有vector支持这个特性（见Item 16）；你不能用bool作为所存储对象的类型实体化你的container，因为，正如Item 18所解释的那样，vector<bool>并不总是像一个vector那样表现，并且它从不实际存储bools；你不能认为list的插入和删除操作（的复杂度）是常量，因为vector和deque在做这些操作时（的复杂度）是线性的。
等该说的说完了该做的做完了以后，留给你的是这样的一个泛化了的Sequence containers：你不能调用reserve，capacity，operator[]，push_front，pop_front，splice或者任何一个需要随机存取iterators的algorithms；这个container的每一个insert和erase调用的操作复杂度是线性的，并且它使所有的iterators、指针和引用失效；并且这个container不能同C兼容，不能存储bools。这样的container是你在想在你的应用程序中使用的吗？我想不是。
如果你压制住你的野心，决定放弃对list的支持。但是你仍然要放弃reserve，capacity，push_front和pop_front；你仍然必须假定所有对insert和erase的调用（的操作复杂度）是线性的并且使一切失效；你仍然要失去同C兼容的内存布局（译注：我想应该是内存布局吧）；并且你仍然不能存储bools
如果你要放弃Sequence containers，而准备改为用不同的Associative containers来进行编码，情况也好不到那里去。为set和map写这样的代码基本上是不可能的，因为sets存储单个对象而maps存储一对对象。虽然可以为set和multiset（或map和multimap）做这样的强制编码，但是，同其它形式的形式相比较，只有一个值（译注：不好意思，没看源代码，我猜是参数）的insert成员函数对于sets/maps的返回值是不一样的。并且你必须谨慎地避免对在container中存储了多少份值的拷贝作任何的假设。对于map和multimap而言，你必须避免使用operator[]，因为这个成员函数只有map才有。
面对现实：这样做是不值得的。不同的container在不同的情形有它们自己的优点和缺点。它们不是设计为可互换的，你基本上是不可能涵盖它们的。如果你想试的话，那你只不过是做春秋大梦，但是这个梦却不是那么的甜美。尽管如此，当你认识到你该选择一个什么样的container的时候，也是黎明破晓之时。嗯，尽管不是最好的，你需要使用一个不同的container类型。现在你明白了，当你改变container类型时，你不仅要修正你的编译器诊断出的所有问题。你也需要检验所用使用container的代码，一方面看看它是否需要根据新container的性能特征作出改变；一方面看看它使iterators、指针和引用失效的规则。
如果你不用vector而转为使用其它的container，你也必须要确定你不再依赖于vetor的与C兼容的内存布局；如果你由其它container转为使用vector，你必须确定你不使用它来存储bools。
尽管不可避免地要时常改变container类型，你也可以以通常的方式方便地作出这种改变，封装、封装，还是封装。其中，最简单的方式就是对container和iterators类型随意地使用typedefs，从而，不要这样编码：
class Widget { ... };
vector
Widget bestWidget;
... // give bestWidget a value
vector
find(vw.begin(), vw.end(), bestWidget); // same value as bestWidget
应该这样写：
class Widget { ... };
typedef vector
typedef WidgetContainer::iterator WCIterator;
WidgetContainer vw;
Widget bestWidget;
...
WCIterator i = find(vw.begin(), vw.end(), bestWidget);
这将会使改变container类型要容易得多，这样做将会给你带来很大的方便，如果问题改变了，只需简单地加入一个自定义的allocator即可。（这样的改变不影响使iterators、指针和引用失效的规则）
class Widget { ... };
template<typename T> // see Item 10 for why this
SpecialAllocator { ... }; // needs to be a template
typedef vector
typedef WidgetContainer::iterator WCIterator;
WidgetContainer vw; // still works
Widget bestWidget;
...
WCIterator i = find(vw.begin(), vw.end(), bestWidget); // still works
如果typedefs的封装层面对你而言没有意义，你还是可能认可这样做所节省的工作量。例如，如果你有这样的一个对象类型
map
CIStringCompare> // CIStringCompare is “case-
// insensitive string compare;”
// Item 19 describes it
而且你想要用const_iterators遍历整个map，你真的想不止一次地这样拼写吗？
map<string, vector
在你用过STL一段时间以后，你会认识到typedefs是一个不错的朋友。一个typedef只是一些其它类型的同义词，所以它所提供的完全是字面上的封装。但是一个typedef不能阻止它的用户做（或是依赖）任何它们没有准备好的（或是依赖的）事。如果你想要限制你暴露给用户的container的选择的话，你需要加强封装性，你需要用类。
如果你想用另一个container来代替现有的一个，为了限制需要修改的代码，可将container封装到一个类里，并且限制可通过类的接口访问的与类相关的信息的数量。例如，如果你需要创建一个自定义的list，不要直接使用list。你应该创建一个CustomerList类，并封装一个list在它的私有部分：
class CustomerList {
private:
typedef list
typedef CustomerContainer::iterator CCIterator;
CustomerContainer customers;
public: // limit the amount of list-specific
... // information visible through
}; // this interface
咋一看，这可能显得有点笨拙，毕竟一个自定义的list还是一个list，是吧？嗯，可能是的。随后你会发现你不必像你通常预期的那样在list的中部插入或是删除客户，你只是需要快速找出你的客户最前面20％的信息——一个对nth_elementalgorithms（见Item 31）的一个特制的任务。但是nth_elementalgorithms需要随机存取iterators，它不能用在一个list中。在这种情况里，你的自定义“list”可能用vector或是deque实现更好一些。
你在考虑这类变化时，你仍然必须检查每一个CustomerList的成员函数和每一个友元，看看它们是怎么被影响的（根据性能和iterators/指针/引用的失效规则，等等）。但是如果你已经对CustomerList的实现细节作了很好的封装以后，那么对于CustomerList用户的影响将会很小。你不能写与container无关的代码，但是这些代码可能能做到与container无关。
（译注：这是Scott Meyers的新书 《Effective STL: 提高STL使用技术的50招》其中一条，在Addison－Wesley网站上公布了其中几条，好东东不敢独享，特此让大家看看，希望有帮助，作这样的翻译是我的第一次尝试，很多地方我自己都觉得不满意，贴上去让大家指教一下好了）
