include/regex

// -*- C++ -*-
//===--------------------------- regex ------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP_REGEX
#define _LIBCPP_REGEX

/*
    regex synopsis

#include <initializer_list>

namespace std
{

namespace regex_constants
{

emum syntax_option_type
{
    icase      = unspecified,
    nosubs     = unspecified,
    optimize   = unspecified,
    collate    = unspecified,
    ECMAScript = unspecified,
    basic      = unspecified,
    extended   = unspecified,
    awk        = unspecified,
    grep       = unspecified,
    egrep      = unspecified
};

constexpr syntax_option_type operator~(syntax_option_type f);
constexpr syntax_option_type operator&(syntax_option_type lhs, syntax_option_type rhs);
constexpr syntax_option_type operator|(syntax_option_type lhs, syntax_option_type rhs);

enum match_flag_type
{
    match_default     = 0,
    match_not_bol     = unspecified,
    match_not_eol     = unspecified,
    match_not_bow     = unspecified,
    match_not_eow     = unspecified,
    match_any         = unspecified,
    match_not_null    = unspecified,
    match_continuous  = unspecified,
    match_prev_avail  = unspecified,
    format_default    = 0,
    format_sed        = unspecified,
    format_no_copy    = unspecified,
    format_first_only = unspecified
};

constexpr match_flag_type operator~(match_flag_type f);
constexpr match_flag_type operator&(match_flag_type lhs, match_flag_type rhs);
constexpr match_flag_type operator|(match_flag_type lhs, match_flag_type rhs);

enum error_type
{
    error_collate    = unspecified,
    error_ctype      = unspecified,
    error_escape     = unspecified,
    error_backref    = unspecified,
    error_brack      = unspecified,
    error_paren      = unspecified,
    error_brace      = unspecified,
    error_badbrace   = unspecified,
    error_range      = unspecified,
    error_space      = unspecified,
    error_badrepeat  = unspecified,
    error_complexity = unspecified,
    error_stack      = unspecified
};

}  // regex_constants

class regex_error
    : public runtime_error
{
public:
    explicit regex_error(regex_constants::error_type ecode);
    regex_constants::error_type code() const;
};

template <class charT>
struct regex_traits
{
public:
    typedef charT                   char_type;
    typedef basic_string<char_type> string_type;
    typedef locale                  locale_type;
    typedef /bitmask_type/          char_class_type;

    regex_traits();

    static size_t length(const char_type* p);
    charT translate(charT c) const;
    charT translate_nocase(charT c) const;
    template <class ForwardIterator>
        string_type
        transform(ForwardIterator first, ForwardIterator last) const;
    template <class ForwardIterator>
        string_type
        transform_primary( ForwardIterator first, ForwardIterator last) const;
    template <class ForwardIterator>
        string_type
        lookup_collatename(ForwardIterator first, ForwardIterator last) const;
    template <class ForwardIterator>
        char_class_type
        lookup_classname(ForwardIterator first, ForwardIterator last,
                         bool icase = false) const;
    bool isctype(charT c, char_class_type f) const;
    int value(charT ch, int radix) const;
    locale_type imbue(locale_type l);
    locale_type getloc()const;
};

template <class charT, class traits = regex_traits<charT>>
class basic_regex
{
public:
    // types:
    typedef charT                               value_type;
    typedef regex_constants::syntax_option_type flag_type;
    typedef typename traits::locale_type        locale_type;

    // constants:
    static constexpr regex_constants::syntax_option_type icase = regex_constants::icase;
    static constexpr regex_constants::syntax_option_type nosubs = regex_constants::nosubs;
    static constexpr regex_constants::syntax_option_type optimize = regex_constants::optimize;
    static constexpr regex_constants::syntax_option_type collate = regex_constants::collate;
    static constexpr regex_constants::syntax_option_type ECMAScript = regex_constants::ECMAScript;
    static constexpr regex_constants::syntax_option_type basic = regex_constants::basic;
    static constexpr regex_constants::syntax_option_type extended = regex_constants::extended;
    static constexpr regex_constants::syntax_option_type awk = regex_constants::awk;
    static constexpr regex_constants::syntax_option_type grep = regex_constants::grep;
    static constexpr regex_constants::syntax_option_type egrep = regex_constants::egrep;

    // construct/copy/destroy:
    basic_regex();
    explicit basic_regex(const charT* p, flag_type f = regex_constants::ECMAScript);
    basic_regex(const charT* p, size_t len, flag_type f);
    basic_regex(const basic_regex&);
    basic_regex(basic_regex&&);
    template <class ST, class SA>
        explicit basic_regex(const basic_string<charT, ST, SA>& p,
                             flag_type f = regex_constants::ECMAScript);
    template <class ForwardIterator>
        basic_regex(ForwardIterator first, ForwardIterator last,
                    flag_type f = regex_constants::ECMAScript);
    basic_regex(initializer_list<charT>, flag_type = regex_constants::ECMAScript);

    ~basic_regex();

    basic_regex& operator=(const basic_regex&);
    basic_regex& operator=(basic_regex&&);
    basic_regex& operator=(const charT* ptr);
    basic_regex& operator=(initializer_list<charT> il);
    template <class ST, class SA>
        basic_regex& operator=(const basic_string<charT, ST, SA>& p);

    // assign:
    basic_regex& assign(const basic_regex& that);
    basic_regex& assign(basic_regex&& that);
    basic_regex& assign(const charT* ptr, flag_type f = regex_constants::ECMAScript);
    basic_regex& assign(const charT* p, size_t len, flag_type f);
    template <class string_traits, class A>
        basic_regex& assign(const basic_string<charT, string_traits, A>& s,
                            flag_type f = regex_constants::ECMAScript);
    template <class InputIterator>
        basic_regex& assign(InputIterator first, InputIterator last,
                            flag_type f = regex_constants::ECMAScript);
    basic_regex& assign(initializer_list<charT>, flag_type = regex_constants::ECMAScript);

    // const operations:
    unsigned mark_count() const;
    flag_type flags() const;

    // locale:
    locale_type imbue(locale_type loc);
    locale_type getloc() const;

    // swap:
    void swap(basic_regex&);
};

typedef basic_regex<char>    regex;
typedef basic_regex<wchar_t> wregex;

template <class charT, class traits>
    void swap(basic_regex<charT, traits>& e1, basic_regex<charT, traits>& e2);

template <class BidirectionalIterator>
class sub_match
    : public pair<BidirectionalIterator, BidirectionalIterator>
{
public:
    typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;
    typedef typename iterator_traits<BidirectionalIterator>::difference_type difference_type;
    typedef BidirectionalIterator                                      iterator;
    typedef basic_string<value_type>                                string_type;

    bool matched;

    difference_type length() const;
    operator string_type() const;
    string_type str() const;

    int compare(const sub_match& s) const;
    int compare(const string_type& s) const;
    int compare(const value_type* s) const;
};

typedef sub_match<const char*>             csub_match;
typedef sub_match<const wchar_t*>          wcsub_match;
typedef sub_match<string::const_iterator>  ssub_match;
typedef sub_match<wstring::const_iterator> wssub_match;

template <class BiIter>
    bool
    operator==(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator!=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator<(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator<=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator>=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator>(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>
    bool
    operator==(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>
    bool
    operator!=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>
    bool
    operator<(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
              const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>
    bool
    operator>(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
              const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>
    bool operator>=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
                    const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>
    bool
    operator<=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>
    bool
    operator==(const sub_match<BiIter>& lhs,
               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);

template <class BiIter, class ST, class SA>
    bool
    operator!=(const sub_match<BiIter>& lhs,
               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);

template <class BiIter, class ST, class SA>
    bool
    operator<(const sub_match<BiIter>& lhs,
              const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);

template <class BiIter, class ST, class SA>
    bool operator>(const sub_match<BiIter>& lhs,
                   const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);

template <class BiIter, class ST, class SA>
    bool
    operator>=(const sub_match<BiIter>& lhs,
               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);

template <class BiIter, class ST, class SA>
    bool
    operator<=(const sub_match<BiIter>& lhs,
               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);

template <class BiIter>
    bool
    operator==(typename iterator_traits<BiIter>::value_type const* lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator!=(typename iterator_traits<BiIter>::value_type const* lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator<(typename iterator_traits<BiIter>::value_type const* lhs,
              const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator>(typename iterator_traits<BiIter>::value_type const* lhs,
              const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator>=(typename iterator_traits<BiIter>::value_type const* lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator<=(typename iterator_traits<BiIter>::value_type const* lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator==(const sub_match<BiIter>& lhs,
               typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>
    bool
    operator!=(const sub_match<BiIter>& lhs,
               typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>
    bool
    operator<(const sub_match<BiIter>& lhs,
              typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>
    bool
    operator>(const sub_match<BiIter>& lhs,
              typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>
    bool
    operator>=(const sub_match<BiIter>& lhs,
               typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>
    bool
    operator<=(const sub_match<BiIter>& lhs,
               typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>
    bool
    operator==(typename iterator_traits<BiIter>::value_type const& lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator!=(typename iterator_traits<BiIter>::value_type const& lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator<(typename iterator_traits<BiIter>::value_type const& lhs,
              const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator>(typename iterator_traits<BiIter>::value_type const& lhs,
              const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator>=(typename iterator_traits<BiIter>::value_type const& lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator<=(typename iterator_traits<BiIter>::value_type const& lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter>
    bool
    operator==(const sub_match<BiIter>& lhs,
               typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>
    bool
    operator!=(const sub_match<BiIter>& lhs,
               typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>
    bool
    operator<(const sub_match<BiIter>& lhs,
              typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>
    bool
    operator>(const sub_match<BiIter>& lhs,
              typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>
    bool
    operator>=(const sub_match<BiIter>& lhs,
               typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>
    bool
    operator<=(const sub_match<BiIter>& lhs,
               typename iterator_traits<BiIter>::value_type const& rhs);

template <class charT, class ST, class BiIter>
    basic_ostream<charT, ST>&
    operator<<(basic_ostream<charT, ST>& os, const sub_match<BiIter>& m);

template <class BidirectionalIterator,
          class Allocator = allocator<sub_match<BidirectionalIterator>>>
class match_results
{
public:
    typedef sub_match<BidirectionalIterator>                  value_type;
    typedef const value_type&                                 const_reference;
    typedef const_reference                                   reference;
    typedef /implementation-defined/                          const_iterator;
    typedef const_iterator                                    iterator;
    typedef typename iterator_traits<BidirectionalIterator>::difference_type difference_type;
    typedef typename allocator_traits<Allocator>::size_type   size_type;
    typedef Allocator                                         allocator_type;
    typedef typename iterator_traits<BidirectionalIterator>::value_type char_type;
    typedef basic_string<char_type>                           string_type;

    // construct/copy/destroy:
    explicit match_results(const Allocator& a = Allocator());
    match_results(const match_results& m);
    match_results(match_results&& m);
    match_results& operator=(const match_results& m);
    match_results& operator=(match_results&& m);
    ~match_results();

    // size:
    size_type size() const;
    size_type max_size() const;
    bool empty() const;

    // element access:
    difference_type length(size_type sub = 0) const;
    difference_type position(size_type sub = 0) const;
    string_type str(size_type sub = 0) const;
    const_reference operator[](size_type n) const;

    const_reference prefix() const;
    const_reference suffix() const;

    const_iterator begin() const;
    const_iterator end() const;
    const_iterator cbegin() const;
    const_iterator cend() const;

    // format:
    template <class OutputIter>
        OutputIter
        format(OutputIter out, const char_type* fmt_first,
               const char_type* fmt_last,
               regex_constants::match_flag_type flags = regex_constants::format_default) const;
    template <class OutputIter, class ST, class SA>
        OutputIter
        format(OutputIter out, const basic_string<char_type, ST, SA>& fmt,
               regex_constants::match_flag_type flags = regex_constants::format_default) const;
    template <class ST, class SA>
        basic_string<char_type, ST, SA>
        format(const basic_string<char_type, ST, SA>& fmt,
               regex_constants::match_flag_type flags = regex_constants::format_default) const;
    string_type
        format(const char_type* fmt,
               regex_constants::match_flag_type flags = regex_constants::format_default) const;

    // allocator:
    allocator_type get_allocator() const;

    // swap:
    void swap(match_results& that);
};

typedef match_results<const char*>             cmatch;
typedef match_results<const wchar_t*>          wcmatch;
typedef match_results<string::const_iterator>  smatch;
typedef match_results<wstring::const_iterator> wsmatch;

template <class BidirectionalIterator, class Allocator>
    bool
    operator==(const match_results<BidirectionalIterator, Allocator>& m1,
               const match_results<BidirectionalIterator, Allocator>& m2);

template <class BidirectionalIterator, class Allocator>
    bool
    operator!=(const match_results<BidirectionalIterator, Allocator>& m1,
               const match_results<BidirectionalIterator, Allocator>& m2);

template <class BidirectionalIterator, class Allocator>
    void
    swap(match_results<BidirectionalIterator, Allocator>& m1,
         match_results<BidirectionalIterator, Allocator>& m2);

template <class BidirectionalIterator, class Allocator, class charT, class traits>
    bool
    regex_match(BidirectionalIterator first, BidirectionalIterator last,
                match_results<BidirectionalIterator, Allocator>& m,
                const basic_regex<charT, traits>& e,
                regex_constants::match_flag_type flags = regex_constants::match_default);

template <class BidirectionalIterator, class charT, class traits>
    bool
    regex_match(BidirectionalIterator first, BidirectionalIterator last,
                const basic_regex<charT, traits>& e,
                regex_constants::match_flag_type flags = regex_constants::match_default);

template <class charT, class Allocator, class traits>
    bool
    regex_match(const charT* str, match_results<const charT*, Allocator>& m,
                const basic_regex<charT, traits>& e,
                regex_constants::match_flag_type flags = regex_constants::match_default);

template <class ST, class SA, class Allocator, class charT, class traits>
    bool
    regex_match(const basic_string<charT, ST, SA>& s,
                match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
                const basic_regex<charT, traits>& e,
                regex_constants::match_flag_type flags = regex_constants::match_default);

template <class charT, class traits>
    bool
    regex_match(const charT* str, const basic_regex<charT, traits>& e,
                regex_constants::match_flag_type flags = regex_constants::match_default);

template <class ST, class SA, class charT, class traits>
    bool
    regex_match(const basic_string<charT, ST, SA>& s,
                const basic_regex<charT, traits>& e,
                regex_constants::match_flag_type flags = regex_constants::match_default);

template <class BidirectionalIterator, class Allocator, class charT, class traits>
    bool
    regex_search(BidirectionalIterator first, BidirectionalIterator last,
                 match_results<BidirectionalIterator, Allocator>& m,
                 const basic_regex<charT, traits>& e,
                 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class BidirectionalIterator, class charT, class traits>
    bool
    regex_search(BidirectionalIterator first, BidirectionalIterator last,
                 const basic_regex<charT, traits>& e,
                 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class charT, class Allocator, class traits>
    bool
    regex_search(const charT* str, match_results<const charT*, Allocator>& m,
                 const basic_regex<charT, traits>& e,
                 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class charT, class traits>
    bool
    regex_search(const charT* str, const basic_regex<charT, traits>& e,
                 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class ST, class SA, class charT, class traits>
    bool
    regex_search(const basic_string<charT, ST, SA>& s,
                 const basic_regex<charT, traits>& e,
                 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class ST, class SA, class Allocator, class charT, class traits>
    bool
    regex_search(const basic_string<charT, ST, SA>& s,
                 match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
                 const basic_regex<charT, traits>& e,
                 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class OutputIterator, class BidirectionalIterator,
          class traits, class charT, class ST, class SA>
    OutputIterator
    regex_replace(OutputIterator out,
                  BidirectionalIterator first, BidirectionalIterator last,
                  const basic_regex<charT, traits>& e,
                  const basic_string<charT, ST, SA>& fmt,
                  regex_constants::match_flag_type flags = regex_constants::match_default);

template <class OutputIterator, class BidirectionalIterator,
          class traits, class charT>
    OutputIterator
    regex_replace(OutputIterator out,
                  BidirectionalIterator first, BidirectionalIterator last,
                  const basic_regex<charT, traits>& e, const charT* fmt,
                  regex_constants::match_flag_type flags = regex_constants::match_default);

template <class traits, class charT, class ST, class SA, class FST, class FSA>>
    basic_string<charT, ST, SA>
    regex_replace(const basic_string<charT, ST, SA>& s,
                  const basic_regex<charT, traits>& e,
                  const basic_string<charT, FST, FSA>& fmt,
                  regex_constants::match_flag_type flags = regex_constants::match_default);

template <class traits, class charT, class ST, class SA>
    basic_string<charT, ST, SA>
    regex_replace(const basic_string<charT, ST, SA>& s,
                  const basic_regex<charT, traits>& e, const charT* fmt,
                  regex_constants::match_flag_type flags = regex_constants::match_default);

template <class traits, class charT, class ST, class SA>
    basic_string<charT>
    regex_replace(const charT* s,
                  const basic_regex<charT, traits>& e,
                  const basic_string<charT, ST, SA>& fmt,
                  regex_constants::match_flag_type flags = regex_constants::match_default);

template <class traits, class charT>
    basic_string<charT>
    regex_replace(const charT* s,
                  const basic_regex<charT, traits>& e,
                  const charT* fmt,
                  regex_constants::match_flag_type flags = regex_constants::match_default);

template <class BidirectionalIterator,
          class charT = typename iterator_traits< BidirectionalIterator>::value_type,
          class traits = regex_traits<charT>>
class regex_iterator
{
public:
    typedef basic_regex<charT, traits>           regex_type;
    typedef match_results<BidirectionalIterator> value_type;
    typedef ptrdiff_t                            difference_type;
    typedef const value_type*                    pointer;
    typedef const value_type&                    reference;
    typedef forward_iterator_tag                 iterator_category;

    regex_iterator();
    regex_iterator(BidirectionalIterator a, BidirectionalIterator b,
                   const regex_type& re,
                   regex_constants::match_flag_type m = regex_constants::match_default);
    regex_iterator(const regex_iterator&);
    regex_iterator& operator=(const regex_iterator&);

    bool operator==(const regex_iterator&) const;
    bool operator!=(const regex_iterator&) const;

    const value_type& operator*() const;
    const value_type* operator->() const;

    regex_iterator& operator++();
    regex_iterator operator++(int);
};

typedef regex_iterator<const char*>             cregex_iterator;
typedef regex_iterator<const wchar_t*>          wcregex_iterator;
typedef regex_iterator<string::const_iterator>  sregex_iterator;
typedef regex_iterator<wstring::const_iterator> wsregex_iterator;

template <class BidirectionalIterator,
          class charT = typename iterator_traits< BidirectionalIterator>::value_type,
          class traits = regex_traits<charT>>
class regex_token_iterator
{
public:
    typedef basic_regex<charT, traits>       regex_type;
    typedef sub_match<BidirectionalIterator> value_type;
    typedef ptrdiff_t                        difference_type;
    typedef const value_type*                pointer;
    typedef const value_type&                reference;
    typedef forward_iterator_tag             iterator_category;

    regex_token_iterator();
    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
                         const regex_type& re, int submatch = 0,
                         regex_constants::match_flag_type m = regex_constants::match_default);
    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
                         const regex_type& re, const vector<int>& submatches,
                         regex_constants::match_flag_type m = regex_constants::match_default);
    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
                         const regex_type& re, initializer_list<int> submatches,
                         regex_constants::match_flag_type m = regex_constants::match_default);
    template <size_t N>
        regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
                             const regex_type& re, const int (&submatches)[N],
                             regex_constants::match_flag_type m = regex_constants::match_default);
    regex_token_iterator(const regex_token_iterator&);
    regex_token_iterator& operator=(const regex_token_iterator&);

    bool operator==(const regex_token_iterator&) const;
    bool operator!=(const regex_token_iterator&) const;

    const value_type& operator*() const;
    const value_type* operator->() const;

    regex_token_iterator& operator++();
    regex_token_iterator operator++(int);
};

typedef regex_token_iterator<const char*>             cregex_token_iterator;
typedef regex_token_iterator<const wchar_t*>          wcregex_token_iterator;
typedef regex_token_iterator<string::const_iterator>  sregex_token_iterator;
typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;

} // std
*/

