📄 三十分钟掌握stl.htm
字号:
lang=EN-US>find()算法中，注意如果first和last指向不同的容器，该算法可能陷入死循环。<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><O:P></O:P></SPAN></SPAN></P>
<P class=MsoNormal><B><SPAN lang=EN-US
style="FONT-SIZE: 10pt">Listing 3. outiter.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 style="mso-spacerun: yes"> </SPAN>// Need copy()</SPAN></PRE><PRE><SPAN lang=EN-US>#include <vector><SPAN style="mso-spacerun: yes"> </SPAN>// Need 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>double darray[10] =</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>{1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9};</SPAN></PRE><PRE><SPAN lang=EN-US> <O:P></O:P></SPAN></PRE><PRE><SPAN lang=EN-US>vector<double> vdouble(10);</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>vector<double>::iterator outputIterator = vdouble.begin();</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>copy(darray, darray + 10, outputIterator);</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>while (outputIterator != vdouble.end()) {</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>cout << *outputIterator << endl;</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>outputIterator++;</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>}</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 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><SPAN
lang=EN-US style="FONT-SIZE: 10pt"> <O:P></O:P></SPAN></P>
<P><SPAN style="FONT-SIZE: 10pt">当使用<SPAN
lang=EN-US>copy()算法的时候，你必须确保目标容器有足够大的空间，或者容器本身是自动扩展的。<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><TT><SPAN
lang=EN-US
style="FONT-SIZE: 10pt; FONT-FAMILY: 黑体">replace()算法显示了前推迭代器的使用方法。</SPAN></TT><SPAN
lang=EN-US style="FONT-SIZE: 10pt"> <O:P></O:P></SPAN></P><PRE><SPAN lang=EN-US>template <class ForwardIterator, class T></SPAN></PRE><PRE><SPAN lang=EN-US>void replace (ForwardIterator first,</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>ForwardIterator last,</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>const T& old_value,</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>const T& new_value);</SPAN></PRE>
<P><SPAN style="FONT-SIZE: 10pt">使用</SPAN><TT><SPAN lang=EN-US
style="FONT-SIZE: 10pt; FONT-FAMILY: 黑体">replace()将[first,last]范围内的所有值为old_value的对象替换为new_value。</SPAN></TT><I><SPAN
lang=EN-US style="FONT-SIZE: 10pt">:</SPAN></I><SPAN lang=EN-US
style="FONT-SIZE: 10pt"><O:P></O:P></SPAN></P><PRE><SPAN lang=EN-US>replace(vdouble.begin(), vdouble.end(), 1.5, 3.14159);</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>reverse()算法要求两个双向迭代器作为参数:<O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>template <class BidirectionalIterator></SPAN></PRE><PRE><SPAN lang=EN-US>void reverse (BidirectionalIterator first,</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>BidirectionalIterator last);</SPAN></PRE>
<P><SPAN style="FONT-SIZE: 10pt">使用</SPAN><TT><SPAN lang=EN-US
style="FONT-SIZE: 10pt; FONT-FAMILY: 黑体">reverse()函数来对容器进行逆向排序</SPAN></TT><SPAN
lang=EN-US style="FONT-SIZE: 10pt">:<O:P></O:P></SPAN></P><PRE><SPAN lang=EN-US>reverse(vdouble.begin(), vdouble.end());</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>const的C++指针也是随机访问迭代器）。STL的排序和搜索函数使用随机访问迭代器。随机访问迭代器可以使用关系操作符作比较。<O:P></O:P></SPAN></SPAN></P>
<P><TT><SPAN lang=EN-US
style="FONT-SIZE: 10pt; FONT-FAMILY: 黑体">random_shuffle()</SPAN></TT><SPAN
lang=EN-US style="FONT-SIZE: 10pt">
函数随机打乱原先的顺序。申明为：<O:P></O:P></SPAN></P><PRE><SPAN lang=EN-US>template <class RandomAccessIterator></SPAN></PRE><PRE><SPAN lang=EN-US>void random_shuffle (RandomAccessIterator first,</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>RandomAccessIterator last);</SPAN></PRE>
<P><SPAN style="FONT-SIZE: 10pt">使用方法：<SPAN
lang=EN-US><O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>random_shuffle(vdouble.begin(), vdouble.end());</SPAN></PRE>
<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><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/O流语句来读写数据。例如：<O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>int value;</SPAN></PRE><PRE><SPAN lang=EN-US>cout << "Enter value: ";</SPAN></PRE><PRE><SPAN lang=EN-US>cin >> value;</SPAN></PRE><PRE><SPAN lang=EN-US>cout << "You entered " << value << endl;</SPAN></PRE>
<P><SPAN style="FONT-SIZE: 10pt">对于迭代器，有另一种方法使用流和标准函数。理解的要点是将输入<SPAN
lang=EN-US>/输出流作为容器看待。因此，任何接受迭代器参数的算法都可以和流一起工作。
<O:P></O:P></SPAN></SPAN></P>
<P class=MsoNormal><B><SPAN lang=EN-US
style="FONT-SIZE: 10pt">Listing 4. outstrm.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 <stdlib.h><SPAN style="mso-spacerun: yes"> </SPAN>// Need random(), srandom()</SPAN></PRE><PRE><SPAN lang=EN-US>#include <time.h><SPAN style="mso-spacerun: yes"> </SPAN>// Need time()</SPAN></PRE><PRE><SPAN lang=EN-US>#include <algorithm><SPAN style="mso-spacerun: yes"> </SPAN>// Need sort(), copy()</SPAN></PRE><PRE><SPAN lang=EN-US>#include <vector><SPAN style="mso-spacerun: yes"> </SPAN>// Need 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>void Display(vector<int>& v, const char* s);</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>// Seed the random number generator</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>srandom( time(NULL) );</SPAN></PRE><PRE><SPAN lang=EN-US> <O:P></O:P></SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>// Construct vector and fill with random integer values</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>vector<int> collection(10);</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>for (int i = 0; i < 10; i++)</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>collection[i] = random() % 10000;;</SPAN></PRE><PRE><SPAN lang=EN-US> <O:P></O:P></SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>// Display, sort, and redisplay</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>Display(collection, "Before sorting");</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>sort(collection.begin(), collection.end());</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>Display(collection, "After sorting");</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>return 0;</SPAN></PRE><PRE><SPAN lang=EN-US>}</SPAN></PRE><PRE><SPAN lang=EN-US> <O:P></O:P></SPAN></PRE><PRE><SPAN lang=EN-US>// Display label s and contents of integer vector v</SPAN></PRE><PRE><SPAN lang=EN-US>void Display(vector<int>& v, const char* s)</SPAN></PRE><PRE><SPAN lang=EN-US>{</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>cout << endl << s << endl;</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>copy(v.begin(), v.end(),</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>ostream_iterator<int>(cout, "\t"));</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>cout << endl;</SPAN></PRE><PRE><SPAN lang=EN-US>}</SPAN></PRE>
<P><SPAN style="FONT-SIZE: 10pt">函数<SPAN
lang=EN-US>Display()显示了如何使用一个输出流迭代器。下面的语句将容器中的值传输到cout输出流对象中:<O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>copy(v.begin(), v.end(),</SPAN></PRE><PRE><SPAN lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>ostream_iterator<int>(cout, "\t"));</SPAN></PRE>
<P><SPAN style="FONT-SIZE: 10pt">第三个参数实例化了<SPAN
lang=EN-US>ostream_iterator<int>类型，并将它作为copy()函数的输出目标迭代器对象。“\t”字符串是作为分隔符。运行结果：<O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>$ g++ outstrm.cpp</SPAN></PRE><PRE><SPAN lang=EN-US>$ ./a.out</SPAN></PRE><PRE><SPAN lang=EN-US>Before sorting</SPAN></PRE><PRE><SPAN lang=EN-US>677<SPAN style="mso-spacerun: yes"> </SPAN>722<SPAN style="mso-spacerun: yes"> </SPAN>686<SPAN style="mso-spacerun: yes"> </SPAN>238<SPAN style="mso-spacerun: yes"> </SPAN>964<SPAN style="mso-spacerun: yes"> </SPAN>397<SPAN style="mso-spacerun: yes"> </SPAN>251<SPAN style="mso-spacerun: yes"> </SPAN>118<SPAN style="mso-spacerun: yes"> </SPAN>11<SPAN style="mso-spacerun: yes"> </SPAN>312</SPAN></PRE><PRE><SPAN lang=EN-US>After sorting</SPAN></PRE><PRE><SPAN lang=EN-US>11<SPAN style="mso-spacerun: yes"> </SPAN>118<SPAN style="mso-spacerun: yes"> </SPAN>238<SPAN style="mso-spacerun: yes"> </SPAN>251<SPAN style="mso-spacerun: yes"> </SPAN>312<SPAN style="mso-spacerun: yes"> </SPAN>397<SPAN style="mso-spacerun: yes"> </SPAN>677<SPAN style="mso-spacerun: yes"> </SPAN>686<SPAN style="mso-spacerun: yes"> </SPAN>722<SPAN style="mso-spacerun: yes"> </SPAN>964</SPAN></PRE>
<P><SPAN style="FONT-SIZE: 10pt">这是<SPAN
lang=EN-US>STL神奇的一面『确实神奇』。为定义输出流迭代器，STL提供了模板类</SPAN></SPAN><TT><SPAN
lang=EN-US
style="FONT-SIZE: 10pt; FONT-FAMILY: 黑体">ostream_iterator</SPAN></TT><SPAN
style="FONT-SIZE: 10pt">。这个类的构造函数有两个参数：一个<SPAN
lang=EN-US>ostream对象和一个string值。因此可以象下面一样简单地创建一个迭代器对象：<O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>ostream_iterator<int>(cout, "\n")</SPAN></PRE>
<P><SPAN style="FONT-SIZE: 10pt">该迭代起可以和任何接受一个输出迭代器的函数一起使用。<SPAN
lang=EN-US><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>copy()这样的算法中。例如，一个程序定义了一个链表和一个矢量容器:<O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>list<double> dList;</SPAN></PRE><PRE><SPAN lang=EN-US>vector<double> dVector;</SPAN></PRE>
<P><SPAN style="FONT-SIZE: 10pt">通过使用<SPAN
lang=EN-US>front_inserter迭代器对象，可以只用单个copy()语句就完成将矢量中的对象插入到链表前端的操作：<O:P></O:P></SPAN></SPAN></P><PRE><SPAN lang=EN-US>copy(dVector.begin(), dVector.end(), front_inserter(dList));</SPAN></PRE>
<P><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: l4 level1 lfo3"><SPAN
lang=EN-US style="FONT-SIZE: 10pt; FONT-FAMILY: Symbol">·<SPAN
style="FONT: 7pt 'Times New Roman'">
</SPAN></SPAN><I><SPAN style="FONT-SIZE: 10pt">普通插入器</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: l4 level1 lfo3"><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">Front
inserters</SPAN></I><SPAN lang=EN-US style="FONT-SIZE: 10pt">
将对象插入到数据集的前面——例如，链表表头。<O:P></O:P></SPAN></P>
<P
style="MARGIN-LEFT: 36pt; TEXT-INDENT: -18pt; tab-stops: list 36.0pt; mso-list: l4 level1 lfo3"><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">Back
inserters</SPAN></I><SPAN lang=EN-US style="FONT-SIZE: 10pt">
将对象插入到集合的尾部——例如，矢量的尾部，导致矢量容器扩展。<O:P></O:P></SPAN></P>
<P><SPAN
style="FONT-SIZE: 10pt">使用插入迭代器可能导致容器中的其他对象移动位置，因而使得现存的迭代器非法。例如，将一个对象插入到矢量容器将导致其他值移动位置以腾出空间。一般来说⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -