Effective STL中文版：50条有效使用STL的经验.docx

EffeCtiVeSTL中文版：50条有效使用STL的经验1. 1容器2. 2vector和SIring3. 3关联容器4. 4迭代器5. 5算法6. 6函数子、函数子类、函数及其他7. 7在程序中使用STL8. 参考书目9. 附录A地域性与忽略大小写的字符串比较10. 附录B对MiCrOSoft的STL平台的说明11-后折页12. 1容器没错，STL中有迭代器（iterator）s算法（algorithm）和函数对象（functionobject）,但是对于大多数C+程序员来说，最值得注意的还是容器。容器比数组功能更强大、更灵活。它们可以动态增长（和缩减），可以自己管理内存，可以记住自己包含了多少对象。它们限定了自己所支持的操作的复杂性。诸如此类的优点还有很多。不难理解它们为何如此受欢迎，因为相对于其竞争者，无论是来自其他库中的容器还是你自己编写的容器，其优越性是显而易见的。STL容器不是简单的好，而是确实很好。本章讲述适用于所有STL容器的准则。随后几章将就特定类型的容器展开论述。本章内容包括：如何就你所面临的具体制约条件选择适当的容器类型；避免一种错误认识，即为一种类型的容器而编写的代码换了其他容器也能工作；对于容器中的对象，复制操作的重要性；当指针或者auto_ptr被存放在容器中时会有什么样的困难；删除操作的细节；用定制的分配子能做什么及不能做什么；使程序获得最高效率的窍门；以及在多线程环境中使用容器时日一些箸虑。涉及的方方面面很多。别着急，饭要一口一口地吃。这些问题将分为几条，逐条下来，你一定会形成一些想法，并将这些想法应用到你正在编写的代码中。第1条：慎重选择容器类型。C+提供了几种不同的容器供你选择，可是你有没有意识到它们的不同点在哪里？为了防止你在选择时有所疏忽，这里给出了简要回顾： 标准STL序列容器：vector、stringsdeque和list。 标准STL关联容器:set、multisetsm叩和multimap。 非标准序列容器SliSt和rope。SliSt是一个单向链表，rope本质上是一个“重型"Stringo（“rope”是重型“siring”，明白了吗？）你可以在第50条中找到对这些非标准（但通常可以使用）的容器的一个简要介绍。 非标准的关联容器hash_set、hash-multisetshash_mapOhash_multimapo在第25条中，我分析了这些基于哈希裴的、标准关联容器的变体（它们通常是广泛可用的）。 VeCtOr<char>作为String的替代。第13条讲述了在何种条件下这种替代是有意义的。 vector作为标准关联容器的替代。正如第23条中所阐明的，有时VeCtor在运行时间和空间上都要优于标准关联容器。 几种标准的非STL容器，包括数组、bitset.valarraysstack、queue和PriOrity_queue°因为它们不是STL容器，所以在本书中很少提及，仅在第16条中提到了一种“数组优于STL容器”的情形，以及在第18条中解释了为什么bitset比VeCtOr<bool>要好。值得记住的是，数组也可以被用于STL算法，因为指针可以被用作数组的迭代器。可以做出的选择是很多的，选择的多样性意味着在做选择时要考虑多种因素。不幸的是，大多数关于STL的讨论对于容器的世界涉及很浅，在“如何选择最合适的容器”这一问题上忽略了很多因素。即便是C+标准也是如此。C+标准就“如何在vector、deque和IiSt中做出选择”提供了如下建议：VeCtOr、IiSt和deque为程序员提供了不同的复杂性，使用时要对此做出权衡。VeCtor是默认应使用的序列类型；当需要频繁地在序列中间做插入和删除操作时，应使用list；当大多数插入和删除操作发生在序列的头部和尾部时，deque是应考虑的数据结构。如果算法复杂性是主要的考虑因素，我认为以上的建议是恰当的，但除此之外需要考虑的还有很多。稍后我们将讨论与算法复杂性相对应的有关容器的重要问题。但首先我要引入对STL容器的一种分类方法，该方法没有得到应有的重视。这就是对连续内存容器（contiguous.memorycontainer）和基于节点的容器（node-basedcontainer）的区分O连续内存容器（也称为基于数组的容器，array-basedcontainer）把它的元素存放在一块或多块（动态分配的）内存中，每块内存中存有多个元素。当有新元素插入或已有的元素被删除时，同一内存块中的其他元素要向前或向后移动，以便为新元素让出空间，或者填充被删除元素所留下的空隙。这种移动影响到效率（参见第5条、第14条）和异常安全性（莪们很快将会看至。这一点）。标港的连续血存容器有VeCu）r、String和deque。非标淄的rope也是一个连续内存容器。基于节点的容器在每一个（动态分配的）内存块中只存放一个元素。容器中元素的插入或删除只影响到指向节点的指针，而不影响节点本身的内容，所以当有插入或删除操作时，元素的值不需要移动。表示链表的容器，如IiSt和slist,是基于节点的；所有标准的关联容器也是如此（通常的实现方式是平衡树）。非标准的哈希容器使用不同的基于节点的实现，在第25条将会看到这一点。有以上这些术语作为基础，我们将概括出选择容器时最重要的一些问题。在接下来的讨论中，我将不考虑非STL容器（如数组、bitset等），因为本书毕竟是一本关于STL的书。 你是否需要在容器的任意位置插入新元素？如果需要，就选择序列容器；关联容器是不行的。 你是否关心容器中的元素是排序的？如果不关心，则哈希容器是一个可行的选择方案；否则，你要避免哈希容器。 你选择的容器必须是标准C+的一部分吗？如果必须是，就排除了哈希容器、SHSt和rpeo 你需要哪种类型的迭代器？如果它们必须是随机访问迭代器，则对容器的选择就被限定为VeCtor、deque和Stringo或许你也可以考虑rope（有关rope的资料，见第50条）。如果要求使用双向迭代器，那么你必须避免SliSt（见第50条）及哈希容器的一个常见实现（见第25条）。 当发生元素的插入或删除操作时，避免移动容器中原来的元素是否很重要？如果是，就要避免连续内存的容器（见第5条）。 容器中数据的布局是否需要和C兼容？如果需要兼容，就只能选择VeCtor（见第16条）。 元素的查找速度是否是关键的考虑因素？如果是，就要考虑哈希容器（见第25条）、排序的Veaor（见第23条）和标准关联容器一或许这就是优先顺序。如果容器内部使用了引用计数技术（referencecounting）,你是否介意？如果是，就要避免使用String,因为许多String而实现都使用了引用计数。rope也需要避免，因为权威的r。Pe实现是基于引用计数的（见第50条）。当然，你需要某种表示字符串的方法，这时你可以考虑VeetOr<char>。对插入和删除操作，你需要事务语义（transactionalsemantics）吗？也就是说，在插入和删除操作失败时，你需要回滚的能力吗？如果需要，你就要使用基于节点的容器。如果对多个元素的插入操作（即针对一个区间的形式见第5条）需要事务语义，则你需要选择list,因为在标准容器中，只有IiSt对多个元素的插入操作提供了事务语义。对那些希望编写异常安全（exceptionsafe）代码的程序员，事务语义显得尤为重要（使用连续内存的容器也可以获得事务语义，但是要付出性能上的代价，而且代码也显得不那么直截了当。更多细节，请参考SUtter的ExceptionQ/C+网中的第17条）。你需要使迭代器、指针和引用变为无效的次数最少吗？如果是这样，就要使用基于节点的容器，因为对这类容器的插入和删除操作从来不会使迭代器、指针和引用变为无效（除非它们指向了一个你正在删除的元素）。而针对连续内存容器的插入和删除操作一般会使指向该容器的迭代器、指针和引用变为无效。如果在容器上使用SWap,使得迭代器、指针或引用变为无效了，你会在意吗？如果在意，那么你要避免使用String,因为String是STL中在SWaP过程中会导致迭代器、指针和引用变为无效的唯一容器。如果序列容器的迭代器是随机访问类型，而且只要没有删除操作发生，且插入操作只发生在容器的末尾，则指向数据的指针和引用就不会变为无效，这样的容器是否对你有帮助？这是非常特殊的情形，但如果你面对的情形正是如此，则deqUe是你所希望的容器（有意思的是，当插入操作仅在容器末尾发生时，deque的迭代器有可能会变为无效。deque是唯一的、迭代器可能会变为无效而指针和引用不会变为无效的STL标准容器）。这些问题并没有涵盖所有的情形。比如，它们没有考虑不同容器类型所采取的不同的内存分配策略（第10条和第14条讨论了这些策略的某些方面）。但它们应该能使你明白，除非你不关心元素的排序情况、是否与标准相符、迭代器的能力、元素布局与C的兼容性、查找速度、因引用计数所引起的反常行为、是否便于实现事务语义，以及迭代器在何种条件下变为无效，否则，除了容器操作的算法复杂性，你还需要考虑更多的因素。算法复杂性是很重要，但它远不是问题的全部。对于容器，STL给了你多种选择。在STL以外，你还有更多的选择。在选择一个容器之前，请仔细考虑所有的选择。存在“默认的容器”吗？我可不这样认为。第2条：不要试图编写独立于容器类型的代码。STL是以泛化（generalization）原则为基础的：数组被泛化为“以其包含的对象的类型为参数”的容器；函数被泛化为“以其使用的迭代器的类型为参数”的算法；指针被泛化为“以其指向的对象的类型为参数”的迭代器。这仅仅是开始。容器类型被泛化为序列和关联容器，类似的容器被赋予相似的功能。标准的连续内存容器（见第1条）提供了随机访问迭代器，而标准的基于节点的容器（也参见第1条）提供了双向迭代器。序列容器支持PUSh_from和/或PUShJack操作，而关联容器则不然。关联容器提供了对数时间的IoWerjXnmd、UPPerJXnmd和equal_range成员函数，但序列容器却没有提供。随着这样的泛化的不断进行，你自然也想加入到这场运动中来。这种想法是值得赞赏的。当你编写自己的容器、迭代器和算法时，你当然想这么做。可是，很多程序员却以一种不同的方式做泛化。他们在自己的软件中不是针对某种具体的容器，而是想把容器的概念泛化，这样他们就能使用，比如VeCtOr,而仍保留以后将其换成CIeqUe或IiSt的选择但不必改变使用该容器的代码。也就是说，他们试图编写独立于容器的代码（containerindependentcode）o这类泛化，尽管出发点是好的，却几乎总是误入歧途。即便是最热心地倡导独立于容器类型的代码的人也会很快意识到，试图编写对序列容器和关联容器都适用的代码几乎是毫无意义的。很多成员函数仅当其容器为某一种类型时才存在，例如，只有序列容器才支持PUSh_front或PUShJDack,只有关联容器才支持CoUm和lower_bound,等等。即使是insert和erase这样的基本操作，也会随容器类型的不同而表现出不同的原型和语义。比如，当你向序列容器中插入对象时，该对象位于被插入的位置处；而当你向关联容器中插入对象时，容器会按照其排序规则，将该对象移动到适当的位置上。又如，当带有一个迭代器参数的erase作用于序列容器时，会返回一个新的迭代器，但当它作用于关联容器时则没有返回值（第9条给出了一个例子，说明这将如何影响你的代码）。假设你想编写对于大多数通用的序列容器（即vector、deque和IiSt）都适用的代码，那么很显然，你的程序只能使用它们的功能的交集，这意味着你不能使用reserve或capacity（见第14条），由山deque而IiSt中没有这样的操作。由手底旃存在，熹味着你也要放弃OPeratO山，而且你要把操作限制在双向迭代器的能力范围之内。进一步说，这意味着你要放弃那些要求随机访问迭代器的操作，包括Sort、Stable_sort、PartiaLSOrt和nth_element（见第31条）。另一方面，为了要支持VeCtor,你就不能使用PUSh_front和pop_front；但是对于VeCtor和deque而言，SPIiCe和成员函数形式的SOrt又是被禁用的。结合以上这些限制条件，最后的这一限制意味着你的“泛化的序列容器”将没有任何形式的Sort可供使用。这是显而易见的。如果违背了上述任何限制，那么你的代码对某一种你想使用的容器将无法编译通过。而能够编译通过的代码则更加危险。这些限制的根源在于，对不同类型的序列容器，使迭代器、指针和引用无效（invalidate）的规则是不同的。要想使你的代码对VeCto、deque和IiSt都能工作，你必须要假定，对任何一种容器，使迭代器、指针和引用无效的任何操作将在你所使用的容器上使它们无效。所以，你必须假定每个insert调用都使所有迭代器、指针和引用无效，因为deque:insert使所有迭代器无效。而且，由于不能调用CaPaCity,因此VeCtOr:insert必须保证使所有的指针和引用也无效（第1条说明了deque比较独特，它有时候可以使迭代器无效而不必使指针和引用也无效）。类似的推理可得出结论，对erase的每次调用都要假定使一切变为无效。还想听到更多吗？你不能把容器中的数据传递到C接口中，因为只有VeCtor支持这一点（见第16条）。你不能使用bool作为要存储的对象类型来实例化（instantiate）你的容器，因为，如第18条所示，VeCtor<bool>并不总是表现得像一个VeCtOl,它实际上并没有存储bool类型的对象。你不能假定IiSt的常数时间的插入和删除操作，因为VeCtOr和deque进行此类操作耗费的是线性时间。当所有这些限制都被遵守之后，你的“泛化的序列容器”将不能使用reserve、capacity.OPerator口、PUSh_front、popjront.splice,以及任何要求随机访问迭代器的操作；每次对该容器执行insert和erase操作将耗费线性时间，并将所有的迭代器、指针和引用变为无效；该容器内部的布局将和C不兼容，不能存储bool类型的数据。这样的容器真的是你想在应用中使用的容器吗？我认为不会是这样的。如果你没有这么野心勃勃，决定不支持list,那么你依然不能使用reserve、CaPaCity、PUSlLfrOnt和pop_front；依然要假定对insert和erase的每次调用都耗费线性时间并使一切（迭代器、指针和引用）变为无效。你依然失去了和C的布局兼容性；你依然不能存储bool类型的数据。如果你放弃序列容器，转而寻求对于不同的关联容器都能工作的代码，情况并不会好到哪里去。编写对于Set和map都适用的代码几乎是不可能的，因为Set存储单个对象而map存储“一对”对象。即便是编写对于Set和multiset域map和multimap）都适用的代码也未是一件容易的事情。以单个值为参数的insert成员函数对于set/m叩和与之对应的multi类型有不同的返回类型，同时你必须十分小心，不要对容器中同一个值有多少拷贝做任何假定。如果使用m叩和multim叩，那么你要避免使用OPerato山，因为这个成员函数只对map存在。面对现实吧：这么做不值得。不同的容器是不同的，它们有非常明显的优缺点。它们并不是被设计来交换使用的，你无法掩盖这一点。如果试图这样做，那么只是在碰运气，而这种运气却是碰不得的。但是，依然可能会有这么一天，你意识到自己所选择的容器类型不是最佳的，所以你想使用另一种容器类型。你已经知道，当改变容器类型时，不仅需要改正编译器诊断出的问题，还要检查使用该容器的所有代码，以便发现按照新类型的性能特点和它使迭代器、指针及引用无效的规则，代码要做出何种改动。如果你想从VeCtor转到其他类型，要确保不再依赖于VeaOr与C的布局兼容性;如果是从其他类型转到VeCtor,要确保没有用它来存储bool类型的数据。考虑到有时候不可避免地要从一种容器类型转到另一种，可以使用常规的方式来实现这种转变：使用封装（encapsulation）技术。最简单的方式是通过对容器类型和其迭代器类型使用类型定义（typedef）。因此，不要这样写：而要这样写：这样就使得改变容器类型要容易得多，尤其当这种改变仅仅是增加一个自定义的分配子时，就显得更为方便（这一改变不影响使迭代器/指针/引用无效的规则）。即使你没有意识到这些类型定义所带来的封装效果，你可能也会很欣赏它们所节省的工作。比如你有如下类型的对象而你想用COnSLiteratOr来遍历此m叩，你真的想把敲入很多遍吗？当你使用STL有少许经验后，会发现类型定义可以帮你的忙。类型定义只不过是其他类型的别名，所以它带来的封装纯粹是词法（lexical）上的。类型定义并不能阻止一个客户去做（或依赖）它们原本无法做到（或依赖）的事情。如果你不想把自己选择的容器暴露给客户（client）,就得多费点劲儿。你需要使用类（class）。要想减少在替换容器类型时所需要修改的代码，可以把容器隐藏到一个类中，并尽量减少那些通过类接口（而使外部）可见的、与容器相关的信息。比如，当你想创建一个顾客列表时，不要直接使用list。相反，创建一个CUStOmerLiSt类，并把IiSt隐藏在其私有部分：乍一看，这显得很傻。毕竟顾客列表也是链表，不是吗？好吧，或许是。到后来，你可能发现并不需要像先前预计的那样要频繁地在列表的中间插入或删除顾客，但是你需要快速确定最前面的20%的顾客一这一任务适合用nth_element算法完成（见第31条）。可是nth_element要求随机访问迭代器。对于list,它无法工作。在这种情况下，你的顾客“列表（list）”最好用VeCtor或deque来实现。在考虑这种改变时，仍需检查CUStomerLiSt的每个成员函数和友元（friend）,看看它们如何受到影响什艮据性能和使迭代器/指针/引用无效的规则，等等）。但如果你在封装CUStomerLiSt的实现细节方面做得很好，CUStOmerLiSt的客户所受的影响应该可以减至最小。你无法编写独立于容器类型的代码，但是，它们（指客户代码）可能可以。第3条：确保容器中的对象拷贝正确而高效。容器中保存了对象，但并不是你提供给容器的那些对象。当（通过如ESert或PUSh_back之类的操作）向容器中加入对象时，存入容器的是你所指定的对象的拷贝。一旦一个对象被保存到容器中，它经常会进一步被拷贝。当对VeCtOr、Strirlg或deque进行元素的插入或删除操作时，现有元素的位置通常会被移动（复制）（见第5条和第14条）。如果你使用下列任何操作排序算?去（见第31条），next_permutation或previous_permutation,removesUniqUe或类似的操作（见第32条），rotate或reverse,等等那么对象将会被移动（拷贝）。没错,拷贝对象是STL的工作方式。可能你想知道这种拷贝动作是怎样进行的。这很简单。利用一个对象的拷贝成员函数就可以很方便地拷贝该对象，特别是对象的拷贝构造函数（COPyconstructor）和拷贝赋值操作符（COPyaSSignmemoPeratOr）（名称很有寓意，不是吗？）。对Widget这样的用户自定义类，这些函数通常被声明为：当然，如果你并没有声明这两个函数，则编译器会为你声明它们。内置类型（built-intype）（如整型、指针类型等）的实现总是简单地按位拷贝（有关拷贝构造函数和拷贝赋值操作符的细节，可参考任何一本C+的入门书。在E伏MVeC+1中，第11条和第27条是专门针对这两个函数的行为的）。考虑到这些拷贝过程，本条款的意图现在应该很清楚了。如果你向容器中填充对象，而对象的拷贝操作又很费时，那么向容器中填充对象这一简单的操作将会成为程序的性能瓶颈。放入容器中的对象越多，拷贝所需要的内存和时间就越多。而且，如果这些对象的“拷贝”有特殊的含义，那么把它们放入容器时将不可避免地会产生错误（引起出错的一种可能情形请参见第8条）。当然，在存在继承关系的情况下，拷贝动作会导致剥离（slicing）o也就是说，如果你创建了一个存放基类对象的容器，却向其中插入派生类的对象，那么在派生类对象（通过基类的拷贝构造函数）被拷贝进容器时，它所特有的部分（即派生类中的信息）将会丢失：“剥离”问题意味着向基类对象的容器中插入派生类对象几乎总是错误的。如果你希望插入后的对象仍像表现得像派生类对象一样，例如调用派生类的虚函数等，那么这种期望是错误的（关于剥离问题的更多背景知识，请参见E伦CfiVeC+的第22条。关于STL中剥离问题的另一个例子，请参见第38条）。使拷贝动作高效、正确，并防止剥离问题发生的一个简单办法是使容器包含指针而不是对象。也就是说，使用Widg&*的容器，而不是Widget的容器。拷贝指针的速度非常快，并且总是会按你期望的方式进行（它拷贝构成指针的每一位），而且当它被拷贝时不会有任何剥离现象发生。不幸的是，指针的容器也有其自身的一些令人头疼的、与STL相关的问题。你可以参考第7条和第33条。如果你想避开这些使人头疼的问题，同时又想避免效率、正确性和剥离这些问题，可能会发现智能指针（smartpointer）是一个诱人的选择。要想了解更多关于这种选择的知识，请参阅第7条。如果以上的讲述使人觉得STL好像是在疯狂拷贝，那就让我们再想一想。没错，STL做了很多拷贝，但它总的设计思想是为了避免不必要的拷贝。事实上，它总体的设计目标是为了避免创建不必要的对象。把它跟C和C+仅有的内置容器（即数组）的行为做比较：这将创建出InaxNumWidgets个Widget对象，即使我们只会使用其中的几个，或者会立即使用从其他地方（比如从文件中）得到的值来覆盖默认构造函数所提供的默认值。如果不是使用数组，而是用STL,则可以使用VeaOr,当需要时它会增长：也可以创建一个空的VeCtor,它包含足够的空间来容纳InaxNumWidgets个Widget对象，但并没有创建任何一个Widgel对象：与数组相比，STL容器要聪明得多。你让它创建多少对象，它就(通过拷贝)创建多少对象，不会多，也不会少。你让它创建时它才创建，只有当你让它使用默认构造函数时它才会使用。没错，STL容器是在创建拷贝；确实是这样的，你需要明白这一点。但是，跟数组相比，它们仍是迈出了一大步。这是一个不可忽略的事实。第4条：调用empty而不是检查size()是否为0。对任一容器C,下面的代码本质上与是等价的。既然如此，你或许会疑惑为什么要偏向于某一种形式，尤其是考虑到empty通常被实现为内联函数(inlinefunction),并且它所做的仅仅是返回SiZe是否为0。你应该使用empty形式，理由很简单：empty对所有的标准容器都是常数时间操作，而对一些IiSt实现，SiZe耗费线性时间。到底是什么使IiSt这么讨厌呢？为什么它不也提供常数时间的SiZe呢？答案在于IiSt所独有的链接(SPIiCe)操作。考虑如下代码：这段代码只有当list2中在含5的节点之后有含10的节点时才工作。假定这不是一个问题，而把注意力集中在下面这个问题上：链接后的IiStI中有多少个元素？很明显，链接后的IiStI中的元素个数是它链接前的元素个数加上链接过莱的元翥个薮。但有多少个元素被链接过来了呢？应该与find(Iist2.begin()1list2.end()15)和find(Iist2.rbegin()1list2rend,10).base()所定义的区间中的元素个数一样多。好，那究竟是多少个呢？如果不遍历该区间来数一数，你是没法知道的。问题就在这里。假定由你来负责实现list。IiSt不仅是容器，而且是标准容器，它将会被广泛使用。你自然会希望自己的实现尽量高效。你发现用户通常希望知道IiSt中有多少个元素，所以你想使SiZe成为常数时间操作。因此，你希望设计list,使它总知道自己含有多少个元素。同时，你知道在所有的标准容器中，只有IiSt具有把元素从一处链接到另一处而不需要拷贝任何数据的能力。你推断，许多IiSt的客户之所以选择它，是因为它提供了高效的链接操作。他们知道把一个区间从一个IiSt链接到另一个IiSt可以通过常数时间来完成。你很清楚他们知道这一点，所以你当然想满足他们的期望，使SPIiCe成为常数时间的成员函数。这将使你左右为难。如果SiZe是常数时间操作，那么IiSt的每个成员函数都必须更新它们所操作的蠢表的大小(SiZe),当然也应括SPliCe。可是SPIiCe更新它所改变的链表6勺大小的唯一方式是计算所链接的元素的个数，而这会使SPliCe不具有你所希望的常数时间操作性能。如果你不要求SPliCe更新它所改变的链表的大小，则SPliCe可以成为常数时间操作，可是这时SiZe会成为线性时间操作。通常，它需要遍历自己的整个数据结构来看一看自己含有多少个元素。不管你怎么看，某些方面IiSt或SPIiCe必须做出其中的一个可以成为常数时间操作，但不可能二者都是。不同的链表实现通过不同的方式解决这一冲突，具体方式取决于作者选择把SiZe还是SPliCe实现得最为高效。如果你使用的IiSt实现恰好是把SPIiCe的常数时间操作放在第一位的，那么你使用empty而不是SiZe会更好些，因为empty操作总是花费常数时间。即使现在你使用的IiSt实现不是这种方式，将来你也可能会发现自己在使用这样的实现。比如，你可能把自己的代码移植到不同的平台上，该平台上的STL采用了不同的实现；又如，你可能决定切换到当前平台上的不同的STL实现。不管发生了什么，调用empty而不是检查SiZe=O是否成立总是没错的。所以，如果你想知道容器中是否含有零个元素，请调用empty。第5条：区间成员函数优先于与之对应的单元素成员函数。快说！给定Vl和v2两个向量(vector),使Vl的内容和v2的后半部分相同的最简单操作是什么？不必为了当v2含有奇数个元素时”一半”的定义而煞费苦心。只要做得合理即可。时间到！如果你的答案是或者与之类似，你就得到了满分，获得金牌；可是如果你的答案含有不止一个函数调用，但没有使用任何形式的循环，那么你几乎可以得到满分，但得不到金牌；如果你的答案含有一个循环，那你尚需改进；如果你的答案含有不止一个循环，那么，我们说你确实需要这本书了。顺便提一下，如果你对该问题答案的第一反应是“啊？”，那么请特别留意，因为你将要学到一些真正有用的东西。设计这个小测验是为了两个目的。首先.我想通过它提醒你注意存在assign这么一个使用极其方便、却为许多程序员所忽略的成员函数。对所有的标准序列容器(vector,string,deque和IiSt),它都存在。当你需要完全替换一个容器的内容时，应该想到赋值(assignment)o如果你想把一个容器拷贝到相同类型的另一个容器，那么OPerator二是可选择的赋值函数，但正如该例子所揭示的那样，当你想给容器一组全新的值时，你可以使用assign,而OPerator二则不能满足你的要求。设计该小测验的第二个目的是为了揭示为什么区间成员函数(rangememberfunction)优先于与之对应的单元素成员函数。区间成员函数是指这样的一类成员函数，它们像STL算法一样，使用两个迭代器参数来确定该成员操作所执行的区间。如果不使用区间成员函数来解决本条款开篇时提出的问题，就得写一个显式的循环，或许像这样：第43条中详细解释了为什么要尽量避免写显式的循环，但不需要读那一条你就能认识到,写这样的代码比调用assign多做了很多工作。稍后我们将会看到，这个循环在一定程度上影响了效率，但我们先不讨论这个问题。避免循环的一种方法是遵从第43条的建议，使用一个算法：同调用assign相比，所做的工作还是多了些。而且，尽管上面的代码中没有循环，但copy中肯定有（见第43条）。结果是，影响效率的因素仍然存在。同样，这个问题稍后再讨论。在这里，我将稍微偏离主题，指出几乎所有通过利用插入迭代器（insertiterator）的方式（即利用inserter、back_inserter或front_inserter）来限定目标区间的CoPy调用，其实都可以（也应该）被替换为对区间成员函数的调用。比如，在这里，对copy的调用可以被替换为利用区间的insert版本：同调用COPy相比，敲键盘的工作稍少了些，但它更加直截了当地说明了所发生的事情：数据被插入到Vl中。对coPy的调用也说明了这一点，但没有这么直接，而是把重点放在了不合适的地方。对这里所发生的事情，有意义的不是元素被拷贝，而是有新的数据被插入到了Vl中。insert成员函数很清晰地表明了这一点，使用COPy则把这一点掩盖了。数据被拷贝这一事实没有任何意义，因为STL就是建立在拷贝数据这一基础上的。对于STL来说，拷贝是基础，这正是本书第3条的内容。太多的STL程序员滥用了copy,所以我刚才给出的建议值得再重复一下：通过利用插入迭代器的方式来限定目标区间的COPy调用，几乎都应该被替换为对区间成员函数的调用。现在回到assign的例子。我们已经给出了使用区间成员函数而不是其相应的单元素成员函数的原因：通过使用区间成员函数，通常可以少写一些代码。使用区间成员函数通常会得到意图清晰和更加直接的代码。一句话，区间成员函数使代码更加易写易懂。为什么不喜欢它呢？唉，有人会把这些观点归结为程序风格（ProgrammingStyle）的问题，而程序员喜欢争论程序风格问题，就像他们喜欢争论“什么是真正的编辑器”一样（就好像总是有什么疑问一样。毫无疑问，EmaCS是）。既然这样，如果能有一个大家都认可的标准来确立区间成员函数对其相应的单元素成员函数的优越性，那将会是非常有益的C对于标准的序列容器，我们有一个标准：效率。当处理标准序列容器时，为了取得同样的结果，使用单元素的成员函数比使用区间成员函数需要更多地调用内存分配子，更频繁地拷贝对象，而且/或者做冗余的操作。比如，假定你要把一个血数组拷贝到一个VeCtor的前端（首先，数据可能来自数组而不是vector,因为数据来自遗留的C代码。关于STL容器和CAPI混合使用时导致的问题，见第16条）。使用VeCtOr的区间insert函数,非常简单:而通过显式地循环调用insert,或多或少可能像这样：请注意，我们必须记得把insert的返回值记下来供下次进入循环时使用。如果在每次插入操作后不更新insertLoc,会遇到两个问题。首先，第一次迭代后的所有循环迭代都将导致不可预料的行为(UndefinedbehaViOr),因为每次调用insert都会使ESeHLOC无效。其次，即使EsertLoc仍然有效，插入总是发生在VeCtOr的最前面(即在v.begin()处),结果这组整数被以相反的顺序拷贝到V中。如果遵从第43条，把循环替换为对COPy的调用，得到如下代码：当copy模板被实例化之后，基于COPy的代码和使用显式循环的代码几乎是相同的，所以，为了分析效率，我们将注意力集中在显式循环上，但要记住，对于使用copy的代码下列分析同样有效。分析显式循环将更易于理解“哪些地方影响了效率”。对，有多个地方影响了效率，使用单元素版本的insert总共在三个方面影响了效率，而如果使用区间版本的insert,则这三种影响都不复存在。第一种影响是不必要的函数调用。把numVakes个元素逐个插入到V中导致了对insert的numValues次调用。而使用区间形式的insert,则只做了一次函数调用，节省了numValues-1次。当然，使用内联(inlining)可能会避免这样的影响，但是，实际中不见得会使用内联。只有一点是肯定的：使用区间形式的insert,肯定不会有这样的影响。内联无法避免第二种影响，即把V中已有的元素频繁地移动到插入后它们所处的位置。每次调用insert把新元素插入到V中时，插入点后的每个元素都要向后移动一个位置，以便为新元素腾出空间。所以，位置P的元素必须被移动到位置P+L等等。在我们的例子中，我们向V的前端插入numValues个元素，这意味着V中插入点之后的每个元素都要向后移动numValues个位置。每次调用insert时，每个元素需向后移动一个位亶，所以每个元素将移动numVahes次。如果插入前V中有n个元素，就会有n*numValues次移动。在这个例子中，V中存储的是血类型，每次移动最终可能会归为调用memmove,可是如果V中存储的是Widget这样的用户自定义类型，则每次移动会导致调用该类型的赋值操作符或拷贝构造函数(大多数情况下会调用赋值操作符，但每次VeCtOr中的最后一个元素被移动时，将会调用该元素的拷贝构造函数)。所以在通常情况下，把numValues个元素逐个插入到含有n个元素的VeCtOr<Widget>的前端将会有n*numValues次函数调用的代价：S-I)*numValues次调用Widget的赋值榛作符和numValues次调用Widget的拷贝构造函数。即使这些调用是内联的，你仍然需要把V中的元素移动numValues次。与此不同的是，C+标准要求区间insert函数把现有容器中的元素直接移动到它们最终的位置上，即只需付出每个元素移动一次的代价。总的代价包括n次移动、numValues次调用该容器中元素类型的拷贝构造函数，以及调用该类型的赋值操作符。与每次插入一个元素的策略相比，区间insert减少了n*(numValues-1)次移动。细算下来，这意味着如果numValues是100,那么区间形式的insert比重复调用单元素形式的insert减少了99%的移动。在讲述单元素形式的成员函数和与其对应的区间成员函数相比所存在的第三个效率问题之前，我需要做一个小小的更正。我在前面的段落中所写的是对的，的确是对的，但并不总是对的。区间insert函数仅当能确定两个迭代器之间的距离而不会失去它们的位置时，才可以一次就把元素移动到其最终位置上。这几乎总是可能的，因为所有的前向迭代器都提供了这样的功能，而前向迭代器几乎无处不在。标准容器的所有迭代器都提供了前向迭代器的功能。非标准哈希容器的迭代器也是如此（见第25条）。指针作为数组的迭代器也提供了这一功能。实际上，不提供这一功能的标准迭代器仅有输入和输出迭代器。所以，我所说的是正确的，除非传入区间形式insert的是输入迭代器（例如istream_iterator,见第6条）。仅在这样的情况下，区间insert也必须把元素一步步移动到其最终位置上，因而它的优势就丧失了（对于输出迭代器不会产生这个问题，因为输出迭代器不能用来标明一个区间）。不明智地使用重复的单元素插入操作而不是一次区间插入操作，这样所带来的最后一个性能问题跟内存分配有关，尽管它同时还伴有讨厌的拷贝问题。在第14条将会指出，如果试图杷一个元素插入到VeCtor中，而它的内存已满，瓠么Veetor将分配具宥更大容量（capacity）的新内存，把它的元素从旧内存拷贝到新内存中，销毁旧内存中的元素，并释放旧内存。然后它把要插入的元素加入进来。第14条还解释了多数VeCto