关于STL的一些零碎

        STL中有着几个重要的概念，即迭代器（iterator）、算法（algorithm）和容器，这三者之间有一些可以墨迹的纠葛。

一、容器选择
1、容器种类       
        （1）标准STL序列容器：vector、string、deque和list。
        （2）标准STL关联容器：set、multiset、map和multimap。
        （3）非标准序列容器：slist和rope，slist是一个单向链表，rope本质是一个重型string。
        （4）非标准关联容器：hash_set、hash_multiset、hash_map和hash_multimap。
        （5）vector：作为string的替代。
        （6）vector作为标砖关联容器的替代。
        （7）几种标准的非STL容器：包括数组、bitset、valarray、stack、queue和priority_queue。
2、容器选择
        C++标准就如何在vector、deque和list中做出选择时提出了如下建议：
        （1）vector是默认应该使用的序列类型，其操作类似于数组。
        （1）当需要频繁地在序列中间做插入和删除操作时，应该选用list。
        （2）当大多数插入和删除操作发生在序列的头部和尾部时，应该选择deque。  

二、empty or size
        判断容器是否为空时，果断选择empty而不是size==0，理由是：empty对所有的标准容器都是常数时间操作，而对一些list实现，size耗费线性时间。
        list之所有会如此笨拙是因为其独有的链接操作（splice），举例说明如下：
        list list1;
        list list2;
        // 把list2中从第一个含5的节点到最后一个含10的所有节点移动到list1的末尾
        list1.splice(list1.end(), list2, find(list2.begin(), list2.end(), 5), find(list2.rbegin(), list2.rend(), 10).base());
        如果要保持size是常数时间，则这个操作必须遍历链接过来的元素数以保证size是常数，这样一来splice就不是常数时间的成员函数了，因为要遍历链接过来的元素。
        熊掌与鱼不能兼得，这个法则同样适合于码农界，因此，STL选择了保证splice常数时间而舍弃size。

三、摒弃auto_ptr
        切勿创建包含auto_ptr的容器对象，因为当复制一个auto_ptr时，它所指向的对象的所有权被移交到复制的auto_ptr上，而它自身被置为NULL，即复制一个auto_ptr意味着改变它的值，举例说明如下：
        auto_ptr pw1(new widget);    //pw1指向一个widget
        auto_ptr pw2(pw1);              //pw2指向pw1的widget，pw1被置为NULL（widget的所有权从pw1转移到pw2上）
        pw1 = pw2;                                       //现在pw1又指向widget了，pw2被置为NULL
        这都不足为奇，再举例就会发现问题所在了，创建一个包含auto_ptr的vector，然后用一个比较该auto_ptr所指的widget值的函数做排序：
        bool widgetAPcompare(const auto_ptr &lhs, const auto_ptr& rhs)
        {
            return *lhs < *rhs;            
        }
        vector  > widgets;
        sort(widgets.begin(), widgets.end(), widgetAPCompare());        //对vector排序
        上面的排序会导致widgets中的一个或多个auto_ptr可能被置为NULL，对vector所做的排序操作可能会改变它的内容，原因如下：
        sort一般采用快速排序算法实现，其在对容器进行排序时，容器中的某个元素被当做基准元素（pivot element），然后对大于和小于等于该元素的其它元素递归调用排序操作，即会把基准元素复制到局部临时变量中，这样容器中作为基准元素的auto_ptr就会被置为NULL，更要命的是这个局部临时变量在作用域结束时，会自动删除自己所指向的widget，因此，当对sort调用返回时，vector中至少有一个widget已经被删除了，也有可能vector中的几个元素都被置为NULL，而相应的几个widget都被删除了，这是因为快速排序是递归算法，所以它很可能在每一层递归时都复制了一个基本元素。