43.泛型算法优于显式循环

Posted on | In

前言

 
算法内部本身就存在循环，因此众多需要用循环实现的任务，算法可以轻松完成。

问题实例

 
假设当前有一个支持重画的class:

1
2
3
4
5
6
class Widget {
public:
    ...
    void redraw() const;
    ...
};

如果我们试图将某个list内所有Widget重画，其循环版本大致如下所示：
1
2
3
4
list<Widget> lw;
for (auto i = lw.begin();i != lw.end(); ++i) {
    i->redraw();
}

当然了，也可以使用for_each算法：
1
for_each(lw.begin(),lw.end(),[](Widget& w){w.redraw();});

泛型算法相较于显式循环的优点

 
一般来说，程序员通常认为循环比算法易读，但本节内容将说明算法更可取，理由有三：

  1. 效率高
  2. 正确性高
  3. 更直观

效率

相较于显式循环，算法的高效性体现在：

  1. 避免了每一次循环结束迭代器都需要与end()作比较（i != lw.end());
  2. 库的实现者可以用更优化的方式来遍历容器。
  3. 大佬们写的算法比我们的实现更高效。

正确性

众所周知，写循环时最麻烦的莫过于确保当前迭代器的有效性，并且保证它指向了正确的位置。

问题实例

假设有一个数组，我们试图将其中的每一个元素都加上41然后插入到deque的前端
，循环体如下所示：

1
2
3
double data[maxNumDoubles];//C API
for(size_t i=0;i<numDoubles;++i)
    d.insert(d.begin(),data[i]+41]);

这段代码的问题在于:插入的元素是反序的，因为每一次都把待插入元素放在了开头。
于是我们做出了如下修改：
1
2
3
4
auto insertLocation = d.begin();
for (size_t i = 0; i < numDoubles; ++i) {
    d.insert(insertLocation++, data[i] + 41);
}

但是实际上这个更不行，因为insert之后后面的迭代器都失效了，insertlocation自然也是如此，所有行为均未定义。
但最终我们还是解决了这个问题，就是每一次插入后都更新insertlocation…
1
2
3
4
5
auto insertLocation = d.begin();
for (size_t i = 0; i < numDoubles; ++i) {
    insertLocation=d.insert(insertLocation, data[i] + 41);
    ++insertLocation;
}

当然，使用插入迭代器也是不错的主意。

使用算法

刚才我们费了半天周折终于利用显示循环写出了正确的程序，那如果使用算法呢？

1
transform(data, data + numDoubles,inserter(d, d.begin()),[](int i){i+=41;});

直观性

任何一个算法在我们读到其名字时就已经了解了它的行为，但显式循环则不然。

总结

 
相对于泛型算法，显式循环稍逊风骚。但它并非一无是处，使用循环能让人更清楚地明白加诸于迭代器上的操作。
我们可以认为泛型算法提升了软件的抽象层次，并且使得它更容易实现、文档化、增强、维护。