Chinaunix首页 | 论坛 | 博客
  • 博客访问: 6004643
  • 博文数量: 2759
  • 博客积分: 1021
  • 博客等级: 中士
  • 技术积分: 4091
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-11 14:14
文章分类

全部博文(2759)

文章存档

2019年(1)

2017年(84)

2016年(196)

2015年(204)

2014年(636)

2013年(1176)

2012年(463)

分类: C/C++

2013-06-30 09:30:00

原文地址:关于STL的一些零碎 作者:scq2099yt

        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都被删除了,这是因为快速排序是递归算法,所以它很可能在每一层递归时都复制了一个基本元素。






        
阅读(1005) | 评论(0) | 转发(0) |
0

上一篇:c语言调用java类

下一篇:java多线程示例

给主人留下些什么吧!~~