Есть ли лучший способ выполнить сопоставление шаблонов URL в C ++, чем итерация? - PullRequest
Новая
       13

Есть ли лучший способ выполнить сопоставление шаблонов URL в C ++, чем итерация?

4 голосов
/ 25 июня 2011

У меня есть процедура сопоставления с образцом, которая ищет значения из std :: map на основе URL-адреса, используемого для запроса команды.Таблица сопоставления 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 классы регулярных выражений, фиксирующие сопоставленные имена и значения токенов в векторах.Код функционально эквивалентен этому (код более подробный, чем обычно написанный для ясности): 

// 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, и мне не разрешено использовать их для этого проекта.

Этот код кажется мне дико неэффективным, потому что я каждый раз перебираю ключи карты, но я страдаю от того, что не могу видеть пресловутый лес для деревьев, и у менятрудное время придумывать альтернативы.Хотя описание звучит бессмысленно, я по сути пытаюсь построить поиск по карте, основанный на регулярном выражении ключа, а не на точном совпадении.Как я могу сделать это более эффективным?Какой шаблон я упустил из виду при разработке этой функции?

Ответы [ 2 ]

6 голосов
/ 25 июня 2011

На мой взгляд, вы можете разделить URL-адрес на его компоненты (используя одно из предложений в здесь возможно), а затем использовать дерево решений , чтобы найти правильныйшаблон.

В этом дереве каждый узел будет регулярным выражением, соответствующим определенному компоненту вашего URL, а листьями будут значения, которые вы в данный момент храните на своей карте: 

                                 session
                                    |   \
                                    |    1
                                    |
                              ([0-9a-fA-F-]+)
                              /     |     \
                             /      |      \
                           url     back    element
                            |       |       |     \
                            |       |       |      5
                            2       3       |
                                        ([0-9a-fA-F-]+)

выше часть дерева для вашего примера.Для реализации дерева вам придется использовать собственную структуру данных, но это довольно просто.

1 голос
/ 25 июня 2011

Вместо того, чтобы заменять токены: session_id и: id в шаблонах конкретными значениями, а затем выполнять сопоставление, как насчет того, чтобы взять кандидатов и использовать для их замены регулярное выражение, чтобы заменить конкретные значения местозаполнителями (session_id и id)?Тогда вы можете напрямую искать обобщенные строки на карте.

...