我的CPP之路

路漫漫其修远兮
随笔 - 42, 文章 - 0, 评论 - 16, 引用 - 0
数据加载中……

STL学习笔记

要着手编个TCP/IP的程序(作业,死任务。。。),以前没弄过STL,感觉会用STL的话会给编程带来很多便捷,能用很多标准类库,决定就学习下。

以前一直不知道迭代器是干嘛的,快速看了以下两篇文章:

STL迭代器
http://blog.csdn.net/hengshan/archive/2010/08/21/5828214.aspx

STL迭代器简介
http://www.cppblog.com/The-Moment/archive/2009/06/18/88023.html

再随便Google下“迭代器”关键字,恍然大悟,原来“迭代器对于STL容器”就像“指针对于数组”的关系,这下就好办了,因为小弟原来的指针功夫不差,转来转去感觉这个世界上最美妙的东西就是void*。

同时,也找到了比较全的STL的reference网站:

大名鼎鼎的cplusplus.com
http://www.cplusplus.com/reference/stl/

SGI公司的技术页面(也不差)
http://www.sgi.com/tech/

这下清楚了,比如iterator是vector的一个成员,begin()和end()返回的就是一个iterator,区别注意,front()和back()返回的是数据的值。

开始游戏,我们来玩STL:

 1 #include <vector>
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 void showAddress(vector<int> a) {
 7     int* pb = &*a.begin();    //如果写成int* pb = a.begin();则编译器报错
 8     int* pe = &*a.end();
 9     cout << "a.size() == " << a.size() << '\n';
10     cout << pb << " -> " << pe << '\n';
11 }
12 
13 int main(){
14     vector<int> a;
15 //    a.resize(a.max_size()/4, 0);    //这行我们先不管,以后再玩
16     cout << "a.max_size() == "<< a.max_size() << '\n';
17     showAddress(a);
18     a.push_back(0);
19     showAddress(a);
20     a.push_back(0);
21     showAddress(a);
22 
23     return 0;
24 }
25 
注意,第7和第8行,如果写成int* pb = a.begin();则编译器报错,原因是begin()返回的是一个迭代器,迭代器是容器的一个成员类型,无法被转换为int*,虽然迭代器和指针的作用一样,但是这么转不行。

如果要取a中第一个元素的地址,得像上面代码第7行所写的那样,先取迭代器指向的值,再取其地址。

运行结果:
a.max_size() == 1073741823       //这个是a能容纳的最多的元素个数,看着玩
a.size() 
== 0
0 -> 0
a.size() 
== 1
0x8aa6018 -> 0x8aa601c
a.size() 
== 2
0x8aa6008 -> 0x8aa6010

可以看到,刚开始a的大小是0。begin()和end()返回的是空迭代器,地址空,所以指针为0。然后我们在第18行代码用push_back()插入一个元素,a的大小变成1,此时begin()和end()返回的是指向头和尾两个元素的迭代器,可以看到,a的大小为1,但是有两个元素,从0x8aa6018 -> 0x8aa601c正好差4,一个int。然后第20行代码再插一个元素,a的大小变成2,地址差8,两个int。

有趣的部分来了,如果用front()和back()来取第一和最后一个元素的值,然后再窥探其地址,结果会一样么?修改代码如下,和上一个代码唯一不一样的是第7和第8行:

 1 #include <vector>
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 void showAddress(vector<int> a) {
 7     int* pb = &a.front();
 8     int* pe = &a.back();
 9     cout << "a.size() == " << a.size() << '\n';
10     cout << pb << " -> " << pe << '\n';
11 }
12 
13 int main(){
14     vector<int> a;
15 //    a.resize(a.max_size()/4, 0);    //1073741823这行我们先不管,以后再玩
16 //    cout << "a.max_size() == "<< a.max_size() << '\n';
17     showAddress(a);
18     a.push_back(0);
19     showAddress(a);
20     a.push_back(0);
21     showAddress(a);
22 
23     return 0;
24 }
25 

运行结果如下:

a.size() == 0
0 -> 0xfffffffc
a.size() 
== 1
0x9fd7018 -> 0x9fd7018
a.size() 
== 2
0x9fd7008 -> 0x9fd700c

一开始a的大小是0,所以取front()得到的是null。有趣的在下面,back()取出来的值的地址是0xfffffffc,而且无论程序运行多少次都不会变,说明不是随机地址,并且0xfffffffc加4就是0x00000000,加1个int就回到了0。接下来的表现也不同,当a的大小为1时,front()和back()取出的是同一个元素,当然啦,第一个和最后一个元素一样。当a的大小为2时,两个地址差4,即1个int的大小,不是差2个。

结论:begin()和end()给出的是指向第1个和第1+size个元素的迭代器(即最后一个元素之后的一个元素的迭代器)。front()和end()给出的是第1和第size个元素的值。

提问,是不是这么说来end()所指向的值永远都是'\0'?

为了验证,给出以下代码:

 1 #include <vector>
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 void showEnd(vector<int> a) {
 7     cout << "*a.end() == " << *a.end() << '\n';
 8 }
 9 
10 int main() {
11     vector<int> a;
12     showEnd(a);
13     a.push_back(7);
14     showEnd(a);
15     a.push_back(7);
16     showEnd(a);
17 
18     return 0;
19 }
20 

