[34] Container classes  Updated! 
(Part of C++ FAQ Lite, Copyright © 1991-2009, Marshall Cline, cline@parashift.com)

简体中文版翻译：Zhiguo Zhang

FAQs in section [34]:

[34.1] 为什么要使用的容器类 ，而不是简单的数组？

因为数组是罪恶。

假设最好的情况：你是一位经验丰富的C程序员，这意味着你很善于处理数组。你知道你可以处理的数组的复杂性，并且你积累了多年经验。而且你聪明-在团队是最聪明的-在全公司也是最聪明的。但是，即便如此， 在开发之前请阅读并思考本节所有的FAQ。

从根本上可以把它归结为这个简单的事实：C + +不是C（这可能说到了你的痛楚！！）。你需要把你的通过丰富经验积累得到的来之不易的智慧搁置起来，应为这两种语言就是不一样。在C中“最好”的做法在C++不一定是“最好”的。如果你真的想使用C编程，那就请你使用C语言编程。但如果你想成为真正的C + +高手，那么就要学习C + +的处事方式。你可能是一个C大师，但如果你刚刚开始学习C + +，你只是一个新手。（哎哟，我知道说到你的痛处。抱歉。）

以下是你需要了解的容器与数组知识：

  1. 容器类可以提高程序员的工作效率。如果你坚持要用数组，而周围的人都愿意使用容器类，你的工作效率可能会比他们低（即使你很聪明，比他们更有经验！）。
  2. 容器类可以让程序员编写更健壮的代码。如果你坚持使用数组，而周围的人都愿意使用容器类，你的代码错误很可能会比他们多（即使你聪明，比他们更有经验）。
  3. 如果你太聪明， 太有经验的，以至于象其他人使用容器类那样你可以高效和安全的使用数组。但是其他人可能要维护你的代码， 他们可能会引入错误。更糟的是，你是唯一一个可以维护你的代码的人，所以管理人员将把你从开发团队中抽出来，让你做全职的代码维护你-这可是你一直想干的！

以下是使用数组的一些具体问题：

  1. 没有检查下标是否出界。（请注意，有些容器类， 如std::vector ，含有不检查下标的元素访问方法。）
  2. 数组通常要求从堆中分配内存（见下文的例子），在这种情况下你必须确定手动分配内存最终被删除（即使例外被抛出的情况下）。当你使用容器类，内存管理是自动处理的，但是当你使用数组的时候，你必须手动编写大量代码（不幸的是 ，通常需要一些技巧 )。例如，除了编写代码来析构所有的对象和delete内存之外，对于数组你通常还需要添加额外的try和catch块来析构所有对象和delete内存，然后再重新引发异常。这是个真正的苦差事， 如这里所示。当使用容器类， 事情将会更简单。
  3. 您不能插入元素到数组中间，甚至添加到数组的末尾，除非你是通过堆分配的数组，即使如此，你必须分配一个新的数组和复制所有的元素。
  4. 容器类给可以传递引用或值，但数组不能：数组总是通过引用传递。如果你想模拟数组的值传递，你必须手动编写代码来明确复制数组元素（可能从堆中分配），以及编写代码来清理数组的拷贝。如果使用容器类，这一切都是自动处理。
  5. 如果你的函数有一个非静态局部数组（即“auto”数组），那么你不能返回该数组。但是如果是容器类对象，那么情况将不是这样。

下面是使用容器的一些思考：

  1. 不同的C + +容器有不同的长处和弱点，但对于任何给定的工作有通常只有一个是较好的-更清晰，更安全，更方便 /便宜，而且往往比数组更有效率。举例来说：
  2. 容器类不一定是最好的解决方案 ，有时你可能需要使用数组。但是这应该是很罕见的，如果/当它发生的时候：

为了澄清这一点，数组是万恶之源。你可能不会这样想，如果你不熟悉C + +。但在你写一大堆使用数组（尤其是如果你让你的代码无内存泄漏和异常安全）的代码之后，你就会知道，这是避易就难。或者，你直接相信我，这将是捷径。选择权在你。

[ Top | Bottom | Previous section | Next section | Search the FAQ ]

[34.2] 如何在C + +实现一个类似perl的关联数组？

使用标准类模板std::map<Key,Val>：

 #include <string>
 #include <map>
 #include <iostream>
 
 int main()
 {
   // age is a map from string to int
   std::map<std::string, int, std::less<std::string> >  age;
 
   age["Fred"] = 42;                     // Fred is 42 years old
   age["Barney"] = 37;                   // Barney is 37
 
   if (todayIsFredsBirthday())           // On Fred's birthday,
     ++ age["Fred"];                     //    increment Fred's age
 
   std::cout << "Fred is " << age["Fred"] << " years old\n";
   ...
 }

[ Top | Bottom | Previous section | Next section | Search the FAQ ]

[34.3] std::vector<T>的储存空间肯定是连续的吗？ Updated! 

[最近被删除的过时的警告， 这个尚未被批准。感谢Alberto Ganesh Barbati and Gerald Thaler （9 / 06）。 点击这里链接到“最近修改文档链”的下一个FAQ] 。

是。

这意味着以下技术是安全的：

 #include <vector>
 #include "Foo.h"  /* get class Foo */
 
 // old-style code that wants an array
 void f(Foo* array, unsigned numFoos);
 
 void g()
 {
   std::vector<Foo> v;
   ...
   f(v.empty() ? NULL : &v[0], v.size());  ← safe
 }