#include <__config>
#include <stdexcept>
#include <__locale>
#include <initializer_list>
#include <utility>
#include <iterator>
#include <string>
#include <memory>
#include <vector>

#pragma GCC system_header

_LIBCPP_BEGIN_NAMESPACE_STD

namespace regex_constants
{

// syntax_option_type

enum syntax_option_type
{
    icase      = 1 << 0,
    nosubs     = 1 << 1,
    optimize   = 1 << 2,
    collate    = 1 << 3,
    ECMAScript = 1 << 4,
    basic      = 1 << 5,
    extended   = 1 << 6,
    awk        = 1 << 7,
    grep       = 1 << 8,
    egrep      = 1 << 9
};

inline
/*constexpr*/
syntax_option_type
operator~(syntax_option_type __x)
{
    return syntax_option_type(~int(__x));
}

inline
/*constexpr*/
syntax_option_type
operator&(syntax_option_type __x, syntax_option_type __y)
{
    return syntax_option_type(int(__x) & int(__y));
}

inline
/*constexpr*/
syntax_option_type
operator|(syntax_option_type __x, syntax_option_type __y)
{
    return syntax_option_type(int(__x) | int(__y));
}

inline
/*constexpr*/
syntax_option_type
operator^(syntax_option_type __x, syntax_option_type __y)
{
    return syntax_option_type(int(__x) ^ int(__y));
}

inline
/*constexpr*/
syntax_option_type&
operator&=(syntax_option_type& __x, syntax_option_type __y)
{
    __x = __x & __y;
    return __x;
}

inline
/*constexpr*/
syntax_option_type&
operator|=(syntax_option_type& __x, syntax_option_type __y)
{
    __x = __x | __y;
    return __x;
}

inline
/*constexpr*/
syntax_option_type&
operator^=(syntax_option_type& __x, syntax_option_type __y)
{
    __x = __x ^ __y;
    return __x;
}

// match_flag_type

enum match_flag_type
{
    match_default     = 0,
    match_not_bol     = 1 << 0,
    match_not_eol     = 1 << 1,
    match_not_bow     = 1 << 2,
    match_not_eow     = 1 << 3,
    match_any         = 1 << 4,
    match_not_null    = 1 << 5,
    match_continuous  = 1 << 6,
    match_prev_avail  = 1 << 7,
    format_default    = 0,
    format_sed        = 1 << 8,
    format_no_copy    = 1 << 9,
    format_first_only = 1 << 10
};

inline
/*constexpr*/
match_flag_type
operator~(match_flag_type __x)
{
    return match_flag_type(~int(__x));
}

inline
/*constexpr*/
match_flag_type
operator&(match_flag_type __x, match_flag_type __y)
{
    return match_flag_type(int(__x) & int(__y));
}

inline
/*constexpr*/
match_flag_type
operator|(match_flag_type __x, match_flag_type __y)
{
    return match_flag_type(int(__x) | int(__y));
}

inline
/*constexpr*/
match_flag_type
operator^(match_flag_type __x, match_flag_type __y)
{
    return match_flag_type(int(__x) ^ int(__y));
}

inline
/*constexpr*/
match_flag_type&
operator&=(match_flag_type& __x, match_flag_type __y)
{
    __x = __x & __y;
    return __x;
}

inline
/*constexpr*/
match_flag_type&
operator|=(match_flag_type& __x, match_flag_type __y)
{
    __x = __x | __y;
    return __x;
}

inline
/*constexpr*/
match_flag_type&
operator^=(match_flag_type& __x, match_flag_type __y)
{
    __x = __x ^ __y;
    return __x;
}

enum error_type
{
    error_collate = 1,
    error_ctype,
    error_escape,
    error_backref,
    error_brack,
    error_paren,
    error_brace,
    error_badbrace,
    error_range,
    error_space,
    error_badrepeat,
    error_complexity,
    error_stack,
    error_temp
};

}  // regex_constants

