天天看点

从零开始学C++之STL(七):剩下5种算法代码分析与使用示例(remove 、rotate 、sort、lower_bound、accumulate)

一、移除性算法 (remove)

如下图所示:

从零开始学C++之STL(七):剩下5种算法代码分析与使用示例(remove 、rotate 、sort、lower_bound、accumulate)

假设现在想要remove 的元素是3,则传入到 _Remove_copy 函数的3个参数如上图第一行所示,Val 即3。

接着遍历First ~ Last 区间的元素,将非移除元素拷贝到前面,覆盖前面的元素,最后的指向如图,函数返回的是Dest 位置,如下代

码所示:

for (; _First != _Last; ++_First)

if (!(*_First == _Val))

            *_Dest++ = *_First;

由上图可看出移除性算法并没有改变元素的个数,如果要真正删除,可以将remove 的返回值传入erase 进行删除,如:

v.erase(remove(v.begin(), v.end(), 3), v.end()); 即会将后面两个元素4 和 5 删除掉。

在这里顺便提一下,erase 会使当前迭代器失效,但可以返回下一个迭代器,故如果需要在遍历中删除,下面的做法才是正确的:

示例代码1:

二、变序性算法( rotate)

rotate 调用了_Rotate,实际上_Rotate 继续调用了某个函数,内部实现代码比较长,而且不容易看懂,这边可以看一下简易的等价

版本实现,来自这里,如下:

假设一个容器有 1 2 3 4 5 6 六个元素,现在想把 1 2 放到后面去,可以这样写 rotate(v.begin(), v.begin()+2, v.end());  如下图所示:

从零开始学C++之STL(七):剩下5种算法代码分析与使用示例(remove 、rotate 、sort、lower_bound、accumulate)

即将first 与 next 对应的元素互换且不断向前推进,直到first == next 为止。

三、排序算法 (sort)

sort 重载了两个版本,第一个版本只有2个参数,默认按从小到大排序(using <code>operator&lt;)</code>;第二个版本有三个参数,即可以自定义比较逻辑

(_Pred)。它们都调用了标准库的std::_Sort, 跟踪进去发现比较复杂,在_Sort 内会根据一些条件选择不同的排序方式,如标准库的堆排序,合并

排序,插入排序等等。站在使用的角度看,没必要去深究,但如果是想学习相关的排序,那是很好的资源。

示例代码2:

此外,sort 有个坑,如果你自己传递比较逻辑,需要注意,如下:

从零开始学C++之STL(七):剩下5种算法代码分析与使用示例(remove 、rotate 、sort、lower_bound、accumulate)

四、已序区间算法 (lower_bound 、upper_bound)

使用这些算法的前提是区间已经是有序的。

lower_bound() 返回第一个“大于等于给定值" 的元素位置,其实还重载了另一个low_bound 版本,如下:

也就是可以自定义比较逻辑,需要注意的是如果使用这个版本,那么区间应该本来就是按comp 方法排序的,如下面这句话:

The elements are compared using <code>operator&lt;</code> for the first version, and comp for the second. The elements in the range shall already

 be sorted according to this same criterion (<code>operator&lt;</code> or comp), or at least partitioned with respect to val.

由于是已序区间,所以函数内用的是二分查找,而两个版本主要的代码不同在于:

_DEBUG_LT(*_Mid, _Val)

_DEBUG_LT_PRED(_Pred, *_Mid, _Val)

upper_bound 与 lower_bound 类似,不过返回的是第一个”大于给定值“ 的元素位置。

示例代码3:

五、数值算法(accumulate)

accumulate 重载了两个版本,第一个版本实现的是累加,第二个版本带_Func 参数,可以自定义计算,比如累乘等。代码都比较好理解,就不赘述

了。看下面的示例代码4:

参考:

C++ primer 第四版

Effective C++ 3rd

C++编程规范