【C++】从几个简单示例，理解STL里的算法＜algorithm＞

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

本文引用自作者编写的下述图书; 本文允许以个人学习、教学等目的引用、讲授或转载，但需要注明原作者"海洋饼干叔
叔"；本文不允许以纸质及电子出版为目的进行抄摘或改编。
1.《Python编程基础及应用》，陈波，刘慧君，高等教育出版社。免费授课视频 Python编程基础及应用
2.《Python编程基础及应用实验教程》, 陈波，熊心志，张全和，刘慧君，赵恒军，高等教育出版社Python编程基础及应用实验教程
3. 《简明C及C++语言教程》，陈波，待出版书稿。免费授课视频

下述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算法函数的极小一部分。读者在实际的程序设计过程中，应尽量避免重新发明轮子，尽可能多地使用现成的算法函数，以提高工作效率。

为了帮助更多的年轻朋友们学好编程，作者在B站上开了两门免费的网课，一门零基础讲Python，一门零基础C和C++一起学，拿走不谢！

简洁的C及C++

Python编程基础及应用

如果你觉得纸质书看起来更顺手，目前Python有两本，C和C++在出版过程中。

Python编程基础及应用

Python编程基础及应用实验教程