Skip to content

Latest commit

 

History

History
45 lines (27 loc) · 3.58 KB

chapter5-0-chinese.md

File metadata and controls

45 lines (27 loc) · 3.58 KB

第5章 STL基础算法

STL不仅包含数据结构,还有很多算法。数据结构可以帮助存放特定情况下需要保存的数据,而算法则会将数据结构中存储的数据进行变换。

让我们来看一个标准的例子,例如对vector实例中的数据进行累加。这个可以简单的通过循环迭代vector中的元素,将所有值累加在一个对应的值上:

vector<int> v {100, 400, 200 /*, ... */ };

int sum {0};
for (int i : v) { sum += i; }

cout << sum << '\n';

不过,作为一个标准的例子,当然可以使用STL的算法来完成:

cout << accumulate(begin(v), end(v), 0) << '\n';

例子中循环变量也不是很长,不过其可读性比accumulate差很多。一个10行的循环代码看起来的确很尴尬,那么本章我们就看来了解一下标准算法(accumulate, copy, move, transformshuffle等等)的工作机制。

其思想就是提供丰富的算法供开发者使用,避免耗费大量的时间在重复制造轮子上面。另一方面就是,即便开发者会自己去实现相应STL中的算法,也要进行大量的测试来确保自己实现的算法是否正确,STL提供的算法都是经过了严格的测试。所以没有必要做重复的工作,这样也能节省代码审阅者的时间,否则他们还要确定算法实现中是否有Bug。

另一个重点是STL算法非常的高效。很多STL算法提供了多种特化实现,这样足以应对依赖迭代器类型的使用方式。例如,将vector中的所有元素都填充0时,就可以使用std::fill。因为vector使用的是一段连续的内存,对于这种使用连续内存存放数据的结构都可以使用std::fill进行填充,这个函数类似于C中的memset函数。当开发者将容器类型从vector改为list,STL算法就不能再使用memset了,并且需要逐个迭代list的元素,并将元素赋0。开发者不能为了使用memset将数据类型写死为vectorarray,因为实际项目中,还是有很多数据结构存储的地址并不是连续的。大多数情况下,想要自己去将代码实现的更聪明是没有太多意义的,因为STL的实现者已经考虑到了这种情况,并且STL还是免费使用的,为什么不用呢?

让我们总结一下前面提到的几点。使用STL算法的好处:

  • 维护性:算法的名字已经说明它要做什么了。显式使用循环的方式与使用STL算法的方式没法对比。
  • 正确性:STL是由专家编写和审阅过的,并且经过了良好的测试,重新实现的复杂程度可能是你无法想象的。
  • 高效性:STL算法真的很高效,至少要比手写的循环要强许多。

很多算法都是对迭代器进行操作,第3章已经解释了迭代器的工作原理。本章专注于如何使用STL算法解决各种问题,了解这些STL应该如何使用。要展示所有STL算法的使用方式不是本书所要做的事情,这个事情C++手册已经完成了,你可以在网上进行查询,或者花钱购买电子/纸质发布版本。

作为一个STL“忍者”需要将C++手册放在手边……嗯,至少放在浏览器的书签中吧。当我们在完成一个任务的过程中,每个开发者都可以回看一下任务本身,在完成自己的任务时,确定这个STL算法是否适合于你的问题。

在线版本的C++手册:http://cppreference.com

其也提供离线下载功能。

Note:

在面试过程中,对于STL算法的熟悉程度也是判断一个开发者对C++的熟悉程度的标准之一。