C++,STL的小故事

一位逻辑学家Robert Kowalski说过Algorithm = Logic + Control。什么是Logic?什么又是Control?其实就是业务逻辑和控制流。

大多情况下,我们要简化的流程就是循环。有个理念叫“no raw loop”,不是说禁止你用for loop,而是将循环流程封装起来,只在业务层暴露抽象算法接口。《Effective STL》中也有过类似探讨——Item 43. Prefer algorithm calls to hand-written loops

下面是一个实例,灵感来自Sean Parent的演讲

看着你的浏览器,想象一下通过某种方式同时选中喜欢的几个标签,然后拖动他们到某一个标签后。这个功能在桌面软件还是比较常见,我们接着用数字做一个类似的抽象。

有如下一串整数,你对小于20的整数情有独钟。当你选中它们之后,统一拖动到整数21之后的位置,这里隐含的信息是选中和未选中的整数,分别的相对位置不变。如下:

8 12 7 3 34 21 ↓ 4 9 17 45 22

对这串数字来说,结果是:

34 21 ↓ 8 12 7 3 ↓ 4 9 17 45 22

意大利面式设计在这里当然是可行的,但我不打算演示。事实上我标出的几个锚已经暗示了更优的组织结构。

根据开闭区间的习惯第一个锚的索引是 6,我们抽取索引6之前所需的元素放置在头部:

8 12 7 3 34 21

我们再抽取索引6至终点的元素:

4 9 17 45 22

呃…这不就是stable_partition么?

vector<int> nums{8, 12, 34, 7, 3,21, 4, 45, 9,  17, 22};
int anchor = 6;
auto itr_n = stable_partition(nums.begin(),nums.begin() + anchor,
                              [](auto n){return n < 20;});
//simpler if using boost::lambda::_1
stable_partition(nums.begin() + anchor, nums.end(), _1 < 20);

8 12 7 3 ↓ 34 21 ↓ 4 9 17 ↓ 45 22

返回值itr_n就是上面第一个锚的位置。接着就更简单了,只要以itr_n为轴心,旋转 8 12 7 3和 34 21

rotate(nums.begin(),itr_n,nums.begin() + anchor);

34 21 ↓ 8 12 7 3 ↓ 4 9 17 ↓ 45 22

至此就完成了。

啊,发生了什么?是否有一种智力换时间的感觉?即使STL没有提供stable_partition和rotate,实现它们也是顺手之举。核心在于,考略到结构层次,相对于意大利面,只牵扯抽象算法的业务逻辑会清晰非常多。我们回头想想Robert Kowalski的Algorithm = Logic + Control,是否引申出了一个战略方针——解耦Logic和Control。这也是STL致力所解决的。

这里我到一个有趣(和上文不强烈相关)的小场景。有一个文本文件,你需要统计其中的单词数量。

Roses are red,
Violets are blue,
sugar is sweet,
And so are you.

这是文件t.txt的内容。下述代码主要目的在娱乐,不一定符合工业标准:

ifstream file("t.txt", istream::ate);

file >> noskipws;
auto size = file.tellg();
file.seekg(0);

unordered_map<string, int> wordCounter;

vector<char> buffer;
buffer.resize(size);

typedef std::istream_iterator<string> s_in;
typedef std::istream_iterator<char> c_in;
auto end = copy_if(c_in(file), c_in(), buffer.begin(),
                    [](char ch) { return ch != '.' && ch != ','; });
file.close();
istringstream dummy(buffer.data());
for_each(s_in(dummy), s_in(), [&](auto &key) { wordCounter[key] += 1; });
//print result
for_each(wordCounter.begin(), wordCounter.end(),
          [](auto &m) { cout << m.first << ": " << m.second << " "; });
//output - you: 1 And: 1 so: 1 sweet: 1 is: 1 are: 3 
//       blue: 1 Violets: 1 Roses: 1 red: 1 sugar: 1 

哗?还能这样瞎搞?由于迭代器的存在,STL的算法同样适用于stream,我觉得这是设计模式中为数不多的好的一面。这里又可以借助不同规格的stream去格式化数据,可谓以逸待劳。另具启发的是stream可以被塞进几乎所有类型的值,也即可以将其看作一个多元类型的tuple。这难道不是在暗示一些邪恶的操作?能有多邪恶就看你的想象力了,吼吼。

Leave a Reply

Your email address will not be published. Required fields are marked *