有趣的表达式v.empty() ? NULL : &v[0]传递NULL指针如果v是空的，否则传递v的第一个元素的指针。如果你事先知道v不是空的，你可以最该为v[0]。

一般来说，这意味着可以保证&v[0] + n == &v[n]，其中v是一个std::vector <T>，n是一个从0 到v.size()-1的整数。

然而 v.begin（）是不能保证是 T *，这意味着v.begin（）不能保证和&v [0]是相同的：

 void g()
 {
   std::vector<Foo> v;
   ...
   f(v.begin(), v.size());  ← Error!! Not Guaranteed!!
     ^^^^^^^^^-- cough, choke, gag; not guaranteed to be the same as &v[0]
 }

不要给我发电子邮件，并告诉我在你特定的编译器的特定版本的特定平台上v.begin（）==&v [0]。我不在乎，并且显然你已完全跑题了。重点是帮助你了解在所有符合标准的实现这种代码是可以保证正常工作的，而不是研究不同的具体实现。

[ Top | Bottom | Previous section | Next section | Search the FAQ ]

[34.4] 如何建立不同类型的对象的 <favorite container>？

你不能，但你可以很好的伪造。在C / C + +中所有的数组是同质的（即元素都是相同的类型）。然而，加上一个间接层你可以构造一个异构容器（异构容器是一个容器所包含的对象是不同类型）。

异构容器有两种情况。

第一情况是要存储的所有对象均是从一个公共基类派生的。那么你可以声明/定义你的容器类存储基类指针。通过存贮派生类对象的指针，你可以间接地存储对象到容器中。然后，你可以通过指针访问存贮在容器中的对象（享受多态）。如果你想知道在容器中的对象的确切类型，你可以使用“dynamic_cast”或typeid()。你可能需要虚拟构造函数技巧来复制包含有不同类型对象的容器 。这种方法的缺点是，内存管理可能会有问题（谁“拥有”指针指向的对象？你析构容器的时候是否需要删除这些指针指向的对象？怎么能保证没有其他人拥有这些指针的副本？如果你不删除这些指针指向的对象当你析构容器的时候，你怎么能确定最终会有人将其删除？）。这也使得复制更加复杂的容器更加困难（有可能破坏容器的复制功能，因为你不想复制指针，至少不是这样在容器 “拥有”指针指向的对象的时候）。

第二种情况是要存储的对象类型是不相交的-他们没有一个共同的基类。方法是使用一个handle类。容器存储handle对象（存储值或指针器，你的选择，按值更容易些）。每一个handle对象知道如何“留住”（即维持一个指针）你要存放到容器内的对象。你可以使用一个单一的handle类，以不同的类型指针作为实例数据，或包含层次结构的handle类，可以处理你要存放的不同类型（容器存储Handle基类指针）。这种方法的缺点是，每次改变容器可以包含类型的时候，你需要维护handle类(们)。好处是可以使用的handle类（们）来封装丑陋的内存管理和管理对象生存期。因此使用handle对象对于第一种情况也是有益的。

[ Top | Bottom | Previous section | Next section | Search the FAQ ]

[34.5] 如何插入/访问/修改链表/哈希表等的元素？

最重要的是要记住：不要从零开始，除非有充分的理由这样做。换句话说，而不要创建自己的链表或哈希表，请使用标准类模板，如std::vector<T>或std::list<T>等。

假设你有一个令人信服的理由来构建自己的容器，下面是如何处理插入（或访问，更改等）的容器的元素。

为了使讨论更具体一些，我将讨论如何插入链表元素。这个例子足够复杂，它可以应用到vectors，哈希表，二叉树等。

链表可以轻松插入到第一个元素之前或最后一个元素之后，但仅仅局限于此，我们的库函数功能就太弱了（功能太弱的函数库还不如没有函数库）。对于答案C + +新手需要消化吸收很多，所以我出几个选择。第一个选择是最简单的，第二个和第三个更好。

  1. 为list提供“当前位置”和成员函数，像advance(), backup(), atEnd(), atBegin(), getCurrElem(), setCurrElem(Elem), insertElem(Elem)，和removeElem()。虽然在小型工程中这样可以工作，但是因为只有一个“当前位置”，所以很难访问两个或两个以上的list元素（例如，“对所有的x，y对执行下列...")。
  2. 删除list上述成员函数本身，并将其移动到一个单独的类ListPosition。ListPosition将充当list的“当前位置”。 这使得在list中可以有多个“位置”。ListPosition将是list的友类。这样list类可以隐藏内部实现细节（否则内部实现都必须成为list的公共成员函数）。注意：对于advance()和backup()ListPosition类可以使用运算符重载，因为运算符重载是成员函数的syntactic sugar。
  3. 考虑将整个迭代作为一个原子事件，并创建一个类模板来实现。这避免了访问公共成员函数（可能是虚函数)，这种访问往往是在一个内部循环发生，从而提高了性能。不幸的是，类模板将增加目标代码的大小，因为模板通过复制代码来获得速度提升。更多信息，请参阅[Koenig, "Templates as interfaces," JOOP, 4, 5 (Sept 91)], and [Stroustrup, "The C++ Programming Language Third Edition," under "Comparator"]。

[ Top | Bottom | Previous section | Next section | Search the FAQ ]

E-Mail E-mail the author
[ C++ FAQ Lite | Table of contents | Subject index | About the author | © | Download your own copy ]
Revised Jan 2, 2009