реализация map.find - PullRequest
Новая
       28

реализация map.find

0 голосов
/ 26 марта 2012

Я пытаюсь реализовать map.find себя, потому что я должен искать среди регулярных выражений. Но мой код работает долго. Помогите плз. Как я могу улучшить код? Могу ли я добавить целое число в итератор другим способом? Встроенная функция работает более чем в 10 раз быстрее. 

iterator find (string toFind)
{
    iterator begin=mainMap.begin();
    int L=0;
    int R=mainMap.size();
    iterator M;
    while (L!=R)
    {
        M=begin;
        addition(&M,((R+L)/2));
        if (match (&(*M).first, &toFind))
            return M;
        if (toFind<(*M).first)
        {
            R=(R+L)/2;
        }
        else 
            L=(R+L)/2+1;
    }
    return mainMap.end();
}

void addition (iterator* it, int n)
{
    for(int i=0;i<n;i++, (*it)++)
    {
    }
}

bool match (const string* expression, const string* line)
{
    return *expression==*line;
}

1 Ответ

0 голосов
/ 26 марта 2012

Вам не нужно реализовывать новый алгоритм поиска. Достаточно передать функтор сравнения на карту.

Что-то вроде 

struct MyLessThan
{
    bool operator(const string& left, const string& right )(
      //Your implementation of less than, where you can use regular expressions
      //Don't forget it should have strict weak ordering

    }
};

и затем определите карту как (используя функтор в качестве аргумента шаблона) 

std::map<string, VALUETYPE, MyLessThan> myMap;

с VALUETYPE тип значений карты.

...