class _LIBCPP_EXCEPTION_ABI regex_error
    : public runtime_error
{
    regex_constants::error_type __code_;
public:
    explicit regex_error(regex_constants::error_type __ecode);
    virtual ~regex_error() throw();
    regex_constants::error_type code() const {return __code_;}
};

template <class _CharT>
struct regex_traits
{
public:
    typedef _CharT                  char_type;
    typedef basic_string<char_type> string_type;
    typedef locale                  locale_type;
    typedef ctype_base::mask        char_class_type;

    static const char_class_type __regex_word = 0x80;
private:
    locale __loc_;
    const ctype<char_type>* __ct_;
    const collate<char_type>* __col_;

public:
    regex_traits();

    static size_t length(const char_type* __p)
        {return char_traits<char_type>::length(__p);}
    char_type translate(char_type __c) const {return __c;}
    char_type translate_nocase(char_type __c) const;
    template <class _ForwardIterator>
        string_type
        transform(_ForwardIterator __f, _ForwardIterator __l) const;
    template <class _ForwardIterator>
        string_type
        transform_primary( _ForwardIterator __f, _ForwardIterator __l) const
            {return __transform_primary(__f, __l, char_type());}
    template <class _ForwardIterator>
        string_type
        lookup_collatename(_ForwardIterator __f, _ForwardIterator __l) const
            {return __lookup_collatename(__f, __l, char_type());}
    template <class _ForwardIterator>
        char_class_type
        lookup_classname(_ForwardIterator __f, _ForwardIterator __l,
                         bool __icase = false) const
            {return __lookup_classname(__f, __l, __icase, char_type());}
    bool isctype(char_type __c, char_class_type __m) const;
    int value(char_type __ch, int __radix) const
        {return __value(__ch, __radix);}
    locale_type imbue(locale_type __l);
    locale_type getloc()const {return __loc_;}

private:
    void __init();

    template <class _ForwardIterator>
        string_type
        __transform_primary(_ForwardIterator __f, _ForwardIterator __l, char) const;
    template <class _ForwardIterator>
        string_type
        __transform_primary(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const;

    template <class _ForwardIterator>
        string_type
        __lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, char) const;
    template <class _ForwardIterator>
        string_type
        __lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const;

    template <class _ForwardIterator>
        char_class_type
        __lookup_classname(_ForwardIterator __f, _ForwardIterator __l,
                           bool __icase, char) const;
    template <class _ForwardIterator>
        char_class_type
        __lookup_classname(_ForwardIterator __f, _ForwardIterator __l,
                           bool __icase, wchar_t) const;

    static int __value(unsigned char __ch, int __radix);
    int __value(char __ch, int __radix) const
        {return __value(static_cast<unsigned char>(__ch), __radix);}
    int __value(wchar_t __ch, int __radix) const;
};

template <class _CharT>
regex_traits<_CharT>::regex_traits()
{
    __init();
}

template <class _CharT>
typename regex_traits<_CharT>::char_type
regex_traits<_CharT>::translate_nocase(char_type __c) const
{
    return __ct_->tolower(__c);
}

template <class _CharT>
template <class _ForwardIterator>
typename regex_traits<_CharT>::string_type
regex_traits<_CharT>::transform(_ForwardIterator __f, _ForwardIterator __l) const
{
    string_type __s(__f, __l);
    return __col_->transform(__s.data(), __s.data() + __s.size());
}

template <class _CharT>
void
regex_traits<_CharT>::__init()
{
    __ct_ = &use_facet<ctype<char_type> >(__loc_);
    __col_ = &use_facet<collate<char_type> >(__loc_);
}

template <class _CharT>
typename regex_traits<_CharT>::locale_type
regex_traits<_CharT>::imbue(locale_type __l)
{
    locale __r = __loc_;
    __loc_ = __l;
    __init();
    return __r;
}

// transform_primary is very FreeBSD-specific

template <class _CharT>
template <class _ForwardIterator>
typename regex_traits<_CharT>::string_type
regex_traits<_CharT>::__transform_primary(_ForwardIterator __f,
                                          _ForwardIterator __l, char) const
{
    const string_type __s(__f, __l);
    string_type __d = __col_->transform(__s.data(), __s.data() + __s.size());
    switch (__d.size())
    {
    case 1:
        break;
    case 12:
        __d[11] = __d[3];
        break;
    default:
        __d.clear();
        break;
    }
    return __d;
}

template <class _CharT>
template <class _ForwardIterator>
typename regex_traits<_CharT>::string_type
regex_traits<_CharT>::__transform_primary(_ForwardIterator __f,
                                          _ForwardIterator __l, wchar_t) const
{
    const string_type __s(__f, __l);
    string_type __d = __col_->transform(__s.data(), __s.data() + __s.size());
    switch (__d.size())
    {
    case 1:
        break;
    case 3:
        __d[2] = __d[0];
        break;
    default:
        __d.clear();
        break;
    }
    return __d;
}

// lookup_collatename is very FreeBSD-specific

string __get_collation_name(const char* __s);

template <class _CharT>
template <class _ForwardIterator>
typename regex_traits<_CharT>::string_type
regex_traits<_CharT>::__lookup_collatename(_ForwardIterator __f,
                                           _ForwardIterator __l, char) const
{
    string_type __s(__f, __l);
    string_type __r;
    if (!__s.empty())
    {
        __r = __get_collation_name(__s.c_str());
        if (__r.empty() && __s.size() <= 2)
        {
            __r = __col_->transform(__s.data(), __s.data() + __s.size());
            if (__r.size() == 1 || __r.size() == 12)
                __r = __s;
            else
                __r.clear();
        }
    }
    return __r;
}

template <class _CharT>
template <class _ForwardIterator>
typename regex_traits<_CharT>::string_type
regex_traits<_CharT>::__lookup_collatename(_ForwardIterator __f,
                                           _ForwardIterator __l, wchar_t) const
{
    string_type __s(__f, __l);
    string __n;
    __n.reserve(__s.size());
    for (typename string_type::const_iterator __i = __s.begin(), __e = __s.end();
                                                              __i != __e; ++__i)
    {
        if (static_cast<unsigned>(*__i) >= 127)
            return string_type();
        __n.push_back(char(*__i));
    }
    string_type __r;
    if (!__s.empty())
    {
        __n = __get_collation_name(__n.c_str());
        if (!__n.empty())
            __r.assign(__n.begin(), __n.end());
        else if (__s.size() <= 2)
        {
            __r = __col_->transform(__s.data(), __s.data() + __s.size());
            if (__r.size() == 1 || __r.size() == 3)
                __r = __s;
            else
                __r.clear();
        }
    }
    return __r;
}

// lookup_classname

ctype_base::mask __get_classname(const char* __s, bool __icase);

