logo标签列表

C++中有比迭代更好的URL模式匹配方法吗？

c++regexpattern-matchingtr1
4

我有一个模式匹配程序，根据请求命令使用的URL从std::map中查找值。 URL映射表填充了像这样的值：

// Assume this->commands_ is defined elsewhere as std::map<std::string, int>
// Providing a number of URL examples to give an idea of the structure of
// the URLs
this->commands_["/session"] = 1;
this->commands_["/session/:sessionid/url"] = 2;
this->commands_["/session/:sessionid/back"] = 3;
this->commands_["/session/:sessionid/forward"] = 4;
this->commands_["/session/:sessionid/element"] = 5;
this->commands_["/session/:sessionid/element/:id/text"] = 6;
this->commands_["/session/:sessionid/element/:id/value"] = 7;

每个URL模式中的令牌（由前面的“：”指定）在调用查找例程时被实际值替换（例如，“/session/1234-8a0f/element/5bed-6789/text”），但它们是命名参数，我需要保留。上面示例中命名令牌的列表不是详尽无遗的，可能存在其他命名令牌在上述位置上。请注意，令牌值是十六进制编码的数字。
目前，我正在迭代地通过映射的键，用正则表达式值替换替换令牌，并使用std :: tr1 regex类对请求的值执行正则表达式匹配，将匹配的令牌名称和值捕获到向量中。代码在功能上与以下代码等效（为了清晰起见，代码比通常更冗长）：
// Assume "using namespace std;" has been declared,
// and appropriate headers #included.
int Server::LookupCommand(const string& uri,
                          vector<string>* names,
                          vector<string>* values) {
    int value = 0;

    // Iterate through the keys of the map
    map<string, int>::const_iterator it = this->commands_.begin();
    for (; it != this->commands_.end(); ++it) {
        string url_candidate = it->first;

        // Substitute template parameter names with regex match strings
        size_t param_start_pos = url_candidate.find_first_of(":");
        while (param_start_pos != string::npos) {
            size_t param_len = string::npos;
            size_t param_end_pos = url_candidate.find_first_of("/",
                                                            param_start_pos);
            if (param_end_pos != string::npos) {
                param_len = param_end_pos - param_start_pos;
            }

            // Skip the leading colon
            string param_name = url_candidate.substr(param_start_pos + 1,
                                                     param_len - 1);
            names->push_back(param_name);
            url_candidate.replace(param_start_pos,
                                  param_len,
                                  "([0-9a-fA-F-]+)");
            param_start_pos = url_candidate.find_first_of(":");
        }

        tr1::regex matcher("^" + url_candidate + "$");
        tr1::match_results<string::const_iterator> matches;
        if (tr1::regex_search(uri, matches, matcher)) {
            size_t param_count = names->size();
            for (unsigned int i = 0; i < param_count; i++) {
                // Need i + 1 to get token match; matches[0] is full string.
                string param_value = matches[i + 1].str();
                values->push_back(param_value);
            }
            found_value = it->second;
            break;
        }
    }
    return value;
}

请注意，我没有使用Boost库，并且在这个项目中也不允许使用它们。
对于我来说，这段代码的效率感觉非常低下，因为我每次都要遍历map的键，但是我看不到树林而错过了森林，很难想出其他办法。虽然描述听起来毫无意义，但我实际上正在尝试构建一个基于正则表达式匹配键而不是确切匹配的映射查找。我该如何使其更加高效？在设计此函数时，我可能忽略了哪些模式？
1
有趣的问题。然而，请注意，std::map在这里根本不是正确的数据结构；它提供了一个基于键的相对排序关系从精确键到值的映射。你想要完全不同的东西，即基于模式匹配关系的键到值的映射。 - Konrad Rudolph
2
同意地说，映射不是正确的数据结构。我在这里使用它作为vector<MyUrlTemplateClass>的功能等效物，在其中迭代向量。当此函数开始运行时，映射是正确的结构，但是在要求发生变化后，我没有回去更正代码以使用不同的数据结构。最终，问题是：使用什么是正确的数据结构？ - JimEvans
2个回答
6
我看来，你可以将URL分成其组件（也许使用这里的建议之一），然后使用决策树来找到正确的模式。
在这棵树中，每个节点都是一个正则表达式，用于匹配你的URL的特定组件，而叶子节点就是你当前在映射中存储的值。
                                 session
                                    |   \
                                    |    1
                                    |
                              ([0-9a-fA-F-]+)
                              /     |     \
                             /      |      \
                           url     back    element
                            |       |       |     \
                            |       |       |      5
                            2       3       |
                                        ([0-9a-fA-F-]+)

上面是你的示例树的一部分。您需要使用自定义数据结构来实现树，但这相当简单。
事实上，我在这个答案和另一个答案中采用了混合方法，但这是我缺失的见解。 - JimEvans
1
不妨不用特定值替换模式中的 :session_id 和 :id 标记，再进行匹配。我们可以将候选项进行正则表达式替换，将特定值替换为占位符(session_id和id)。这样，您就可以直接在映射中查找通用字符串了。
该方法面临两个挑战。首先，“sessionid”和“id”不是URL中可能出现在这些位置的唯一标记名称；示例URL只是看起来如此。其次，令牌值是十六进制编码的，因此它们可能包括字母字符。我已经编辑了问题和示例代码，以使其更加清晰明了。 - JimEvans
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接