c++ - 一组具有不同 == 和 < 运算符语义的结构

Question

我使用的是一个非常简单的结构，映射，定义如下:

struct mapping{
    int code;
    string label;

    bool operator<(const mapping& map) const {
        return code < map.code;
    }

    bool operator==(const mapping& map) const {
        return label.compare(map.label) == 0 ;
    }
};

我想创建一组按他们的代码排序的映射。为此，我重载了 < 运算符。它工作正常。我可以毫无问题地插入一些具有不同标签的映射。

当我尝试插入具有相同代码但不同标签的映射时，问题就来了。实际上，在该过程的第二步中，我不知道之前是否插入了具有相同标签的映射。所以，我需要调用 find() 函数来确定是否是这种情况。如果没有插入具有相同标签的映射，没关系，我只需要插入这个新的(但它的代码暂时与另一个映射相同)。如果存在一个具有相同标签的映射，我只需要更新它的代码。我虽然像我那样重载 == 运算符应该足够了，但情况并非如此，如以下代码所示。

mapping m = {1,"xxx"};
mapping m2 ={1, "yyy"};

this->fn[0].insert(m);

set<mapping>::iterator itTmp;
itTmp = this->fn[0].find(m2);
if (itTmp != this->fn[0].end() ) {
    cout << "m2 exists "<<endl;

    if ( !(*itTmp == m2) ){
        cout << "But it is different according to the definition of the == operator "<<endl;
    }
} 

相关输出是:

m2 exists
But it is different according to the definition of the == operator

我怎样才能解决这个问题并设法处理具有非常不同语义的运算符 < 和 ==？理想情况下，我想避免迭代整个集合来寻找具有相同标签的映射。这种策略的复杂度为 O(n)，在我的应用程序中 n 可能非常大。与 find() 的复杂性类似，我更喜欢 O(log n) 的解决方案。

谢谢，

杨

Answer 1

如果一个类可以按其多个字段合理排序，则它根本不应该有关系运算符(operator== 和 operator!= 除外)。

是的，std::map和 std::set默认使用 std::less作为比较器(在内部使用 operator<)，但这只是为了方便，所以您不需要编写一个函数对象来创建一个 set<double>。 , 其中double有一个规范的排序顺序(因此定义了一个(内置的)operator<)。

它们还提供了一个比较器模板参数，您可以而且应该使用它来准确地提供您对该容器(如关系数据库)所需的索引。还有一些容器(在 boost 中)为一组元素维护多个索引。

例如，考虑一个 point2d类:

struct point2d { int x, y; };

人们可能想索引一个 point2d 的容器由 x或 y ，所以按照上面的，point2d不应该定义 operator<根本。为了避免类的每个用户发明他们自己的排序函数对象，它们可以与 point2d 一起提供。 :

struct less_point2d_by_x {
    typedef bool result_value;
    // the mixed overloads are for use in std::lower_bound and similar
    bool operator()( int lhs, int rhs ) const { return lhs < rhs; }
    bool operator()( int lhs, point2d rhs ) const { return lhs < rhs.x; }
    bool operator()( point2d lhs, int rhs ) const { return lhs.x < rhs; }
    bool operator()( point2d lhs, point2d rhs ) const { return lhs.x < rhs.x; }
};
// same for _y

用法:

std::vector<point2d> v = ...;
std::sort(v.begin(), v.end(), less_point2d_by_x()); // sort by x
std::sort(v.begin(), v.end(), less_point2d_by_y()); // sort by y

std::set<point2d, less_point2d_by_x> orderedByX;
std::set<point2d, less_point2d_by_y> orderedByY;

如果您不害怕模板，您甚至可以将关系运算符模板化，如下所示:

template <template <typename T> class Op=std::less>
struct point2d_by_x {
    typedef bool result_value;
    // the mixed overloads are for use in std::lower_bound and similar
    bool operator()( int lhs, int rhs )         const { return Op<int>()(lhs, rhs); }
    bool operator()( int lhs, point2d rhs )     const { return Op<int>()(lhs, rhs.x); }
    bool operator()( point2d lhs, int rhs )     const { return Op<int>()(lhs.x, rhs); }
    bool operator()( point2d lhs, point2d rhs ) const { return Op<int>()(lhs.x, rhs.x); }
};
// same for _y

用法:

std::vector<point2d> v = ...;
std::sort(v.begin(), v.end(), point2d_by_x<std::less>()); // sort ascending by x
std::sort(v.begin(), v.end(), point2d_by_x<>()); // same
std::sort(v.begin(), v.end(), point2d_by_x<std::greater>()); // sort descending by x
// find the position where a `point2d` with `x = 14` would go in the ordering:
std::lower_bound(v.begin(), v.end(), 14, point2d_by_x<std::greater>());

std::set<point2d, point2d_by_x<std::less> > increasingXOrder;
std::set<point2d, point2d_by_y<std::less> > increasingYOrder;