`
huozheleisi
  • 浏览: 1226836 次
文章分类
社区版块
存档分类
最新评论

详细解说 STL string

 
阅读更多

详细解说 STL string
Linux 发表于 2005-10-9 14:30:49



前言: string 的角色
1 string 使用
1.1 充分使用 string 操作符
1.2 眼花缭乱的 string find 函数
1.3 string insert, replace, erase 2 string 和 C 风格字符串
3 string 和 Charactor Traits
4 string 建议
5 小结
6 附录前言: string 的角色

C++ 语言是个十分优秀的语言,但优秀并不表示完美。还是有许多人不愿意使用 C 或者 C++,
为什么?原因众多,其中之一就是 C/C++的文本处理功能太麻烦,用起来很不方便。以前没
有接触过其他语言时,每当别人这么说,我总是不屑一顾,认为他们根本就没有领会 C++
的精华,或者不太懂 C++,现在我接触 perl, php, 和 Shell 脚本以后,开始理解了以前为什么
有人说 C++文本处理不方便了。

举例来说,如果文本格式是:用户名 电话号码,文件名 name.txt
Tom 23245332
Jenny 22231231
Heny 22183942
Tom 23245332
...


现在我们需要对用户名排序,且只输出不同的姓名。

那么在 shell 编程中,可以这样用:
awk '{print $1}' name.txt | sort | uniq


简单吧?

如果使用 C/C++ 就麻烦了,他需要做以下工作:
先打开文件,检测文件是否打开,如果失败,则退出。
声明一个足够大得二维字符数组或者一个字符指针数组
读入一行到字符空间
然后分析一行的结构,找到空格,存入字符数组中。
关闭文件
写一个排序函数,或者使用写一个比较函数,使用 qsort 排序
遍历数组,比较是否有相同的,如果有,则要删除,copy...
输出信息


你可以用 C++或者 C 语言去实现这个流程。如果一个人的主要工作就是处理这种类似的文
本(例如做 apache 的日志统计和分析),你说他会喜欢 C/C++么?


当然,有了 STL,这些处理会得到很大的简化。我们可以使用 fstream 来代替麻烦的
fopen fread fclose, 用 vector 来代替数组。最重要的是用 string 来代替 char * 数组,使用 sort
排序算法来排序,用 unique 函数来去重。听起来好像很不错 。看看下面代码(例程 1):
#i nclude <string>
#i nclude <iostream>
#i nclude <algorithm>
#i nclude <vector>
#i nclude <fstream>
using namespace std;
int main(){
ifstream in("name.txt");
string strtmp;
vector<string> vect;
while(getline(in, strtmp, '/n'))
vect.push_back(strtmp.substr(0, strtmp.find(' ')));
sort(vect.begin(), vect.end());
vector<string>::iterator it=unique(vect.begin(), vect.end());
copy(vect.begin(), it, ostream_iterator<string>(cout, "/n"));
return 0;
}


也还不错吧,至少会比想象得要简单得多!(代码里面没有对错误进行处理,只是为了说明
问题,不要效仿).

当然,在这个文本格式中,不用 vector 而使用 map 会更有扩充性,例如,还可通过人名找
电话号码等等,但是使用了 map 就不那么好用 sort 了。你可以用 map 试一试。



这里 string 的作用不只是可以存储字符串,还可以提供字符串的比较,查找等。在 sort 和
unique 函数中就默认使用了 less 和 equal_to 函数, 上面的一段代码,其实使用了 string 的以
下功能:
存储功能,在 getline() 函数中
查找功能,在 find() 函数中
子串功能,在 substr() 函数中
string operator < , 默认在 sort() 函数中调用
string operator == , 默认在 unique() 函数中调用


总之,有了 string 后,C++的字符文本处理功能总算得到了一定补充,加上配合 STL 其他容
器使用,其在文本处理上的功能已经与 perl, shell, php 的距离缩小很多了。 因此掌握 string 会
让你的工作事半功倍。



1 string 使用


其实,string 并不是一个单独的容器,只是 basic_string 模板类的一个 typedef 而已,相对应
的还有 wstring, 你在 string 头文件中你会发现下面的代码:
extern "C++" {
typedef basic_string <char> string;
typedef basic_string <wchar_t> wstring;
} // extern "C++"

由于只是解释 string 的用法,如果没有特殊的说明,本文并不区分 string 和 basic_string 的区
别。

string 其实相当于一个保存字符的序列容器,因此除了有字符串的一些常用操作以外,还有
包含了所有的序列容器的操作。字符串的常用操作包括:增加、删除、修改、查找比较、链
接、输入、输出等。详细函数列表参看附录。不要害怕这么多函数,其实有许多是序列容器
带有的,平时不一定用的上。



如果你要想了解所有函数的详细用法,你需要查看 basic_string,或者下载 STL 编程手册。
这里通过实例介绍一些常用函数。
1.1 充分使用 string 操作符


string 重载了许多操作符,包括 +, +=, <, =, , [], <<, >>等,正式这些操作符,对字符串操作非
常方便。先看看下面这个例子:tt.cpp(例程 2)

#i nclude <string>
#i nclude <iostream>
using namespace std;
int main(){
string strinfo="Please input your name:";
cout << strinfo ;
cin >> strinfo;
if( strinfo == "winter" )
cout << "you are winter!"<<endl;
else if( strinfo != "wende" )
cout << "you are not wende!"<<endl;
else if( strinfo < "winter")
cout << "your name should be ahead of winter"<<endl;
else
cout << "your name should be after of winter"<<endl;
strinfo += " , Welcome to China!";
cout << strinfo<<endl;
cout <<"Your name is :"<<endl;
string strtmp = "How are you? " + strinfo;
for(int i = 0 ; i < strtmp.size(); i ++)
cout<<strtmp[i];
return 0;
}

下面是程序的输出
-bash-2.05b$ make tt
c++ -O -pipe -march=pentiumpro tt.cpp -o tt
-bash-2.05b$ ./tt
Please input your name:Hero
you are not wende!
Hero , Welcome to China!
How are you? Hero , Welcome to China!


有 了 这 些 操 作 符 , 在 STL 中 仿 函 数 都 可 以 直 接 使 用 string 作 为 参 数 , 例
如 less, great, equal_to 等,因此在把 string 作为参数传递的时候,它的使用和 int 或者 float
等已经没有什么区别了。例如,你可以使用:
map<string, int> mymap;
//以上默认使用了 less<string>


有了 operator + 以后,你可以直接连加,例如:

string strinfo="Winter";
string strlast="Hello " + strinfo + "!";
//你还可以这样:
string strtest="Hello " + strinfo + " Welcome" + " to China" + " !";

看见其中的特点了吗?只要你的等式里面有一个 string 对象,你就可以一直连续"+",但有
一点需要保证的是,在开始的两项中,必须有一项是 string 对象。其原理很简单:

系统遇到"+"号,发现有一项是 string 对象。
系统把另一项转化为一个临时 string 对象。
执行 operator + 操作,返回新的临时 string 对象。
如果又发现"+"号,继续第一步操作。

由于这个等式是由左到右开始检测执行,如果开始两项都是 const char* ,程序自己并没有
定义两个 const char* 的加法,编译的时候肯定就有问题了。

有了操作符以后,assign(), append(), compare(), at()等函数,除非有一些特殊的需求时,一般
是用不上。当然 at()函数还有一个功能,那就是检查下标是否合法,如果是使用:
string str="winter";
//下面一行有可能会引起程序中断错误
str[100]='!';
//下面会抛出异常:throws: out_of_range
cout<<str.at(100)<<endl;


了解了吗?如果你希望效率高,还是使用[]来访问,如果你希望稳定性好,最好使用 at()来
访问。
string 只是提供了按照位置和区间的 replace 函数,而不能用一个 string 字串来替换指定 string
中的另一个字串。这里写一个函数来实现这个功能:

void string_replace(string & strBig, const string & strsrc, const string &strdst) {
string::size_type pos=0;
string::size_type srclen=strsrc.size();
string::size_type dstlen=strdst.size();
while( (pos=strBig.find(strsrc, pos)) != string::npos){
strBig.replace(pos, srclen, strdst);
pos += dstlen;
}
}看看如何调用:
#i nclude <string>
#i nclude <iostream>
using namespace std;
int main() {
string strinfo="This is Winter, Winter is a programmer. Do you know Winter?";
cout<<"Orign string is :/n"<<strinfo<<endl;
string_replace(strinfo, "Winter", "wende");
cout<<"After replace Winter with wende, the string is :/n"<<strinfo<<endl;
return 0;
}其输出结果:
Orign string is :
This is Winter, Winter is a programmer. Do you know Winter?
After replace Winter with wende, the string is :
This is wende, wende is a programmer. Do you know wende?如果不用 replace 函数,则可以使用
erase 和 insert 来替换,也能实现 string_replace 函数的功能:
void string_replace(string & strBig, const string & strsrc, const string &strdst) {
string::size_type pos=0;
string::size_type srclen=strsrc.size();
string::size_type dstlen=strdst.size();
while( (pos=strBig.find(strsrc, pos)) != string::npos){
strBig.erase(pos, srclen);
strBig.insert(pos, strdst);
pos += dstlen;
}
}当然,这种方法没有使用 replace 来得直接。
2 string 和 C 风格字符串
现在看了这么多例子,发现 const char* 可以和 string 直接转换,例如我们在上面的例子中,
使用
string_replace(strinfo, "Winter", "wende");来代用
void string_replace(string & strBig, const string & strsrc, const string &strdst) 在 C 语言中只有
char* 和 const char*,为了使用起来方便,string 提供了三个函数满足其要求:
const charT* c_str() const
const charT* data() const
size_type copy(charT* buf, size_type n, size_type pos = 0) const 其中:
c_str 直接返回一个以/0 结尾的字符串。
data 直接以数组方式返回 string 的内容,其大小为 size()的返回值,结尾并没有/0 字符。
copy 把 string 的内容拷贝到 buf 空间中。
你或许会问,c_str()的功能包含 data(),那还需要 data()函数干什么?看看源码:
const charT* c_str () const
{ if (length () == 0) return ""; terminate (); return data (); } 原 来 c_str() 的 流 程 是 : 先 调 用
terminate(),然后在返回 data()。因此如果你对效率要求比较高,而且你的处理又不一定需要
以/0 的方式结束,你最好选择 data()。但是对于一般的 C 函数中,需要以 const char*为输入
参数,你就要使用 c_str()函数。
对于 c_str() data()函数,返回的数组都是由 string 本身拥有,千万不可修改其内容。其原因
是许多 string 实现的时候采用了引用机制,也就是说,有可能几个 string 使用同一个字符存
储空间。而且你不能使用 sizeof(string)来查看其大小。详细的解释和实现查看 Effective STL
的条款 15:小心 string 实现的多样性。

另外在你的程序中,只在需要时才使用 c_str()或者 data()得到字符串,每调用一次,下次再
使用就会失效,如:

string strinfo("this is Winter");
...
//最好的方式是:
foo(strinfo.c_str());
//也可以这么用:
const char* pstr=strinfo.c_str();
foo(pstr);
//不要再使用了 pstr 了, 下面的操作已经使 pstr 无效了。
strinfo += " Hello!";
foo(pstr);//错误!会遇到什么错误?当你幸运的时候 pstr 可能只是指向"this is Winter Hello!"
的字符串,如果不幸运,就会导致程序出现其他问题,总会有一些不可遇见的错误。总之不
会是你预期的那个结果。

3 string 和 Charactor Traits
了解了 string 的用法,该详细看看 string 的真相了。前面提到 string 只是 basic_string 的一个
typedef。看看 basic_string 的参数:
template <class charT, class traits = char_traits<charT>,
class Allocator = allocator<charT> >
class basic_string
{
//...
}char_traits 不仅是在 basic_string 中有用,在 basic_istream 和 basic_ostream 中也需要用到。
就像 Steve Donovan 在过度使用 C++模板中提到的,这些确实有些过头了,要不是系统自己
定义了相关的一些属性,而且用了个 typedef,否则还真不知道如何使用。

但复杂总有复杂道理。有了 char_traits,你可以定义自己的字符串类型。当然,有了
char_traits < char > 和 char_traits < wchar_t > 你的需求使用已经足够了,为了更好的理解
string ,咱们来看看 char_traits 都有哪些要求。

如果你希望使用你自己定义的字符,你必须定义包含下列成员的结构: 表达式 描述
char_type 字符类型
int_type int 类型
pos_type 位置类型
off_type 表示位置之间距离的类型
state_type 表示状态的类型
assign(c1,c2) 把字符 c2 赋值给 c1
eq(c1,c2) 判断 c1,c2 是否相等
lt(c1,c2) 判断 c1 是否小于 c2
length(str) 判断 str 的长度
compare(s1,s2,n) 比较 s1 和 s2 的前 n 个字符
copy(s1,s2, n) 把 s2 的前 n 个字符拷贝到 s1 中
move(s1,s2, n) 把 s2 中的前 n 个字符移动到 s1 中
assign(s,n,c) 把 s 中的前 n 个字符赋值为 c
find(s,n,c) 在 s 的前 n 个字符内查找 c
eof() 返回 end-of-file
to_int_type© 将 c 转换成 int_type
to_char_type(i) 将 i 转换成 char_type
not_eof(i) 判断 i 是否为 EOF
eq_int_type(i1,i2) 判断 i1 和 i2 是否相等
想看看实际的例子,你可以看看 sgi STL 的 char_traits 结构源码.

现在默认的 string 版本中,并不支持忽略大小写的比较函数和查找函数,如果你想练练手,
你可以试试改写一个 char_traits , 然后生成一个 case_string 类, 也可以在 string 上做继承,然
后派生一个新的类,例如:ext_string,提供一些常用的功能,例如:

定义分隔符。给定分隔符,把 string 分为几个字段。
提供替换功能。例如,用 winter, 替换字符串中的 wende
大小写处理。例如,忽略大小写比较,转换等
整形转换。例如把"123"字符串转换为 123 数字。
这 些 都 是 常 用 的 功 能 , 如 果 你 有 兴 趣 可 以 试 试 。 其 实 有 人 已 经 实 现 了 , 看 看
Extended STL string。如果你想偷懒,下载一个头文件就可以用,有了它确实方便了很多。
要是有人能提供一个支持正则表达式的 string,我会非常乐意用。

4 string 建议
使用 string 的方便性就不用再说了,这里要重点强调的是 string 的安全性。
string 并不是万能的,如果你在一个大工程中需要频繁处理字符串,而且有可能是多线程,
那么你一定要慎重(当然,在多线程下你使用任何 STL 容器都要慎重)。
string 的实现和效率并不一定是你想象的那样,如果你对大量的字符串操作,而且特别关心
其效率,那么你有两个选择,首先,你可以看看你使用的 STL 版本中 string 实现的源码;另
一选择是你自己写一个只提供你需要的功能的类。
string 的 c_str()函数是用来得到 C 语言风格的字符串,其返回的指针不能修改其空间。而且
在下一次使用时重新调用获得新的指针。
string 的 data()函数返回的字符串指针不会以'/0'结束,千万不可忽视。
尽量去使用操作符,这样可以让程序更加易懂(特别是那些脚本程序员也可以看懂)
5 小结
难怪有人说:
string 使用方便功能强,我们一直用它!

6 附录
string 函数列表 函数名 描述
begin 得到指向字符串开头的 Iterator
end 得到指向字符串结尾的 Iterator
rbegin 得到指向反向字符串开头的 Iterator
rend 得到指向反向字符串结尾的 Iterator
size 得到字符串的大小
length 和 size 函数功能相同
max_size 字符串可能的最大大小
capacity 在不重新分配内存的情况下,字符串可能的大小
empty 判断是否为空
operator[] 取第几个元素,相当于数组
c_str 取得 C 风格的 const char* 字符串
data 取得字符串内容地址
operator= 赋值操作符
reserve 预留空间
swap 交换函数
insert 插入字符
append 追加字符
push_back 追加字符
operator+= += 操作符
erase 删除字符串
clear 清空字符容器中所有内容
resize 重新分配空间
assign 和赋值操作符一样
replace 替代
copy 字符串到空间
find 查找
rfind 反向查找
find_first_of 查找包含子串中的任何字符,返回第一个位置
find_first_not_of 查找不包含子串中的任何字符,返回第一个位置
find_last_of 查找包含子串中的任何字符,返回最后一个位置
find_last_not_of 查找不包含子串中的任何字符,返回最后一个位置
substr 得到字串
compare 比较字符串
operator+ 字符串链接
operator== 判断是否相等
operator!= 判断是否不等于
operator< 判断是否小于
operator>> 从输入流中读入字符串
operator<< 字符串写入输出流
getline 从输入流中读入一行
有效使用 STL 迭代器的三条基本原则
STL 迭代器的概念看上去似乎已经足够直观了,然而,你会很快发现容器类(Container)实际
上 提 供 了 四 种 不 同 的 迭 代 器 类 型 : iterator 、 const_iterator 、 reverse_iterator 和
const_reverse_iterator。进而,你会注意到容器类的 insert 和 erase 方法仅接受这四种类型中
的一种作为参数。问题来了:为什么需要四种不同的迭代器呢?它们之间存在何种联系?它
们是否可以相互转换?是否可以在 STL 算法(Algorithm)和其他工具函数中混合使用不同类
型的迭代器? 这些迭代器与相应的容器类及其方法之间又是什么关系?
这篇从新近出版的《Effective STL》中摘录的文章将会通过迭代器使用的三条基本原则来回
答上述问题,它们能够帮助你更为有效的使用 STL 迭代器。

原则一:尽量使用 iterator 取代 const_iterator、reverse_iterator 和 const_reverse_iterator

STL 中的所有标准容器类都提供四种不同的迭代器类型。对于容器类 container<T>而言,
iterator 的功用相当于 T*,而 const_iterator 则相当于 const T*(可能你也见到过 T const *这
样的写法,它们具有相同的语义[2])。累加一个 iterator 或者 const_iterator 可以由首至尾的遍
历一个容器内的所有元素。reverse_iterator 与 const_reverse_iterator 同样分别对应于 T*和
const T*,所不同的是,累加 reverse_iterator 或者 const_reverse_iterator 所产生的是由容器的
尾端开始的反向遍历。

让我们先来看一下 vector<T>容器 insert 和 erase 方法的样式:
iterator insert(iterator position, const T& x);
iterator erase(iterator position);
iterator erase(iterator rangeBegin, iterator rangeEnd);

不同容器的 insert 和 erase 方法虽然可能具有截然不同的返回类型,但它们的参数形式却大
都与此类似。需要注意的是:这些方法仅接受 iterator 类型的参数,而不是 const_iterator、
reverse_iterator 或者 const_reverse_iterator。虽然容器类支持四种不同的迭代器类型,但其中
iterator 似乎有更为广泛的应用[3]。

下图清晰的表明了不同类型的迭代器之间的转换关系:

如图所示,你可以隐式的将 iterator 转换成 const_iterator 或者 reverse_iterator,也可以隐式的
将 reverse_iterator 转换成 const_reverse_iterator。并且,reverse_iterator 可以通过调用其 base()
成 员 函 数 转 换 为 iterator 。 const_reverse_iterator 也 可 以 类 似 的 通 过 base() 转 换 成 为
const_iterator。然而,一个图中无法显示的事实是:通过 base()得到的也许并非你所期待的
iterator,我们将会在原则三中详细讨论这一点。
很 显 然 , 我 们 没 有 办 法 从 一 个 const_iterator 转 换 得 到 一 个 iterator , 也 无 法 从
const_reverse_iterator 得到 reverse_iterator。这一点非常重要,因为这意味着当你仅仅得到一
个 const_iterator 或者 const_reverse_iterator,你会在调用容器类的一些成员函数时遇到麻烦。
这些成员函数要求 iterator 作为参数,而你无法从 const 类型的迭代器中直接得到 iterator。
当需要指出插入或者删除的位置时,const 类型的迭代器总是显得那么力不从心。
千万不要傻乎乎的宣称 const 类型的迭代器一无是处,它们仍然可以在特定的场合使用。比
如,const 类型的迭代器可以与 STL 算法默契配合——因为 STL 算法通常只关心迭代器属于
何种概念范畴(Category),而对其类型(Type)没有限制。很多容器类的成员方法也接受 const
类型的迭代器,只有 insert 和 erase 显得有些吹毛求疵。

即便是在需要插入或删除操作的时候,面对 const 类型的迭代器你也并非走投无路。一般情
况下仍然有办法通过 const 类型的迭代器取得一个 iterator,但这种方法并不总是行得通。而
且就算可行,它也显得复杂而缺乏效率。原则二中将会提及这种转换的方法。


现在,我们已经有足够的理由相信应该尽量使用 iterator 取代 const 或者 reverse 类型的迭代
器:
·大多数 insert 和 erase 方法要求使用 iterator。如果你需要调用这些方法,你就必须使用
iterator。
·没有一条简单有效的途径可以将 const_iterator 转换成 iterator,我们将会在原则二中讨论
的技术并不普遍适用,而且效率不彰。
·从 reverse_iterator 转换而来的 iterator 在使用之前可能需要相应的调整,在原则三种我们
会讨论何时需要调整以及调整的原因。
由此可见,尽量使用 iterator 而不是 const 或 reverse 类型的迭代器,可以使得容器的使用更
为简单而有效,并且可以避免潜在的问题。
在实践中,你可能会更多的面临 iterator 与 const_iterator 之间的选择,因为 iterator 与
reverse_iterator 之间的选择结果显而易见——依赖于顺序或者逆序的的遍历。而且,即使你
选择了 reverse_iterator,当需要 iterator 的时候,你仍然可以通过 base()方法得到相应的 iterator
(可能需要一些调整,我们会在条款三中讨论)。
而在 iterator 和 const_iterator 之间举棋不定的时候,你有更充分的理由选择 iterator,即使
const_iterator 同样可行,即使你并不需要调用容器类的任何成员函数。其中的缘由包括
iterator 与 const_iterator 之间的比较,如下代码所示:
typedef deque<int> IntDeque; //typedef 可以极大的简化
typedef IntDeque::iteratorIter; //STL 容器类和 iterator
typedef IntDeque::const_iteratorConstIter;//的操作。

Iter i;
ConstIter ci;
... //使 ci 和 i 指向同一容器。
if (i == ci) ... //比较 iterator 和 const_iterator

我们所做的只是同一个容器中两个 iterator 之间的比较,这是 STL 中最为简单而常用的动作。
唯一的变化是等号的一边是 iterator,而另一边是 const_iterator。这应该不是问题,因为 iterator
应该在比较之前隐式的转换成 const_iterator,真正的比较应该在两个 const_iterator 之间进
行。
对于设计良好的 STL 实现而言,情况确实如此。但对于其它一些实现,这段代码甚至无法
通过编译。原因在于,这些 STL 实现将 const_iterator 的等于操作符(operator==)作为
const_iterator 的一个成员函数而不是友元函数。而问题的解决之道显得非常有趣:只要交换
两个 iterator 的位置,就万事大吉了。
if (ci==i)...//问题的解决方法

不仅是比较是否相等,只要你在同一个表达式中混用 iterator 和 const_iterator(或者
reverse_iterator 和 const_reverse_iterator),这样的问题就会出现。例如,当你试图在两个随
机存取迭代器之间进行减法操作时:
if (i-ci >= 3) ...//i 与 ci 之间有至少三个元素

如果迭代器的类型不同,你的完全正确的代码可能会被无理的拒绝。你可以想见解决的方法
(交换 i 和 ci 的位置),但这次,不仅仅是互换位置了:
if (ci+3 <= i) ...//问题的解决方法

避免类似问题的最简单的方法是减少混用不同类型的迭代器的机会,尽量以 iterator 取代
const_iterator。从 const correctness 的角度来看,仅仅为了避免一些可能存在的 STL 实现的
弊端(而且,这些弊端都有较为直接的解决途径)而抛弃 const_iterator 显得有欠公允。但综
合考虑到 iterator 与容器类成员函数的粘连关系,得出 iterator 较之 const_iterator 更为实用的
结论也就不足为奇了。更何况,从实践的角度来看,并不总是值得卷入 const_iterator 的麻烦
当中去。


原则二:使用 distance 和 advance 将 const_iterator 转换成 iterator

原则一中指出容器类的部分方法仅接受 iterator 作为参数,而不是 const_iterator。那么,如
何 在 一 个 const_iterator 指 出 的 容 器 位 置 上 插 入 新 元 素 呢 ? 换 言 之 , 如 何 通 过 一 个
const_iterator 得到指向容器中相同位置的 iterator 呢?由于并不存在从 const_iterator 到 iterator
之间的隐式转换,你必须自己找到一条转换的途径。
嗨,我知道你在想什么!“每当无路可走的时候,就祭起强制类型转换的大旗!”。在 C++的
世界里,强制类型转换似乎总是最后的杀手锏。老实说,这恐怕算不上什么好主意——真不
知道你是哪儿学来的。
让我们看看当你想把一个 const_iterator 强制转换为 iterator 时会发生什么:
typedef deque<int> IntDeque;//typedef, 简化代码。
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;

ConstIter ci;//const_iterator
Iter i(ci);//编译错误!
//没有隐式转换途径!
Iter i(const_cast<Iter>(ci));//编译错误!
//转换不能成立!

这里只是以的 deque 为例,但是用其它容器类(list, set, multiset, map, multimap 甚至非标准
STL 的基于 hash 表的容器[4])产生的代码大同小异。也许 vector 或 string 类的代码能够顺
利编译,但这是非常特殊的情形。
包含显式类型转换的代码不能通过编译的原因在于,对于这些容器而言,iterator 和
const_iterator 是完全不同的类。它们之间并不比 string 和 complex<float>具有更多的血缘关
系。编译器无法在两个毫无关联的类之间进行 const_cast 转换。reinterpret_cast、static_cast
甚至 C 语言风格的类型转换也不能胜任。
不过,对于 vector 和 string 容器来说,包含 const_cast 的代码也许能够通过编译。因为通常
情况下 STL 的大多数实现都会采用真实的指针作为 vector 和 string 容器的迭代器。就这种实
现而言,vector<T>::iterator 和 vector<T>::const_iterator 分别被定义为 T*和 const T*,
string::iterator 和 string::const_iterator 则被定义为 char*和 const char*。因此,const_iterator 与
iterator 之间的 const_cast 转换被最终解释成 const T*到 T*的转换。当然,这样的类型转换没
有问题。但是,即便在这种 STL 的实现当中,reverse_iterator 和 const_reverse_iterator 仍然
是实在的类,所以仍然不能直接将 const_reverse_iterator 强制转换成 reverse_iterator。而且,
这些 STL 实现为了方便调试通常只会在 Release 模式时才使用指针表示 vector 和 string 的迭
代器[5]。所有这些事实表明,出于可移植性的考虑,这样的强制类型转换即使是对 vector
和 string 来说也不可取。

如果你得到一个 const_iterator 并且可以访问它所指向的容器,那么这里有一条安全、可移植
的途径将它转换成 iterator,而且,用不着搅乱类型系统的强制转换。下面是基本的解决思
路,称之为“思路”是因为还要稍作修改才能让这段代码通过编译。
typedef deque<int> IntDeque;
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;

IntDeque d;
ConstIter ci;
...//ci 指向 d。
Iter i(d.begin());//指向 d 的起始位置。
advance(i, distance(i, ci));//调整 i,指向 ci 位置。

这种方法看上去非常简单,也很直观:要得到与 const_iterator 指向同一位置的 iterator,首
先将 iterator 指向容器的起始位置,并且取得 const_iterator 距离容器起始位置的偏移量,然
后将 iterator 向后移动相同的偏移即可。这些动作是通过<iterator>中声明的两个算法函数实
现的:distance 用以取得两个指向同一个容器的 iterator 之间的距离;advance 则用于将一个
iterator 移动制定的距离。如果 ci 和 i 指向同一个容器,并且 i 指向容器的器时位置,表达式
advance(i, distance(i, ci))会将 i 移动到与 ci 相同的位置上。
如果这段代码能够通过编译,它就能完成这种转换任务。但似乎事情并不那么顺利。先来看
看 distance 的定义:
template<typename InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last);
不必为长达 56 个字符的返回类型操心,也不用理会 difference_type 是什么东西。仔细看看
调用的参数!编译器需要推断出它所遇到的 distance 调用的参数类型。再来看看我们的
distance 调用:
advance(i, distance(i, ci));//调整 i,指向 ci 位置。

i 和 ci 分别是 distance 函数的两个参数,它们的类型分别是 deque<int>::iterator 和
deque<int>::const_iterator,而 distance 函数需要一种确定的参数类型,所以调用失败。也许
相应的错误信息会告诉你编译器无法推断出 InputIterator 的类型。

要顺利的通过编译,你需要排除distance调用的歧义性。最简单的办法就是显式的指明distance
调用的模版参数类型,从而避免编译器为此大伤脑筋。
advance(i, distance<ConstIter>(i, ci));





这样,我们就可以通过advance和distance将一个const_iterator转换成iterator了。但另一个值的
考虑的问题是,这样做的效率如何?答案在于你所转换的究竟是什么样的迭代器。对于随机
存取的迭代器(如vector, string和deque)而言,这种转换只需要一个与容器中元素个数无关
的常数时间;对于双向迭代器(其它容器,包括基于hash表的非标准容器的一些实现[6])而
言,这种转换是与容器元素个数相关的线性时间操作。

这种从const_iterator到iterator的转换可能需要线性的时间代价,并且需要访问const_iterator
所属的容器。从这个角度出发,也许你需要重新审视你的设计:是否真的需要从const_iterator
到iterator的转换呢?

原则三:正确理解如何使用通过base()得到的iterator

调用reverse_iterator的base()方法可以得到“与之相对应的”iterator。这句话也许有些辞不达
意。还是先来看一下这段代码,我们首先把从 1 到 5 的 5 个数放进一个vector中,然后产生
一个指向 3 的reverse_iterator,并且通过其base()函数取得一个iterator。
vector<int> v;

for(int i = 0;i < 5; ++ i) {//插入 1 到 5
v.push_back(i);
}

vector<int>::reverse_iterator ri =//使ri指向 3
find(v.rbegin(), v.rend(), 3);
vector<int>::iterator i(ri.base());//取得i.






下图表示了执行上述代码之后的i和ci迭代器位置:











如图所示,rbegin()与end()、rend()与begin()之间存在一个元素的偏移,并且ri与i之间仍然保
留了这种偏移。但这还远远不够,针对你所要进行的特定操作,你还需要知道一些技术细节。
原则一指出容器类的部分成员函数仅接受iterator类型的参数。上面的例子中,你并不能直接
在ri所指出的位置上插入元素,因为insert方法不接受reverse_iterator作为参数。如果你要删
除ri位置上的元素,erase方法也有同样的问题。为了完成这种插入/删除操作,你必须首先用
base方法将reverse_iterator转换成iterator,然后用iterator调用insert或erase方法。
先让我们假设你要在ri指出的位置上进行插入操作,并且假设你要插入的值是 99。由于ri遍
历vector的顺序是自右向左,而insert操作会将新元素插入到ri位置,并且将原先ri位置的元素
移到遍历过程的“下一个”位置,插入操作之后,3 应该出现在 99 的左侧,如下图所示:


当然,这些只是我们的假设而已。insert实际上并不接受reverse_iterator类型的参数,所以我
们必须用i取代ri。如上所述,在插入操作之前,ri指向元素 3 而通过base()得到的i指向元素 4。
考虑到insert与遍历方向的关系,直接使用i进行insert操作,我们会得到与上述假设完全相同
的结果。
·如果要在一个reverse_iterator指出的位置上插入新元素,只需通过base()得到相应的iterator
然后调用insert方法即可。对于insert操作而言,reverse_iterator与通过其base()方法得到的
iterator是完全等价的。

现在再来考虑删除元素的情况,先来回顾一下最初(没有进行insert操作)的vector的状态以
及i与ri的位置:

如果你要删除ri指向的元素,你恐怕不能直接使用i了。这时i与ri分别指向不同的位置,因此,
你需要删除的是i所指向元素的前一个元素。
·如果要删除一个reverse_iterator指向的元素,需要通过base()得到相应的iterator,并且删除
此iterator所指向的前一位值的元素。对于erase操作而言,reverse_iterator与通过其base()方法
得到的iterator并非完全等价。

我们还是有必要看看erase操作的实际代码:
vector<int> v;
... //插入 1 到 5,同上
vecot<int>::reverse_iterator ri =
find(v.rbegin(), v.rend(), 3); //ri指向 3
v.erase(--ri.base()); //vector编译不通过。

这段代码并不存在什么设计问题,表达式--ri.base()确实能够指出我们需要删除的元素。而且,
它们能够处理除了vector和string之外的其他所有容器。但问题是,对于vector和string,
--ri.base()可能会无法通过编译。这是因为vector和string容器的iterator和const_iterator通常会
采用真实的指针来实现,而ri.base()会返回一个内建指针。
C和C++都加强了对指针类型返回值的限制,你不能直接修改函数返回的指针。如果vector
和string选用真实的指针作为iterator,你也就不能修改base()的返回值,所以--ri.base()无法通
过编译。出于通用性和可移植性的考虑,应该避免直接修改base()的返回值。当然,我们只
需要先增加ri的值,然后再调用base()方法:
...//同上
v.erase((++ri).base());//这下编译没问题了!

当你需要删除一个由reverse_iterator指出的元素时,应该首选这种更为通用而可移植的方法。
由此可见,通过base()方法可以取得一个与reverse_iterator“相对应的”iterator的说法并不准
确。对于insert而言,这种对应关系确实存在;但是对于erase操作,情况并非如此简单。当
你需要将reverse_iterator转换成iterator的时候,你必须根据所要进行的操作对base()的返回值
进行相应的调整。

总结:
STL容器提供了四种不同的迭代器类型,但在实践当中,iterator比其它三种迭代器更为实用。
如果你有一个const_iterator,并且可以访问它所指向的容器,你就可以通过advance和distance
得到与值相应的iterator。如果你有一个reverse_iterator,你可以通过base()方法得到“相对应
的”iterator,但在你进行删除操作之前,必须首先调整iterator的值。

备注与参考:
[1]Scott Meyers, Effective STL: 50 specific ways to improve your use of standard template library
. Addison-Wesley, 2001. ISBN 0-201-749629. 本文摘录了Effective STL中的条款 26 至 28。
[2] Const T vs. T Const. Dan Saks. Embedded Systems Programming,1999 二月。
[3] 很难弄清为什么iterator会比其它三种迭代器更为特殊。HP公司的最初的STL实现中使用
了iterator作为insert和erase的参数,而STL标准化过程中对此也未作改动。这种情况可能在
STL的未来版本中有所改变。C++类库工作小组的 180 号备注中提到:“这个问题应该成为重
新 审 视 C++ 标 准 中 的 const 问 题 时 的 一 个 主 要 部 分 ”
http://anubis.dkuug.dk/jtc1/sc-22/wg21/docs/lwg-defects.html)。
[4] 有两个较为常用的STL实现中包含了基于hash表的容器,Dinkumware STL和SGISTL。你
可以在 1998 年 12 月版CUJ上找到P.J.Plauger的栏目“hash table”,它介绍了Dinkumware STL
的实现。就我所知,只有Effective STL的条款 25 涉及SGISTL中hash类型容器的实现。你可
以在http://www.sgi.com/tech/stl/HashAssociative-Containers.html找到SGI版本的调用界面。
[5]STLPort再Debug模式下就是如此。你可以在http://www.stlport.org找到相关资料。
[6]Dinkumware STL实现的hash 容器提供双向迭代器,除此以外,SGISTL、STLPort和
Metrowerk的hash容器实现都仅提供单向迭代器。

作者简介:
Scott Meyers,C++程序设计领域著名作家,Effective STL是他的第三本C++专著。Brown大
学计算机科学博士,NumeriX LLC和Info Cruiser顾问委员会成员。提供计算机科学领域的教
学和咨询服务,网址:http://www.aristeia.com

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics