3

我正在使用一个非常简单的结构，映射，定义如下：

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) 中的解决方案。

谢谢，

约安

4

5 回答 5

1

正如@PiotrNycz 指出的那样，std::set根本不使用或关心operator==，只有operator<. 这包括std::set<X>::find会员。因此，您的find调用是定位具有相同代码的元素，而不是具有相同标签的元素。

但是命名空间范围函数std::find确实使用operator==，而不是operator<。

itTmp = std::find(this->fn[0].begin(), this->fn[0].end(), m2);

由于您set是按代码而非标签排序的，因此当元素数量很大时，查找具有给定标签的元素的效率不如查找具有给定代码的元素。如果这很重要，其他答案就如何更改容器类型以提供帮助提供了建议。

于 2012-06-21T12:10:21.003 回答
1

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

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

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

例如，考虑一个point2d类：

struct point2d { int x, y; };

point2d可以合理地希望通过xor来索引 s 的容器y，因此按照上述内容，point2d根本不应该定义 an 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;
于 2012-06-21T20:58:56.003 回答
0

std::set使用operator<，因此您需要将您的语义插入operator==到operator<. 您可以通过例如首先检查 来做到这一点code，如果相等，则比较label。

更新标准库中的有序容器必须使用隐含严格弱顺序的比较器。这意味着operator<需要推导出一个严格的顺序（不同的元素有不同的顺序），但是很弱，因为它对不等式一无所知。

在您的情况下，正如评论中指出的那样，您需要比较string label. 两种选择：

return code < map.code || (!(map.code < code) && label < map.label);

或相反，首先检查label然后code.

仅检查是否相等label会破坏“严格”的排序感。

于 2012-06-21T09:57:01.507 回答
0

如果您希望 O(log n) 查找代码或映射，则std::set不是正确的容器，因为它仅按一个顺序排序。您需要的是一个双映射，其值为指向另一个映射中条目的指针。这样，每个成员都是其映射中的一个键，并且可以在 O(log n) 中找到。

如果可以使用 boost，请检查boost.bimap

于 2012-06-21T09:59:13.517 回答
0

可能您应该创建几个容器（两个或三个）。例如：

std::list<mapping> storage; // actual storage
std::multiset<mapping*, compare_by_code_functor> by_code; // sorted by code
std::set<mapping*, compare_by_label_functor> by_label; // sorted by label

或者

std::list<mapping> storage; // actual storage
std::multiset<std::list<mapping>::iterator, compare_by_code_functor> by_code; // sorted by code
std::set<std::list<mapping>::iterator, compare_by_label_functor> by_label; // sorted by label
于 2012-06-21T10:51:47.260 回答