C++ 中相当于 Python 的 cmp 或 Haskell 的 compare

Question

问题：

有没有类似于Python的cmp或者Haskell的compare的C++方法？

compare就像把operator==和operator<合在一起。它会返回LT（小于）、EQ（等于）或GT（大于）。而且它的速度是调用operator==和operator<的两倍，因为它只需要一次遍历。

更多细节：

在工作中，我经常有一些结构体用作映射的键，比如：

struct RecordUsedAsAKey {
    int field_a;
    string field_b;
    vector<float> field_c;

    // operator< is needed for keys in maps.
    bool operator<(const RecordUsedAsAKey& other) const;
};

bool RecordUsedAsAKey::operator<(const RecordUsedAsAKey& other) const {
    if (field_a != other.field_a)
        return field_a < other.field_a;
    if (field_b != other.field_b)
        return field_b < other.field_b;
    return field_c < other.field_c;
}

但是RecordUsedAsAKey::operator<有个问题，就是速度不够快。

• 当string::operator!=找到不同的字符时，程序在string::operator<中又会遍历相同的字符，这样就浪费了时间。
• 对于vector的比较也是一样。

如果我有一个类似于Haskell的compare的方法，我的比较方式会更高效：

Ordering RecordUsedAsAKey::compare(const RecordUsedAsAKey& other) const {
    Ordering t;
    if ((t = field_a.compare(other.field_a)) != EQ)
        return t;
    if ((t = field_b.compare(other.field_b)) != EQ)
        return t;
    return field_c.compare(other.field_c);
}

这样更高效，因为string的compare方法只需要对字符串进行一次遍历。

顺便提一下：在Haskell中，整个比较的代码只需要写deriving Ord。

Answer 1

这是一个更简单、更通用的版本，来自Sylvain Defresne的回答：

template<typename T>
order compare(const T &left, const T &right) {
    if (left < right)
        return order_lt;
    else if (left == right)
        return order_eq;
    return order_gt;
}

Answer 2

因为 map 的工作方式是基于 operator< 的，而很多操作符的实现也是依赖于 operator<，所以如果只用这个来做事情，可能会更好。

举个例子：

template <typename T>
int compare(const T& x, const T& y)
{
    if (x < y) return -1;
    else if (y < x) return 1;
    else return 0;
}

或者，更好的是，

template <typename T, typename F>
int compare(const T& x, const T& y, F pred)
{
    if (pred(x, y)) return -1;
    else if (pred(y, x)) return 1;
    else return 0;
}

template <typename T>
int compare(const T& x, const T& y)
{
    return compare(x, y, std::less<T>());
}

这样你就可以在需要的时候使用 compare(k1, k2, mymap.key_comp())。

当你的程序运行正常后，并且你确定 compare 是性能瓶颈，你可以针对那些有问题的类型进行特别处理。比如说，

template <typename C, typename T, typename A>
int compare(const std::basic_string<C, T, A>& x,
            const std::basic_string<C, T, A>& y)
{
    return x.compare(y);
}

如果你担心字符串类型的效率。

如果你在比较序列，可以使用 std::lexicographical_compare。不过，你可能想重新实现一下，以处理相等的情况，这里有一个针对 std::vector 的优化版本：

template <typename T, typename A, typename F>
int compare(const std::vector<T, A>& x,
            const std::vector<T, A>& y, F pred)
{
    std::vector<T, A>::const_iterator i = x.begin();
    std::vector<T, A>::const_iterator j = y.begin();

    while (i != x.end())
    {
        if (j == y.end()) return 1;
        if (pred(*i, *j)) return -1
        else if (pred(*j, *i)) return 1;

        ++i; ++j;
    }

    return j == y.end() ? 0 : -1;
}

Answer 3

你可以很简单地自己实现这个功能，作为一个独立的函数。

#include <string>
#include <vector>
enum order {
    order_lt = -1,
    order_eq,
    order_gt
};

// General case, templated version.
template < typename T >
order compare(T left, T right) {
    if (left < right)
        return order_lt;
    if (left == right)
        return order_eq;
    return order_gt;
}

// Specialization
order compare(const std::string& left, const std::string& right) {
    return order(left.compare(right));
}
template < typename T >
order compare(const std::vector<T>& left, const std::vector<T>& right) {
     order o = compare(left.size(), right.size());
     if (o != order_eq)
         return o;
     for (size_t i = 0; i < left.size(); ++ i) {
         o = compare(left[i], right[i]);
         if (o != order_eq)
             return o;
     }
     return order_eq;
}

注意：我对代码进行了编辑，加入了一个模板版本，以适应更一般的情况（前提是这个类型定义了operator<和operator==）。我还保留了一些特化，因为在某些类型（主要是容器）上，这样可以提高运行速度。

编辑：使用std::string::compare代替strcmp。