📄 三十分钟掌握stl.htm
字号:
<P
style="MARGIN-LEFT: 36pt; TEXT-INDENT: -18pt; tab-stops: list 36.0pt; mso-list: l2 level1 lfo2"><SPAN
lang=EN-US style="FONT-SIZE: 10pt; FONT-FAMILY: Symbol">·<SPAN
style="FONT: 7pt 'Times New Roman'">
</SPAN></SPAN><I><SPAN lang=EN-US
style="FONT-SIZE: 10pt">Bidirectional iterators</SPAN></I><SPAN
style="FONT-SIZE: 10pt">提供读写操作，并能向前和向后操作。<SPAN
lang=EN-US><O:P></O:P></SPAN></SPAN></P>
<P
style="MARGIN-LEFT: 36pt; TEXT-INDENT: -18pt; tab-stops: list 36.0pt; mso-list: l2 level1 lfo2"><SPAN
lang=EN-US style="FONT-SIZE: 10pt; FONT-FAMILY: Symbol">·<SPAN
style="FONT: 7pt 'Times New Roman'">
</SPAN></SPAN><I><SPAN lang=EN-US style="FONT-SIZE: 10pt">Random
access iterators</SPAN></I><SPAN
style="FONT-SIZE: 10pt">提供读写操作，并能在数据中随机移动。<SPAN
lang=EN-US><O:P></O:P></SPAN></SPAN></P>
<P><SPAN style="FONT-SIZE: 10pt">尽管各种不同的<SPAN
lang=EN-US>STL实现细节方面有所不同，还是可以将上面的迭代器想象为一种类继承关系。从这个意义上说，下面的迭代器继承自上面的迭代器。由于这种继承关系，你可以将一个Forward迭代器作为一个output或input迭代器使用。同样，如果一个算法要求是一个bidirectional
迭代器，那么只能使用该种类型和随机访问迭代器。 <O:P></O:P></SPAN></SPAN></P>
<H3><SPAN
style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 16.0pt">指针迭代器</SPAN><SPAN
lang=EN-US
style="FONT-SIZE: 10.5pt; mso-bidi-font-size: 16.0pt; mso-font-kerning: 0pt"><O:P></O:P></SPAN></H3>
<P><SPAN
style="FONT-SIZE: 10pt">正如下面的小程序显示的，一个指针也是一种迭代器。该程序同样显示了<SPAN
lang=EN-US>STL的一个主要特性——它不只是能够用于它自己的类类型，而且也能用于任何C或C++类型。<A
href="http://www.csdn.net/editor/Editor.htm#Listing 1"><SPAN
style="FONT-SIZE: 12pt">Listing 1</SPAN></A>, iterdemo.cpp,
显示了如何把指针作为迭代器用于STL的find()算法来搜索普通的数组。<O:P></O:P></SPAN></SPAN></P>
<P class=MsoNormal><B><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">表</SPAN></B><B><SPAN
lang=EN-US style="FONT-SIZE: 10pt"> 1. iterdemo.cpp</SPAN></B><SPAN
lang=EN-US style="FONT-SIZE: 10pt"> <O:P></O:P></SPAN></P><PRE><SPAN lang=EN-US>#include <iostream.h></SPAN></PRE><PRE><SPAN lang=EN-US>#include <algorithm></SPAN></PRE><PRE><SPAN lang=EN-US> <O:P></O:P></SPAN></PRE><PRE><SPAN lang=EN-US>using namespace std;</SPAN></PRE><PRE><SPAN lang=EN-US> <O:P></O:P></SPAN></PRE><PRE><SPAN lang=EN-US>#define SIZE 100</SPAN></PRE><PRE><SPAN lang=EN-US>int iarray[SIZE];</SPAN></PRE><PRE><SPAN lang=EN-US> <O:P></O:P></SPAN></PRE><PRE><SPAN lang=EN-US>int main()</SPAN></PRE><PRE><SPAN lang=EN-US>{</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>iarray[20] = 50;</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>int* ip = find(iarray, iarray + SIZE, 50);</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>if (ip == iarray + SIZE)</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>cout << "50 not found in array" << endl;</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>else</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>cout << *ip << " found in array" << endl;</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>return 0;</SPAN></PRE><PRE><SPAN lang=EN-US>}</SPAN></PRE>
<P><SPAN style="FONT-SIZE: 10pt">在引用了<SPAN
lang=EN-US>I/O流库和STL算法头文件（注意没有.h后缀），该程序告诉编译器使用std名字空间。使用std名字空间的这行是可选的，因为可以删除该行对于这么一个小程序来说不会导致名字冲突。<O:P></O:P></SPAN></SPAN></P>
<P><SPAN style="FONT-SIZE: 10pt">程序中定义了尺寸为<SPAN
lang=EN-US>SIZE的全局数组。由于是全局变量，所以运行时数组自动初始化为零。下面的语句将在索引20位置处地元素设置为50,并使用find()算法来搜索值50:
<O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>iarray[20] = 50;</SPAN></PRE><PRE><SPAN lang=EN-US>int* ip = find(iarray, iarray + SIZE, 50);</SPAN></PRE>
<P><TT><SPAN lang=EN-US
style="FONT-SIZE: 10pt; FONT-FAMILY: 黑体">find()函数接受三个参数。头两个定义了搜索的范围。由于C和C++数组等同于指针，表达式iarray指向数组的第一个元素。而第二个参数iarray
+ SIZE等同于</SPAN></TT><I><SPAN lang=EN-US
style="FONT-SIZE: 10pt">past-the-end</SPAN></I><SPAN lang=EN-US
style="FONT-SIZE: 10pt">
值，也就是数组中最后一个元素的后面位置。第三个参数是待定位的值，也就是50。</SPAN><TT><SPAN lang=EN-US
style="FONT-SIZE: 10pt; FONT-FAMILY: 黑体">find()函数返回和前两个参数相同类型的迭代器，这儿是一个指向整数的指针ip。</SPAN></TT><SPAN
lang=EN-US style="FONT-SIZE: 10pt"> <O:P></O:P></SPAN></P>
<P class=tiptitle><B><SPAN
style="FONT-SIZE: 10pt">提示</SPAN></B><SPAN lang=EN-US
style="FONT-SIZE: 10pt"><O:P></O:P></SPAN></P>
<P><SPAN style="FONT-SIZE: 10pt">必须记住<SPAN
lang=EN-US>STL使用模板。因此，STL函数自动根据它们使用的数据类型来构造。<O:P></O:P></SPAN></SPAN></P>
<P><SPAN style="FONT-SIZE: 10pt">为了判断</SPAN><TT><SPAN lang=EN-US
style="FONT-SIZE: 10pt; FONT-FAMILY: 黑体">find()是否成功，例子中测试ip和</SPAN></TT><SPAN
style="FONT-SIZE: 10pt"> <I><SPAN
lang=EN-US>past-the-end</SPAN></I><SPAN lang=EN-US> 值是否相等：
<O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>if (ip == iarray + SIZE) ...</SPAN></PRE>
<P><SPAN
style="FONT-SIZE: 10pt">如果表达式为真，则表示在搜索的范围内没有指定的值。否则就是指向一个合法对象的指针，这时可以用下面的语句显示：<SPAN
lang=EN-US>:<O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>cout << *ip << " found in array" << endl;</SPAN></PRE>
<P><SPAN style="FONT-SIZE: 10pt">测试函数返回值和<SPAN
lang=EN-US>NULL是否相等是不正确的。不要象下面这样使用：<O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>int* ip = find(iarray, iarray + SIZE, 50);</SPAN></PRE><PRE><SPAN lang=EN-US>if (ip != NULL) ...<SPAN style="mso-spacerun: yes"> </SPAN>// ??? incorrect</SPAN></PRE>
<P><SPAN style="FONT-SIZE: 10pt">当使用<SPAN
lang=EN-US>STL函数时，只能测试ip是否和<I>past-the-end</I>
值是否相等。尽管在本例中ip是一个C++指针,其用法也必须符合STL迭代器的规则。<O:P></O:P></SPAN></SPAN></P>
<H3><SPAN
style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 16.0pt">容器迭代器</SPAN><SPAN
lang=EN-US
style="FONT-SIZE: 10.5pt; mso-bidi-font-size: 16.0pt; mso-font-kerning: 0pt"><O:P></O:P></SPAN></H3>
<P><SPAN style="FONT-SIZE: 10pt">尽管<SPAN
lang=EN-US>C++指针也是迭代器，但用的更多的是容器迭代器。容器迭代器用法和iterdemo.cpp一样，但和将迭代器申明为指针变量不同的是，你可以使用容器类方法来获取迭代器对象。两个典型的容器类方法是begin()和end()。它们在大多数容器中表示整个容器范围。其他一些容器还使用rbegin()和rend()方法提供反向迭代器，以按反向顺序指定对象范围。<O:P></O:P></SPAN></SPAN></P>
<P><SPAN style="FONT-SIZE: 10pt">下面的程序创建了一个矢量容器（<SPAN
lang=EN-US>STL的和数组等价的对象），并使用迭代器在其中搜索。该程序和前一章中的程序相同。<O:P></O:P></SPAN></SPAN></P>
<P class=MsoNormal><B><SPAN lang=EN-US
style="FONT-SIZE: 10pt">Listing 2. vectdemo.cpp</SPAN></B><SPAN
lang=EN-US style="FONT-SIZE: 10pt"> <O:P></O:P></SPAN></P><PRE><SPAN lang=EN-US>#include <iostream.h></SPAN></PRE><PRE><SPAN lang=EN-US>#include <algorithm></SPAN></PRE><PRE><SPAN lang=EN-US>#include <vector></SPAN></PRE><PRE><SPAN lang=EN-US> <O:P></O:P></SPAN></PRE><PRE><SPAN lang=EN-US>using namespace std;</SPAN></PRE><PRE><SPAN lang=EN-US> <O:P></O:P></SPAN></PRE><PRE><SPAN lang=EN-US>vector<int> intVector(100);</SPAN></PRE><PRE><SPAN lang=EN-US> <O:P></O:P></SPAN></PRE><PRE><SPAN lang=EN-US>void main()</SPAN></PRE><PRE><SPAN lang=EN-US>{</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>intVector[20] = 50;</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>vector<int>::iterator intIter =</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>find(intVector.begin(), intVector.end(), 50);</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>if (intIter != intVector.end())</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>cout << "Vector contains value " << *intIter << endl;</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>else</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>cout << "Vector does not contain 50" << endl;</SPAN></PRE><PRE><SPAN lang=EN-US>}</SPAN></PRE><PRE><SPAN lang=EN-US> <O:P></O:P></SPAN></PRE>
<P><SPAN style="FONT-SIZE: 10pt">注意用下面的方法显示搜索到的数据：<SPAN
lang=EN-US><O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>cout << "Vector contains value " << *intIter << endl;</SPAN></PRE>
<H3><SPAN
style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 16.0pt">常量迭代器</SPAN><SPAN
lang=EN-US
style="FONT-SIZE: 10.5pt; mso-bidi-font-size: 16.0pt; mso-font-kerning: 0pt"><O:P></O:P></SPAN></H3>
<P><SPAN
style="FONT-SIZE: 10pt">和指针一样，你可以给一个迭代器赋值。例如，首先申明一个迭代器：<SPAN
lang=EN-US><O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>vector<int>::iterator first;</SPAN></PRE>
<P><SPAN style="FONT-SIZE: 10pt">该语句创建了一个<SPAN
lang=EN-US>vector<int>类的迭代器。下面的语句将该迭代器设置到intVector的第一个对象，并将它指向的对象值设置为123：:<O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>first = intVector.begin();</SPAN></PRE><PRE><SPAN lang=EN-US>*first = 123;</SPAN></PRE>
<P><SPAN
style="FONT-SIZE: 10pt">这种赋值对于大多数容器类都是允许的，除了只读变量。为了防止错误赋值，可以申明迭代器为：<SPAN
lang=EN-US><O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>const vector<int>::iterator result;</SPAN></PRE><PRE><SPAN lang=EN-US>result = find(intVector.begin(), intVector.end(), value);</SPAN></PRE><PRE><SPAN lang=EN-US>if (result != intVector.end())</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>*result = 123;<SPAN style="mso-spacerun: yes"> </SPAN>// ???</SPAN></PRE>
<P class=warningtitle><B><SPAN
style="FONT-SIZE: 10pt">警告</SPAN></B><SPAN lang=EN-US
style="FONT-SIZE: 10pt"><O:P></O:P></SPAN></P>
<P><SPAN style="FONT-SIZE: 10pt">另一种防止数据被改变得方法是将容器申明为<SPAN
lang=EN-US>const类型。<O:P></O:P></SPAN></SPAN></P>
<P><SPAN style="FONT-SIZE: 10pt">『呀！在<SPAN
lang=EN-US>VC中测试出错,正确的含义是result成为常量而不是它指向的对象不允许改变，如同int *const
p;看来这作者自己也不懂』 <O:P></O:P></SPAN></SPAN></P>
<H2><SPAN
style="FONT-FAMILY: 黑体; mso-ascii-font-family: Arial">使用迭代器编程</SPAN><SPAN
lang=EN-US style="mso-font-kerning: 0pt"><O:P></O:P></SPAN></H2>
<P><SPAN
style="FONT-SIZE: 10pt">你已经见到了迭代器的一些例子，现在我们将关注每种特定的迭代器如何使用。由于使用迭代器需要关于<SPAN
lang=EN-US>STL容器类和算法的知识，在阅读了后面的两章后你可能需要重新复习一下本章内容。<O:P></O:P></SPAN></SPAN></P>
<H3><SPAN
style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 16.0pt">输入迭代器</SPAN><SPAN
lang=EN-US
style="FONT-SIZE: 10.5pt; mso-bidi-font-size: 16.0pt; mso-font-kerning: 0pt"><O:P></O:P></SPAN></H3>
<P><SPAN style="FONT-SIZE: 10pt">输入迭代器是最普通的类型。输入迭代器至少能够使用<SPAN
lang=EN-US>==和!=测试是否相等；使用*来访问数据；使用++操作来递推迭代器到下一个元素或到达<I>past-the-end</I>
值。<O:P></O:P></SPAN></SPAN></P>
<P><SPAN style="FONT-SIZE: 10pt">为了理解迭代器和<SPAN
lang=EN-US>STL函数是如何使用它们的，现在来看一下find()模板函数的定义：<O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>template <class InputIterator, class T></SPAN></PRE><PRE><SPAN lang=EN-US>InputIterator find(</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>InputIterator first, InputIterator last, const T& value) {</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>while (first != last && *first != value) ++first;</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>return first;</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>}</SPAN></PRE>
<P><SPAN lang=EN-US style="FONT-SIZE: 10pt"><O:P></O:P></SPAN></P>
<P class=normaltitle><B><SPAN
style="FONT-SIZE: 10pt">注意</SPAN></B><SPAN lang=EN-US
style="FONT-SIZE: 10pt"><O:P></O:P></SPAN></P>
<P><SPAN style="FONT-SIZE: 10pt">在<SPAN
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -