комплекс карт найти операцию - PullRequest
Новая
       24

комплекс карт найти операцию

4 голосов
/ 17 февраля 2009

Я хочу сделать следующее:
Определите карту между строкой и объектом любого типа (может быть списком, целым числом - чем угодно).
Ключи к карте могут быть следующими (значения, опять же, не важны):
"AAA / 123" ==> 1
"AAA / " ==> 2
"BBB / " ==> 3
"CCC / *" ==> 4
"CCC / 123" ==> 5
Теперь уловка в том, что я хочу найти правильные значения, учитывая следующие строки:
«AAA / 123» должно дать 1.
«AAA / 111» должно дать 2.
«CCC / 111» должен дать 4.
«CCC / 123» должен дать 5.
«BBB / AAA / 123» должно дать 3.

Есть идеи, как мне это сделать с C ++ и, возможно, STL / boost?

Ответы [ 3 ]

3 голосов
/ 17 февраля 2009

Вот вариант ответа litb (который был каким-то образом удален из списка ответов), который может сработать, если удалить '*': 

template<typename Map> typename Map::const_iterator
find_prefix(Map const& map, typename Map::key_type const& key)
{
    typename Map::const_iterator it = map.upper_bound(key);
    while (it != map.begin())
    {
        --it;
        if(key.substr(0, it->first.size()) == it->first)
            return it;
    }

    return map.end(); // map contains no prefix
}

Я забыл добавить код, который его использует: 

std::map<std::string, int> smap;
smap["AAA/"] = 1;
smap["BBB/"] = 2;
smap["AAA/AA"] = 3;

find_prefix(smap, "AAA/AB")->second; // ==> 1
find_prefix(smap, "AAA/AA")->second; // ==> 3
find_prefix(smap, "BBB/AB")->second; // ==> 2
find_prefix(smap, "CCC/AB"); // ==> smap.end()

любой комментарий (и спасибо litb)?

1 голос
/ 17 февраля 2009

Из вашего требования кажется, что вам не нужна структура данных карты, но она может быть задана или что-то очень простое.

Я думаю, что структура вроде этой std :: map может вам помочь. Boost :: any сможет хранить что угодно, но предостережение заключается в том, что вам нужно знать, что тип значения должен прочитать его обратно.

Ключ - это строка, и, следовательно, она также может быть выражением регулярного выражения. С этой структурой вам понадобится два проходных алгоритма: 

std::map<std::string, boost::any> _map;
if (_map.find(key) != _map.end)
{
   // exact match
}
else
{
   // Have to do sequential regex (use boost::regex) matching
}

Поскольку оценка регулярных выражений во время выполнения может быть дорогостоящей, вы можете использовать std :: vector>, так что для шаблонов регулярных выражений вы сохраняете скомпилированное регулярное выражение в одном из полей.

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

0 голосов
/ 17 февраля 2009

Как насчет использования двух карт? 

std::map<std::string, std::map<int, object> >

Если вы хотите посмотреть aaa / * вы делаете 

a.find("aaa") => you get an iterator to the map with all "aaa" prefix

Если вы хотите посмотреть AAA / 123, вы делаете 

a.find("aaa")->find(123)

(конечно, вы ДОЛЖНЫ подтвердить, что вы не получили конца, это только для примера)

...