C++ 11使用std :: equal_range和自定义比较函数

Question

考虑这个例子

(请注意,这只是我用来说明问题的方法.我很清楚有更有效的方法来解析算术表达式,虽然主题很吸引人,但这与我的实际问题无关.它只是一个半- 现实的例子,如果我可以这样说.
我同意解析器的事情可能会使问题看起来更复杂,但我想不出更抽象的例子).

假设您想要一个简单的表达式解析器.你将从tokenizer中获取一些字符串,其中一些可能是模糊的.

例如,字符串" - "可以表示一元减号或二元减号.

假设您希望获得字符串" - "的所有可能含义.

你可以这样做:

1)定义描述所有可能运算符的排序数组

// types of operators
enum class opType: char { unary, lasso, rasso, none };

// operator descriptors
struct opDesc {
    string symbol;
    opType type;
    char   priority;

    // partial order comparison
    bool operator< (const opDesc& a) const
    {
        // unary operators first
        if (symbol == a.symbol) return type < a.type;
        return symbol < a.symbol;
    }

    // comparison with strings
    static bool comp_desc_str (const opDesc& a, const string& s)
    {
        return a.symbol < s;
    }
    static bool comp_str_desc (const string& s, const opDesc& a)
    {
        return s < a.symbol;
    }
};

static opDesc op_descriptors[] = {
    { "+" , opType::unary, 8 }, // unary +
    { "-" , opType::unary, 8 }, // unary -
    { "*" , opType::lasso, 6 }, // multiplication
    { "/" , opType::lasso, 6 }, // division
    { "+" , opType::lasso, 5 }, // addition
    { "-" , opType::lasso, 5 }, // substraction
};

2)用于std::equal_range获取给定字符串的所有可能匹配项

// sort descriptors by value and type
sort(begin(op_descriptors), end(op_descriptors));

// do some searches
string patterns[] = { "+", "-", ">>", "**" };

for (string s : patterns)
{
    pair<opDesc*, opDesc*> ops;

    ops = equal_range(
        std::begin(op_descriptors), 
        std::end  (op_descriptors), 
        s,
        opDesc::comp_desc_str);

    cout << s <<": "<< ops.first[0] << ops.second[-1] << endl;
}

这段代码不会编译,抱怨opDesc::comp_desc_str(它希望参数相反,即string第一个,opDesc下一个).

如果我尝试使用以相反顺序获取其参数的版本替换该函数:

ops = equal_range(
    std::begin(op_descriptors), 
    std::end  (op_descriptors), 
    s,
    opDesc::comp_str_desc);

它也不会编译,抱怨参数再次以错误的顺序(在算法的某个其他点).

但是,此代码可以使用(请参阅此处的实时版本)

#include <regex>
#include <iostream>

using namespace std;

// types of operators
enum class opType: char { unary, lasso, rasso, none };

// operator descriptors
struct opDesc {
    string symbol;
    opType type;
    char   priority;

    // partial order comparison
    bool operator< (const opDesc& a) const
    {
        // unary operators first
        if (symbol == a.symbol) return type < a.type;
        return symbol < a.symbol;
    }

    // comparison with strings
    static bool comp_desc_str (const opDesc& a, const string& s)
    {
        return a.symbol < s;
    }
    static bool comp_str_desc (const string& s, const opDesc& a)
    {
        return s < a.symbol;
    }

    // display
    friend ostream& operator<<(ostream& os, const opDesc& op);
};

ostream& operator<<(ostream& os, const opDesc& op)
{
    os << op.symbol << "[" << (int)op.type << ":" << (int)op.priority << "]";
    return os;
}

static opDesc op_descriptors[] = {
    { "+" , opType::unary, 8 }, // unary +
    { "-" , opType::unary, 8 }, // unary -
    { "~" , opType::unary, 8 }, // bitwise not
    { "**", opType::rasso, 7 }, // power
    { "*" , opType::lasso, 6 }, // multiplication
    { "/" , opType::lasso, 6 }, // division
    { "%" , opType::lasso, 6 }, // remainder
    { "+" , opType::lasso, 5 }, // addition
    { "-" , opType::lasso, 5 }, // substraction
    { "<<", opType::lasso, 4 }, // left shift
    { ">>", opType::lasso, 4 }, // right shift
    { "&" , opType::lasso, 3 }, // bitwise and
    { "^" , opType::lasso, 2 }, // bitwise xor
    { "|" , opType::lasso, 1 }, // bitwise or 
    { "(" , opType::none , 0 }, // braces
    { ")" , opType::none , 0 }
};

