C++ - 算法(algorithm) 的 谓词(predicate) 详解

转载至：http://blog.csdn.net/caroline_wendy/article/details/15378055

算法谓词, 即标准库算法传递的参数, 可以指定算法的操作, 如std::sort, 默认是从小到大, 通过谓词可以修改从大到小.

本文包含基本的5种谓词模式: 函数,函数指针,lambda表达式,函数对象,库定义的函数对象.

 

1. 函数(function)谓词

通过传递函数名, 匹配二元谓词(binary predicates), 根据函数提供的策略, 输出值;

代码:

[cpp]  view plain  copy  print ?

1. /*Function Predicate*/  
2. bool isLarger (const std::string &s1, const std::string &s2) {  
3.     return s1.size() > s2.size();  
4. }  
5. ......  
6. std::stable_sort(sv.begin(), sv.end(), isLarger);  

 

2. 函数指针(function pointer)谓词

建立一个函数指针, 传入算法, 使用指针代替函数名, 用法类似函数谓词.

代码:

[cpp]  view plain  copy  print ?

1. bool (*pf) (const std::string &s1, const std::string &s2);  
2.     pf = &isLarger;  
3.     std::stable_sort(sv.begin(), sv.end(), *pf);  

 

3. Lambda表达式(lambda expression)谓词

Lambda表达式格式: [capture list] (parameter list) -> return type { function body }

需要匹配谓词数, 一元(unary) 或 二元(binary), 也可以通过[capture list]传递函数的变量;

代码:

[cpp]  view plain  copy  print ?

1. std::stable_sort(sv.begin(), sv.end(),  
2.     [](const std::string& s1, const std::string& s2){ return s1.size()>s2.size(); });  

 

4. 函数对象(Function Object)谓词

类中重载函数的调用"()", 使类可以被调用, 并且传入算法谓词中, 进行使用.

代码:

[cpp]  view plain  copy  print ?

1. /*Function Object*/  
2. class LargerString {  
3. public:  
4.     bool operator() (const std::string& a, const std::string& b) {  
5.         return a.size() > b.size();  
6.     }  
7. };  
8. ......  
9. std::stable_sort(sv.begin(), sv.end(), LargerString());  

 

 

5. 库定义的函数对象(Library-Defined Function Object)谓词

使用标准库定义的函数对象, 充当算法中的谓词, 包含在#include<functional>,包含基本的算法和逻辑操作.

代码:

[cpp]  view plain  copy  print ?

1. std::stable_sort(sv.begin(), sv.end(), std::less<std::string>());  

 

所有方法代码(Eclipse CDT; GCC 4.7.1):

[cpp]  view plain  copy  print ?

1. /* 
2.  * CppPrimer.cpp 
3.  * 
4.  *  Created on: 2013.11.11 
5.  *      Author: Caroline 
6.  */  
7.   
8. /*eclipse cdt*/  
9.   
10. #include <iostream>  
11. #include <string>  
12. #include <vector>  
13. #include <algorithm>  
14. #include <functional>  
15.   
16. using namespace std;  
17.   
18. class PrintString {  
19. public:  
20.     PrintString (std::ostream &o = std::cout, char c = ' ') : os(o), sep(c) { }  
21.     void operator() (const std::string &s) const { os << s << sep; }  
22. private:  
23.     std::ostream &os;  
24.     char sep;  
25. };  
26.   
27. /*Function Predicate*/  
28. bool isLarger (const std::string &s1, const std::string &s2) {  
29.     return s1.size() > s2.size();  
30. }  
31.   
32. /*Function Object*/  
33. class LargerString {  
34. public:  
35.     bool operator() (const std::string& a, const std::string& b) {  
36.         return a.size() > b.size();  
37.     }  
38. };  
39.   
40. int main (void) {  
41.   
42.     std::vector<std::string> sv = {"Beauty", "Girl", "Lady", "Women", "Pretty"};  
43.   
44.     std::stable_sort(sv.begin(), sv.end(), isLarger);  
45.     std::cout << "Function Predicate : ";  
46.     std::for_each(sv.begin(), sv.end(), PrintString(std::cout));  
47.     std::cout << std::endl;  
48.   
49.     std::stable_sort(sv.begin(), sv.end(),  
50.             [](const std::string& s1, const std::string& s2){ return s1.size()>s2.size(); });  
51.     std::cout << "Lambda Expression Predicate : ";  
52.     std::for_each(sv.begin(), sv.end(), PrintString(std::cout));  
53.     std::cout << std::endl;  
54.   
55.     bool (*pf) (const std::string &s1, const std::string &s2);  
56.     pf = &isLarger;  
57.     std::stable_sort(sv.begin(), sv.end(), *pf);  
58.     std::cout << "Function Pointer Predicate : ";  
59.     std::for_each(sv.begin(), sv.end(), PrintString(std::cout));  
60.     std::cout << std::endl;  
61.   
62.     std::stable_sort(sv.begin(), sv.end(), LargerString());  
63.     std::cout << "Function Object Predicate : ";  
64.     std::for_each(sv.begin(), sv.end(), PrintString(std::cout));  
65.     std::cout << std::endl;  
66.   
67.   
68.     std::stable_sort(sv.begin(), sv.end(), std::larger<std::string>());  
69.     std::cout << "Library-Defined Function Object Predicate : ";  
70.     std::for_each(sv.begin(), sv.end(), PrintString(std::cout));  
71.     std::cout << std::endl;  
72.   
73.     return 0;  
74.   
75. }  

输出:

[plain]  view plain  copy  print ?

1. Function Predicate : Beauty Pretty Women Girl Lady   
2. Lambda Expression Predicate : Beauty Pretty Women Girl Lady   
3. Function Pointer Predicate : Beauty Pretty Women Girl Lady   
4. Function Object Predicate : Beauty Pretty Women Girl Lady   
5. Library-Defined Function Object Predicate : Women Pretty Lady Girl Beauty