Effective STL 学习笔记 Item 21：Comparison Function 相关
*/-->
div.org-src-container {
font-size: 85%;
font-family: monospace;
}
Table of Contents
1 Always have comparison functions return false for equal values
执行下面的代码：
set<int, less_equal<int> >s; // s is sorted by "<="
s.insert(10); // insert the value 10a.
s.insert(10); // Insert the value 10b again...
第三行会成功么？这里我们使用了 less_equal 作为计算是否 Equivalence 的比较算法，结合前面 对于 Equivalence 的定义，我们可以知道：
\begin{equation}
\left.\begin{matrix}
& !(10_a
最后的结论是先插入的 10 和后插入的 10 不是等价的 (Equivalence) ，最后会导致 10 在这个 set 里面出现两次。
同样的问题即便是在 multiset 里面也存在。 Multiset 确实允许一个元素在 set 里面出现多次，但如调用该容器的 equal_range 方法，该方法会对容器的每个元素调用上面的公式，最后发现相同的值并不等价，从而不能返回完整的 range。
让比较函数在比较等值对象的时候，始终返回 false 则解决了上面的问题，假设：
\(pred(10a, 10b) = pred(10b, 10a) =false\) ，则：
\begin{equation}
\left.\begin{matrix}
& !pred(10_a, 10_b) \\
& !pred(10_b, 10_a)
\end{matrix}\right\}\Rightarrow !false \& !false \Rightarrow true \& true \Rightarrow true
\end{equation}
对于 set 和 multiset，无论是插入还是 equal_range 都没有问题了，记住，给定两个对象，比较函数：
\(pred(a, b)\) 决定了对象 a 是否应该插在对象 b 的前面 。 对象 A 永远不应该插在它自己（ 或者其等值对象之前）,要永远返回 False 。
2 Strict Weak Ordering
STL 容器中的 \(operator Strict Weak Ordering ，直译为“严格弱排序 ”，名字比较诡异，但其实就是一个受到若干“ 严格 ”约束的 < 操作符，该操作符可以用于集合的排序，形成一个符合
STL 要求的集合。 这些约束条件包括：
-
反自反性 (irreflexive): 对给定的元素 x，始终满足： \(!(x
返回去看前面的内容，即要求 \(pred(x, x) = false\) ，要求排序算法对等值对象始终返回 false，其实也正事要求符合反自反性。 - 非对称性 (asymmetry): 即 $ (x < y)⇒ !(y < x)$
- 传递性 (Transitivity): \((x
- 不可比较的传递性: 对于给定的 x, y, z，如果 x 不能和 y 比较，y 不能和 z 比较，则 x 不能和 z 比较。
上面的这个定义不是太好记忆，下面这个衍化版倒是好记：
- Strict: pred (X, X) is always false.
- Weak: If !pred (X, Y) && !pred (Y, X), X==Y.
- Ordering: If pred (X, Y) && pred (Y, Z), then pred (X, Z).
如果不符合上面的规定，则对两个对象执行 Equivalence 判定会出问题， Associative Container 的定义也就不完全。
例如，有个表示屏幕坐标点的类，为其写 \(operator
class Pos
{
public:
Pos(int x, int y)
:m_x(x),
m_y(y)
{}
virtual ~Pos(){}
bool operator< (const Pos& p) const
{
return m_x < p.m_x && m_y < p.m_y;
}
private:
int m_x;
int m_y;
};
上面的 \(operator
正确的写法应该是：
class Pos
{
public:
Pos(int x, int y)
:m_x(x),
m_y(y)
{}
virtual ~Pos(){}
bool operator< (const Pos& p) const
{
if (m_x < p.m_x)
{
return true;
}
else if (m_x > p.m_x)
{
return false;
} if (m_y < p.m_y)
{
return true;
}
else if (m_y > p.m_y)
{
return false;
}
return false;
}
private:
int m_x;
int m_y;
};
（使用许可：署名-非商业性使用-相同方式共享 3.0 *许可协议 。）