int main(void)
{
    // sort descriptors by value and type
    sort(begin(op_descriptors), end(op_descriptors));

    // do some searches
    string patterns[] = { "+", "-", ">>", "**" };

    for (string s : patterns)
    {
        pair<opDesc*, opDesc*> ops;
        // this won't work
        /*
        ops = equal_range(
            std::begin(op_descriptors), 
            std::end  (op_descriptors), 
            s,
            opDesc::comp_desc_str or opDesc::comp_str_desc);
        */
        // this works
        ops.first = lower_bound(
            std::begin(op_descriptors), 
            std::end  (op_descriptors), 
            s, opDesc::comp_desc_str);
        ops.second = upper_bound(
            std::begin(op_descriptors), 
            std::end  (op_descriptors), 
            s, opDesc::comp_str_desc);
        cout << s <<": "<< ops.first[0] << ops.second[-1] << endl;
    }
}

输出:

+: +[0:8]+[1:5]     // unary and binary "-" operators found
-: -[0:8]-[1:5]     // same thing for "+"
>>: >>[1:4]>>[1:4]  // first == second when there is only
**: **[2:7]**[2:7]  // one version of the operator

我在VisualC++ 2013和g ++上尝试了这个代码,结果相同
(只有模板错误消息的混淆变化).

问题

• 是否有一个特殊原因lower_bound,upper_bound应该要求两种不同的自定义比较功能？
• 有没有一种解决方法,MSVC在使用仿函数解决问题时在调试版本中抛出虚假错误？
• 是否有一个明确的解决方法来解决这个问题(即使用equal_range预期而不是两次执行作业并使其在Visual C++ 2013上以调试模式进行编译)？

Answer 1

std::lower_bound需要comp(*it, val)而std::upper_bound需要comp(val, *it).

所以你的comp算子必须提供bool operator () (const opDesc& a, const string& s) const和bool operator ()(const string& s, const opDesc& a) const.

所以,你可以使用以下comp仿函数:

struct lessOpDescWithString
{
    bool operator () (const opDesc& lhs, const std::string& rhs) const {
       return opDesc::comp_desc_str(lhs, rhs);
    }

    bool operator () (const std::string& lhs, const opDesc& rhs) const {
       return opDesc::comp_str_desc(lhs, rhs);
    }
};

Answer 2

我自己的答案，仅总结其他贡献，特别是 Jarod42 的：

为什么要进行两次比较

的算法equal_range需要内部（在本例中）和外部（ ）类型之间的>比较。<opDescstd::string

由于这种情况，您无法a<b从, 中推出，因此您必须提供两个不同的比较器。!(b<a)==

从功能上讲，您可以选择比较操作的任何工作组合，例如<and>或<and <=，但是 std:: 人选择了<与交换参数的固定比较，这是由函数签名决定的选择：它只需要定义一个(type, foreign type)和一个(foreign type, type)变体。

lower_boundonly require <（表示为type < foreigh type）而upper_boundonly require >（表示为foreign type < type），因此两者都可以使用单个函数，但equal_range必须能够访问两个原型。

这样做的方法

实际的解决方案是定义一个函数对象（又名函子）来完成这项工作：

// operator descriptors
struct opDesc {
    string symbol;
    opType type;
    char   priority;

    // partial order comparison
    bool operator< (const opDesc& a) const
    {
        // unary operators first
        if (symbol == a.symbol) return type < a.type;
        return symbol < a.symbol;
    }

    // functor to compare with strings
    struct comp
    {
        bool operator() (const opDesc& a, const std::string& b) const
        {
           return a.symbol < b;
        }

        bool operator() (const std::string& a, const opDesc& b) const
        {
           return a < b.symbol;
        }
    };

并像这样使用它：

pair<opDesc*, opDesc*> ops;
ops = equal_range(
    std::begin(op_descriptors), 
    std::end  (op_descriptors), 
    s,
    opDesc::comp()); // <- functor to provide two different comparison functions

MSVC 错误

此外，由于仅在调试模式下启用了模糊的偏执检查，因此无法在 MSVC++ 2013 上编译。发布版本可以正常编译，g++ 中的代码也可以正常编译，无论调试级别如何。

从使用的神秘名称来看，模板似乎检查比较是否定义了全序（它不应该这样做，因为这个 API 的全部目的是处理部分有序的结构）。

我当前的（丑陋的）解决方法是禁用一些内部调试标志：

#if (defined _MSC_VER && defined _DEBUG)
#define _ITERATOR_DEBUG_LEVEL 1
#endif // _MSC_VER && _DEBUG

在包含 std:: 标头之前

Jarod42 建议的另一种可能的解决方法是定义缺失的比较函数。

    // functor to compare with strings
    struct comp
    {
        bool operator() (const opDesc& a, const std::string& b)
        { return a.symbol < b; }
        bool operator() (const std::string& a, const opDesc& b)
        { return a < b.symbol; }

        // just to make Microsoft Visual C++ happy when compiling in debug mode
        bool operator() (const opDesc& a, const opDesc& b)
        { assert(false); return false; }
    };