Boost это просто. Часть 1. Boost.Regex

    Эта статья является первой в цикле статей, которые я собираюсь посвятить, наверное лучшей, библиотеке для С++.
    В данной статье рассматриваются следующие вопросы касательно регулярных выражений:
    • regex_match
    • regex_search
    • regex_replace
    • regex_iterator
    • regex_token_iterator
    • Partial match


    Введение


    Я не хочу вступать в полемику по поводу нужности или не нужности регулярных выражений, каждый для себя решает сам. Моей целью было донести простоту использования Boost.Regex для тех, кому нравится использовать регулярные выражения. Для тех кому регулярные выражения не знакомы я советую прочесть хотя бы Википедию, а если кто-то хочет поглубже с ними познакомится, то я бы посоветовал Mastering regular expressions.
    Boost.Regex является собираемой библиотекой, т.е для ее использования необходимо ее собрать. Как это сделать написано в Getting started.
    Собирая библиотек вы можете выбрать один из двух алгоритмов, которые будет использоваться в движке регулирных выражений: рекурсивный и не-рекурсивный. Первый быстрый, но может грозить переполнением стека, второй немного медленней, но безопасный. Макросы для определения разных способов BOOST_REGEX_RECURSIVE и BOOST_REGEX_NON_RECURSIVE соответственно. Так же, каждый алгоритм может быть немного настроен. Макросы для настройки и их описание можно посмотреть Здесь
    Boost.Regex поддерживает следующие типы синтаксисов для регулярных выражений:
    1. Perl(по умолчанию)
    2. POSIX Extended
    3. POSIX Basic

    Необходимо учесть, что '.'(точка) по умолчанию включает в себя '\n'. Это может быть изменено передачей специального флага, в соответствующий алгоритм.

    Основные алгоритмы


    boost::regex_match


    Данный алгоритм используется для проверки соответсвия входящей строки и некоторого регулярного выражения, возвращая true Если строка соответсвует и false в другом случае.
    Типичный способ использования: regex_match(входящая_строка, [результаты_нахождения_соответствий], регулярное_выражение, [флаги]).
    Полный список всех перегруженных объявлений смотри в документации.
    Пример его использования:
    std::string xStr("AAAA-12222-BBBBB-44455");
    boost::regex xRegEx("(\\w+)-(\\d+)-(\\w+)-(\\d+)");
    boost::smatch xResults;
    std::cout << "==========================Results============================== \n";
    std::cout << "Does this line match our needs? " << std::boolalpha << boost::regex_match(xStr,  xResults, xRegEx) << "\n";
    std::cout << "Print entire match:\n " << xResults[0] << std::endl;
    std::cout << "Print the former string into another format:\n" << xResults[1] << "+"
                                    << xResults[2] << "+"
                                    << xResults[3] << "+"
                                    << xResults[4] << std::endl;


    * This source code was highlighted with Source Code Highlighter.

    Результатом работы будет:
    ==========================Results==============================
    Does this line match our needs? true
    Print entire match:
    AAAA-12222-BBBBB-44455
    Print the former string into another format:
    AAAA+12222+BBBBB+44455

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


    результаты_нахождения_соответствий — является опциональным параметром и есть ни что иное, как объект класса match_results. Этот объект является массивом объектов класса sub_match, который в свою очередь, не более чем объект-хранитель итераторов на начало и конец найденного соответсвия в строке. результаты_нахождения_соответствий служит для сохранения результатов работы алгоритма. Так, если алгоритм был выполнен успешно, то нулевой член массива будет хранить sub_match для всего найденного соответствия(исключение состовляет использование partial match, но об этом позже). Каждый последующий член массива будет хранить итераторы на каждый capture содержащийся в регулярном выражении. Каждый элемент массива может быть проверен на наличие контента через флаг matched. Важно помнить, что каждый sub_match хранит итераторы на входящую_строку, поэтому нельзя передавать в качестве исходной строки временный объект и в дальнейшем использовать результаты алгоритма, в лучшем случае получите assert в дебаге, в худшем undefined behavior с головной болью. При рекурсивном capture в регулярном выражении(например "(\w)+")) в результирующий match_result попадет только последний capture, это поведение по умолчание, которое можно изменить. Чтобы мы могли получить доступ ко всем рекурсивным capture, мы должны передать флаг match_extra в [флаги], но это еще не все, для того, чтобы match_extra сработал, необходим объявить дефайн BOOST_REGEX_MATCH_EXTRA во всех транслируемых юнитах. Или просто раскомментировать define в boost/regex/user.hpp. Это функциональность помечена как эксперементальная и сильно уменьшающая производительность. У меня так и не получилось ее опробовать, т.к моя VS2008 выдает Access violation в недрах xutulity при попытке использования алгоритмов regex_* с раскомментированным дефайном. Не протестированный пример ее использования:
    std::string xStr("The boost library has a great opportunity for the regex!");
    boost::regex xRegEx("(\\b\\w{5}\\b)*");
    boost::smatch xResults;
    std::cout << "==========================Results============================== \n";  
    if( boost::regex_search(xStr, xResults, xRegEx, boost::match_extra) )
    {
      std::cout << "Words consist from exact 5 digits have been found in our line:\n";
      for(int j = 0; j < xResults.captures(1).size(); ++j)
         std::cout << xResults.captures(1)[j] << std::endl;
    }


    * This source code was highlighted with Source Code Highlighter.

    [Флаги] — необязательный параметр, с дефолтовым значением match_default. Про доступные флаги, можно посмотреть здесь. Флаги комбинируются посредством '|'(or).

    Partial match


    Частичное соответсвие необходимо для проверки входной строки, на частичное соответсвие регулярному выражению. Это может быть полезным при валидации поступающих асинхронно данных или при больших объемах данных, т.е в тех случаях когда в конкретный момент времени нет возможности провести полное соответсвие между регулярным выражением и исходной строкой. Чтобы использовать partial match, необходимо передать флаг match_partial в [флаги]. При этом, если используется частичное соответствие, то используемый алгоритм(regex_match, regex_search etc.) вернет true, но флаг matched у нулевого элеменат match_results будет уставновлен в false. То, что было найдено в результате частичного соответствия, можно получить через этот же нулевой элемент.
    Пример использования:
    std::string xStr("AAAA-12222");
    boost::regex xRegEx("(\\w+)-(\\d+)-(\\w+)-(\\d+)");
    boost::smatch xResults;
    std::cout << "==========================Results============================== \n";
    std::cout << "Does this line match the regex? " << std::boolalpha << boost::regex_match(xStr, xResults, xRegEx,
                     boost::match_default | boost::match_partial) << "\n";
    std::cout << "Is it the partial match? " << std::boolalpha <<  !xResults[0].matched << "\nPrint the partial match:\n" << xResults[0] << std::endl;


    * This source code was highlighted with Source Code Highlighter.

    Вывод:
    ==========================Results==============================
    Does this line match the regex? true
    Is it the partial match? true
    Print the partial match:
    AAAA-12222

    regex_search


    Данный алгоритм предназначен для поиска подстроки в исходной строке, по заданному регулярному выражению.
    Формат использования выглядит следующим образом:
    regex_search(входящая_строка, [результаты_нахождения_соответствий], регулярное_выражение, [флаги]).
    Пример использования:
    std::string xStr("The boost library has a great opportunity for the regex!");
    boost::regex xRegEx("\\b(?:\\w+?)((\\w)\\2)(?:\\w+?)\\b");
    boost::smatch xResults;
    std::cout << "==========================Results============================== \n";
    std::string::const_iterator xItStart = xStr.begin();
    std::string::const_iterator xItEnd = xStr.end();
    while( boost::regex_search(xItStart, xItEnd, xResults, xRegEx) )
    {
      std::cout << "Word, we've searched, is \"" << xResults[0] << "\". It has two \"" << xResults[2] << "\" inside itself.\n";
      xItStart = xResults[1].second;
    }


    * This source code was highlighted with Source Code Highlighter.

    Вывод:
    ==========================Results==============================
    Word, we've searched, is «boost». It has two «o» inside itself.
    Word, we've searched, is «opportunity». It has two «p» inside itself.


    regex_replace


    Алгоритм используется для замены всех вхождений подстрок, соответсвующих регулярному выражению, на строку заданному в определенном формате. Результат может быть получен через итератор, переданный в качестве аргумента либо как возращаемая строка. Части сроки которые не соответствуют регулярному выражению, копируются в выходнуб строку не измененными, если не задан флаг format_no_copy, который оставляет только заматченные строки в результате. При переданном флаге format_first_only, заменяется только первая подстрока, соответствующая регулярному выражению.
    Типично используемый формат:
    regex_replace(входящая_строка, регулярное_выражение, форматная_строка, [флаги]).
    форматная_строка определяет строку, на которую будет заменятся найденная подстрока.
    Она может подчинятся одному из следующих правил синтаксиса:
    • sed флаг:format_sed
    • Perl(по умолчанию) флаг:format_perl
    • Boost-extended флаг:format_all
    • Литеральный, т.е не использует никаких специальных символов. Флаг:format_literal

    Пример использования:
    std::string xStr("AAAA-12222-BBBBB-44455");
    boost::regex xRegEx("(\\w+)-(\\d+)-(\\w+)-(\\d+)");
    std::string xFormatString("$1*$2*$3*$4");
    boost::smatch xResults;
    std::cout << "==========================Results============================== \n";
    std::cout << "Print string after replace:\n " << boost::regex_replace(xStr, xRegEx, xFormatString, boost::match_default | boost::format_perl) << std::endl;
      


    * This source code was highlighted with Source Code Highlighter.

    Вывод:
    ==========================Results==============================
    Print string after replace:
    AAAA*12222*BBBBB*44455


    Вспомогательные средства


    regex_iterator


    Данный итератор может быть удобен для последовательного поиска вхождений подстроки, соответствующей регулярному выражению. При каждом инкрементировании находится следующая подстрока, с помощью regex_search. При разыменовывании итератора мы получаем объект типа match_results, с помощью которого мы можем получить всю необходимую информацию.
    Формат использования: regex_iterator(начальный_итератор, конечный _итератор, регулярное_выражение)
    Пример использования:
    std::string xStr("AAAA-12222-BBBBB-44455");
    boost::regex xRegEx("(\\w|\\d)+");
    boost::smatch xResults;
    std::cout << "==========================Results============================== \n";
    boost::sregex_iterator xIt(xStr.begin(), xStr.end(), xRegEx);
    boost::sregex_iterator xInvalidIt;
    while(xIt != xInvalidIt)
      std::cout << *xIt++ << "*";


    * This source code was highlighted with Source Code Highlighter.

    Вывод:
    ==========================Results==============================
    AAAA*12222*BBBBB*44455*


    regex_token_iterator


    Очень полезный интрумент для разбиаения строки на токены,
    Формат использования: regex_token_iterator(начальный_итератор, конечный _итератор, регулярное_выражение, [submatch])
    [submatch] используется для указания, как следует интерпретировать токены в строке.
    При -1 итератор возвращает часть последовательности, которая не соответствует регулярному выражению. Т.е возвращается либо строка, которая идет после первого совпадения, до начала следующего совпадения(не включая первый символ совпадения). Либо, с начала строки, если начала строки не удовлетворяет регулярному выражению. Т.е при передаче -1, регулярное выражения является разделителем. При 0, каждое смещение итератора(++) дает следующую часть строки которая была “заматчена“, т.е каждый разыменованный итератор является capture строки. При любом положительном числе, в качестве параметра, выбирается capture регулярного выражения соответствующий числу, переданному в качестве параметра. Так же можно передать массив индексов в качестве параметра, тогда итератор будет искать каждый capture согласно индексам в массиве, т.е если массив состоит из {4, 2, 1}, тогда начальный итератор будет указывать на 4 capture, следующий итератор на 2 и т.д. Процесс будет повторятся для всей последовательности, пока не закончатся соответствия для данного регулярного выражения. По дефолту это параметр равен 0.
    Разыменованный итератор является объектом класса sub_match.
    Примеры использования:
    std::string xStr("AAAA-12222-BBBBB-44455");
    boost::regex xRegEx("(\\w|\\d)+");
    boost::smatch xResults;
    std::cout << "==========================Results============================== \n";
    boost::sregex_token_iterator xItFull(xStr.begin(), xStr.end(), xRegEx, 0);
    boost::sregex_token_iterator xInvalidIt;
    std::cout << "Result the same as the regex_iterator: \n";
    while(xItFull != xInvalidIt)
      std::cout << *xItFull++ << "*";
    //Parts of captures
    boost::regex xRegEx2("(\\w+)-(\\d+)");
    boost::sregex_token_iterator xItFirstCapture(xStr.begin(), xStr.end(), xRegEx2, 1);
    std::cout << "\nShow only first captures: \n";
    while(xItFirstCapture != xInvalidIt)
      std::cout << *xItFirstCapture++ << "*";
    //Reverse order
    int aIndices[] = {2,1};
    boost::sregex_token_iterator xItReverseCapture(xStr.begin(), xStr.end(), xRegEx2, aIndices);
    std::cout << "\nShow captures in the reverse order: \n";
      while(xItReverseCapture != xInvalidIt)
    std::cout << *xItReverseCapture++ << "*";
    //Delimiters
    boost::regex xRegEx3("(\\w|\\d)+");
    boost::sregex_token_iterator xItDelimiters(xStr.begin(), xStr.end(), xRegEx3, -1);
    std::cout << "\nShow delimiters: \n";
    while(xItDelimiters != xInvalidIt)
      std::cout << *xItDelimiters++ << " ";


    * This source code was highlighted with Source Code Highlighter.

    Вывод:
    ==========================Results==============================
    Result the same as the regex_iterator:
    AAAA*12222*BBBBB*44455*
    Show only first captures:
    AAAA*BBBBB*
    Show captures in the reverse order:
    12222*AAAA*44455*BBBBB*
    Show delimiters:
    — — -

    Замечание


    Любой алгоритм может выбросить исключение типа std::runtime_error в случае если сложность проверки полного соответствия(matching) N элементов начнет превышать О(N^2) или в случае переполнения стека(если Boost.Regex был собран в рекурсивном режиме)

    Поделиться публикацией
    Комментарии 38
      +3
      класс и материал отличный и изложение и оформление не подкачало.
      эталонная статья на хабре, все бы такие были

      жду продолжений
        –2
        IMHO, гораздо интереснее было бы прочитать о том, как: благодаря boost мы повысили нашу эффективность на 500%, или решение задачи коммивояжера на boost генетическим алгоритмом, или boost и управление Большим Адронным Коллайдером, или распознавание номеров автомобилей на фотографиях с реализацией на C++/boost, или символьные вычисления в boost. Что-то в таком роде, хоть с каким-нибудь интересным примером. Tutorial'ы же все умеют читать.
          +1
          напишите, подайте пример
            +1
            Уже писал несколько раз. Boost же мне не интересен. И потом, я же просто выражаю своё мнение о том, как подобные введения в библиотеки делать интереснее. Перечисление набора функций совсем ничего не даёт — их описания и без того доступны. Гораздо интереснее увидеть то, чего эти функции позволяют в итоге достичь. Хотя бы сравнили с pcre в скорости работы и в удобстве использования.
              0
              I second this! Я не понимаю зачем нужны такие маны — гораздо удобнее и полезнее прочитать официальную доку буста и посмотреть пару семплов. Алсо, Boost.Regex — отстой, ибо нет named groups.
                0
                Приятнее и быстрее прочитать что-то на русском (это если с английским не очень)
                  +4
                  Я вообще ничего на русском не читаю. Я больше доверяю себе, а не каким-то переводчикам. Вот наглядный пример: s43.radikal.ru/i102/0902/68/72ba5d34369a.jpg
                    0
                    Ну это не пример))) хотя улыбнуло )
                    Автор статьи по-моему грамотно написал.
                    0
                    Я бы согласился, если бы не имело место такое большое число опечаток в статье. Лично мне приятнее читать чистый «чужой» язык, чем неаккуратный родной.

                    В любом случае, автору — спасибо.
            0
            Статья хорошая, спасибо.

            Еще, правда, интересует сравнительная характеристика Boost.Regex и QRegExp из Qt: что в каких случаях предпочтительнее и почему.
              +1
              По скорости я их не сравнивал, но по возможностям регулярки из Qt уступают бустовским. В QRegExp некоторое не реализовано, например lookaround, что не дает полноценно использовать регулярки. Лично я использую boost::regex вместе с Qt. Кстати в сети есть адптер boost::regex под Qt, подстроенный под кутешные типы.
              0
              Спасибо, что пишите такие статьи, давно хотел посмотреть регэксп в бусте, да как-то руки не доходили. Теперь как-нибудь на досуге, начну с вашего поста.
              • НЛО прилетело и опубликовало эту надпись здесь
                  0
                  Судя по блогу VS team, intellisense они должны значительно улучшить для vs2010. А пока, можно использовать vissual assist, правда он платный, и может быть установлен только на платную версию VS :(
                  0
                  исправьте «результаты_нахождения_соответсТвий»
                    0
                    спасибо, поправил.
                    0
                    Спасибо! Освоил регулярные выражения вместе с перлом, теперь орабатывать строки в C++ будет проще.
                      +2
                      Статься не плохая, но я бы убрал заголовок «Boost это просто». Это не просто. Для того, чтобы использовать boost надо понимать хотя бы как он устроен и что делать, когда у вас ошибка и это не опечатка. Для того, чтобы это хотя бы понимать, надо прилично владеть шаблонами и tmp.

                      Поэтому все же для новичков, это обманчивая простота, имхо.
                        0
                        Статья*
                          +1
                          Я бы не был столь категоричен, для использования того же regex, можно и не владеть шаблонами вообще. Т.к все шаблонизированные классы заtypdefчены в алиасы, которые потом и используются. Если вы посмотрите на код в моих примерах, то можете увидеть, что там нет явных шаблонов.
                          К тому же, я не считаю основы С++ чем-то сложным, все таки если человек хочет продвинуто использовать язык, он должен в нем ориентироваться. А как устроен буст и его исходники знать не обязательно, более того, меня часто в пот бросает от исходников буста :) Но это не мешает мне его использовать. Я, собственно, и запланировал пистать статьи в подобном ключе, чтобы новичек в бусте не терялся, а мог максимально быстро получить требуемую ему информацию.
                          К тому же, «Буст это просто» располагает человека, к простоте на подсознательном уровне, стирая барьеры ужаса перед бустом(да да и такое бывает, я видел несколько людей находящимся в священном трепете перед бустом :) )
                            0
                            Я не категоричен. Я как раз тоже отношу себя к новичкам. И мне boost очень нравится, но в проде я бы не рискнул его использовать, так как случись что, я просто не смогу разобраться оперативно в ошибке, потому что даже понять портянку на несколько экранов не просто.
                              0
                              Не бойтесь его использовать, поначалу может и будет туго, потом приучитесь.
                              По поводу чтения «простыней» ошибок, советую прочитать 49 совет из вот этой книжки, да и сама книжка будет полезна, не только новичку.
                                0
                                Эх, я кстати, давно ищу что-нибудь стоящее по STL. Этой книги в России вообще не видел в продаже :-(
                                  0
                                  В продаже не найдешь. Саттера недавно переиздали, а Майерса нет, как и многих других отличных авторов. Но можно скачать в сети, они есть в неплохом качестве. Хотя я бы посоветовал читать на английском сразу, в будущем все равно придется.
                                0
                                Чтобы легче было разгребать портянки на несколько экранов можно использовать STLFilt.
                            0
                            отличная статья, жаль, что для меня уже не актуальная :)
                            Сам во всём разбирался. Кстати, автор, match_extra у меня в RAD Studio 2009 работал как надо.

                            еще не совсем понял почему regex_match пытается поставить в соответствие всю строку регулярному выражению.
                            А если мне нужно из текста выдрать несколько одинаковых конструкций, ну к примеру внутри формы вытащить все инпуты, то приходится извращаться вот так:

                            boost::regex xRegEx(".*(<input[^>]*>)+.*");
                            т.е. «лишние» по сравнению с php конструкции вида ".*(<выражение>)+.*"

                            Это и очень отжирает память, ведь в результаты идет вся строка.

                            Да, дополнительно еще раз отмечу, что в результатах помещаются указатели на исходную строку, и пока не разберешь результаты поиска, ничего с искомой строкой делать нельзя :) Сам на это попадался, прога вылетала с Access Violation в произвольном месте, еле откопал причину.
                              +1
                              >еще не совсем понял почему regex_match пытается поставить в соответствие всю строку регулярному >выражению.
                              >А если мне нужно из текста выдрать несколько одинаковых конструкций, ну к примеру внутри формы >вытащить все инпуты, то приходится извращаться вот так
                              Для этого лучше использовать regex_search в цикле, или вспомогательные стредства типа regex_iterator и regex_token_iterator. regex_match служит для валидации строки.
                                0
                                А вот как раз с regex_iterator'ами я и не разобрался :)

                                Блин, и почему нельзя было сделать Regex_search с флагом match_all?
                                  0
                                  ну как минимум чтобы соответствовать С++0x. Нет смысла перегружать функции лишними возможностями, которые могут быть реализоваными через простой цикл. Всем не угодишь :)
                              0
                              Можете подсказать хорошее сравнение RegExp-библиотек для C++?
                              Почему Вы выбрали именно Boost? Я пока в поисках, но Boost меня сильно испугал тем, что пришлось качать и устанавливать несколько сотен мегабайт, когда я хотел простую компактную RegExp-библиотеку.
                                0
                                Посмотрите
                                Я выбрал boost, потомучто это лучшее, что было создано для C++, за все его время существования, конкретно boost::regex я выбрал, потомучто меня не устроил функционал предоставляемый Qt::RegExp.
                                А размера буста боятся не стоит, он во многих вещах спасает + любой уважающий себя С++ программист, должен стараться освоить буст, я считаю. Поверьте, Вы получите большое преимущество, научившись использовтиаь буст.
                                0
                                В boost есть утилита bcp которая позволяет вытаскивать только конкретные библиотеки.

                                Также boost, насколько я понимаю, в некоторых местах будет частью нового стандарта. Если не прав, знатоки пусть подправят. Например, в моей системе уже есть tr1/memory/shared_ptr из boost.

                                Так что игнорировать его неправильно, наверное.
                                  0
                                  правильно, многое, из того что появляется в бусте входит в дальнейшем в стандарт.
                                  Вот здесь, описаны фичи из tr1 которые реализованы в бусте.
                                  +1
                                  Справедливости ради нужно заметить, что качать нужно всего 27 МБ. Компилировать всё тоже совершенно не обязательно — достаточно скомпилировать только нужную библиотеку, а часть библиотек так вообще полностью в заголовочных файлах и линковать ничего не нужно. Если вы пишете под Windows всё ещё немножечко проще — под Windows работает Auto-Linking и вам не нужно указывать какую библиотеку линковать в какой конфигурации — нужно просто указать где собранные библиотеки лежат.
                                    0
                                    Я как раз ожидал, что меня поправят и скажут, что это я просто неправильно её использовал.
                                    Я подозревал, что сотни метров ради одних регекспов — это что-то не то.
                                    Спасибо
                                  0
                                  Покажите, пожалуйста, использование regex (boost::match_results, boost::regex_match и т.п.) на примере работы с wchar_t строками (std::wstring)

                                  P.S.
                                  Прежде чем отписываться кэповскими советами, для начала попробуйте сами поменять std::string на std::wstring и собрать примеры.

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

                                  Самое читаемое