闲谈STL容器之size()成员函数
浏览:2367次 出处信息
在实际情况不是特别要求自己需要实现特殊的数据结构的时候,一般采用STL容器,是又快又好又安全的做法。
孙子兵法曰:“知己知彼,百战不殆”。
我们一般人写程序,不可避免要使用别人开发的库来搭积木。其实也讲究这个“知己知彼”:
知己----对自己程序要实现的业务逻辑分析清楚,时间上、空间上的复杂度等;
知彼----对我们所使用的库也要有一定的了解,了解的越清楚越好;当然我们可能不会去完全了解各个库,这要看个人的修养方向了。
回到STL容器来说,一般容器都有size()成员函数的实现,我们很明白它返回的是容器里元素的个数,一般可能都认为这个size()应该及其简单,时间复杂度应该是O(1)。实际情况是不是这样呢,我们简单分析下vector, list, deque(我下载的是SGI源代码)。
先看vector:
以下是代码片段: class vector { public: size_type size() const { return size_type(end() - begin()); } iterator begin() { return _M_start; } iterator end() { return _M_finish; } protected: _Tp* _M_start; _Tp* _M_finish; _Tp* _M_end_of_storage; }; |
可见,vector的size()实现在时间复杂度上确实是常量级的,很简单很快,就如我们想像中一样。注意它没有一个_size。
再看list:
以下是代码片段: class list{ public: size_type size() const { size_type __result = 0; distance(begin(), end(), __result); return __result; } }; |
注意了,尽然不是我们想象的。既不同于vector实现,也没有一个_size, 而是调用的一个全局函数:
头文件stl_iterator_base.h:
以下是代码片段: template <class _InputIterator, class _Distance> inline void distance(_InputIterator __first, _InputIterator __last, _Distance& __n) { __STL_REQUIRES(_InputIterator, _InputIterator); __distance(__first, __last, __n, iterator_category(__first)); } template <class _InputIterator, class _Distance> inline void __distance(_InputIterator __first, _InputIterator __last, _Distance& __n, input_iterator_tag) { while (__first != __last) { ++__first; ++__n; } } |
大家看到了吧,它竟然使用迭代器遍历了整个链表,那么size()在时间复杂度上就不再是我们想象中的常量级,而是O(n)。为什么这样呢,这要对iterator和traits有所了解,才明白这么做的必要性。
所以,如果你的list里数据很多,而你每次操作前还要调用size()来看看是否超过你的最大数目,那执行速度比你想象中要慢很多。所以处理这种情况,如果你必须每次要看看它的元素数目,把list包装一下,自己维护一个_size算了,也浪费不了多少内存,4字节嘛。
最后看看deque:
以下是代码片段: class deque { public: size_type size() const { return _M_finish - _M_start; } protected: iterator _M_start; iterator _M_finish; }; |
不错,看起来和vector一样,其实不然。
别忘了c++语法有一个重要概念:运算符重载。
以下是代码片段: struct _Deque_iterator { typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; typedef ptrdiff_t difference_type; typedef _Deque_iterator _Self; difference_type operator-(const _Self& __x) const { return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) + (_M_cur - _M_first) + (__x._M_last - __x._M_cur); } }; |
为什么这么复杂了?这要怪deque采用map作为主控,使用分段连续线性空间的设计。怎么说都比list那个实现快。
可以说STL的代码风格是让人难受的,当我们无聊而心情又好的时候,读读侯捷的《STL源码剖析》吧,分析对比一下,也有一些乐趣。
建议继续学习:
- 关于使用STL的红黑树map还是hashmap的问题 (阅读:7942)
- 萃取(traits)编程技术的介绍和应用 (阅读:5034)
- 一个简单的stl中string的split函数 (阅读:3265)
- STL笔记之二叉查找树 (阅读:3061)
- 小趣闻:STL的三个版本 (阅读:2876)
- STL笔记之hashtable (阅读:2638)
- 倒置字符串中的单词 (阅读:2474)
- STL可能的误用-find_first_of和erase (阅读:2036)
- 不得不留意的STL string重载函数和隐式类型转换 (阅读:1391)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:PHP中的Hash算法
后一篇:关于 getter 和 setter >>
文章信息
- 作者:梁-兄 来源: C++博客-梁 兄
- 标签: size STL
- 发布时间:2009-11-02 21:09:56
建议继续学习
近3天十大热文
- [41] 界面设计速成
- [36] Oracle MTS模式下 进程地址与会话信
- [33] IOS安全–浅谈关于IOS加固的几种方法
- [33] 如何拿下简短的域名
- [32] 视觉调整-设计师 vs. 逻辑
- [32] 程序员技术练级攻略
- [32] 图书馆的世界纪录
- [31] android 开发入门
- [31] 【社会化设计】自我(self)部分――欢迎区
- [28] 读书笔记-壹百度:百度十年千倍的29条法则