Добрый день!

Имеется строка std::basic_string <char_type>. Имеется контейнер (пока не понятно какой) содержащий boost::basic_regex <char_type> (ключ) и некоторый тип (значение);

Необходимо осуществить в контейнере следующий поиск: ищется первый подходящий для строки boost::basic_regex <char_type> возвращается соотв. значение;

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

Возникает наивный вопрос: Как это сделать?

Пока имеется линейный вариант поиска:

    ///////////////////////////////////////////////////////////
    /// declaration for regex predicante object
    ///////////////////////////////////////////////////////////
    template <typename _Second> class RegexPredicante : public std::unary_function
        <std::pair <boost::shared_ptr <const boost::basic_regex <StringType::value_type> >,
            _Second>, bool>
    {
            const StringType & _M_String;
            //---------------------------------------------------------------------------
    public:
//---------------------------------------------------------------------------------------
            ///////////////////////////////////////////////////////////
            /// typedef for second type
            ///////////////////////////////////////////////////////////
            typedef _Second SecondType;
//---------------------------------------------------------------------------------------
            explicit RegexPredicante (const StringType & _P_String) : _M_String (_P_String) {}
            //---------------------------------------------------------------------------
            bool operator () (const std::pair <boost::shared_ptr <const boost::basic_regex
                <StringType::value_type> >, SecondType> & _P_Pair) const
            {
                //-----------------------------------------------------------------------
                return boost::regex_match (_M_String, * _P_Pair.first);
            }
            //---------------------------------------------------------------------------
    };

    ///////////////////////////////////////////////////////////
    /// declaration for get regex value fumction
    ///////////////////////////////////////////////////////////
    template <typename _Exception, typename _Second> inline _Second GetRegexValue
        (const StringType & _P_String, const std::deque <std::pair <boost::shared_ptr 
            <const boost::basic_regex <StringType::value_type> >, _Second> > & _P_Deque)
    {
        ///////////////////////////////////////////////////////////
        /// typedef for const iterator
        ///////////////////////////////////////////////////////////
        typedef std::deque <std::pair <boost::shared_ptr <const boost::basic_regex
            <StringType::value_type> >, _Second> >::const_iterator ConstIterator;

        ///////////////////////////////////////////////////////////
        /// typedef for exception type
        ///////////////////////////////////////////////////////////
        typedef _Exception ExceptionType;
        //-------------------------------------------------------------------------------
        const ConstIterator _L_Result = std::find_if (_P_Deque.begin (), 
            _P_Deque.end (), RegexPredicante <VariableType> (_P_String));

        if (_L_Result == _P_Deque.end ())
        {
            ThrowException <ExceptionType> (_P_String);
            //---------------------------------------------------------------------------
        }
        //-------------------------------------------------------------------------------
        return _L_Result->second;
    }

, в качестве контейнера deque пар;

Может кто решал подобные проблемы и поделиться своими соображениями по этому поводу?

Заранее благодарен за ответы.

Здравствуйте, np9mi7, Вы писали:

N>Добрый день!

N>Имеется строка std::basic_string <char_type>. Имеется контейнер (пока не понятно какой) содержащий boost::basic_regex <char_type> (ключ) и некоторый тип (значение);

N>Необходимо осуществить в контейнере следующий поиск: ищется первый подходящий для строки boost::basic_regex <char_type> возвращается соотв. значение;

N>При выполнении программы этот поиск будет осуществляться достаточно часто, поэтому хочеться его как можно сильнее ускорить, то есть отказаться от линейности;

N>Возникает наивный вопрос: Как это сделать?

Бинарный поиск возможен, когда контейнер отсортирован по некоторому критерию. Отсортировать произвольный набор регулярных выражений так, чтобы для каждой входной строки все подходящие выражения лежали строго после всех неподходящий выражений, невозможно (доказательство предоставляется читателю в качестве упражнения).

Как я понимаю, нужен некий распознаватель, который бы умел разбирать несколько разных конструкций, причём делал это максимально эффективно и сообщал, что же именно распозналось. Для классических регулярных выражений (которые поддерживают только |, *, +, скобки и конкатенацию, без backreference’ов) задача решается построением для каждого выражения эквивалентного ему конечного автомата, а потом совмещением этих конечных автоматов в одном. Естественно, boost::regex тут ни при чём, надо руками делать