C++11 使用带有自定义比较函数的 std::equal_range

Question

考虑这个例子

(请注意，这只是我为了说明问题而编造的东西。我很清楚有更有效的方法来解析算术表达式，虽然这个主题很吸引人，但这与我的实际无关问题。这只是一个半现实的例子，如果我可以这样说的话。
我同意解析器可能会使问题看起来更复杂，但我想不出更抽象的例子)。

假设您想做一个简单的表达式解析器。您将从分词器中获取一些字符串，其中一些可能不明确。

例如，字符串“-”可以表示一元减号或二进制减号。

假设您想获得字符串“-”的所有可能含义。

你可以这样做:

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);

它也不会编译，提示参数的顺序再次错误(在算法的其他点)。

然而，此代码将有效(see a live version here)

#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 上以 Debug模式编译)？

Answer 1

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

所以你的 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);
    }
};