Effective STL 学习笔记 Item 21:Comparison Function 相关

| 分类 C-Family  | 标签 c++  stl 

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_b) \\ & !(10_b <= 10_a) \end{matrix}\right\}\Rightarrow !true \& !true \Rightarrow false \& false \Rightarrow false \end{equation}

最后的结论是先插入的 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 < x)\)
    返回去看前面的内容,即要求 \(pred(x, x) = false\) ,要求排序算法对等值对象始终返回 false,其实也正事要求符合反自反性。
  • 非对称性 (asymmetry): 即 $ (x < y)⇒ !(y < x)$
  • 传递性 (Transitivity): \((x < y) \& (y < z) \Rightarrow (x < z)\)
  • 不可比较的传递性: 对于给定的 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 <\) 中,可以发现 \(pred((0, 1), (1, 0)) ==false\) 且: \(pred((1, 0), (0, 1)) ==false\) , 根据定义,则 (1, 0) == (0, 1), 这明显是一个错误的结论。

正确的写法应该是:

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;
};

上一篇     下一篇