C++5×5断想之五：我之C++拍案惊奇

理解“remove”为什么实际上并没有删除任何东西，1998年？我与STL的remove算法相遇得不是时候。当我期望Visitor设计模式访问个啥的时候，我也认定remove算法就应该删除某个东西。但结果让我非常震惊，我发现在容器上执行remove[注释5]时，容器内元素数目根本不会改变！我有一种被出卖的感觉——我是正儿八经要求删除啊！骗子！谎言！无聊的广告！

后来我读到一篇文章——可能是Andrew Koenig的《C++ Containers are Not Their Elements》（发表于《C++ Report》1998年11-12月刊）——它才让我明白STL内部的真相：算法不能改变容器内元素的数目，因为算法根本不知道容器的类型。容器还可能是一个数组呢，显然数组的大小是不可改变的[注释6]。自然，算法应该和容器彼此独立，互不影响。我认识到，“remove”不会改变容器内元素数目，因为它不能。直到那时，我才算真正理解了STL的内部结构，知道迭代器（iterator）虽然通常由容器成员函数提供，但就像容器和算法一样，其实它也是完全独立的实体。后来，我把这篇文章读了很多次。类似上面的解释，可能别人都说过很多回了，但别怪我鹦鹉学舌，这可是我第一次真正理解remove。

自此以后，我就能与remove和睦相处了。再后来，当发现remove不仅将份内事情做得很好，而且效率超过绝大多数程序员自己编写的循环（remove的运行时间是线性的，而普通循环是二次的）时，我甚至对它有点另眼相看了。虽然我仍然不太喜欢这个命名，但也说不清到底哪个名字既能准确描述其行为，又便于记忆。

理解Boost库里shared_ptr的deleter如何工作，2004年。Boost的引用计数智能指针shared_ptr很有趣——你可以向其构造器传递一个函数或者仿函数（function object，或functor），当引用计数归零的时候，它将在被引用对象上调用删除器（deleter）[译注7]。乍一看，似乎没啥了不起啊，但请看代码：

template<typename T>

class shared_ptr {

public:

      template<typename U, typename D>

      explicit shared_ptr(U* ptr, D deleter);

      ...

};

注意shared_ptr<T>必然在析构时调用类型为D的删除器，然而它根本不知道D为何物。这个对象不能包含类型为D的数据成员，也不能指向类型为D的对象，因为声明其数据成员时，D对它而言还是未知的。那么，shared_ptr对象如何跟踪删除器（它在构造阶段传入；当T对象将被销毁时，还得使用它）呢？更通俗地说，构造器如何将未知类型的信息传递给它正在构造的对象，而这个对象本身对信息类型完全无知？

答案很简单：让此对象包含一个指向已知类型基类的指针（Boost叫它sp_counted_base），然后让构造器以D为参数实例化一个派生于上述基类的模板（Boost中叫sp_counted_impl_p和sp_counted_impl_pd），最后用声明于基类、实现于派生类的虚函数（Boost中使用dispose）去调用删除器。用图表示更为直观：

完全明白了——只要你看过这个图[译注8、9]。而且，看过此图后，我想你马上就会意识到它可以应用在很多领域；它为模板设计拓宽了思路，比如，模板化类使用很少的模板参数（例如shared_ptr只有一个），就可以跟踪无限个先前未知类型的信息）。当我想到这些的时候，我禁不住面露赞许的微笑，难抑钦佩之情[译注10]。

好了，文章结束，这就是我的5×5系列的末篇。简单总结一下本系列全部文章：C++历史上最重要的图书、文献、软件、人物，最后是对我来说最难以忘怀的五个神奇时刻。我还将再次和大家讨论这类有趣的话题，不过那至少应该是又一个18年后了。

注释：

1. 可能不一定非叫“特殊”成员函数不可——不过《Standard》如此称呼——具体包括缺省构造器、拷贝构造器、拷贝赋值操作符和析构函数。之所以“特殊”，是因为如果使用了它们而又未显式声明，编译器一般会隐式生成。

2. “Grinch两腿冰冷站在雪地里，想了又想：‘怎么会这样呢？’”参见Dr. Seuss的《Grinch如何偷走圣诞节》（Random House出版社，1957年）。不过在网上也能看到哦（http://www.kraftmstr.com/christmas/books/grinch.html，别告诉Random House）。

3. 我指的是不消耗更多运行时时间。他们大量使用了模板，当然会增加编译时间。

4. 你将两个数相乘时，就等于增加了指数次数，没忘记吧？

5. 我指的是STL的通用算法，而非list类的成员函数。

6. 重新分配内存不能算，不是所有的数组都是动态分配的。

7. 不要吃惊，TR1的shared_ptr就是以Boost的shared_ptr为基础并提供了相同功能。我正讨论的是Boost的shared_ptr，因为它有一个实现，我们这里说的也是实现问题。TR1仅仅是一个规范，如果你书生意气，问我TR1里讲的东西如何实现，那就没意思了。

8. 更准确地说，你以前应该看到过相关解释。譬如我，我得到的解释（我经常要别人给我讲解C++方面的问题）来自于Usenet新闻组的一个免费讨论（http://tinyurl.com/r66ql）。

9.我相信它也是外部多态（External Polymorphism，http://www.cs.wustl.edu/~schmidt/PDF/External-Polymorphism.pdf）设计模式的一个应用。自从我读过Chris Cleeland 和Douglas C. Schmidt于1998年9月发表在《C++ Report》上的有关此模式的文章后，我就喜欢上它了。不过直到现在，我仍然没看到这个模式的广泛应用。

10. 我觉得有两点需要说明。第一，它是Boost中大量成功创新的一个典范，Boost的创新性正是我将其列入“最重要C++软件”的原因之一。第二，很可惜的是，Boost中的这些创新未被整理并在C++社区广泛传播，很多有趣的东西，都掩藏在Boost库的盖子下不为人知。 

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1793463