使用class template扩展STL map容器类对象的一个例子

xiaomiao

//////////////////////////////////////////////////////////////////
//auto_map: 析购时候对map对象的second区域字段释放内存
/////////////////////////////////////////////////////////////////
template <class Key, class T, class Compare = less<Key>,
          class Allocator = allocator<pair<const Key, T> > >
class auto_map : public map<Key,T,Compare,Allocator>
{
public:
    explicit auto_map(const Compare& comp = Compare(),
             const Allocator& alloc = Allocator())
    :map<Key,T,Compare,Allocator>(comp,alloc)
    {
    };
    void clear()
    {
        fnFree();

        map<Key,T,Compare,Allocator>::clear();
    }
    ~auto_map()
    {
        fnFree();  
    };

private:
    void fnFree()
    {
            // you must declare typename keyword here
        typename map<Key,T,Compare,Allocator>::iterator it = map<Key,T,Compare,Allocator>::begin();
        for(;it != map<Key,T,Compare,Allocator>::end();++it)
        {
            delete (*it).second;
        }  
    }
};

converse

要是second不是指针呢?

hellhell

大概用functor对delete再包一层比较好

whyglinux

STL 的设计中没有使用虚函数机制，这主要是从执行效率方面来考虑的。因此，对于 STL 中的容器类来说，它所有的成员函数，包括析构函数，都是非虚成员函数。而如果一个类的析构函数是非虚函数的话，就决定了不适合从这个类派生其它类型，因为如果这么做的话，通过基类指针删除指向的派生类对象时会造成不正确的析构。

如果要在容器类的基础上建立一个新的类型，用容器类声明一个新建类的数据成员是唯一正确的做法。千万不要把 C++ 标准库中的容器类作为基类使用。

wolf0403

convers 那个签名啊，看一次一身冷汗……

STL 的设计中没有使用虚函数机制，这主要是从执行效率方面来考虑的

晚生不以为然。STL 遵从 C++ 设计思想，一切以值语意为设计根本（与此相对的是 Java/C# 的引用语意），从一个类的复制构造函数的重要性就可以窥见端倪。STL 非常完整地继承并发扬了这个设计思路，容器元素只能是『值』——就算你放的是一个指针，它也只当作一个值来操作。

因此，使用 shared_ptr 才是王道。

wolf0403

事实上，如果 STL 使用引用语意管理元素，效率可以得到进一步提升（想想 vector 重新分配时导致的全部对象复制）。
基于指针语意的容器可以参考 ptypes 系列：）

SeaKing911

顶一个，立志要学好STL

whyglinux

原帖由 wolf0403 于 2006-9-29 00:05 发表
晚生不以为然。STL 遵从 C++ 设计思想，一切以值语意为设计根本（与此相对的是 Java/C# 的引用语意），从一个类的复制构造函数的重要性就可以窥见端倪。STL 非常完整 ...

容器类采用值语义还是引用语义只是决定了容器中元素的归属问题，不会影响容器的操作——值语义决定了在容器中操作的元素是对象的拷贝，对原来的对象没有影响；引用语义不产生拷贝，操作的是同一个对象。既然如此，那么值或引用语义也就不会影响到容器的接口界面，就更不用说界面的实现方式了，所以说这不是 STL 容器类不使用虚函数成员的原因所在。

这篇文章支持我前面的观点，供参考
http://www.codersource.net/published/view/326/stl_overview.aspx


题外话：“晚生不以为然”这句话在语意表达上不连贯。“晚生”当然是一种自谦，含虚心之意；之后的“不以为然”其意是表示不同意，但多含轻视意，结果到了这里语意陡转，谦虚之意荡然无存。这恐非本意。因此，可将“晚生不以为然”换为“晚生以为不然”，这就没有语病了。

原帖由 wolf0403 于 2006-9-29 00:11 发表
事实上，如果 STL 使用引用语意管理元素，效率可以得到进一步提升（想想 vector 重新分配时导致的全部对象复制）。
基于指针语意的容器可以参考 ptypes 系列：）

如果真是你说的那样的话，STL 容器类会毫不犹豫地使用（至少是部分使用）引用语义。然而实际上 STL 一直基于值语义，这应该很能说明一些问题了。

需要清楚的是：引用是一种间接访问方式；另外，引用语义一般还需要进行引用计数，等等。这些“附加项”往往决定了引用语义容器无论在实现效率还是在执行效率的许多方面（比如遍历容器）都没有值语义容器高效。因此，情况都不是绝对的：想当然地认为引用语义一定比值语义高效是站不住脚的；不过，有的情况用引用语义会带来使用上的方便，有的情况也会带来效率上的提升。

实际中既存在着值语义需求又存在着引用语义需求。由于所有的引用语义需求都可以在值语义的基础上进行构建实现，加上引用语义在实现和应用上的限制，通常认为 C＋＋ 标准库中只提供基于值语义的容器类就足够了——其余的在此基础上由用户去实现吧。

另外，无论是哪种容器，它代表的其实是一种数据结构和算法。每个容器都有自己的特点和缺陷，选择了其中之一也就意味着同时接受了它的缺点，所以到底哪种容器适合使用不是单一方面所能决定的，这中间还存在着一个综合平衡和使用的问题。比如你上面提到的 vector 重新分配内存和拷贝的问题，可以通过事先为
vector 分配内存、或者用 list 代替 vector 等方法避免这个问题，而有时这样的问题不可避免。通常要综合考虑多方面的情况，才能决定一种适合问题解决的、代价最小的方案。

wolf0403

呵呵，首先为『晚生不以为然』的疏漏表示抱歉。。：）

