[译]Custom comparison, equality and equivalence with the STL

从一段代码引用开始:

std::vector&lt; std::pair<int, std::string=""> &gt; v1 = ... // v1 is filled with data
std::vector&lt; std::pair<int, std::string=""> &gt; v2 = ... // v2 is filled with data
std::vector&lt; std::pair<int, std::string=""> &gt; results;</int,></int,></int,>

std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());

std::set_difference(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(result),
compareFirst);

我们在两个排好序的vector v1 和 v2上调用std::set_difference. std::set_difference 把结果写入 result, std::back_inserter 确保输出的结果从result 的后面添入. 自定义的compareFirst 作为比较函数提供给std::set_difference

默认地, std::set_difference 通过 std::pair 默认的比较函数来比较里面的元素(比较pair的first和second), 我们自定义了compareFirst, 希望只比较pair的first. compareFirst不是STL的函数, 需要我们自己实现.

std::set_difference 使用的前提是input已经排好序, 倘若我们自定义比较函数C, 而通过C我们能把元素排好序, 那么我们使用这个C代替sort的默认排序也是可以的.

在此例中, 我们使用std::set_difference 只对pair的first进行排序, 尽管它们已经通过”first + second”的方式排序完了.

下面来实现compareFirst. 初版:

bool compareFirst(const std::pair<int, std::string="">&amp; p1, const std::pair<int, std::string="">&amp; p2)
{
return p1.first == p2.first; // not final code, bug lurking here!
}

实际上, 上面的代码不会得到我们预期的结果. 为什么? 毕竟std::set_difference 会检查元素跟另一个容器的元素是否相等(equal), 不是吗?</int,></int,>

为了理解上面的内容, 我们把STL大概地分为两类: 操作排序元素的 和操作乱序元素的.

Comparing elements

C++中描述”a is the same as b” 有两种方法

- the natural way: a == b. This is called equality. Equality is based on operator==.
- the other way: a is not smaller than b and b is not smaller than a, so !(a<b) &&="" !(b<a).="" this="" is="" called="" equivalence.="" equivalence="" based="" on="" operator<.="" 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    
对于基本类型如int, 甚至实践中大多数类型, `equivalence` 和`quality` 是相通的. 但是正如*Scott Meyers* 在&lt;&lt; Effective STL&gt;&gt; 一书条目19中指出的, 对于有一些类型, 即使"并非罕见", `equivalence` 和 `equality` 是不同的, 如 大小写不敏感的string类型.

<u>Why such a far-fetched way to express a simple thing?</u>

当我们使用算法对容器内元素进行排序时, 很容易理解必须有独一无二的排序方法(如有多种排序方法, 会很笨重, 并可能产生不一致的结果). 所以对于一个特定的容器, 排序时, "==" 和"&lt;" 只能选一个.

对于STL中排序的部分, 我们别无选择: 排序时必须使用"&lt;";
而乱序部分, 则没有这个约束, 我们可以使用"==".

**Implementing the comparator**

STL的乱序部分使用"==", 而排序部分使用"&lt;". 我们自定义的比较函数也必须遵循这种逻辑.

现在我们可以理解怎么自定义实现`std::set_difference` 的比较函数`compareFirst` 了.




bool compareFirst(const std::pair<int, std::string="">& p1, const std::pair<int, std::string="">& p2) { return p1.first < p2.first; // correct, STL-compatible code. }

原文地址: http://www.fluentcpp.com/2017/02/16/custom-comparison-equality-equivalence-stl/ </int,></int,>