template <class _CharT>
template <class _ForwardIterator>
typename regex_traits<_CharT>::char_class_type
regex_traits<_CharT>::__lookup_classname(_ForwardIterator __f,
                                         _ForwardIterator __l,
                                         bool __icase, char) const
{
    string_type __s(__f, __l);
    __ct_->tolower(&__s[0], &__s[0] + __s.size());
    return __get_classname(__s.c_str(), __icase);
}

template <class _CharT>
template <class _ForwardIterator>
typename regex_traits<_CharT>::char_class_type
regex_traits<_CharT>::__lookup_classname(_ForwardIterator __f,
                                         _ForwardIterator __l,
                                         bool __icase, wchar_t) const
{
    string_type __s(__f, __l);
    __ct_->tolower(&__s[0], &__s[0] + __s.size());
    string __n;
    __n.reserve(__s.size());
    for (typename string_type::const_iterator __i = __s.begin(), __e = __s.end();
                                                              __i != __e; ++__i)
    {
        if (static_cast<unsigned>(*__i) >= 127)
            return char_class_type();
        __n.push_back(char(*__i));
    }
    return __get_classname(__n.c_str(), __icase);
}

template <class _CharT>
bool
regex_traits<_CharT>::isctype(char_type __c, char_class_type __m) const
{
    if (__ct_->is(__m, __c))
        return true;
    return (__c == '_' && (__m & __regex_word));
}

template <class _CharT>
int
regex_traits<_CharT>::__value(unsigned char __ch, int __radix)
{
    if ((__ch & 0xF8u) == 0x30)  // '0' <= __ch && __ch <= '7'
        return __ch - '0';
    if (__radix != 8)
    {
        if ((__ch & 0xFEu) == 0x38)  // '8' <= __ch && __ch <= '9'
            return __ch - '0';
        if (__radix == 16)
        {
            __ch |= 0x20;  // tolower
            if ('a' <= __ch && __ch <= 'f')
                return __ch - ('a' - 10);
        }
    }
    return -1;
}

template <class _CharT>
inline
int
regex_traits<_CharT>::__value(wchar_t __ch, int __radix) const
{
    return __value(static_cast<unsigned char>(__ct_->narrow(__ch, char_type())), __radix);
}

template <class _CharT> class __transition;

template <class _CharT>
class __state
{
    typedef __transition<_CharT> __transition;
    __transition* __t1_;
    __transition* __t2_;
    int __state_;
    enum
    {
        __not_tried = 0,
        __1_succeded = 1,
        __1_failed = 2,
        __2_not_tried = 0,
        __2_succeded = 4,
        __2_failed = 8
    };

    __state(const __state&);
    __state& operator=(const __state&);
public:
    __state()
        : __t1_(), __t2_(), __state_() {}
    ~__state();

    __state* __test(_CharT __c, bool& __consume, unsigned& __begin_sub,
                                                 unsigned& __end_sub);

    void __add_one(__transition* __t) {__t1_ = __t;}

    void __reset_state();
};

template <class _CharT>
__state<_CharT>::~__state()
{
    delete __t1_;
    delete __t2_;
}

template <class _CharT>
__state<_CharT>*
__state<_CharT>::__test(_CharT __c, bool& __consume, unsigned& __begin_sub,
                                                     unsigned& __end_sub)
{
    __state* __r = nullptr;
    if ((__state_ & 3) == 0)
    {
        if (__t1_)
        {
            __r = __t1_->__test(__c, __consume, __begin_sub, __end_sub);
            if (__r)
                __state_ |= __1_succeded;
            else
                __state_ |= __1_failed;
        }
        else
            __state_ |= __1_failed;
    }
    else if ((__state_ & 0xC) == 0)
    {
        if (__t2_)
        {
            __r = __t2_->__test(__c, __consume, __begin_sub, __end_sub);
            if (__r)
                __state_ |= __2_succeded;
            else
                __state_ |= __2_failed;
        }
        else
            __state_ |= __2_failed;
    }
    return __r;
}

template <class _CharT>
void
__state<_CharT>::__reset_state()
{
    __state_ = __not_tried;
    if (__t1_)
        __t1_->__reset_state();
    if (__t2_)
        __t2_->__reset_state();
}

template <class _CharT>
class __transition
{
    __transition(const __transition&);
    __transition& operator=(const __transition&);

protected:
    typedef __state<_CharT> __state;
    typedef unique_ptr<__state, void(*)(__state*)> __sptr;

    static void __delete_state(__state* __p) {delete __p;}
    static void __ignore_state(__state*) {}

    __sptr __sptr_;
public:
    __transition(bool __owns, __state* __st)
        : __sptr_(__st, __owns ? &__delete_state : &__ignore_state) {}
    virtual ~__transition() {}

    virtual __state* __test(_CharT, bool& __consume, unsigned& __begin_sub,
                                                     unsigned& __end_sub);

    void __reset_state();
};

template <class _CharT>
typename __transition<_CharT>::__state*
__transition<_CharT>::__test(_CharT, bool& __consume, unsigned&, unsigned&)
{
    __consume = false;
    return __sptr_.get();
}
 
template <class _CharT>
void
__transition<_CharT>::__reset_state()
{
    if (__sptr_.get_deleter() == &__delete_state)
        __sptr_->__reset_state();
}

template <class _CharT>
class __match_char
    : public __transition<_CharT>
{
    typedef __transition<_CharT> base;
    _CharT __c_;
public:
    typedef typename base::__state __state;

    __match_char(_CharT __c, bool __owns, __state* __st)
        : base(__owns, __st), __c_(__c) {}

    virtual __state* __test(_CharT __c, bool& __consume, unsigned&, unsigned&);
};

template <class _CharT>
typename __match_char<_CharT>::__state*
__match_char<_CharT>::__test(_CharT __c, bool& __consume, unsigned&, unsigned&)
{
    if (__c == __c_)
    {
        __consume = true;
        return base::__sptr_.get();
    }
    __consume = false;
    return nullptr;
}
 
template <class _CharT>
class __begin_marked_subexpression
    : public __transition<_CharT>
{
    typedef __transition<_CharT> base;
    unsigned __sub_;
public:
    typedef typename base::__state __state;

    __begin_marked_subexpression(unsigned __sub, bool __owns, __state* __st)
        : base(__owns, __st), __sub_(__sub) {}

    virtual __state* __test(_CharT, bool& __consume, unsigned& __begin_sub,
                                                     unsigned&);
};

template <class _CharT>
typename __begin_marked_subexpression<_CharT>::__state*
__begin_marked_subexpression<_CharT>::__test(_CharT, bool& __consume,
                                             unsigned& __begin_sub, unsigned&)
{
    __consume = false;
    __begin_sub = __sub_;
    return base::__sptr_.get();
}
 
template <class _CharT>
class __end_marked_subexpression
    : public __transition<_CharT>
{
    typedef __transition<_CharT> base;
    unsigned __sub_;
public:
    typedef typename base::__state __state;

    __end_marked_subexpression(unsigned __sub, bool __owns, __state* __st)
        : base(__owns, __st), __sub_(__sub) {}

    virtual __state* __test(_CharT, bool& __consume, unsigned&,
                                                     unsigned& __end_sub);
};

template <class _CharT>
typename __end_marked_subexpression<_CharT>::__state*
__end_marked_subexpression<_CharT>::__test(_CharT, bool& __consume,
                                           unsigned&, unsigned& __end_sub)
{
    __consume = false;
    __end_sub = __sub_;
    return base::__sptr_.get();
}
 
template <class, class> class match_results;

template <class _CharT, class _Traits = regex_traits<_CharT> >
class basic_regex
{
public:
    // types:
    typedef _CharT                              value_type;
    typedef regex_constants::syntax_option_type flag_type;
    typedef typename _Traits::locale_type       locale_type;

private:
    _Traits   __traits_;
    flag_type __flags_;
    unsigned __marked_count_;
    int __open_count_;
    shared_ptr<__state<_CharT> > __start_;
    __state<_CharT>* __end_;

public:
    // constants:
    static const/*expr*/ regex_constants::syntax_option_type icase = regex_constants::icase;
    static const/*expr*/ regex_constants::syntax_option_type nosubs = regex_constants::nosubs;
    static const/*expr*/ regex_constants::syntax_option_type optimize = regex_constants::optimize;
    static const/*expr*/ regex_constants::syntax_option_type collate = regex_constants::collate;
    static const/*expr*/ regex_constants::syntax_option_type ECMAScript = regex_constants::ECMAScript;
    static const/*expr*/ regex_constants::syntax_option_type basic = regex_constants::basic;
    static const/*expr*/ regex_constants::syntax_option_type extended = regex_constants::extended;
    static const/*expr*/ regex_constants::syntax_option_type awk = regex_constants::awk;
    static const/*expr*/ regex_constants::syntax_option_type grep = regex_constants::grep;
    static const/*expr*/ regex_constants::syntax_option_type egrep = regex_constants::egrep;

    // construct/copy/destroy:
    basic_regex();
    explicit basic_regex(const value_type* __p, flag_type __f = regex_constants::ECMAScript)
        : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
        {__parse(__p, __p + __traits_.length(__p));}
    basic_regex(const value_type* __p, size_t __len, flag_type __f)
        : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
        {__parse(__p, __p + __len);}
    basic_regex(const basic_regex&);
#ifdef _LIBCPP_MOVE
    basic_regex(basic_regex&&);
#endif
    template <class _ST, class _SA>
        explicit basic_regex(const basic_string<value_type, _ST, _SA>& __p,
                             flag_type __f = regex_constants::ECMAScript)
        : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
        {__parse(__p.begin(), __p.end());}
    template <class _ForwardIterator>
        basic_regex(_ForwardIterator __first, _ForwardIterator __last,
                    flag_type __f = regex_constants::ECMAScript)
        : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
        {__parse(__first, __last);}
    basic_regex(initializer_list<value_type> __il,
                flag_type __f = regex_constants::ECMAScript)
        : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
        {__parse(__il.begin(), __il.end());}

    ~basic_regex();

    basic_regex& operator=(const basic_regex&);
#ifdef _LIBCPP_MOVE
    basic_regex& operator=(basic_regex&&);
#endif
    basic_regex& operator=(const value_type* __p);
    basic_regex& operator=(initializer_list<value_type> __il);
    template <class _ST, class _SA>
        basic_regex& operator=(const basic_string<value_type, _ST, _SA>& __p);