我们回到最初的问题。楼主为了能够在删除 map 元素的同时为 map 中被映射对象（mapped_type）调用 delete 释放而派生了 std::map，您就此提出『STL 的设计中没有使用虚函数机制』以及『而如果一个类的析构函数是非虚函数的话，就决定了不适合从这个类派生其它类型』。实际上错误是从这里开始的。首先，STL 的容器设计确实没有采用虚函数，但是这并不代表我们不能从这些容器类派生。虚拟函数的作用只存在于我们需要多态行为的时候，也就是说，我们需要通过基类接口操作派生类对象的时候才会起到作用。而这里，很明显的，楼主的代码实际只是在重用 std::map 的实现代码和接口，并不希望客户程序将这个 auto_map 当作一个 std::map 使用，因此，std::map 是否使用了虚拟函数已经无关紧要。
实际上，可以翻开 STL 源码看看。包括 vector 在内的容器，在 STL 中很常见的实现都包含了类型的派生。使用一个基类负责内存的分配和管理，而最终的 vector 等容器类专注于容器语意的实现。这种纯粹的代码重用是不需要借助于虚拟函数的，也并不违反 STL 中『高效』的设计初衷。
其次，楼主的代码其实更好（或者说，更符合教科书理论）的实现方案是，将 auto_map<T> 私有派生自 std::map<T>，然后重新实现这个接口。私有继承作为 C++ 中比较独特的一种继承手段，实际是专门用于表达『实现继承』的概念的。私有继承后，可以通过 using 语法公开可以直接重用的接口，而自己实现不可直接重用的接口。这样就可以在编译器层面防止『从 std::map 引用或指针操作 auto_map』这种错误的产生了。

我的第一个回答是误解了题意，而随后关于值语意和引用语意的容器中，您使用错误的论据证明了错误的论题。如果有兴趣我们可以单独探讨。

wolf0403

对于容器管理指针或者对象本身，我们可以做一个效率和实用性方面的分析。首先分析普通情况：当容器中保存的是指向对象的指针，而不是对象本身的时候，我们会在多少情况下造成效率的损失？
要说效率损失的程度，首先需要考察的是，效率损失的可能来源。有多少情况下我们需要操作对象本身？

• 向容器中插入对象的时候
• 通过迭代器引用对象的时候
• 析构容器，删除容器管理的所有对象的时候
  

另外还有一个特殊情况，就是

• vector / deque 重新分配内存时，引发的容器中元素的移动
  

详细对比一下这三个情况下，保存指针的容器和保存对象容器的行为区别：

• 向容器中插入对象的时候
  
  • STL：复制一个对象，将这个对象的副本交由STL容器管理
  • 指针语意：取对象地址存入容器
    
• 通过迭代器引用对象的时候
  
  • STL：根据容器的cv-qualifier，返回reference或const_reference，然后通过这个返回的引用来间接引用对象
  • 指针语意：直接返回对象地址
    
• 析构容器，删除容器管理的所有对象的时候
  
  • STL：析构所有容器管理的对象
  • 指针语意：根据容器策略，减少对象引用记数，或者（当对象彻底交由容器管理时）析构元素
    
• vector / deque 特殊情况下：
  
  • STL：分配内存，为每个位于旧缓存中的元素在新地址上创建副本（通过copy-ctor），析构旧副本
  • 指针语意：直接复制指针到新的缓存，然后直接释放旧缓存，不涉及对象操作
    
  
  

对比分析一下可以发现，

• 情况1：当构造一个元素只是为了加入容器时，STL 会强迫带来一次额外的对象复制
• 情景2：效率取决于引用和指针的底层实现方式，多数编译器不会有太大差别（据说部分编译器将引用实现为双重指针，则引用反而带来更大效率问题）
• 情景3：指针语意容器明显可以提高基于策略的灵活性
  

在特殊情况下，由于内存重分配是一个容器内部的过程，属于实现细节，本身不应该与对象有任何相关；而在 STL 实现中，不仅调用了额外的对象操作，甚至影响了对象的生命周期。这不仅带来效率的损失，甚至可能带来语意的差别，导致错误的出现（譬如，如果需要用容器管理一系列不可复制的对象）。

因此，简单的结论是，指针容器在所有情况下完胜基于值语意的 STL 容器。

如果真是你说的那样的话，STL 容器类会毫不犹豫地使用（至少是部分使用）引用语义

请注意，前面我已经提到过，STL选用值语意而非引用语意，完全是为了遵循贯穿C++语言设计的值语意整体思路。C++的类型系统突出值语意，突出对象生命期，并极大程度鼓励程序员在实现类型的时候通过重载操作符，模拟原始值类型（int, double 等）的行为方式。这样在很多情况下固然能写出风格统一、漂亮的代码，但是当作为实现容器时仍坚持这种方式，带来的只能是一些不必要的损失。
为了解决不必要的对象复制问题，C++社区先后推出了多种解决方案：消除临时对象的 RVO/NRV优化，以及新的  move-constructor 提案。几乎可以认为，move-constructor 就是为了解决 vector 的性能和语意问题而专门提出的。所以，STL 的值语意设计绝不是完美的。它实际上只是一个语言政策的，或者说，对问题进行错误建模的牺牲品。

ps. 还有一种情况会引发单独元素访问：从容器中删除一个元素。除 vector / deque 之外，两种容器的行为都只涉及析构元素和释放内存；而对于 vector / deque 可能引发部分元素的移动，归入前文的特殊情况讨论。

[ 本帖最后由 wolf0403 于 2006-10-1 08:37 编辑 ]