编译通过,运行结果:
Erreur de segmentation

这是法语(ubuntu-10.10法语的locale),英语的意思是
Segmentation fault,我无法理解这个运行时错误。
WinXP下也是编译通过,运行结果:
弹出对话框“testvector.exe 遇到问题需要关闭。我们对此引起的不便表示抱歉。”点击“不发送”,在命令行中有如下结果:
“Process returned -1073741819 (0xC0000005)   execution time : 12.891 s
Press any key to continue.”
目前不能理解,望高手解答。小弟不胜感激。

然后我们把第12行的showEnd注释掉,编译,通过,运行结果:

*a.end() == 0
*a.end() == 0

这个结果是分别在a中添加两个int元素之后取end()指向的值,可以得到的结论,即size为1和2,非0时,取end()所指的元素得到的结果是0。当size为0时,取end()所指元素得到的结果是运行时错误“Segmentation fault”。所以要当心size为0,对end()的使用。

接下来我们来玩第一个源代码中的第15行,a.resize(a.max_size()/4, 0);a的尺寸会变得很大,并且3次showAddress都会操作这个庞然大物,观测内存,在虚拟机ubuntu下内存在10秒内轻松突破1G多。。。只感觉virtualbox突然一卡,硬盘狂闪,因为虚拟机中ubuntu的swap实际上就是读写硬盘。。。直到耗尽swap内存,然后throw出如下:

a.max_size() == 1073741823
terminate called after throwing an instance of 
'std::bad_alloc'
  what():  std::bad_alloc
Abandon

显然是没有再多内存可分配了。

查看如下两篇blog,稍微了解到,编写STL需要注意程序效率问题,否则STL也不是万能的。。。

http://hi.baidu.com/janvyking999/blog/item/2b3dbd547f50dbcdb745ae05.html
http://hi.baidu.com/hins_pan/blog/item/515b0637f92499d2a3cc2b8a.html
都是介绍Effective STL这本书的。

有关如何取迭代器所指向的值的地址,查看了如下帖子:

如何将 迭代器的指针转换成 DWORD
http://bbs.pfan.cn/showpost.asp?id=17059

最后总结:

begin()和end()返回的是迭代器,指向第1和第1+size个元素。front()和back()返回的是元素的值,指向第1和第size个元素。注意在size为0和1时两种方法的区别。

所遗留的问题,目前还不知道对于一个容器的名字,编译器会返回什么。(比如数组的名字返回的是第一个元素的地址)此问题所引申的问题就是容器如果作为其他函数的参数时,传地址和传值的区别。

本文测试环境默认为ubuntu-10.10搭配g++ 4.4.5,各别指明处为winxp sp3搭配g++ 4.5.0。

真正要搞STL还得啃标准库源码。

posted on 2010-12-26 11:36 yanvenhom 阅读(3443) 评论(7)  编辑 收藏 引用 所属分类: C/C++

评论

# re: STL学习笔记  回复  更多评论   


接下来有趣了!一开始a的大小是0,可以推测出只有一个'\0'元素,所以取front()的地址出来的是0. ----> 一开始取出的是null, 是因为开始没有分配内存, 没有元素. vector 记录了分配的内存的起始地址,容量,以及使用了多少两个元素,不存在需要一个'\0'元素.

另外:
begin()返回指向第一个元素的迭代器(vector<>中是地址,对其他容器则不有不同的表示方法)
end()返回最后一个元素之后一个元素的迭代器, end()处的元素都是不可访问的,不同的容器迭代器的end()表示方法也不一样

迭代器范围是一个左闭右开区间, 有效范围是 [begin(), end()), 所以end()的值只应该使用 == 或 != 来确定, 不要使用 > 或 < 来确定.

2010-12-26 15:07 | jmchxy

# re: STL学习笔记[未登录]  回复  更多评论   

@jmchxy
多谢大哥,突然明白开闭区间的作用了。

ok,修改原文:

接下来有趣了!一开始a的大小是0,所以取front()得到的是null。

不过“size为0时back()所得元素的地址为0xfffffffc”这一点,还不理解,因为这个现象表示,back()得到的地址比front()得到的地址小4,即1个int。back()跑到front()前面去了。
2010-12-26 21:49 | yanvenhom

# re: STL学习笔记  回复  更多评论   

@jmchxy
我修改了第三段源码,把第12行注释掉了,即size为0时,不取end(),在size为1和2,非0时再取end(),结果*a.end()都是0。就是说当且仅当size为0时取end()才会有Segmentation fault错误。
2010-12-26 22:23 | yanvenhom

# re: STL学习笔记  回复  更多评论   

没必要看源代码,手册已经很清楚咧。。。
2010-12-27 19:14 | 空明流转

# re: STL学习笔记  回复  更多评论   

@空明流转
多谢大侠踩过,偶前面去大侠主页看过了,很有意思的成长经历。
2010-12-27 23:55 | yanvenhom

# re: STL学习笔记  回复  更多评论   

厚街翻译的一本stl手册??挺好的,中文版手册
2010-12-30 01:43 | zjh

# re: STL学习笔记  回复  更多评论   

@zjh
Nicolai M. Josuttis 写的 The C++ Standard Library
http://ishare.iask.sina.com.cn/f/5204914.html
2010-12-30 04:03 | yanvenhom

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理