    // assign:
    basic_regex& assign(const basic_regex& __that);
#ifdef _LIBCPP_MOVE
    basic_regex& assign(basic_regex&& __that);
#endif
    basic_regex& assign(const value_type* __p, flag_type __f = regex_constants::ECMAScript);
    basic_regex& assign(const value_type* __p, size_t __len, flag_type __f);
    template <class _ST, class _SA>
        basic_regex& assign(const basic_string<value_type, _ST, _SA>& __s,
                            flag_type __f = regex_constants::ECMAScript);
    template <class _InputIterator>
        basic_regex& assign(_InputIterator __first, _InputIterator __last,
                            flag_type __f = regex_constants::ECMAScript);
    basic_regex& assign(initializer_list<value_type> __il,
                        flag_type = regex_constants::ECMAScript);

    // const operations:
    unsigned mark_count() const {return __marked_count_;}
    flag_type flags() const {return __flags_;}

    // locale:
    locale_type imbue(locale_type __loc) {return __traits_.imbue(__loc);}
    locale_type getloc() const {return __traits_.getloc();}

    // swap:
    void swap(basic_regex&);

private:
    template <class _ForwardIterator>
        void __parse(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_basic_reg_exp(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_RE_expression(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_simple_RE(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_nondupl_RE(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_one_char_or_coll_elem_RE(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_Back_open_paren(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_Back_close_paren(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_Back_open_brace(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_Back_close_brace(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_BACKREF(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_ORD_CHAR(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_QUOTED_CHAR(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_RE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_ERE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_bracket_expression(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_follow_list(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_expression_term(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_equivalence_class(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_character_class(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_collating_symbol(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_DUP_COUNT(_ForwardIterator __first, _ForwardIterator __last, int& __c);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_extended_reg_exp(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_ERE_branch(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_ERE_expression(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_one_char_or_coll_elem_ERE(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_ORD_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);
    template <class _ForwardIterator>
        _ForwardIterator
        __parse_QUOTED_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);

    void __push_l_anchor() {}
    void __push_r_anchor() {}
    void __push_match_any() {}
    void __push_greedy_inf_repeat(int __min) {}
    void __push_exact_repeat(int __count) {}
    void __push_repeat(int __min, int __max) {}
    void __start_nonmatching_list() {}
    void __start_matching_list() {}
    void __end_nonmatching_list() {}
    void __end_matching_list() {}
    void __push_char(value_type __c);
    void __push_char(const typename _Traits::string_type& __c) {}
    void __push_range() {}
    void __push_class_type(typename _Traits::char_class_type) {}
    void __push_back_ref(int __i) {}
    void __push_alternation() {}
    void __push_begin_marked_subexpression();
    void __push_end_marked_subexpression(unsigned);

    template <class _BidirectionalIterator, class _Allocator>
        bool
        __search(_BidirectionalIterator __first, _BidirectionalIterator __last,
                 match_results<_BidirectionalIterator, _Allocator>& __m,
                 regex_constants::match_flag_type __flags) const;

    template <class _B, class _A, class _C, class _T>
    friend
    bool
    regex_search(_B, _B, match_results<_B, _A>&, const basic_regex<_C, _T>&,
                 regex_constants::match_flag_type);
};

template <class _CharT, class _Traits>
inline
basic_regex<_CharT, _Traits>::basic_regex()
    : __traits_(), __flags_(), __marked_count_(0)
{
}

template <class _CharT, class _Traits>
basic_regex<_CharT, _Traits>::~basic_regex()
{
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
void
basic_regex<_CharT, _Traits>::__parse(_ForwardIterator __first,
                                      _ForwardIterator __last)
{
    switch (__flags_ & 0x3F0)
    {
    case ECMAScript:
        break;
    case basic:
        __parse_basic_reg_exp(__first, __last);
        break;
    case extended:
        __parse_extended_reg_exp(__first, __last);
        break;
    case awk:
        break;
    case grep:
        break;
    case egrep:
        break;
    default:
        throw regex_error(regex_constants::error_temp);
    }
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_basic_reg_exp(_ForwardIterator __first,
                                                    _ForwardIterator __last)
{
    if (__first != __last)
    {
        if (*__first == '^')
        {
            __push_l_anchor();
            ++__first;
        }
        if (__first != __last)
        {
            __first = __parse_RE_expression(__first, __last);
            if (__first != __last)
            {
                _ForwardIterator __temp = next(__first);
                if (__temp == __last && *__first == '$')
                {
                    __push_r_anchor();
                    ++__first;
                }
            }
        }
        if (__first != __last)
            throw regex_error(regex_constants::error_temp);
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_extended_reg_exp(_ForwardIterator __first,
                                                       _ForwardIterator __last)
{
    while (true)
    {
        _ForwardIterator __temp = __parse_ERE_branch(__first, __last);
        if (__temp == __first)
            throw regex_error(regex_constants::error_temp);
        __first = __temp;
        if (__first == __last)
            break;
        if (*__first != '|')
            throw regex_error(regex_constants::error_temp);
        __push_alternation();
        ++__first;
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_ERE_branch(_ForwardIterator __first,
                                                 _ForwardIterator __last)
{
    _ForwardIterator __temp = __parse_ERE_expression(__first, __last);
    if (__temp == __first)
        throw regex_error(regex_constants::error_temp);
    do
    {
        __first = __temp;
        __temp = __parse_ERE_expression(__first, __last);
    } while (__temp != __first);
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_ERE_expression(_ForwardIterator __first,
                                                     _ForwardIterator __last)
{
    _ForwardIterator __temp = __parse_one_char_or_coll_elem_ERE(__first, __last);
    if (__temp == __first && __temp != __last)
    {
        switch (*__temp)
        {
        case '^':
            __push_l_anchor();
            ++__temp;
            break;
        case '$':
            __push_r_anchor();
            ++__temp;
            break;
        case '(':
            __push_begin_marked_subexpression();
            unsigned __temp_count = __marked_count_;
            ++__open_count_;
            __temp = __parse_extended_reg_exp(++__temp, __last);
            if (__temp == __last || *__temp != ')')
                throw regex_error(regex_constants::error_paren);
            __push_end_marked_subexpression(__temp_count);
            --__open_count_;
            ++__temp;
            break;
        }
    }
    if (__temp != __first)
        __temp = __parse_ERE_dupl_symbol(__temp, __last);
    __first = __temp;
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_RE_expression(_ForwardIterator __first,
                                                    _ForwardIterator __last)
{
    while (true)
    {
        _ForwardIterator __temp = __parse_simple_RE(__first, __last);
        if (__temp == __first)
            break;
        __first = __temp;
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_simple_RE(_ForwardIterator __first,
                                                _ForwardIterator __last)
{
    if (__first != __last)
    {
        _ForwardIterator __temp = __parse_nondupl_RE(__first, __last);
        if (__temp != __first)
        {
            __first = __temp;
            __first = __parse_RE_dupl_symbol(__first, __last);
        }
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_nondupl_RE(_ForwardIterator __first,
                                                 _ForwardIterator __last)
{
    _ForwardIterator __temp = __first;
    __first = __parse_one_char_or_coll_elem_RE(__first, __last);
    if (__temp == __first)
    {
        __temp = __parse_Back_open_paren(__first, __last);
        if (__temp != __first)
        {
            __push_begin_marked_subexpression();
            unsigned __temp_count = __marked_count_;
            __first = __parse_RE_expression(__temp, __last);
            __temp = __parse_Back_close_paren(__first, __last);
            if (__temp == __first)
                throw regex_error(regex_constants::error_paren);
            __push_end_marked_subexpression(__temp_count);
            __first = __temp;
        }
        else
            __first = __parse_BACKREF(__first, __last);
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_RE(
                                                       _ForwardIterator __first,
                                                       _ForwardIterator __last)
{
    _ForwardIterator __temp = __parse_ORD_CHAR(__first, __last);
    if (__temp == __first)
    {
        __temp = __parse_QUOTED_CHAR(__first, __last);
        if (__temp == __first)
        {
            if (__temp != __last && *__temp == '.')
            {
                __push_match_any();
                ++__temp;
            }
            else
                __temp = __parse_bracket_expression(__first, __last);
        }
    }
    __first = __temp;
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_ERE(
                                                       _ForwardIterator __first,
                                                       _ForwardIterator __last)
{
    _ForwardIterator __temp = __parse_ORD_CHAR_ERE(__first, __last);
    if (__temp == __first)
    {
        __temp = __parse_QUOTED_CHAR_ERE(__first, __last);
        if (__temp == __first)
        {
            if (__temp != __last && *__temp == '.')
            {
                __push_match_any();
                ++__temp;
            }
            else
                __temp = __parse_bracket_expression(__first, __last);
        }
    }
    __first = __temp;
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_Back_open_paren(_ForwardIterator __first,
                                                      _ForwardIterator __last)
{
    if (__first != __last)
    {
        _ForwardIterator __temp = next(__first);
        if (__temp != __last)
        {
            if (*__first == '\\' && *__temp == '(')
                __first = ++__temp;
        }
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_Back_close_paren(_ForwardIterator __first,
                                                       _ForwardIterator __last)
{
    if (__first != __last)
    {
        _ForwardIterator __temp = next(__first);
        if (__temp != __last)
        {
            if (*__first == '\\' && *__temp == ')')
                __first = ++__temp;
        }
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_Back_open_brace(_ForwardIterator __first,
                                                      _ForwardIterator __last)
{
    if (__first != __last)
    {
        _ForwardIterator __temp = next(__first);
        if (__temp != __last)
        {
            if (*__first == '\\' && *__temp == '{')
                __first = ++__temp;
        }
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_Back_close_brace(_ForwardIterator __first,
                                                       _ForwardIterator __last)
{
    if (__first != __last)
    {
        _ForwardIterator __temp = next(__first);
        if (__temp != __last)
        {
            if (*__first == '\\' && *__temp == '}')
                __first = ++__temp;
        }
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_BACKREF(_ForwardIterator __first,
                                              _ForwardIterator __last)
{
    if (__first != __last)
    {
        _ForwardIterator __temp = next(__first);
        if (__temp != __last)
        {
            if (*__first == '\\' && '1' <= *__temp && *__temp <= '9')
            {
                __push_back_ref(*__temp - '0');
                __first = ++__temp;
            }
        }
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_ORD_CHAR(_ForwardIterator __first,
                                               _ForwardIterator __last)
{
    if (__first != __last)
    {
        _ForwardIterator __temp = next(__first);
        if (__temp == __last && *__first == '$')
            return __first;
        // Not called inside a bracket
        if (*__first == '.' || *__first == '\\' || *__first == '[')
            return __first;
        __push_char(*__first);
        ++__first;
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_ORD_CHAR_ERE(_ForwardIterator __first,
                                                   _ForwardIterator __last)
{
    if (__first != __last)
    {
        switch (*__first)
        {
        case '^':
        case '.':
        case '[':
        case '$':
        case '(':
        case '|':
        case '*':
        case '+':
        case '?':
        case '{':
        case '\\':
            break;
        case ')':
            if (__open_count_ == 0)
            {
                __push_char(*__first);
                ++__first;
            }
            break;
        default:
            __push_char(*__first);
            ++__first;
            break;
        }
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR(_ForwardIterator __first,
                                                  _ForwardIterator __last)
{
    if (__first != __last)
    {
        _ForwardIterator __temp = next(__first);
        if (__temp != __last)
        {
            if (*__first == '\\')
            {
                switch (*__temp)
                {
                case '^':
                case '.':
                case '*':
                case '[':
                case '$':
                case '\\':
                    __push_char(*__temp);
                    __first = ++__temp;
                    break;
                }
            }
        }
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR_ERE(_ForwardIterator __first,
                                                      _ForwardIterator __last)
{
    if (__first != __last)
    {
        _ForwardIterator __temp = next(__first);
        if (__temp != __last)
        {
            if (*__first == '\\')
            {
                switch (*__temp)
                {
                case '^':
                case '.':
                case '*':
                case '[':
                case '$':
                case '\\':
                case '(':
                case ')':
                case '|':
                case '+':
                case '?':
                case '{':
                    __push_char(*__temp);
                    __first = ++__temp;
                    break;
                }
            }
        }
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_RE_dupl_symbol(_ForwardIterator __first,
                                                     _ForwardIterator __last)
{
    if (__first != __last)
    {
        if (*__first == '*')
        {
            __push_greedy_inf_repeat(0);
            ++__first;
        }
        else
        {
            _ForwardIterator __temp = __parse_Back_open_brace(__first, __last);
            if (__temp != __first)
            {
                int __min = 0;
                __first = __temp;
                __temp = __parse_DUP_COUNT(__first, __last, __min);
                if (__temp == __first)
                    throw regex_error(regex_constants::error_badbrace);
                __first = __temp;
                if (__first == __last)
                    throw regex_error(regex_constants::error_brace);
                if (*__first != ',')
                {
                    __temp = __parse_Back_close_brace(__first, __last);
                    if (__temp == __first)
                        throw regex_error(regex_constants::error_brace);
                    __push_exact_repeat(__min);
                    __first = __temp;
                }
                else
                {
                    ++__first;  // consume ','
                    int __max = -1;
                    __first = __parse_DUP_COUNT(__first, __last, __max);
                    __temp = __parse_Back_close_brace(__first, __last);
                    if (__temp == __first)
                        throw regex_error(regex_constants::error_brace);
                    if (__max == -1)
                        __push_greedy_inf_repeat(__min);
                    else
                    {
                        if (__max < __min)
                            throw regex_error(regex_constants::error_badbrace);
                        __push_repeat(__min, __max);
                    }
                    __first = __temp;
                }
            }
        }
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_ERE_dupl_symbol(_ForwardIterator __first,
                                                      _ForwardIterator __last)
{
    if (__first != __last)
    {
        switch (*__first)
        {
        case '*':
            __push_greedy_inf_repeat(0);
            ++__first;
            break;
        case '+':
            __push_greedy_inf_repeat(1);
            ++__first;
            break;
        case '?':
            __push_repeat(0, 1);
            ++__first;
            break;
        case '{':
            {
                int __min;
                _ForwardIterator __temp = __parse_DUP_COUNT(__first, __last, __min);
                if (__temp == __first)
                    throw regex_error(regex_constants::error_badbrace);
                __first = __temp;
                if (__first == __last)
                    throw regex_error(regex_constants::error_brace);
                switch (*__first)
                {
                case '}':
                    __push_exact_repeat(__min);
                    ++__first;
                    break;
                case ',':
                    if (++__first == __last)
                        throw regex_error(regex_constants::error_badbrace);
                    if (*__first == '}')
                    {
                        __push_greedy_inf_repeat(__min);
                        ++__first;
                    }
                    else
                    {
                        int __max;
                        __temp = __parse_DUP_COUNT(__first, __last, __max);
                        if (__temp == __first)
                            throw regex_error(regex_constants::error_brace);
                        __first = __temp;
                        if (__first == __last || *__first != '}')
                            throw regex_error(regex_constants::error_brace);
                        ++__first;
                        if (__max < __min)
                            throw regex_error(regex_constants::error_badbrace);
                        __push_repeat(__min, __max);
                    }
                default:
                    throw regex_error(regex_constants::error_badbrace);
                }
            }
            break;
        }
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_bracket_expression(_ForwardIterator __first,
                                                         _ForwardIterator __last)
{
    if (__first != __last && *__first == '[')
    {
        if (++__first == __last)
            throw regex_error(regex_constants::error_brack);
        bool __non_matching = false;
        if (*__first == '^')
        {
            ++__first;
            __non_matching = true;
            __start_nonmatching_list();
        }
        else
            __start_matching_list();
        if (__first == __last)
            throw regex_error(regex_constants::error_brack);
        if (*__first == ']')
        {
            __push_char(']');
            ++__first;
        }
        __first = __parse_follow_list(__first, __last);
        if (__first == __last)
            throw regex_error(regex_constants::error_brack);
        if (*__first == '-')
        {
            __push_char('-');
            ++__first;
        }
        if (__first == __last || *__first != ']')
            throw regex_error(regex_constants::error_brack);
        if (__non_matching)
            __end_nonmatching_list();
        else
            __end_matching_list();
        ++__first;
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_follow_list(_ForwardIterator __first,
                                                  _ForwardIterator __last)
{
    if (__first != __last)
    {
        while (true)
        {
            _ForwardIterator __temp = __parse_expression_term(__first, __last);
            if (__temp == __first)
                break;
            __first = __temp;
        }
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_expression_term(_ForwardIterator __first,
                                                      _ForwardIterator __last)
{
    if (__first != __last && *__first != ']')
    {
        bool __parsed_one = false;
        _ForwardIterator __temp = next(__first);
        if (__temp != __last && *__first == '[')
        {
            if (*__temp == '=')
                return __parse_equivalence_class(++__temp, __last);
            else if (*__temp == ':')
                return __parse_character_class(++__temp, __last);
            else if (*__temp == '.')
            {
                __first = __parse_collating_symbol(++__temp, __last);
                __parsed_one = true;
            }
        }
        if (!__parsed_one)
        {
            __push_char(*__first);
            ++__first;
        }
        if (__first != __last && *__first != ']')
        {
            __temp = next(__first);
            if (__temp != __last && *__first == '-' && *__temp != ']')
            {
                // parse a range
                __first = __temp;
                ++__temp;
                if (__temp != __last && *__first == '[' && *__temp == '.')
                    __first = __parse_collating_symbol(++__temp, __last);
                else
                {
                    __push_char(*__first);
                    ++__first;
                }
                __push_range();
            }
        }
    }
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_equivalence_class(_ForwardIterator __first,
                                                        _ForwardIterator __last)
{
    // Found [=
    //   This means =] must exist
    value_type _Equal_close[2] = {'=', ']'};
    _ForwardIterator __temp = _STD::search(__first, __last, _Equal_close,
                                                            _Equal_close+2);
    if (__temp == __last)
        throw regex_error(regex_constants::error_brack);
    // [__first, __temp) contains all text in [= ... =]
    typedef typename _Traits::string_type string_type;
    string_type __collate_name =
        __traits_.lookup_collatename(__first, __temp);
    if (__collate_name.empty())
        throw regex_error(regex_constants::error_brack);
    string_type __equiv_name =
        __traits_.transform_primary(__collate_name.begin(),
                                    __collate_name.end());
    if (!__equiv_name.empty())
        __push_char(__equiv_name);
    else
        __push_char(__collate_name);
    __first = next(__temp, 2);
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_character_class(_ForwardIterator __first,
                                                      _ForwardIterator __last)
{
    // Found [:
    //   This means :] must exist
    value_type _Colon_close[2] = {':', ']'};
    _ForwardIterator __temp = _STD::search(__first, __last, _Colon_close,
                                                            _Colon_close+2);
    if (__temp == __last)
        throw regex_error(regex_constants::error_brack);
    // [__first, __temp) contains all text in [: ... :]
    typedef typename _Traits::char_class_type char_class_type;
    char_class_type __class_type =
        __traits_.lookup_classname(__first, __temp, __flags_ & icase);
    if (__class_type == 0)
        throw regex_error(regex_constants::error_brack);
    __push_class_type(__class_type);
    __first = next(__temp, 2);
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_collating_symbol(_ForwardIterator __first,
                                                       _ForwardIterator __last)
{
    // Found [.
    //   This means .] must exist
    value_type _Dot_close[2] = {'.', ']'};
    _ForwardIterator __temp = _STD::search(__first, __last, _Dot_close,
                                                            _Dot_close+2);
    if (__temp == __last)
        throw regex_error(regex_constants::error_brack);
    // [__first, __temp) contains all text in [. ... .]
    typedef typename _Traits::string_type string_type;
    string_type __collate_name =
        __traits_.lookup_collatename(__first, __temp);
    if (__collate_name.empty())
        throw regex_error(regex_constants::error_brack);
    __push_char(__collate_name);
    __first = next(__temp, 2);
    return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_DUP_COUNT(_ForwardIterator __first,
                                                _ForwardIterator __last,
                                                int& __c)
{
    if (__first != __last && '0' <= *__first && *__first <= '9')
    {
        __c = *__first - '0';
        for (++__first; __first != __last && '0' <= *__first && *__first <= '9';
                                                                      ++__first)
        {
            __c *= 10;
            __c += *__first - '0';
        }
    }
    return __first;
}

template <class _CharT, class _Traits>
void
basic_regex<_CharT, _Traits>::__push_char(value_type __c)
{
    unique_ptr<__state<_CharT> > __new_end(new __state<_CharT>);
    unique_ptr<__transition<_CharT> > __new_transition(
        new __match_char<_CharT>(__c, true, __new_end.get()));
    __state<_CharT>* __e = __new_end.release();
    if (__end_ == nullptr)
    {
        __start_.reset(new __state<_CharT>);
        __end_ = __start_.get();
    }
    __end_->__add_one(__new_transition.release());
    __end_ = __e;
}

template <class _CharT, class _Traits>
void
basic_regex<_CharT, _Traits>::__push_begin_marked_subexpression()
{
    unique_ptr<__state<_CharT> > __new_end(new __state<_CharT>);
    unique_ptr<__transition<_CharT> > __new_transition(
        new __begin_marked_subexpression<_CharT>(++__marked_count_, true, __new_end.get()));
    __state<_CharT>* __e = __new_end.release();
    if (__end_ == nullptr)
    {
        __start_.reset(new __state<_CharT>);
        __end_ = __start_.get();
    }
    __end_->__add_one(__new_transition.release());
    __end_ = __e;
}

template <class _CharT, class _Traits>
void
basic_regex<_CharT, _Traits>::__push_end_marked_subexpression(unsigned __sub)
{
    unique_ptr<__state<_CharT> > __new_end(new __state<_CharT>);
    unique_ptr<__transition<_CharT> > __new_transition(
        new __end_marked_subexpression<_CharT>(__sub, true, __new_end.get()));
    __state<_CharT>* __e = __new_end.release();
    if (__end_ == nullptr)
    {
        __start_.reset(new __state<_CharT>);
        __end_ = __start_.get();
    }
    __end_->__add_one(__new_transition.release());
    __end_ = __e;
}

typedef basic_regex<char>    regex;
typedef basic_regex<wchar_t> wregex;

// sub_match

template <class _BidirectionalIterator>
class sub_match
    : public pair<_BidirectionalIterator, _BidirectionalIterator>
{
public:
    typedef _BidirectionalIterator                              iterator;
    typedef typename iterator_traits<iterator>::value_type      value_type;
    typedef typename iterator_traits<iterator>::difference_type difference_type;
    typedef basic_string<value_type>                            string_type;

    bool matched;

    difference_type length() const
        {return matched ? _STD::distance(this->first, this->second) : 0;}
    string_type str() const
        {return matched ? string_type(this->first, this->second) : string_type();}
    operator string_type() const
        {return str();}

    int compare(const sub_match& __s) const
        {return str().compare(__s.str());}
    int compare(const string_type& __s) const
        {return str().compare(__s);}
    int compare(const value_type* __s) const
        {return str().compare(__s);}
};

typedef sub_match<const char*>             csub_match;
typedef sub_match<const wchar_t*>          wcsub_match;
typedef sub_match<string::const_iterator>  ssub_match;
typedef sub_match<wstring::const_iterator> wssub_match;

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator==(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
{
    return __x.compare(__y) == 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
{
    return !(__x == __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
{
    return __x.compare(__y) < 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
{
    return !(__y < __x);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
{
    return !(__x < __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
{
    return __y < __x;
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator==(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
           const sub_match<_BiIter>& __y)
{
    return __y.compare(__x.c_str()) == 0;
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
           const sub_match<_BiIter>& __y)
{
    return !(__x == __y);
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
          const sub_match<_BiIter>& __y)
{
    return __y.compare(__x.c_str()) > 0;
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
          const sub_match<_BiIter>& __y)
{
    return __y < __x;
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool operator>=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
                const sub_match<_BiIter>& __y)
{
    return !(__x < __y);
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
           const sub_match<_BiIter>& __y)
{
    return !(__y < __x);
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator==(const sub_match<_BiIter>& __x,
           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
{
    return __x.compare(__y.c_str()) == 0;
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(const sub_match<_BiIter>& __x,
           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
{
    return !(__x == __y);
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<(const sub_match<_BiIter>& __x,
          const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
{
    return __x.compare(__y.c_str()) < 0;
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool operator>(const sub_match<_BiIter>& __x,
               const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
{
    return __y < __x;
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>=(const sub_match<_BiIter>& __x,
           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
{
    return !(__x < __y);
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<=(const sub_match<_BiIter>& __x,
           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
{
    return !(__y < __x);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator==(typename iterator_traits<_BiIter>::value_type const* __x,
           const sub_match<_BiIter>& __y)
{
    return __y.compare(__x) == 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(typename iterator_traits<_BiIter>::value_type const* __x,
           const sub_match<_BiIter>& __y)
{
    return !(__x == __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<(typename iterator_traits<_BiIter>::value_type const* __x,
          const sub_match<_BiIter>& __y)
{
    return __y.compare(__x) > 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>(typename iterator_traits<_BiIter>::value_type const* __x,
          const sub_match<_BiIter>& __y)
{
    return __y < __x;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>=(typename iterator_traits<_BiIter>::value_type const* __x,
           const sub_match<_BiIter>& __y)
{
    return !(__x < __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<=(typename iterator_traits<_BiIter>::value_type const* __x,
           const sub_match<_BiIter>& __y)
{
    return !(__y < __x);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator==(const sub_match<_BiIter>& __x,
           typename iterator_traits<_BiIter>::value_type const* __y)
{
    return __x.compare(__y) == 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(const sub_match<_BiIter>& __x,
           typename iterator_traits<_BiIter>::value_type const* __y)
{
    return !(__x == __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<(const sub_match<_BiIter>& __x,
          typename iterator_traits<_BiIter>::value_type const* __y)
{
    return __x.compare(__y) < 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>(const sub_match<_BiIter>& __x,
          typename iterator_traits<_BiIter>::value_type const* __y)
{
    return __y < __x;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>=(const sub_match<_BiIter>& __x,
           typename iterator_traits<_BiIter>::value_type const* __y)
{
    return !(__x < __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<=(const sub_match<_BiIter>& __x,
           typename iterator_traits<_BiIter>::value_type const* __y)
{
    return !(__y < __x);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator==(typename iterator_traits<_BiIter>::value_type const& __x,
           const sub_match<_BiIter>& __y)
{
    typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
    return __y.compare(string_type(1, __x)) == 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(typename iterator_traits<_BiIter>::value_type const& __x,
           const sub_match<_BiIter>& __y)
{
    return !(__x == __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<(typename iterator_traits<_BiIter>::value_type const& __x,
          const sub_match<_BiIter>& __y)
{
    typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
    return __y.compare(string_type(1, __x)) > 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>(typename iterator_traits<_BiIter>::value_type const& __x,
          const sub_match<_BiIter>& __y)
{
    return __y < __x;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>=(typename iterator_traits<_BiIter>::value_type const& __x,
           const sub_match<_BiIter>& __y)
{
    return !(__x < __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<=(typename iterator_traits<_BiIter>::value_type const& __x,
           const sub_match<_BiIter>& __y)
{
    return !(__y < __x);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator==(const sub_match<_BiIter>& __x,
           typename iterator_traits<_BiIter>::value_type const& __y)
{
    typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
    return __x.compare(string_type(1, __y)) == 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(const sub_match<_BiIter>& __x,
           typename iterator_traits<_BiIter>::value_type const& __y)
{
    return !(__x == __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<(const sub_match<_BiIter>& __x,
          typename iterator_traits<_BiIter>::value_type const& __y)
{
    typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
    return __x.compare(string_type(1, __y)) < 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>(const sub_match<_BiIter>& __x,
          typename iterator_traits<_BiIter>::value_type const& __y)
{
    return __y < __x;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>=(const sub_match<_BiIter>& __x,
           typename iterator_traits<_BiIter>::value_type const& __y)
{
    return !(__x < __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<=(const sub_match<_BiIter>& __x,
           typename iterator_traits<_BiIter>::value_type const& __y)
{
    return !(__y < __x);
}

template <class _CharT, class _ST, class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
basic_ostream<_CharT, _ST>&
operator<<(basic_ostream<_CharT, _ST>& __os, const sub_match<_BiIter>& __m)
{
    return __os << __m.str();
}

template <class _BidirectionalIterator,
          class _Allocator = allocator<sub_match<_BidirectionalIterator> > >
class match_results
{
public:
    typedef _Allocator                                        allocator_type;
    typedef sub_match<_BidirectionalIterator>                 value_type;
private:
    typedef vector<value_type, allocator_type>                __container_type;

    __container_type  __matches_;
    value_type __unmatched_;
    value_type __prefix_;
    value_type __suffix_;
public:
    typedef const value_type&                                 const_reference;
    typedef const_reference                                   reference;
    typedef typename __container_type::const_iterator         const_iterator;
    typedef const_iterator                                    iterator;
    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
    typedef typename allocator_traits<allocator_type>::size_type size_type;
    typedef typename iterator_traits<_BidirectionalIterator>::value_type char_type;
    typedef basic_string<char_type>                           string_type;

    // construct/copy/destroy:
    explicit match_results(const allocator_type& __a = allocator_type());
//    match_results(const match_results&) = default;
//    match_results& operator=(const match_results&) = default;
#ifdef _LIBCPP_MOVE
//    match_results(match_results&& __m) = default;
//    match_results& operator=(match_results&& __m) = default;
#endif
//    ~match_results() = default;

    // size:
    size_type size() const {return __matches_.size();}
    size_type max_size() const {return __matches_.max_size();}
    bool empty() const {return size() == 0;}

    // element access:
    difference_type length(size_type __sub = 0) const
        {return (*this)[__sub].length();}
    difference_type position(size_type __sub = 0) const
        {return _STD::distance(__prefix_.first, (*this)[__sub].first);}
    string_type str(size_type __sub = 0) const
        {return (*this)[__sub].str();}
    const_reference operator[](size_type __n) const
        {return __n < __matches_.size() ? __matches_[__n] : __unmatched_;}

    const_reference prefix() const {return __prefix_;}
    const_reference suffix() const {return __suffix_;}

    const_iterator begin() const {return empty() ? __matches_.end() : __matches_.begin() + 1;}
    const_iterator end() const {return __matches_.end();}
    const_iterator cbegin() const {return empty() ? __matches_.end() : __matches_.begin() + 1;}
    const_iterator cend() const {return __matches_.end();}

    // format:
    template <class _OutputIter>
        _OutputIter
        format(_OutputIter __out, const char_type* __fmt_first,
               const char_type* __fmt_last,
               regex_constants::match_flag_type __flags = regex_constants::format_default) const;
    template <class _OutputIter, class _ST, class _SA>
        _OutputIter
        format(_OutputIter __out, const basic_string<char_type, _ST, _SA>& __fmt,
               regex_constants::match_flag_type __flags = regex_constants::format_default) const;
    template <class _ST, class _SA>
        basic_string<char_type, _ST, _SA>
        format(const basic_string<char_type, _ST, _SA>& __fmt,
               regex_constants::match_flag_type __flags = regex_constants::format_default) const;
    string_type
        format(const char_type* __fmt,
               regex_constants::match_flag_type __flags = regex_constants::format_default) const;

    // allocator:
    allocator_type get_allocator() const {return __matches_.get_allocator();}

    // swap:
    void swap(match_results& __m);

private:
    void __init(unsigned __s,
                _BidirectionalIterator __f, _BidirectionalIterator __l);

    template <class, class> friend class basic_regex;

    template <class _B, class _A, class _C, class _T>
    friend
    bool
    regex_match(_B, _B, match_results<_B, _A>&, const basic_regex<_C, _T>&,
                regex_constants::match_flag_type);
};

template <class _BidirectionalIterator, class _Allocator>
match_results<_BidirectionalIterator, _Allocator>::match_results(
        const allocator_type& __a)
    : __matches_(__a),
      __unmatched_(),
      __prefix_(),
      __suffix_()
{
}

template <class _BidirectionalIterator, class _Allocator>
void
match_results<_BidirectionalIterator, _Allocator>::__init(unsigned __s,
                         _BidirectionalIterator __f, _BidirectionalIterator __l)
{
    __matches_.resize(__s);
    for (unsigned __i = 0; __i < __s; ++__i)
    {
        __matches_[__i].first   = __l;
        __matches_[__i].second  = __l;
        __matches_[__i].matched = false;
    }
    __unmatched_.first   = __l;
    __unmatched_.second  = __l;
    __unmatched_.matched = false;
    __prefix_.first      = __f;
    __prefix_.second     = __f;
    __prefix_.matched    = false;
    __suffix_.first      = __l;
    __suffix_.second     = __l;
    __suffix_.matched    = false;
}

typedef match_results<const char*>             cmatch;
typedef match_results<const wchar_t*>          wcmatch;
typedef match_results<string::const_iterator>  smatch;
typedef match_results<wstring::const_iterator> wsmatch;

template <class _BidirectionalIterator, class _Allocator>
    bool
    operator==(const match_results<_BidirectionalIterator, _Allocator>& __x,
               const match_results<_BidirectionalIterator, _Allocator>& __y);

template <class _BidirectionalIterator, class _Allocator>
    bool
    operator!=(const match_results<_BidirectionalIterator, _Allocator>& __x,
               const match_results<_BidirectionalIterator, _Allocator>& __y);

template <class _BidirectionalIterator, class _Allocator>
    void
    swap(match_results<_BidirectionalIterator, _Allocator>& __x,
         match_results<_BidirectionalIterator, _Allocator>& __y);

// regex_search

template <class _CharT, class _Traits>
template <class _BidirectionalIterator, class _Allocator>
bool
basic_regex<_CharT, _Traits>::__search(
        _BidirectionalIterator __first, _BidirectionalIterator __last,
        match_results<_BidirectionalIterator, _Allocator>& __m,
        regex_constants::match_flag_type __flags) const
{
    bool __r = false;
    if (__start_)
    {
        __m.__init(1 + mark_count(), __first, __last);
        for (; __first != __last; ++__first)
        {
            __start_->__reset_state();
            unsigned __begin_sub = 0;
            unsigned __end_sub = 0;
            bool __consume;
            __state<_CharT>* __st = __start_->__test(*__first, __consume,
                                                     __begin_sub, __end_sub);
            if (__st)
            {
                _BidirectionalIterator& __f = __m.__matches_[0].first;
                _BidirectionalIterator& __l = __m.__matches_[0].second;
                __f = __l = __first;
                if (__begin_sub != 0)
                    __m.__matches_[__begin_sub].first = __l;
                if (__end_sub != 0)
                {
                    __m.__matches_[__end_sub].second = __l;
                    __m.__matches_[__end_sub].matched = true;
                }
                if (__consume)
                    ++__l;
                while (__l != __last && __st != __end_)
                {
                    __begin_sub = 0;
                    __end_sub = 0;
                    __st = __st->__test(*__l, __consume, __begin_sub, __end_sub);
                    if (__st == nullptr)
                        break;
                    if (__begin_sub != 0)
                        __m.__matches_[__begin_sub].first = __l;
                    if (__end_sub != 0)
                    {
                        __m.__matches_[__end_sub].second = __l;
                        __m.__matches_[__end_sub].matched = true;
                    }
                    if (__consume)
                        ++__l;
                }
                if (__st == __end_)
                {
                    __r = __m.__matches_[0].matched = true;
                    __m.__prefix_.second = __first;
                    __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
                    __m.__suffix_.first = __l;
                    __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
                    break;
                }
                __m.__matches_.assign(__m.__matches_.size(), __m.__unmatched_);
            }
            if (__flags & regex_constants::match_continuous)
                break;
        }
    }
    if (!__r)
        __m.__matches_.clear();
    return __r;
}

template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>
inline _LIBCPP_INLINE_VISIBILITY
bool
regex_search(_BidirectionalIterator __first, _BidirectionalIterator __last,
             match_results<_BidirectionalIterator, _Allocator>& __m,
             const basic_regex<_CharT, _Traits>& __e,
             regex_constants::match_flag_type __flags = regex_constants::match_default)
{
    return __e.__search(__first, __last, __m, __flags);
}

template <class _BidirectionalIterator, class _CharT, class _Traits>
inline _LIBCPP_INLINE_VISIBILITY
bool
regex_search(_BidirectionalIterator __first, _BidirectionalIterator __last,
             const basic_regex<_CharT, _Traits>& __e,
             regex_constants::match_flag_type __flags = regex_constants::match_default)
{
    match_results<_BidirectionalIterator> __m;
    return _STD::regex_search(__first, __last, __m, __e, __flags);
}

template <class _CharT, class _Allocator, class _Traits>
inline _LIBCPP_INLINE_VISIBILITY
bool
regex_search(const _CharT* __str, match_results<const _CharT*, _Allocator>& __m,
             const basic_regex<_CharT, _Traits>& __e,
             regex_constants::match_flag_type __flags = regex_constants::match_default)
{
    return _STD::regex_search(__str, __str + _Traits::length(__str), __m, __e, __flags);
}

template <class _CharT, class _Traits>
inline _LIBCPP_INLINE_VISIBILITY
bool
regex_search(const _CharT* __str, const basic_regex<_CharT, _Traits>& __e,
             regex_constants::match_flag_type __flags = regex_constants::match_default)
{
    return _STD::regex_search(__str, __str + _Traits::length(__str), __e, __flags);
}

template <class _ST, class _SA, class _CharT, class _Traits>
inline _LIBCPP_INLINE_VISIBILITY
bool
regex_search(const basic_string<_CharT, _ST, _SA>& __s,
             const basic_regex<_CharT, _Traits>& __e,
             regex_constants::match_flag_type __flags = regex_constants::match_default)
{
    return _STD::regex_search(__s.begin(), __s.end(), __e, __flags);
}

template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
inline _LIBCPP_INLINE_VISIBILITY
bool
regex_search(const basic_string<_CharT, _ST, _SA>& __s,
             match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
             const basic_regex<_CharT, _Traits>& __e,
             regex_constants::match_flag_type __flags = regex_constants::match_default)
{
    return _STD::regex_search(__s.begin(), __s.end(), __m, __e, __flags);
}

// regex_match

template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>
bool
regex_match(_BidirectionalIterator __first, _BidirectionalIterator __last,
            match_results<_BidirectionalIterator, _Allocator>& __m,
            const basic_regex<_CharT, _Traits>& __e,
            regex_constants::match_flag_type __flags = regex_constants::match_default)
{
    bool __r = _STD::regex_search(__first, __last, __m, __e,
                            __flags | regex_constants::match_continuous);
    if (__r)
    {
        __r = !__m.suffix().matched;
        if (!__r)
            __m.__matches_.clear();
    }
    return __r;
}

template <class _BidirectionalIterator, class _CharT, class _Traits>
inline _LIBCPP_INLINE_VISIBILITY
bool
regex_match(_BidirectionalIterator __first, _BidirectionalIterator __last,
            const basic_regex<_CharT, _Traits>& __e,
            regex_constants::match_flag_type __flags = regex_constants::match_default)
{
    match_results<_BidirectionalIterator> __m;
    return _STD::regex_match(__first, __last, __m, __e, __flags);
}

template <class _CharT, class _Allocator, class _Traits>
inline _LIBCPP_INLINE_VISIBILITY
bool
regex_match(const _CharT* __str, match_results<const _CharT*, _Allocator>& __m,
            const basic_regex<_CharT, _Traits>& __e,
            regex_constants::match_flag_type __flags = regex_constants::match_default)
{
    return _STD::regex_match(__str, __str + _Traits::length(__str), __m, __e, __flags);
}

template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
inline _LIBCPP_INLINE_VISIBILITY
bool
regex_match(const basic_string<_CharT, _ST, _SA>& __s,
            match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
            const basic_regex<_CharT, _Traits>& __e,
            regex_constants::match_flag_type __flags = regex_constants::match_default)
{
    return _STD::regex_match(__s.begin(), __s.end(), __m, __e, __flags);
}

template <class _CharT, class _Traits>
inline _LIBCPP_INLINE_VISIBILITY
bool
regex_match(const _CharT* __str, const basic_regex<_CharT, _Traits>& __e,
            regex_constants::match_flag_type __flags = regex_constants::match_default)
{
    return _STD::regex_match(__str, __str + _Traits::length(__str), __e, __flags);
}

template <class _ST, class _SA, class _CharT, class _Traits>
inline _LIBCPP_INLINE_VISIBILITY
bool
regex_match(const basic_string<_CharT, _ST, _SA>& __s,
            const basic_regex<_CharT, _Traits>& __e,
            regex_constants::match_flag_type __flags = regex_constants::match_default)
{
    return _STD::regex_match(__s.begin(), __s.end(), __e, __flags);
}

_LIBCPP_END_NAMESPACE_STD

#endif  // _LIBCPP_REGEX