0

当我尝试在自定义有序集中查找元素时遇到问题。

File: c:\program files (x86)\microsoft visual studio 10.0\vc\include\xtree
Line: 1746

Expression: invalid operator<

我需要一组字符串，其中元素根据我的需要进行排序。

比较器对象：

struct OrderComparator {
public:
    static map<string,int> valueOrder;

    bool operator()( const string lhs, const string rhs ) {
        map<string,int>::iterator resultLhs,resultRhs;
        resultLhs = valueOrder.find(lhs);
        resultRhs = valueOrder.find(rhs);
        if (resultLhs == valueOrder.end() || resultRhs == valueOrder.end())
        {
            return false;
        }
        else {
            bool result = resultLhs->second <= resultRhs->second;
            return result;
        }
    }

    static map<string,int> create_map()
    {
        map<string,int> m;
        m["A"] = 1; 
        m["B"] = 2;
        m["C"] = 3;
        m["D"] = 4;
        return m;
    }
};

比较器工作正常！

但是当我试图在集合中搜索时出现提到的错误。

typedef set<string, OrderComparator> TREESET_CMP;
...
TREESET_CMP::iterator it = myTree.find(obj); <-fails
...

如果有人能告诉我为什么会发生这种情况以及如何解决它，我会很高兴。

完整的工作迷你示例：

    #include "stdafx.h"
#include <string>
#include <set>
#include <map>
#include <iterator>
#include <algorithm>
using namespace std;
#include <stdio.h>
#include <tchar.h>

struct OrderComparator {
public:
    static map<string,int> valueOrder;

    bool operator()( const string lhs, const string rhs ) {
        map<string,int>::iterator resultLhs,resultRhs;
        resultLhs = valueOrder.find(lhs);
        resultRhs = valueOrder.find(rhs);
        if (resultLhs == valueOrder.end() || resultRhs == valueOrder.end())
        {
            return false;
        }
        else {
            bool result = resultLhs->second <= resultRhs->second;
            return result;
        }
    }

    static map<string,int> create_map()
    {
        map<string,int> m;
        m["A"] = 1; 
        m["B"] = 2;
        m["C"] = 3;
        m["D"] = 4;
        return m;
    }
};
map<string,int> OrderComparator::valueOrder = OrderComparator::create_map();

typedef set<string, OrderComparator> TREESET_CMP;

int _tmain(int argc, _TCHAR* argv[])
{
    TREESET_CMP myTree;
    myTree.insert("B");
    myTree.insert("C");
    myTree.insert("A");

    TREESET_CMP::const_iterator it = myTree.find("A");
    system("PAUSE");

}
4

3 回答 3

3

您的比较没有定义严格的弱排序

严格的弱排序必须具有这些不变量（引用自上面的链接）

  • 非自反性 f(x, x) 一定是假的。
  • 反对称 f(x, y) 意味着 !f(y, x)
  • 传递性 f(x, y) 和 f(y, z) 隐含 f(x, z)。
  • 等价的传递性 等价（如上定义）是传递性的：如果 x 等价于 y 并且 y 等价于 z，则 x 等价于 z。（这意味着等价实际上确实满足等价关系的数学定义。）

你的至少失败了非反身性（将一个对象与自身进行比较必须是错误的）和反对称性（如果 x 小于 y，那么 y 不小于 x）

基本上，<=不是有效的排序，因为x <= x返回 true，这意味着您永远无法在集合中找到元素。为了找到一个元素，该集合会寻找一个具有该属性的元素，!cmp(key, element) && !cmp(element, key)但它永远不会对您的排序起作用。

最简单的解决方法可能是更改<=为<，但可能还有其他问题。

于 2013-03-06T17:52:36.470 回答
1

您的比较器可以是这样的：

bool operator()( const string &lhs, const string &rhs ) {
    map<string,int>::iterator resultLhs,resultRhs;
    resultLhs = valueOrder.find(lhs);
    resultRhs = valueOrder.find(rhs);
    if (resultLhs == valueOrder.end()) return false;
    if (resultRhs == valueOrder.end()) return true;

    return resultLhs->second < resultRhs->second;
}

您可以将 2 行替换为：

if (resultRhs == valueOrder.end()) return false;
if (resultLhs == valueOrder.end()) return true;

如果您希望在此之前对地图中不存在的字符串进行排序。

于 2013-03-06T18:10:00.697 回答
0

尝试将您的比较方法声明为const并使用 const 引用进行争论。第一个修复是确保您可以使用常量版本调用您的方法，OrderComarator第二个修复是避免复制。

bool operator()( const string& lhs, const string& rhs ) const {
于 2013-03-06T17:48:24.640 回答