时间：2014.05.17
地点：基地二楼
------------------------------------------------------------------------------
一、谓词
有些算法会对输入的序列元素进行比较运算，但具体使用何种，我们往往根据需求而变化，于是C++泛型编程中将这个需求抽象为算法的一个参数，该参数是一个谓词，谓词是一个可被调用的表达式，谓词的返回结果是一个能用作条件的值。标准库算法使用的谓词有一元谓词和二元谓词，这里的一元和二元表示该谓词只接受一个参数或者两个参数。接受谓词参数的算法会对输入序列中的元素调用这个谓词进行计算。举个例子来说，我们知道sort算法中默认使用<运算符对元素进行比较来排序，现在我们可定义一个谓词，告诉sort函数，用这个谓词来代替原来的<运算符来对元素进行比较，然后进行排序操作。
bool IsShorter(const string& s1, const string& s2)
{
return s1.size() < s2.size();
}
以上部分我们定义了一个谓词，然后就可将该谓词传递给算法sort，sort就会用该算法代替之前的<运算符比较两个元素，也就是说，之前的排序我们是用默认的<运算对两个元素的大小进行比较后决定两个元素的次序的，现在我们用的谓词是通过比较两个元素的长度大小来决定两个元素的次序的，于是最终结果将是按元素长度进行排序，也就是说，我们通过一个自定义的谓词传递给算法，从而改变算法是如何对元素进行排序的行为的。
一个完整的测试例子如下：
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
bool IsShorter(const string& s1, const string& s2)
{
return s1.size() < s2.size();
}
int main()
{
vector<string> words{ "turtle", "fox", "slow", "red", "the", "oveer", "quick" };
sort(words.begin(), words.end(), IsShorter);
for (const auto& s : words)
cout << s << " ";
return 0;
}
这里顺便介绍一个stable_sort()算法，它的用法和上面那个sort()算法一样，也接受一对迭代器和一个谓词，不过它排序是稳定排序，如过有要求将单词按长度进行排序，而相同长度的单词就按字典排序的话，可先用默认版的sort对单词进行排序，默认是字典排序，然后再用自定义谓词的stable_sort排序，即现在是按单词长度排序，如果长度相同，把持先有的单词次序相对位置不变，即原来的字典排序后相对位置。
------------------------------------------------------------------------------
二、练习
标准库中有一个partion算法，啊，快速排序中就要用到，我们可自己定义划分谓词将它传递给该算法，partion算法会根据该谓词对元素进行划分，使得谓词为true的值会排在容器前，使得谓词为false的值会排在容器后，而且还返回一个迭代器，指向最后一个使得谓词为true的元素之后的那个位置，先要求partion算法根据元素的大小将string划分为长度小于5和长度大于或等于5的两个部分，并打印出长度大于或等于5的string。这个实现如下：
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool IsBigString(const string& str)
{
return str.size() < 5;
}
int main()
{
vector<string> words{ "This", "is", "my", "first", "string", "test", "example" };
auto cursor_iter=partition(words.begin(), words.end(), IsBigString);
for (auto it = cursor_iter; it != words.end(); ++it)
cout << *it << " ";
return 0;
}
看来掌握泛型算法真的很实用呀~