大家好，欢迎来到IT知识分享网。

除了各种容器类，STL标准模板库还提供了众多算法类的非成员函数，以满足排序、查找、替代、转换、批处理等常规需求。

知识产权协议

下述C++程序使用了std::sort( )算法对容器进行排序。

1 //Project - Algorithm1 2 #include <iostream> 3 #include <vector> 4 #include <deque> 5 #include <algorithm> 6 using namespace std; 7 8 void display(const string& s){ cout << s << " "; } 9 10 int main(){ 11 cout << "Sort alphabetically: "; 12 vector<string> vs {"tom","angela","dorothy","jack"}; 13 sort(vs.begin(),vs.end()); 14 for_each(vs.begin(),vs.end(),display); 15 16 cout << "\nSort by length: "; 17 deque<string> ds {"tom","angela","dorothy","jack"}; 18 sort(ds.begin(),ds.end(), 19 [](string& s1,string& s2){return s1.size()<s2.size();}); 20 for_each(ds.begin(),ds.end(),display); 21 22 return 0; 23 }

上述程序的执行结果为：

1 Sort alphabetically: angela dorothy jack tom 2 Sort by length: tom jack angela dorothy

第5行：导入头文件algorithm（算法）。STL中与算法相关的函数大多在该头文件中定义。

第8行：一个简单的显示函数，它将参数字符串s输出在控制台上，并附加一个空格。

第13行：使用sort( )函数对字符串向量vs进行排序，从执行结果的第1行可见，字符串元素是按照字母序递增排序的。如本书19.5.2节所述，把同一个容器的两个迭代器配合使用，可以表示容器元素的一个连续子集。在这里，sort( )函数的两个参数都是来自于向量vs的迭代器，其表明了待排序的元素范围。sort( )函数通过这些迭代器来比较和交换元素。

第14行：通过for_each( )算法函数遍历并打印vs的全部元素。两个迭代器参数表明了元素的遍历范围[vs.begin(),vs.end( ) )，第3个参数display则为函数指针。可以预见，在for_each( )函数内部，程序对元素的遍历是通过循环完成的，对于每一个元素，for_each( )会调用display( )函数将其打印输出到控制台。

第18 ~ 19行：使用sort()函数对双端队列ds进行排序。与第13行不同，这里我们为sort( )函数额外添加了一个函数指针，该函数将在排序过程中用于元素大小的比较。事实上，模板函数sort( )存在多个函数名重载的版本，第18行与第13行使用的是不同版本的sort( )函数。

第20行：使用for_each( )算法函数遍历并打印双端队列ds的全部元素。请读者注意，第20行代码中的被遍历容器是双端队列，而第14行则是向量。借助于模板参数及迭代器的帮助，算法函数可以应用于不同的容器类型。

下述C++程序向我们演示了算法函数transform( )、count( )、max_element( )、min_element( )以及binary_search( )的用法。

1 //Project - Algorithm2 2 #include <iostream> 3 #include <vector> 4 #include <list> 5 #include <algorithm> 6 using namespace std; 7 8 int main(){ 9 list<string> ls {"91","42","2","52","11","2","37","2"}; 10 vector<int> vi; 11 transform(ls.begin(),ls.end(), 12 insert_iterator<vector<int>>(vi,vi.begin()), 13 [](const string& s){return stoi(s);}); 14 15 cout << "elements of vi after transform: "; 16 for_each(vi.begin(),vi.end(),[](int v){cout << v << " ";}); 17 18 cout << "\ncount(vi,2) = " << count(vi.cbegin(),vi.cend(),2); 19 cout << "\nmax_element(vi) = " << *max_element(vi.cbegin(),vi.cend()); 20 cout << "\nmin_element(vi) = " << *min_element(vi.cbegin(),vi.cend()); 21 22 sort(vi.begin(),vi.end()); 23 cout << "\ncontent of vi after sort: "; 24 for_each(vi.begin(),vi.end(),[](int v){cout << v << " ";}); 25 26 cout << "\n37 in vi: " << 27 (binary_search(vi.cbegin(),vi.cend(),37)?"yes":"no"); 28 cout << "\n96 in vi: " << 29 (binary_search(vi.cbegin(),vi.cend(),96)?"yes":"no"); 30 31 return 0; 32 }

上述程序的执行结果为：

1 elements of vi after transform: 91 42 2 52 11 2 37 2 2 count(vi,2) = 3 3 max_element(vi) = 91 4 min_element(vi) = 2 5 content of vi after sort: 2 2 2 11 37 42 52 91 6 37 in vi: yes 7 96 in vi: no

第9行：定义字符串类型的双向链表ls。请读者注意，该链表内的元素为字符串类型。

第10 ~ 13行：使用transform( )函数将字符串列表ls中的元素逐一转换成整数，并加入到向量vi中。参数1和参数2系源于ls的迭代器，表明了待转换的数据范围；参数3则为是一个源自vi的插入迭代器，通过该迭代器，transform( )函数将转换生成的整数插入向量vi；参数4则是一个匿名函数，它将参数字符串s转换成整数并返回。

本例中，transform( )函数通过一个循环来遍历待处理的数据，对于每一个元素，它调用参数4所指向的函数将其转换成整数，然后再通过参数3提供的插入迭代器将其加入容器vi。

第16行：使用for_each( )遍历并打印vi的全部元素，其中元素的打印工作是通过由参数3所描述的匿名函数来完成的。执行结果的第1行可见，ls内的全部字符串元素成功转换并加入到vi中，元素间的相对顺序保持不变。

第18行：使用count( )函数统计向量vi中值为2的元素的出现次数。执行结果第2行显示，向量vi中包含3个2。容易看出，count( )的参数1、2预期为迭代器，它们表示统计的数据范围。

第19 ~ 20行：使用max_element( )、min_element( )查找向量vi中的最大元素和最小元素。由于这两个函数返回的指向最大/最小元素的迭代器，因此，需要加*号进行解引用才能得到相应的元素值。执行结果的第3行、第4行展示了期待的正确输出。

第22行：使用算法函数sort( )对向量vi进行排序。

第24行：遍历并输出向量vi排序后的全部元素。执行结果的第5行可见，排序后的vi递增有序。

第26 ~ 29行：使用折半查找函数binary_search( )在向量vi中查找值为37和96的元素。如果指定元素存在，函数返回真，否则返回假。执行结果的第6、7行显示向量包含37，但不包含96。

如第5章所述，折半查找可以在一个有序的序列中快速查找元素，每经过一次比较，该算法可以将搜索范围缩小一半。

STL标准模板库还提供find( )函数，该函数可以在容器内进行顺序查找。事实上，本节只介绍了STL算法函数的极小一部分。读者在实际的程序设计过程中，应尽量避免重新发明轮子，尽可能多地使用现成的算法函数，以提高工作效率。

本案例节选自作者编写的教材及配套实验指导书。

《C++编程基础及应用》（高等教育出版社，出版过程中）

《Python编程基础及应用》，高等教育出版社

《Python编程基础及应用实验教程》，高等教育出版社

高校教师同行如果期望索取样书，教学支持资料，加群，请私信作者，联系时请提供学校及个人姓名为盼，各高校在读学生勿扰为谢。

青少年读者们如果期望系统性地学习Python及C/C++程序设计语言，欢迎尝试下述今日头条（西瓜）免费视频课程。

C/C++从入门到放弃（重庆大学现场版）

Python编程基础及应用（重庆大学现场版）