1// class template regex -*- C++ -*-
2
3// Copyright (C) 2007-2020 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25/**
26 * @file tr1/regex
27 * @author Stephen M. Webb  <stephen.webb@bregmasoft.ca>
28 * This is a TR1 C++ Library header.
29 */
30
31#ifndef _GLIBCXX_TR1_REGEX
32#define _GLIBCXX_TR1_REGEX 1
33
34#pragma GCC system_header
35
36#include <algorithm>
37#include <bitset>
38#include <iterator>
39#include <locale>
40#include <stdexcept>
41#include <string>
42#include <vector>
43#include <utility>
44#include <sstream>
45
46namespace std _GLIBCXX_VISIBILITY(default)
47{
48_GLIBCXX_BEGIN_NAMESPACE_VERSION
49
50namespace tr1
51{
52/**
53 * @defgroup tr1_regex Regular Expressions
54 * A facility for performing regular expression pattern matching.
55 */
56 ///@{
57
58/** @namespace std::regex_constants
59 *  @brief ISO C++ 0x entities sub namespace for regex.
60 */
61namespace regex_constants
62{
63  /**
64   * @name 5.1 Regular Expression Syntax Options
65   */
66  ///@{
67  enum __syntax_option
68    {
69      _S_icase,
70      _S_nosubs,
71      _S_optimize,
72      _S_collate,
73      _S_ECMAScript,
74      _S_basic,
75      _S_extended,
76      _S_awk,
77      _S_grep,
78      _S_egrep,
79      _S_syntax_last
80    };
81
82  /**
83   * @brief This is a bitmask type indicating how to interpret the regex.
84   *
85   * The @c syntax_option_type is implementation defined but it is valid to
86   * perform bitwise operations on these values and expect the right thing to
87   * happen.
88   *
89   * A valid value of type syntax_option_type shall have exactly one of the
90   * elements @c ECMAScript, @c basic, @c extended, @c awk, @c grep, @c egrep
91   * %set.
92   */
93  typedef unsigned int syntax_option_type;
94
95  /**
96   * Specifies that the matching of regular expressions against a character
97   * sequence shall be performed without regard to case.
98   */
99  static const syntax_option_type icase      = 1 << _S_icase;
100
101  /**
102   * Specifies that when a regular expression is matched against a character
103   * container sequence, no sub-expression matches are to be stored in the
104   * supplied match_results structure.
105   */
106  static const syntax_option_type nosubs     = 1 << _S_nosubs;
107
108  /**
109   * Specifies that the regular expression engine should pay more attention to
110   * the speed with which regular expressions are matched, and less to the
111   * speed with which regular expression objects are constructed. Otherwise
112   * it has no detectable effect on the program output.
113   */
114  static const syntax_option_type optimize   = 1 << _S_optimize;
115
116  /**
117   * Specifies that character ranges of the form [a-b] should be locale
118   * sensitive.
119   */
120  static const syntax_option_type collate    = 1 << _S_collate;
121
122  /**
123   * Specifies that the grammar recognized by the regular expression engine is
124   * that used by ECMAScript in ECMA-262 [Ecma International, ECMAScript
125   * Language Specification, Standard Ecma-262, third edition, 1999], as
126   * modified in tr1 section [7.13].  This grammar is similar to that defined
127   * in the PERL scripting language but extended with elements found in the
128   * POSIX regular expression grammar.
129   */
130  static const syntax_option_type ECMAScript = 1 << _S_ECMAScript;
131
132  /**
133   * Specifies that the grammar recognized by the regular expression engine is
134   * that used by POSIX basic regular expressions in IEEE Std 1003.1-2001,
135   * Portable Operating System Interface (POSIX), Base Definitions and
136   * Headers, Section 9, Regular Expressions [IEEE, Information Technology --
137   * Portable Operating System Interface (POSIX), IEEE Standard 1003.1-2001].
138   */
139  static const syntax_option_type basic      = 1 << _S_basic;
140
141  /**
142   * Specifies that the grammar recognized by the regular expression engine is
143   * that used by POSIX extended regular expressions in IEEE Std 1003.1-2001,
144   * Portable Operating System Interface (POSIX), Base Definitions and Headers,
145   * Section 9, Regular Expressions.
146   */
147  static const syntax_option_type extended   = 1 << _S_extended;
148
149  /**
150   * Specifies that the grammar recognized by the regular expression engine is
151   * that used by POSIX utility awk in IEEE Std 1003.1-2001.  This option is
152   * identical to syntax_option_type extended, except that C-style escape
153   * sequences are supported.  These sequences are:
154   * \\\\, \\a, \\b, \\f,
155   * \\n, \\r, \\t , \\v,
156   * \\&apos;, &apos;, and \\ddd
157   * (where ddd is one, two, or three octal digits).
158   */
159  static const syntax_option_type awk        = 1 << _S_awk;
160
161  /**
162   * Specifies that the grammar recognized by the regular expression engine is
163   * that used by POSIX utility grep in IEEE Std 1003.1-2001.  This option is
164   * identical to syntax_option_type basic, except that newlines are treated
165   * as whitespace.
166   */
167  static const syntax_option_type grep       = 1 << _S_grep;
168
169  /**
170   * Specifies that the grammar recognized by the regular expression engine is
171   * that used by POSIX utility grep when given the -E option in
172   * IEEE Std 1003.1-2001.  This option is identical to syntax_option_type
173   * extended, except that newlines are treated as whitespace.
174   */
175  static const syntax_option_type egrep      = 1 << _S_egrep;
176
177  ///@}
178
179  /**
180   * @name 5.2 Matching Rules
181   *
182   * Matching a regular expression against a sequence of characters [first,
183   * last) proceeds according to the rules of the grammar specified for the
184   * regular expression object, modified according to the effects listed
185   * below for any bitmask elements set.
186   *
187   */
188  ///@{
189
190  enum __match_flag
191    {
192      _S_not_bol,
193      _S_not_eol,
194      _S_not_bow,
195      _S_not_eow,
196      _S_any,
197      _S_not_null,
198      _S_continuous,
199      _S_prev_avail,
200      _S_sed,
201      _S_no_copy,
202      _S_first_only,
203      _S_match_flag_last
204    };
205
206  /**
207   * @brief This is a bitmask type indicating regex matching rules.
208   *
209   * The @c match_flag_type is implementation defined but it is valid to
210   * perform bitwise operations on these values and expect the right thing to
211   * happen.
212   */
213  typedef std::bitset<_S_match_flag_last> match_flag_type;
214
215  /**
216   * The default matching rules.
217   */
218  static const match_flag_type match_default     = 0;
219
220  /**
221   * The first character in the sequence [first, last) is treated as though it
222   * is not at the beginning of a line, so the character (^) in the regular
223   * expression shall not match [first, first).
224   */
225  static const match_flag_type match_not_bol     = 1 << _S_not_bol;
226
227  /**
228   * The last character in the sequence [first, last) is treated as though it
229   * is not at the end of a line, so the character ($) in the regular
230   * expression shall not match [last, last).
231   */
232  static const match_flag_type match_not_eol     = 1 << _S_not_eol;
233
234  /**
235   * The expression \\b is not matched against the sub-sequence
236   * [first,first).
237   */
238  static const match_flag_type match_not_bow     = 1 << _S_not_bow;
239
240  /**
241   * The expression \\b should not be matched against the sub-sequence
242   * [last,last).
243   */
244  static const match_flag_type match_not_eow     = 1 << _S_not_eow;
245
246  /**
247   * If more than one match is possible then any match is an acceptable
248   * result.
249   */
250  static const match_flag_type match_any         = 1 << _S_any;
251
252  /**
253   * The expression does not match an empty sequence.
254   */
255  static const match_flag_type match_not_null    = 1 << _S_not_null;
256
257  /**
258   * The expression only matches a sub-sequence that begins at first .
259   */
260  static const match_flag_type match_continuous  = 1 << _S_continuous;
261
262  /**
263   * --first is a valid iterator position.  When this flag is set then the
264   * flags match_not_bol and match_not_bow are ignored by the regular
265   * expression algorithms 7.11 and iterators 7.12.
266   */
267  static const match_flag_type match_prev_avail  = 1 << _S_prev_avail;
268
269  /**
270   * When a regular expression match is to be replaced by a new string, the
271   * new string is constructed using the rules used by the ECMAScript replace
272   * function in ECMA- 262 [Ecma International, ECMAScript Language
273   * Specification, Standard Ecma-262, third edition, 1999], part 15.5.4.11
274   * String.prototype.replace. In addition, during search and replace
275   * operations all non-overlapping occurrences of the regular expression
276   * are located and replaced, and sections of the input that did not match
277   * the expression are copied unchanged to the output string.
278   *
279   * Format strings (from ECMA-262 [15.5.4.11]):
280   * @li $$  The dollar-sign itself ($)
281   * @li $&  The matched substring.
282   * @li $`  The portion of @a string that precedes the matched substring.
283   *         This would be match_results::prefix().
284   * @li $'  The portion of @a string that follows the matched substring.
285   *         This would be match_results::suffix().
286   * @li $n  The nth capture, where n is in [1,9] and $n is not followed by a
287   *         decimal digit.  If n <= match_results::size() and the nth capture
288   *         is undefined, use the empty string instead.  If n >
289   *         match_results::size(), the result is implementation-defined.
290   * @li $nn The nnth capture, where nn is a two-digit decimal number on
291   *         [01, 99].  If nn <= match_results::size() and the nth capture is
292   *         undefined, use the empty string instead. If
293   *         nn > match_results::size(), the result is implementation-defined.
294   */
295  static const match_flag_type format_default    = 0;
296
297  /**
298   * When a regular expression match is to be replaced by a new string, the
299   * new string is constructed using the rules used by the POSIX sed utility
300   * in IEEE Std 1003.1- 2001 [IEEE, Information Technology -- Portable
301   * Operating System Interface (POSIX), IEEE Standard 1003.1-2001].
302   */
303  static const match_flag_type format_sed        = 1 << _S_sed;
304
305  /**
306   * During a search and replace operation, sections of the character
307   * container sequence being searched that do not match the regular
308   * expression shall not be copied to the output string.
309   */
310  static const match_flag_type format_no_copy    = 1 << _S_no_copy;
311
312  /**
313   * When specified during a search and replace operation, only the first
314   * occurrence of the regular expression shall be replaced.
315   */
316  static const match_flag_type format_first_only = 1 << _S_first_only;
317
318  ///@}
319
320  /**
321   * @name 5.3 Error Types
322   */
323  ///@{
324
325  enum error_type
326    {
327      _S_error_collate,
328      _S_error_ctype,
329      _S_error_escape,
330      _S_error_backref,
331      _S_error_brack,
332      _S_error_paren,
333      _S_error_brace,
334      _S_error_badbrace,
335      _S_error_range,
336      _S_error_space,
337      _S_error_badrepeat,
338      _S_error_complexity,
339      _S_error_stack,
340      _S_error_last
341    };
342
343  /** The expression contained an invalid collating element name. */
344  static const error_type error_collate(_S_error_collate);
345
346  /** The expression contained an invalid character class name. */
347  static const error_type error_ctype(_S_error_ctype);
348
349  /**
350   * The expression contained an invalid escaped character, or a trailing
351   * escape.
352   */
353  static const error_type error_escape(_S_error_escape);
354
355  /** The expression contained an invalid back reference. */
356  static const error_type error_backref(_S_error_backref);
357
358  /** The expression contained mismatched [ and ]. */
359  static const error_type error_brack(_S_error_brack);
360
361  /** The expression contained mismatched ( and ). */
362  static const error_type error_paren(_S_error_paren);
363
364  /** The expression contained mismatched { and } */
365  static const error_type error_brace(_S_error_brace);
366
367  /** The expression contained an invalid range in a {} expression. */
368  static const error_type error_badbrace(_S_error_badbrace);
369
370  /**
371   * The expression contained an invalid character range,
372   * such as [b-a] in most encodings.
373   */
374  static const error_type error_range(_S_error_range);
375
376  /**
377   * There was insufficient memory to convert the expression into a
378   * finite state machine.
379   */
380  static const error_type error_space(_S_error_space);
381
382  /**
383   * One of <em>*?+{</em> was not preceded by a valid regular expression.
384   */
385  static const error_type error_badrepeat(_S_error_badrepeat);
386
387  /**
388   * The complexity of an attempted match against a regular expression
389   * exceeded a pre-set level.
390   */
391  static const error_type error_complexity(_S_error_complexity);
392
393  /**
394   * There was insufficient memory to determine whether the
395   * regular expression could match the specified character sequence.
396   */
397  static const error_type error_stack(_S_error_stack);
398
399  ///@}
400}
401
402  // [7.8] Class regex_error
403  /**
404   *  @brief A regular expression exception class.
405   *  @ingroup exceptions
406   *
407   *  The regular expression library throws objects of this class on error.
408   */
409  class regex_error
410  : public std::runtime_error
411  {
412  public:
413    /**
414     * @brief Constructs a regex_error object.
415     *
416     * @param ecode the regex error code.
417     */
418    explicit
419    regex_error(regex_constants::error_type __ecode)
420    : std::runtime_error("regex_error"), _M_code(__ecode)
421    { }
422
423    /**
424     * @brief Gets the regex error code.
425     *
426     * @returns the regex error code.
427     */
428    regex_constants::error_type
429    code() const
430    { return _M_code; }
431
432  protected:
433    regex_constants::error_type _M_code;
434  };
435
436  // [7.7] Class regex_traits
437  /**
438   * @brief Describes aspects of a regular expression.
439   *
440   * A regular expression traits class that satisfies the requirements of tr1
441   * section [7.2].
442   *
443   * The class %regex is parameterized around a set of related types and
444   * functions used to complete the definition of its semantics.  This class
445   * satisfies the requirements of such a traits class.
446   */
447  template<typename _Ch_type>
448    struct regex_traits
449    {
450    public:
451      typedef _Ch_type                     char_type;
452      typedef std::basic_string<char_type> string_type;
453      typedef std::locale                  locale_type;
454      typedef std::ctype_base::mask        char_class_type;
455
456    public:
457      /**
458       * @brief Constructs a default traits object.
459       */
460      regex_traits()
461      { }
462
463      /**
464       * @brief Gives the length of a C-style string starting at @p __p.
465       *
466       * @param __p a pointer to the start of a character sequence.
467       *
468       * @returns the number of characters between @p *__p and the first
469       * default-initialized value of type @p char_type.  In other words, uses
470       * the C-string algorithm for determining the length of a sequence of
471       * characters.
472       */
473      static std::size_t
474      length(const char_type* __p)
475      { return string_type::traits_type::length(__p); }
476
477      /**
478       * @brief Performs the identity translation.
479       *
480       * @param c A character to the locale-specific character set.
481       *
482       * @returns c.
483       */
484      char_type
485      translate(char_type __c) const
486      { return __c; }
487
488      /**
489       * @brief Translates a character into a case-insensitive equivalent.
490       *
491       * @param c A character to the locale-specific character set.
492       *
493       * @returns the locale-specific lower-case equivalent of c.
494       * @throws std::bad_cast if the imbued locale does not support the ctype
495       *         facet.
496       */
497      char_type
498      translate_nocase(char_type __c) const
499      {
500	using std::ctype;
501	using std::use_facet;
502	return use_facet<ctype<char_type> >(_M_locale).tolower(__c);
503      }
504
505      /**
506       * @brief Gets a sort key for a character sequence.
507       *
508       * @param first beginning of the character sequence.
509       * @param last  one-past-the-end of the character sequence.
510       *
511       * Returns a sort key for the character sequence designated by the
512       * iterator range [F1, F2) such that if the character sequence [G1, G2)
513       * sorts before the character sequence [H1, H2) then
514       * v.transform(G1, G2) < v.transform(H1, H2).
515       *
516       * What this really does is provide a more efficient way to compare a
517       * string to multiple other strings in locales with fancy collation
518       * rules and equivalence classes.
519       *
520       * @returns a locale-specific sort key equivalent to the input range.
521       *
522       * @throws std::bad_cast if the current locale does not have a collate
523       *         facet.
524       */
525      template<typename _Fwd_iter>
526        string_type
527        transform(_Fwd_iter __first, _Fwd_iter __last) const
528        {
529	  using std::collate;
530	  using std::use_facet;
531	  const collate<_Ch_type>& __c(use_facet<
532				       collate<_Ch_type> >(_M_locale));
533	  string_type __s(__first, __last);
534	  return __c.transform(__s.data(), __s.data() + __s.size());
535	}
536
537      /**
538       * @brief Dunno.
539       *
540       * @param first beginning of the character sequence.
541       * @param last  one-past-the-end of the character sequence.
542       *
543       * Effects: if typeid(use_facet<collate<_Ch_type> >) ==
544       * typeid(collate_byname<_Ch_type>) and the form of the sort key
545       * returned by collate_byname<_Ch_type>::transform(first, last) is known
546       * and can be converted into a primary sort key then returns that key,
547       * otherwise returns an empty string. WTF??
548       *
549       * @todo Implement this function.
550       */
551      template<typename _Fwd_iter>
552        string_type
553        transform_primary(_Fwd_iter __first, _Fwd_iter __last) const;
554
555      /**
556       * @brief Gets a collation element by name.
557       *
558       * @param first beginning of the collation element name.
559       * @param last  one-past-the-end of the collation element name.
560       *
561       * @returns a sequence of one or more characters that represents the
562       * collating element consisting of the character sequence designated by
563       * the iterator range [first, last). Returns an empty string if the
564       * character sequence is not a valid collating element.
565       *
566       * @todo Implement this function.
567       */
568      template<typename _Fwd_iter>
569        string_type
570        lookup_collatename(_Fwd_iter __first, _Fwd_iter __last) const;
571
572      /**
573       * @brief Maps one or more characters to a named character
574       *        classification.
575       *
576       * @param first beginning of the character sequence.
577       * @param last  one-past-the-end of the character sequence.
578       *
579       * @returns an unspecified value that represents the character
580       * classification named by the character sequence designated by the
581       * iterator range [first, last). The value returned shall be independent
582       * of the case of the characters in the character sequence. If the name
583       * is not recognized then returns a value that compares equal to 0.
584       *
585       * At least the following names (or their wide-character equivalent) are
586       * supported.
587       * - d
588       * - w
589       * - s
590       * - alnum
591       * - alpha
592       * - blank
593       * - cntrl
594       * - digit
595       * - graph
596       * - lower
597       * - print
598       * - punct
599       * - space
600       * - upper
601       * - xdigit
602       *
603       * @todo Implement this function.
604       */
605      template<typename _Fwd_iter>
606        char_class_type
607        lookup_classname(_Fwd_iter __first, _Fwd_iter __last) const;
608
609      /**
610       * @brief Determines if @p c is a member of an identified class.
611       *
612       * @param c a character.
613       * @param f a class type (as returned from lookup_classname).
614       *
615       * @returns true if the character @p c is a member of the classification
616       * represented by @p f, false otherwise.
617       *
618       * @throws std::bad_cast if the current locale does not have a ctype
619       *         facet.
620       */
621      bool
622      isctype(_Ch_type __c, char_class_type __f) const;
623
624      /**
625       * @brief Converts a digit to an int.
626       *
627       * @param ch    a character representing a digit.
628       * @param radix the radix if the numeric conversion (limited to 8, 10,
629       *              or 16).
630       *
631       * @returns the value represented by the digit ch in base radix if the
632       * character ch is a valid digit in base radix; otherwise returns -1.
633       */
634      int
635      value(_Ch_type __ch, int __radix) const;
636
637      /**
638       * @brief Imbues the regex_traits object with a copy of a new locale.
639       *
640       * @param loc A locale.
641       *
642       * @returns a copy of the previous locale in use by the regex_traits
643       *          object.
644       *
645       * @note Calling imbue with a different locale than the one currently in
646       *       use invalidates all cached data held by *this.
647       */
648      locale_type
649      imbue(locale_type __loc)
650      {
651	std::swap(_M_locale, __loc);
652	return __loc;
653      }
654
655      /**
656       * @brief Gets a copy of the current locale in use by the regex_traits
657       * object.
658       */
659      locale_type
660      getloc() const
661      { return _M_locale; }
662
663    protected:
664      locale_type _M_locale;
665    };
666
667  template<typename _Ch_type>
668    bool regex_traits<_Ch_type>::
669    isctype(_Ch_type __c, char_class_type __f) const
670    {
671      using std::ctype;
672      using std::use_facet;
673      const ctype<_Ch_type>& __ctype(use_facet<
674				     ctype<_Ch_type> >(_M_locale));
675
676      if (__ctype.is(__c, __f))
677	return true;
678#if 0
679      // special case of underscore in [[:w:]]
680      if (__c == __ctype.widen('_'))
681	{
682	  const char* const __wb[] = "w";
683	  char_class_type __wt = this->lookup_classname(__wb,
684							__wb + sizeof(__wb));
685	  if (__f | __wt)
686	    return true;
687	}
688
689      // special case of [[:space:]] in [[:blank:]]
690      if (__c == __ctype.isspace(__c))
691	{
692	  const char* const __bb[] = "blank";
693	  char_class_type __bt = this->lookup_classname(__bb,
694							__bb + sizeof(__bb));
695	  if (__f | __bt)
696	    return true;
697	}
698#endif
699      return false;
700    }
701
702  template<typename _Ch_type>
703    int regex_traits<_Ch_type>::
704    value(_Ch_type __ch, int __radix) const
705    {
706      std::basic_istringstream<_Ch_type> __is(string_type(1, __ch));
707      int __v;
708      if (__radix == 8)
709	__is >> std::oct;
710      else if (__radix == 16)
711	__is >> std::hex;
712      __is >> __v;
713      return __is.fail() ? -1 : __v;
714    }
715
716  // [7.8] Class basic_regex
717  /**
718   * Objects of specializations of this class represent regular expressions
719   * constructed from sequences of character type @p _Ch_type.
720   *
721   * Storage for the regular expression is allocated and deallocated as
722   * necessary by the member functions of this class.
723   */
724  template<typename _Ch_type, typename _Rx_traits = regex_traits<_Ch_type> >
725    class basic_regex
726    {
727    public:
728      // types:
729      typedef _Ch_type                              value_type;
730      typedef regex_constants::syntax_option_type flag_type;
731      typedef typename _Rx_traits::locale_type  locale_type;
732      typedef typename _Rx_traits::string_type  string_type;
733
734      /**
735       * @name Constants
736       * tr1 [7.8.1] std [28.8.1]
737       */
738      ///@{
739      static const regex_constants::syntax_option_type icase
740        = regex_constants::icase;
741      static const regex_constants::syntax_option_type nosubs
742        = regex_constants::nosubs;
743      static const regex_constants::syntax_option_type optimize
744        = regex_constants::optimize;
745      static const regex_constants::syntax_option_type collate
746        = regex_constants::collate;
747      static const regex_constants::syntax_option_type ECMAScript
748        = regex_constants::ECMAScript;
749      static const regex_constants::syntax_option_type basic
750        = regex_constants::basic;
751      static const regex_constants::syntax_option_type extended
752        = regex_constants::extended;
753      static const regex_constants::syntax_option_type awk
754        = regex_constants::awk;
755      static const regex_constants::syntax_option_type grep
756        = regex_constants::grep;
757      static const regex_constants::syntax_option_type egrep
758        = regex_constants::egrep;
759      ///@}
760
761      // [7.8.2] construct/copy/destroy
762      /**
763       * Constructs a basic regular expression that does not match any
764       * character sequence.
765       */
766      basic_regex()
767      : _M_flags(regex_constants::ECMAScript), _M_pattern(), _M_mark_count(0)
768      { _M_compile(); }
769
770      /**
771       * @brief Constructs a basic regular expression from the sequence
772       * [p, p + char_traits<_Ch_type>::length(p)) interpreted according to the
773       * flags in @p f.
774       *
775       * @param p A pointer to the start of a C-style null-terminated string
776       *          containing a regular expression.
777       * @param f Flags indicating the syntax rules and options.
778       *
779       * @throws regex_error if @p p is not a valid regular expression.
780       */
781      explicit
782      basic_regex(const _Ch_type* __p,
783		  flag_type __f = regex_constants::ECMAScript)
784      : _M_flags(__f), _M_pattern(__p), _M_mark_count(0)
785      { _M_compile(); }
786
787      /**
788       * @brief Constructs a basic regular expression from the sequence
789       * [p, p + len) interpreted according to the flags in @p f.
790       *
791       * @param p   A pointer to the start of a string containing a regular
792       *            expression.
793       * @param len The length of the string containing the regular expression.
794       * @param f   Flags indicating the syntax rules and options.
795       *
796       * @throws regex_error if @p p is not a valid regular expression.
797       */
798      basic_regex(const _Ch_type* __p, std::size_t __len, flag_type __f)
799      : _M_flags(__f) , _M_pattern(__p, __len), _M_mark_count(0)
800      { _M_compile(); }
801
802      /**
803       * @brief Copy-constructs a basic regular expression.
804       *
805       * @param rhs A @p regex object.
806     */
807      basic_regex(const basic_regex& __rhs)
808      : _M_flags(__rhs._M_flags), _M_pattern(__rhs._M_pattern),
809	_M_mark_count(__rhs._M_mark_count)
810      { _M_compile(); }
811
812      /**
813       * @brief Constructs a basic regular expression from the string
814       * @p s interpreted according to the flags in @p f.
815       *
816       * @param s A string containing a regular expression.
817       * @param f Flags indicating the syntax rules and options.
818       *
819       * @throws regex_error if @p s is not a valid regular expression.
820       */
821      template<typename _Ch_traits, typename _Ch_alloc>
822        explicit
823        basic_regex(const basic_string<_Ch_type, _Ch_traits, _Ch_alloc>& __s,
824		    flag_type __f = regex_constants::ECMAScript)
825	: _M_flags(__f), _M_pattern(__s.begin(), __s.end()), _M_mark_count(0)
826        { _M_compile(); }
827
828      /**
829       * @brief Constructs a basic regular expression from the range
830       * [first, last) interpreted according to the flags in @p f.
831       *
832       * @param first The start of a range containing a valid regular
833       *              expression.
834       * @param last  The end of a range containing a valid regular
835       *              expression.
836       * @param f     The format flags of the regular expression.
837       *
838       * @throws regex_error if @p [first, last) is not a valid regular
839       *         expression.
840       */
841      template<typename _InputIterator>
842        basic_regex(_InputIterator __first, _InputIterator __last,
843		    flag_type __f = regex_constants::ECMAScript)
844	: _M_flags(__f), _M_pattern(__first, __last), _M_mark_count(0)
845        { _M_compile(); }
846
847#ifdef _GLIBCXX_INCLUDE_AS_CXX11
848      /**
849       * @brief Constructs a basic regular expression from an initializer list.
850       *
851       * @param l  The initializer list.
852       * @param f  The format flags of the regular expression.
853       *
854       * @throws regex_error if @p l is not a valid regular expression.
855       */
856      basic_regex(initializer_list<_Ch_type> __l,
857		  flag_type __f = regex_constants::ECMAScript)
858	: _M_flags(__f), _M_pattern(__l.begin(), __l.end()), _M_mark_count(0)
859        { _M_compile(); }
860#endif
861
862      /**
863       * @brief Destroys a basic regular expression.
864       */
865      ~basic_regex()
866      { }
867
868      /**
869       * @brief Assigns one regular expression to another.
870       */
871      basic_regex&
872      operator=(const basic_regex& __rhs)
873      { return this->assign(__rhs); }
874
875      /**
876       * @brief Replaces a regular expression with a new one constructed from
877       * a C-style null-terminated string.
878       *
879       * @param A pointer to the start of a null-terminated C-style string
880       *        containing a regular expression.
881       */
882      basic_regex&
883      operator=(const _Ch_type* __p)
884      { return this->assign(__p, flags()); }
885
886      /**
887       * @brief Replaces a regular expression with a new one constructed from
888       * a string.
889       *
890       * @param A pointer to a string containing a regular expression.
891       */
892      template<typename _Ch_typeraits, typename _Allocator>
893        basic_regex&
894        operator=(const basic_string<_Ch_type, _Ch_typeraits, _Allocator>& __s)
895        { return this->assign(__s, flags()); }
896
897      // [7.8.3] assign
898      /**
899       * @brief the real assignment operator.
900       *
901       * @param that Another regular expression object.
902       */
903      basic_regex&
904      assign(const basic_regex& __that)
905      {
906	basic_regex __tmp(__that);
907	this->swap(__tmp);
908	return *this;
909      }
910
911      /**
912       * @brief Assigns a new regular expression to a regex object from a
913       * C-style null-terminated string containing a regular expression
914       * pattern.
915       *
916       * @param p     A pointer to a C-style null-terminated string containing
917       *              a regular expression pattern.
918       * @param flags Syntax option flags.
919       *
920       * @throws regex_error if p does not contain a valid regular expression
921       * pattern interpreted according to @p flags.  If regex_error is thrown,
922       * *this remains unchanged.
923       */
924      basic_regex&
925      assign(const _Ch_type* __p,
926	     flag_type __flags = regex_constants::ECMAScript)
927      { return this->assign(string_type(__p), __flags); }
928
929      /**
930       * @brief Assigns a new regular expression to a regex object from a
931       * C-style string containing a regular expression pattern.
932       *
933       * @param p     A pointer to a C-style string containing a
934       *              regular expression pattern.
935       * @param len   The length of the regular expression pattern string.
936       * @param flags Syntax option flags.
937       *
938       * @throws regex_error if p does not contain a valid regular expression
939       * pattern interpreted according to @p flags.  If regex_error is thrown,
940       * *this remains unchanged.
941       */
942      basic_regex&
943      assign(const _Ch_type* __p, std::size_t __len, flag_type __flags)
944      { return this->assign(string_type(__p, __len), __flags); }
945
946      /**
947       * @brief Assigns a new regular expression to a regex object from a
948       * string containing a regular expression pattern.
949       *
950       * @param s     A string containing a regular expression pattern.
951       * @param flags Syntax option flags.
952       *
953       * @throws regex_error if p does not contain a valid regular expression
954       * pattern interpreted according to @p flags.  If regex_error is thrown,
955       * *this remains unchanged.
956       */
957      template<typename _Ch_typeraits, typename _Allocator>
958        basic_regex&
959        assign(const basic_string<_Ch_type, _Ch_typeraits, _Allocator>& __s,
960	       flag_type __f = regex_constants::ECMAScript)
961        {
962	  basic_regex __tmp(__s, __f);
963	  this->swap(__tmp);
964	  return *this;
965	}
966
967      /**
968       * @brief Assigns a new regular expression to a regex object.
969       *
970       * @param first The start of a range containing a valid regular
971       *              expression.
972       * @param last  The end of a range containing a valid regular
973       *              expression.
974       * @param flags Syntax option flags.
975       *
976       * @throws regex_error if p does not contain a valid regular expression
977       * pattern interpreted according to @p flags.  If regex_error is thrown,
978       * the object remains unchanged.
979       */
980      template<typename _InputIterator>
981        basic_regex&
982        assign(_InputIterator __first, _InputIterator __last,
983	       flag_type __flags = regex_constants::ECMAScript)
984        { return this->assign(string_type(__first, __last), __flags); }
985
986#ifdef _GLIBCXX_INCLUDE_AS_CXX11
987      /**
988       * @brief Assigns a new regular expression to a regex object.
989       *
990       * @param l     An initializer list representing a regular expression.
991       * @param flags Syntax option flags.
992       *
993       * @throws regex_error if @p l does not contain a valid regular
994       * expression pattern interpreted according to @p flags.  If regex_error
995       * is thrown, the object remains unchanged.
996       */
997      basic_regex&
998      assign(initializer_list<_Ch_type> __l,
999	     flag_type __f = regex_constants::ECMAScript)
1000      { return this->assign(__l.begin(), __l.end(), __f); }
1001#endif
1002
1003      // [7.8.4] const operations
1004      /**
1005       * @brief Gets the number of marked subexpressions within the regular
1006       * expression.
1007       */
1008      unsigned int
1009      mark_count() const
1010      { return _M_mark_count; }
1011
1012      /**
1013       * @brief Gets the flags used to construct the regular expression
1014       * or in the last call to assign().
1015       */
1016      flag_type
1017      flags() const
1018      { return _M_flags; }
1019
1020      // [7.8.5] locale
1021      /**
1022       * @brief Imbues the regular expression object with the given locale.
1023       *
1024       * @param loc A locale.
1025       */
1026      locale_type
1027      imbue(locale_type __loc)
1028      { return _M_traits.imbue(__loc); }
1029
1030      /**
1031       * @brief Gets the locale currently imbued in the regular expression
1032       *        object.
1033       */
1034      locale_type
1035      getloc() const
1036      { return _M_traits.getloc(); }
1037
1038      // [7.8.6] swap
1039      /**
1040       * @brief Swaps the contents of two regular expression objects.
1041       *
1042       * @param rhs Another regular expression object.
1043       */
1044      void
1045      swap(basic_regex& __rhs)
1046      {
1047	std::swap(_M_flags,      __rhs._M_flags);
1048	std::swap(_M_pattern,    __rhs._M_pattern);
1049	std::swap(_M_mark_count, __rhs._M_mark_count);
1050	std::swap(_M_traits,     __rhs._M_traits);
1051      }
1052
1053    private:
1054      /**
1055       * @brief Compiles a regular expression pattern into a NFA.
1056       * @todo Implement this function.
1057       */
1058      void _M_compile();
1059
1060    protected:
1061      flag_type    _M_flags;
1062      string_type  _M_pattern;
1063      unsigned int _M_mark_count;
1064      _Rx_traits   _M_traits;
1065    };
1066
1067  /** @brief Standard regular expressions. */
1068  typedef basic_regex<char>    regex;
1069#ifdef _GLIBCXX_USE_WCHAR_T
1070  /** @brief Standard wide-character regular expressions. */
1071  typedef basic_regex<wchar_t> wregex;
1072#endif
1073
1074
1075  // [7.8.6] basic_regex swap
1076  /**
1077   * @brief Swaps the contents of two regular expression objects.
1078   * @param lhs First regular expression.
1079   * @param rhs Second regular expression.
1080   */
1081  template<typename _Ch_type, typename _Rx_traits>
1082    inline void
1083    swap(basic_regex<_Ch_type, _Rx_traits>& __lhs,
1084	 basic_regex<_Ch_type, _Rx_traits>& __rhs)
1085    { __lhs.swap(__rhs); }
1086
1087
1088  // [7.9] Class template sub_match
1089  /**
1090   * A sequence of characters matched by a particular marked sub-expression.
1091   *
1092   * An object of this class is essentially a pair of iterators marking a
1093   * matched subexpression within a regular expression pattern match. Such
1094   * objects can be converted to and compared with std::basic_string objects
1095   * of a similar base character type as the pattern matched by the regular
1096   * expression.
1097   *
1098   * The iterators that make up the pair are the usual half-open interval
1099   * referencing the actual original pattern matched.
1100   */
1101  template<typename _BiIter>
1102    class sub_match : public std::pair<_BiIter, _BiIter>
1103    {
1104    public:
1105      typedef typename iterator_traits<_BiIter>::value_type      value_type;
1106      typedef typename iterator_traits<_BiIter>::difference_type
1107                                                            difference_type;
1108      typedef _BiIter                                              iterator;
1109
1110    public:
1111      bool matched;
1112
1113      /**
1114       * Gets the length of the matching sequence.
1115       */
1116      difference_type
1117      length() const
1118      { return this->matched ? std::distance(this->first, this->second) : 0; }
1119
1120      /**
1121       * @brief Gets the matching sequence as a string.
1122       *
1123       * @returns the matching sequence as a string.
1124       *
1125       * This is the implicit conversion operator.  It is identical to the
1126       * str() member function except that it will want to pop up in
1127       * unexpected places and cause a great deal of confusion and cursing
1128       * from the unwary.
1129       */
1130      operator basic_string<value_type>() const
1131      {
1132	return this->matched
1133	  ? std::basic_string<value_type>(this->first, this->second)
1134	  : std::basic_string<value_type>();
1135      }
1136
1137      /**
1138       * @brief Gets the matching sequence as a string.
1139       *
1140       * @returns the matching sequence as a string.
1141       */
1142      basic_string<value_type>
1143      str() const
1144      {
1145	return this->matched
1146	  ? std::basic_string<value_type>(this->first, this->second)
1147	  : std::basic_string<value_type>();
1148      }
1149
1150      /**
1151       * @brief Compares this and another matched sequence.
1152       *
1153       * @param s Another matched sequence to compare to this one.
1154       *
1155       * @retval <0 this matched sequence will collate before @p s.
1156       * @retval =0 this matched sequence is equivalent to @p s.
1157       * @retval <0 this matched sequence will collate after @p s.
1158       */
1159      int
1160      compare(const sub_match& __s) const
1161      { return this->str().compare(__s.str()); }
1162
1163      /**
1164       * @brief Compares this sub_match to a string.
1165       *
1166       * @param s A string to compare to this sub_match.
1167       *
1168       * @retval <0 this matched sequence will collate before @p s.
1169       * @retval =0 this matched sequence is equivalent to @p s.
1170       * @retval <0 this matched sequence will collate after @p s.
1171       */
1172      int
1173      compare(const basic_string<value_type>& __s) const
1174      { return this->str().compare(__s); }
1175
1176      /**
1177       * @brief Compares this sub_match to a C-style string.
1178       *
1179       * @param s A C-style string to compare to this sub_match.
1180       *
1181       * @retval <0 this matched sequence will collate before @p s.
1182       * @retval =0 this matched sequence is equivalent to @p s.
1183       * @retval <0 this matched sequence will collate after @p s.
1184       */
1185      int
1186      compare(const value_type* __s) const
1187      { return this->str().compare(__s); }
1188    };
1189
1190
1191  /** @brief Standard regex submatch over a C-style null-terminated string. */
1192  typedef sub_match<const char*>             csub_match;
1193  /** @brief Standard regex submatch over a standard string. */
1194  typedef sub_match<string::const_iterator>  ssub_match;
1195#ifdef _GLIBCXX_USE_WCHAR_T
1196  /** @brief Regex submatch over a C-style null-terminated wide string. */
1197  typedef sub_match<const wchar_t*>          wcsub_match;
1198  /** @brief Regex submatch over a standard wide string. */
1199  typedef sub_match<wstring::const_iterator> wssub_match;
1200#endif
1201
1202  // [7.9.2] sub_match non-member operators
1203
1204  /**
1205   * @brief Tests the equivalence of two regular expression submatches.
1206   * @param lhs First regular expression submatch.
1207   * @param rhs Second regular expression submatch.
1208   * @returns true if @a lhs  is equivalent to @a rhs, false otherwise.
1209   */
1210  template<typename _BiIter>
1211    inline bool
1212    operator==(const sub_match<_BiIter>& __lhs,
1213	       const sub_match<_BiIter>& __rhs)
1214    { return __lhs.compare(__rhs) == 0; }
1215
1216  /**
1217   * @brief Tests the inequivalence of two regular expression submatches.
1218   * @param lhs First regular expression submatch.
1219   * @param rhs Second regular expression submatch.
1220   * @returns true if @a lhs  is not equivalent to @a rhs, false otherwise.
1221   */
1222  template<typename _BiIter>
1223    inline bool
1224    operator!=(const sub_match<_BiIter>& __lhs,
1225	       const sub_match<_BiIter>& __rhs)
1226    { return __lhs.compare(__rhs) != 0; }
1227
1228  /**
1229   * @brief Tests the ordering of two regular expression submatches.
1230   * @param lhs First regular expression submatch.
1231   * @param rhs Second regular expression submatch.
1232   * @returns true if @a lhs precedes @a rhs, false otherwise.
1233   */
1234  template<typename _BiIter>
1235    inline bool
1236    operator<(const sub_match<_BiIter>& __lhs,
1237	      const sub_match<_BiIter>& __rhs)
1238    { return __lhs.compare(__rhs) < 0; }
1239
1240  /**
1241   * @brief Tests the ordering of two regular expression submatches.
1242   * @param lhs First regular expression submatch.
1243   * @param rhs Second regular expression submatch.
1244   * @returns true if @a lhs does not succeed @a rhs, false otherwise.
1245   */
1246  template<typename _BiIter>
1247    inline bool
1248    operator<=(const sub_match<_BiIter>& __lhs,
1249	       const sub_match<_BiIter>& __rhs)
1250    { return __lhs.compare(__rhs) <= 0; }
1251
1252  /**
1253   * @brief Tests the ordering of two regular expression submatches.
1254   * @param lhs First regular expression submatch.
1255   * @param rhs Second regular expression submatch.
1256   * @returns true if @a lhs does not precede @a rhs, false otherwise.
1257   */
1258  template<typename _BiIter>
1259    inline bool
1260    operator>=(const sub_match<_BiIter>& __lhs,
1261	       const sub_match<_BiIter>& __rhs)
1262    { return __lhs.compare(__rhs) >= 0; }
1263
1264  /**
1265   * @brief Tests the ordering of two regular expression submatches.
1266   * @param lhs First regular expression submatch.
1267   * @param rhs Second regular expression submatch.
1268   * @returns true if @a lhs succeeds @a rhs, false otherwise.
1269   */
1270  template<typename _BiIter>
1271    inline bool
1272    operator>(const sub_match<_BiIter>& __lhs,
1273	      const sub_match<_BiIter>& __rhs)
1274    { return __lhs.compare(__rhs) > 0; }
1275
1276  /**
1277   * @brief Tests the equivalence of a string and a regular expression
1278   *        submatch.
1279   * @param lhs A string.
1280   * @param rhs A regular expression submatch.
1281   * @returns true if @a lhs  is equivalent to @a rhs, false otherwise.
1282   */
1283  template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc>
1284    inline bool
1285    operator==(const basic_string<
1286	       typename iterator_traits<_Bi_iter>::value_type,
1287	       _Ch_traits, _Ch_alloc>& __lhs,
1288	       const sub_match<_Bi_iter>& __rhs)
1289    { return __lhs == __rhs.str(); }
1290
1291  /**
1292   * @brief Tests the inequivalence of a string and a regular expression
1293   *        submatch.
1294   * @param lhs A string.
1295   * @param rhs A regular expression submatch.
1296   * @returns true if @a lhs  is not equivalent to @a rhs, false otherwise.
1297   */
1298  template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc>
1299    inline bool
1300    operator!=(const basic_string<
1301	       typename iterator_traits<_Bi_iter>::value_type,
1302	       _Ch_traits, _Ch_alloc>& __lhs, const sub_match<_Bi_iter>& __rhs)
1303    { return __lhs != __rhs.str(); }
1304
1305  /**
1306   * @brief Tests the ordering of a string and a regular expression submatch.
1307   * @param lhs A string.
1308   * @param rhs A regular expression submatch.
1309   * @returns true if @a lhs precedes @a rhs, false otherwise.
1310   */
1311  template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc>
1312    inline bool
1313    operator<(const basic_string<
1314	      typename iterator_traits<_Bi_iter>::value_type,
1315	      _Ch_traits, _Ch_alloc>& __lhs, const sub_match<_Bi_iter>& __rhs)
1316     { return __lhs < __rhs.str(); }
1317
1318  /**
1319   * @brief Tests the ordering of a string and a regular expression submatch.
1320   * @param lhs A string.
1321   * @param rhs A regular expression submatch.
1322   * @returns true if @a lhs succeeds @a rhs, false otherwise.
1323   */
1324  template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc>
1325    inline bool
1326    operator>(const basic_string<
1327	      typename iterator_traits<_Bi_iter>::value_type,
1328	      _Ch_traits, _Ch_alloc>& __lhs, const sub_match<_Bi_iter>& __rhs)
1329    { return __lhs > __rhs.str(); }
1330
1331  /**
1332   * @brief Tests the ordering of a string and a regular expression submatch.
1333   * @param lhs A string.
1334   * @param rhs A regular expression submatch.
1335   * @returns true if @a lhs does not precede @a rhs, false otherwise.
1336   */
1337  template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc>
1338    inline bool
1339    operator>=(const basic_string<
1340	       typename iterator_traits<_Bi_iter>::value_type,
1341	       _Ch_traits, _Ch_alloc>& __lhs, const sub_match<_Bi_iter>& __rhs)
1342    { return __lhs >= __rhs.str(); }
1343
1344  /**
1345   * @brief Tests the ordering of a string and a regular expression submatch.
1346   * @param lhs A string.
1347   * @param rhs A regular expression submatch.
1348   * @returns true if @a lhs does not succeed @a rhs, false otherwise.
1349   */
1350  template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc>
1351    inline bool
1352    operator<=(const basic_string<
1353	       typename iterator_traits<_Bi_iter>::value_type,
1354	       _Ch_traits, _Ch_alloc>& __lhs, const sub_match<_Bi_iter>& __rhs)
1355    { return __lhs <= __rhs.str(); }
1356
1357  /**
1358   * @brief Tests the equivalence of a regular expression submatch and a
1359   *        string.
1360   * @param lhs A regular expression submatch.
1361   * @param rhs A string.
1362   * @returns true if @a lhs is equivalent to @a rhs, false otherwise.
1363   */
1364  template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc>
1365    inline bool
1366    operator==(const sub_match<_Bi_iter>& __lhs,
1367	       const basic_string<
1368	       typename iterator_traits<_Bi_iter>::value_type,
1369	       _Ch_traits, _Ch_alloc>& __rhs)
1370    { return __lhs.str() == __rhs; }
1371
1372  /**
1373   * @brief Tests the inequivalence of a regular expression submatch and a
1374   *        string.
1375   * @param lhs A regular expression submatch.
1376   * @param rhs A string.
1377   * @returns true if @a lhs is not equivalent to @a rhs, false otherwise.
1378   */
1379  template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc>
1380    inline bool
1381    operator!=(const sub_match<_Bi_iter>& __lhs,
1382	       const basic_string<
1383	       typename iterator_traits<_Bi_iter>::value_type,
1384	       _Ch_traits, _Ch_alloc>& __rhs)
1385    { return __lhs.str() != __rhs; }
1386
1387  /**
1388   * @brief Tests the ordering of a regular expression submatch and a string.
1389   * @param lhs A regular expression submatch.
1390   * @param rhs A string.
1391   * @returns true if @a lhs precedes @a rhs, false otherwise.
1392   */
1393  template<typename _Bi_iter, class _Ch_traits, class _Ch_alloc>
1394    inline bool
1395    operator<(const sub_match<_Bi_iter>& __lhs,
1396	      const basic_string<
1397	      typename iterator_traits<_Bi_iter>::value_type,
1398	      _Ch_traits, _Ch_alloc>& __rhs)
1399    { return __lhs.str() < __rhs; }
1400
1401  /**
1402   * @brief Tests the ordering of a regular expression submatch and a string.
1403   * @param lhs A regular expression submatch.
1404   * @param rhs A string.
1405   * @returns true if @a lhs succeeds @a rhs, false otherwise.
1406   */
1407  template<typename _Bi_iter, class _Ch_traits, class _Ch_alloc>
1408    inline bool
1409    operator>(const sub_match<_Bi_iter>& __lhs,
1410	      const basic_string<
1411	      typename iterator_traits<_Bi_iter>::value_type,
1412	      _Ch_traits, _Ch_alloc>& __rhs)
1413    { return __lhs.str() > __rhs; }
1414
1415  /**
1416   * @brief Tests the ordering of a regular expression submatch and a string.
1417   * @param lhs A regular expression submatch.
1418   * @param rhs A string.
1419   * @returns true if @a lhs does not precede @a rhs, false otherwise.
1420   */
1421  template<typename _Bi_iter, class _Ch_traits, class _Ch_alloc>
1422    inline bool
1423    operator>=(const sub_match<_Bi_iter>& __lhs,
1424	       const basic_string<
1425	       typename iterator_traits<_Bi_iter>::value_type,
1426	       _Ch_traits, _Ch_alloc>& __rhs)
1427    { return __lhs.str() >= __rhs; }
1428
1429  /**
1430   * @brief Tests the ordering of a regular expression submatch and a string.
1431   * @param lhs A regular expression submatch.
1432   * @param rhs A string.
1433   * @returns true if @a lhs does not succeed @a rhs, false otherwise.
1434   */
1435  template<typename _Bi_iter, class _Ch_traits, class _Ch_alloc>
1436    inline bool
1437    operator<=(const sub_match<_Bi_iter>& __lhs,
1438	       const basic_string<
1439	       typename iterator_traits<_Bi_iter>::value_type,
1440	       _Ch_traits, _Ch_alloc>& __rhs)
1441    { return __lhs.str() <= __rhs; }
1442
1443  /**
1444   * @brief Tests the equivalence of a C string and a regular expression
1445   *        submatch.
1446   * @param lhs A C string.
1447   * @param rhs A regular expression submatch.
1448   * @returns true if @a lhs  is equivalent to @a rhs, false otherwise.
1449   */
1450  template<typename _Bi_iter>
1451    inline bool
1452    operator==(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
1453	       const sub_match<_Bi_iter>& __rhs)
1454    { return __lhs == __rhs.str(); }
1455
1456  /**
1457   * @brief Tests the inequivalence of an iterator value and a regular
1458   *        expression submatch.
1459   * @param lhs A regular expression submatch.
1460   * @param rhs A string.
1461   * @returns true if @a lhs is not equivalent to @a rhs, false otherwise.
1462   */
1463  template<typename _Bi_iter>
1464    inline bool
1465    operator!=(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
1466	       const sub_match<_Bi_iter>& __rhs)
1467    { return __lhs != __rhs.str(); }
1468
1469  /**
1470   * @brief Tests the ordering of a string and a regular expression submatch.
1471   * @param lhs A string.
1472   * @param rhs A regular expression submatch.
1473   * @returns true if @a lhs precedes @a rhs, false otherwise.
1474   */
1475  template<typename _Bi_iter>
1476    inline bool
1477    operator<(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
1478	      const sub_match<_Bi_iter>& __rhs)
1479    { return __lhs < __rhs.str(); }
1480
1481  /**
1482   * @brief Tests the ordering of a string and a regular expression submatch.
1483   * @param lhs A string.
1484   * @param rhs A regular expression submatch.
1485   * @returns true if @a lhs succeeds @a rhs, false otherwise.
1486   */
1487  template<typename _Bi_iter>
1488    inline bool
1489    operator>(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
1490	      const sub_match<_Bi_iter>& __rhs)
1491    { return __lhs > __rhs.str(); }
1492
1493  /**
1494   * @brief Tests the ordering of a string and a regular expression submatch.
1495   * @param lhs A string.
1496   * @param rhs A regular expression submatch.
1497   * @returns true if @a lhs does not precede @a rhs, false otherwise.
1498   */
1499  template<typename _Bi_iter>
1500    inline bool
1501    operator>=(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
1502	       const sub_match<_Bi_iter>& __rhs)
1503    { return __lhs >= __rhs.str(); }
1504
1505  /**
1506   * @brief Tests the ordering of a string and a regular expression submatch.
1507   * @param lhs A string.
1508   * @param rhs A regular expression submatch.
1509   * @returns true if @a lhs does not succeed @a rhs, false otherwise.
1510   */
1511  template<typename _Bi_iter>
1512    inline bool
1513    operator<=(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
1514	       const sub_match<_Bi_iter>& __rhs)
1515    { return __lhs <= __rhs.str(); }
1516
1517  /**
1518   * @brief Tests the equivalence of a regular expression submatch and a
1519   *        string.
1520   * @param lhs A regular expression submatch.
1521   * @param rhs A pointer to a string?
1522   * @returns true if @a lhs  is equivalent to @a rhs, false otherwise.
1523   */
1524  template<typename _Bi_iter>
1525    inline bool
1526    operator==(const sub_match<_Bi_iter>& __lhs,
1527	       typename iterator_traits<_Bi_iter>::value_type const* __rhs)
1528    { return __lhs.str() == __rhs; }
1529
1530  /**
1531   * @brief Tests the inequivalence of a regular expression submatch and a
1532   *        string.
1533   * @param lhs A regular expression submatch.
1534   * @param rhs A pointer to a string.
1535   * @returns true if @a lhs is not equivalent to @a rhs, false otherwise.
1536   */
1537  template<typename _Bi_iter>
1538    inline bool
1539    operator!=(const sub_match<_Bi_iter>& __lhs,
1540	       typename iterator_traits<_Bi_iter>::value_type const* __rhs)
1541    { return __lhs.str() != __rhs; }
1542
1543  /**
1544   * @brief Tests the ordering of a regular expression submatch and a string.
1545   * @param lhs A regular expression submatch.
1546   * @param rhs A string.
1547   * @returns true if @a lhs precedes @a rhs, false otherwise.
1548   */
1549  template<typename _Bi_iter>
1550    inline bool
1551    operator<(const sub_match<_Bi_iter>& __lhs,
1552	      typename iterator_traits<_Bi_iter>::value_type const* __rhs)
1553    { return __lhs.str() < __rhs; }
1554
1555  /**
1556   * @brief Tests the ordering of a regular expression submatch and a string.
1557   * @param lhs A regular expression submatch.
1558   * @param rhs A string.
1559   * @returns true if @a lhs succeeds @a rhs, false otherwise.
1560   */
1561  template<typename _Bi_iter>
1562    inline bool
1563    operator>(const sub_match<_Bi_iter>& __lhs,
1564	      typename iterator_traits<_Bi_iter>::value_type const* __rhs)
1565    { return __lhs.str() > __rhs; }
1566
1567  /**
1568   * @brief Tests the ordering of a regular expression submatch and a string.
1569   * @param lhs A regular expression submatch.
1570   * @param rhs A string.
1571   * @returns true if @a lhs does not precede @a rhs, false otherwise.
1572   */
1573  template<typename _Bi_iter>
1574    inline bool
1575    operator>=(const sub_match<_Bi_iter>& __lhs,
1576	       typename iterator_traits<_Bi_iter>::value_type const* __rhs)
1577    { return __lhs.str() >= __rhs; }
1578
1579  /**
1580   * @brief Tests the ordering of a regular expression submatch and a string.
1581   * @param lhs A regular expression submatch.
1582   * @param rhs A string.
1583   * @returns true if @a lhs does not succeed @a rhs, false otherwise.
1584   */
1585  template<typename _Bi_iter>
1586    inline bool
1587    operator<=(const sub_match<_Bi_iter>& __lhs,
1588	       typename iterator_traits<_Bi_iter>::value_type const* __rhs)
1589    { return __lhs.str() <= __rhs; }
1590
1591  /**
1592   * @brief Tests the equivalence of a string and a regular expression
1593   *        submatch.
1594   * @param lhs A string.
1595   * @param rhs A regular expression submatch.
1596   * @returns true if @a lhs is equivalent to @a rhs, false otherwise.
1597   */
1598  template<typename _Bi_iter>
1599    inline bool
1600    operator==(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
1601	       const sub_match<_Bi_iter>& __rhs)
1602    { return __lhs == __rhs.str(); }
1603
1604  /**
1605   * @brief Tests the inequivalence of a string and a regular expression
1606   *        submatch.
1607   * @param lhs A string.
1608   * @param rhs A regular expression submatch.
1609   * @returns true if @a lhs is not equivalent to @a rhs, false otherwise.
1610   */
1611  template<typename _Bi_iter>
1612    inline bool
1613    operator!=(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
1614	       const sub_match<_Bi_iter>& __rhs)
1615    { return __lhs != __rhs.str(); }
1616
1617  /**
1618   * @brief Tests the ordering of a string and a regular expression submatch.
1619   * @param lhs A string.
1620   * @param rhs A regular expression submatch.
1621   * @returns true if @a lhs precedes @a rhs, false otherwise.
1622   */
1623  template<typename _Bi_iter>
1624    inline bool
1625    operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
1626	      const sub_match<_Bi_iter>& __rhs)
1627    { return __lhs < __rhs.str(); }
1628
1629  /**
1630   * @brief Tests the ordering of a string and a regular expression submatch.
1631   * @param lhs A string.
1632   * @param rhs A regular expression submatch.
1633   * @returns true if @a lhs succeeds @a rhs, false otherwise.
1634   */
1635  template<typename _Bi_iter>
1636    inline bool
1637    operator>(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
1638	      const sub_match<_Bi_iter>& __rhs)
1639    { return __lhs > __rhs.str(); }
1640
1641  /**
1642   * @brief Tests the ordering of a string and a regular expression submatch.
1643   * @param lhs A string.
1644   * @param rhs A regular expression submatch.
1645   * @returns true if @a lhs does not precede @a rhs, false otherwise.
1646   */
1647  template<typename _Bi_iter>
1648    inline bool
1649    operator>=(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
1650	       const sub_match<_Bi_iter>& __rhs)
1651    { return __lhs >= __rhs.str(); }
1652
1653  /**
1654   * @brief Tests the ordering of a string and a regular expression submatch.
1655   * @param lhs A string.
1656   * @param rhs A regular expression submatch.
1657   * @returns true if @a lhs does not succeed @a rhs, false otherwise.
1658   */
1659  template<typename _Bi_iter>
1660    inline bool
1661    operator<=(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
1662	       const sub_match<_Bi_iter>& __rhs)
1663    { return __lhs <= __rhs.str(); }
1664
1665  /**
1666   * @brief Tests the equivalence of a regular expression submatch and a
1667   *        string.
1668   * @param lhs A regular expression submatch.
1669   * @param rhs A const string reference.
1670   * @returns true if @a lhs  is equivalent to @a rhs, false otherwise.
1671   */
1672  template<typename _Bi_iter>
1673    inline bool
1674    operator==(const sub_match<_Bi_iter>& __lhs,
1675	       typename iterator_traits<_Bi_iter>::value_type const& __rhs)
1676    { return __lhs.str() == __rhs; }
1677
1678  /**
1679   * @brief Tests the inequivalence of a regular expression submatch and a
1680   *        string.
1681   * @param lhs A regular expression submatch.
1682   * @param rhs A const string reference.
1683   * @returns true if @a lhs is not equivalent to @a rhs, false otherwise.
1684   */
1685  template<typename _Bi_iter>
1686    inline bool
1687    operator!=(const sub_match<_Bi_iter>& __lhs,
1688	       typename iterator_traits<_Bi_iter>::value_type const& __rhs)
1689    { return __lhs.str() != __rhs; }
1690
1691  /**
1692   * @brief Tests the ordering of a regular expression submatch and a string.
1693   * @param lhs A regular expression submatch.
1694   * @param rhs A const string reference.
1695   * @returns true if @a lhs precedes @a rhs, false otherwise.
1696   */
1697  template<typename _Bi_iter>
1698    inline bool
1699    operator<(const sub_match<_Bi_iter>& __lhs,
1700	      typename iterator_traits<_Bi_iter>::value_type const& __rhs)
1701    { return __lhs.str() < __rhs; }
1702
1703  /**
1704   * @brief Tests the ordering of a regular expression submatch and a string.
1705   * @param lhs A regular expression submatch.
1706   * @param rhs A const string reference.
1707   * @returns true if @a lhs succeeds @a rhs, false otherwise.
1708   */
1709  template<typename _Bi_iter>
1710    inline bool
1711    operator>(const sub_match<_Bi_iter>& __lhs,
1712	      typename iterator_traits<_Bi_iter>::value_type const& __rhs)
1713    { return __lhs.str() > __rhs; }
1714
1715  /**
1716   * @brief Tests the ordering of a regular expression submatch and a string.
1717   * @param lhs A regular expression submatch.
1718   * @param rhs A const string reference.
1719   * @returns true if @a lhs does not precede @a rhs, false otherwise.
1720   */
1721  template<typename _Bi_iter>
1722    inline bool
1723    operator>=(const sub_match<_Bi_iter>& __lhs,
1724	       typename iterator_traits<_Bi_iter>::value_type const& __rhs)
1725    { return __lhs.str() >= __rhs; }
1726
1727  /**
1728   * @brief Tests the ordering of a regular expression submatch and a string.
1729   * @param lhs A regular expression submatch.
1730   * @param rhs A const string reference.
1731   * @returns true if @a lhs does not succeed @a rhs, false otherwise.
1732   */
1733  template<typename _Bi_iter>
1734    inline bool
1735    operator<=(const sub_match<_Bi_iter>& __lhs,
1736	       typename iterator_traits<_Bi_iter>::value_type const& __rhs)
1737    { return __lhs.str() <= __rhs; }
1738
1739  /**
1740   * @brief Inserts a matched string into an output stream.
1741   *
1742   * @param os The output stream.
1743   * @param m  A submatch string.
1744   *
1745   * @returns the output stream with the submatch string inserted.
1746   */
1747  template<typename _Ch_type, typename _Ch_traits, typename _Bi_iter>
1748    inline
1749    basic_ostream<_Ch_type, _Ch_traits>&
1750    operator<<(basic_ostream<_Ch_type, _Ch_traits>& __os,
1751	       const sub_match<_Bi_iter>& __m)
1752    { return __os << __m.str(); }
1753
1754  // [7.10] Class template match_results
1755  /**
1756   * @brief The results of a match or search operation.
1757   *
1758   * A collection of character sequences representing the result of a regular
1759   * expression match.  Storage for the collection is allocated and freed as
1760   * necessary by the member functions of class template match_results.
1761   *
1762   * This class satisfies the Sequence requirements, with the exception that
1763   * only the operations defined for a const-qualified Sequence are supported.
1764   *
1765   * The sub_match object stored at index 0 represents sub-expression 0, i.e.
1766   * the whole match. In this case the sub_match member matched is always true.
1767   * The sub_match object stored at index n denotes what matched the marked
1768   * sub-expression n within the matched expression. If the sub-expression n
1769   * participated in a regular expression match then the sub_match member
1770   * matched evaluates to true, and members first and second denote the range
1771   * of characters [first, second) which formed that match. Otherwise matched
1772   * is false, and members first and second point to the end of the sequence
1773   * that was searched.
1774   *
1775   * @nosubgrouping
1776   */
1777  template<typename _Bi_iter,
1778	   typename _Allocator = allocator<sub_match<_Bi_iter> > >
1779    class match_results
1780    : private std::vector<std::tr1::sub_match<_Bi_iter>, _Allocator>
1781    {
1782    private:
1783      typedef std::vector<std::tr1::sub_match<_Bi_iter>, _Allocator>
1784                                                              _Base_type;
1785
1786    public:
1787      /**
1788       * @name 10.? Public Types
1789       */
1790      ///@{
1791      typedef sub_match<_Bi_iter>                             value_type;
1792      typedef typename _Base_type::const_reference            const_reference;
1793      typedef const_reference                                 reference;
1794      typedef typename _Base_type::const_iterator             const_iterator;
1795      typedef const_iterator                                  iterator;
1796      typedef typename iterator_traits<_Bi_iter>::difference_type
1797                                                              difference_type;
1798      typedef typename _Allocator::size_type                  size_type;
1799      typedef _Allocator                                      allocator_type;
1800      typedef typename iterator_traits<_Bi_iter>::value_type  char_type;
1801      typedef basic_string<char_type>                         string_type;
1802      ///@}
1803
1804    public:
1805      /**
1806       * @name 10.1 Construction, Copying, and Destruction
1807       */
1808      ///@{
1809
1810      /**
1811       * @brief Constructs a default %match_results container.
1812       * @post size() returns 0 and str() returns an empty string.
1813       */
1814      explicit
1815      match_results(const _Allocator& __a = _Allocator())
1816      : _Base_type(__a), _M_matched(false)
1817      { }
1818
1819      /**
1820       * @brief Copy constructs a %match_results.
1821       */
1822      match_results(const match_results& __rhs)
1823      : _Base_type(__rhs), _M_matched(__rhs._M_matched),
1824	_M_prefix(__rhs._M_prefix), _M_suffix(__rhs._M_suffix)
1825      { }
1826
1827      /**
1828       * @brief Assigns rhs to *this.
1829       */
1830      match_results&
1831      operator=(const match_results& __rhs)
1832      {
1833	match_results __tmp(__rhs);
1834	this->swap(__tmp);
1835	return *this;
1836      }
1837
1838      /**
1839       * @brief Destroys a %match_results object.
1840       */
1841      ~match_results()
1842      { }
1843
1844      ///@}
1845
1846      /**
1847       * @name 10.2 Size
1848       */
1849      ///@{
1850
1851      /**
1852       * @brief Gets the number of matches and submatches.
1853       *
1854       * The number of matches for a given regular expression will be either 0
1855       * if there was no match or mark_count() + 1 if a match was successful.
1856       * Some matches may be empty.
1857       *
1858       * @returns the number of matches found.
1859       */
1860      size_type
1861      size() const
1862      { return _M_matched ? _Base_type::size() + 1 : 0; }
1863
1864      //size_type
1865      //max_size() const;
1866      using _Base_type::max_size;
1867
1868      /**
1869       * @brief Indicates if the %match_results contains no results.
1870       * @retval true The %match_results object is empty.
1871       * @retval false The %match_results object is not empty.
1872       */
1873      _GLIBCXX_NODISCARD bool
1874      empty() const
1875      { return size() == 0; }
1876
1877      ///@}
1878
1879      /**
1880       * @name 10.3 Element Access
1881       */
1882      ///@{
1883
1884      /**
1885       * @brief Gets the length of the indicated submatch.
1886       * @param sub indicates the submatch.
1887       *
1888       * This function returns the length of the indicated submatch, or the
1889       * length of the entire match if @p sub is zero (the default).
1890       */
1891      difference_type
1892      length(size_type __sub = 0) const
1893      { return _M_matched ? this->str(__sub).length() : 0; }
1894
1895      /**
1896       * @brief Gets the offset of the beginning of the indicated submatch.
1897       * @param sub indicates the submatch.
1898       *
1899       * This function returns the offset from the beginning of the target
1900       * sequence to the beginning of the submatch, unless the value of @p sub
1901       * is zero (the default), in which case this function returns the offset
1902       * from the beginning of the target sequence to the beginning of the
1903       * match.
1904       */
1905      difference_type
1906      position(size_type __sub = 0) const
1907      {
1908	return _M_matched ? std::distance(this->prefix().first,
1909					  (*this)[__sub].first) : 0;
1910      }
1911
1912      /**
1913       * @brief Gets the match or submatch converted to a string type.
1914       * @param sub indicates the submatch.
1915       *
1916       * This function gets the submatch (or match, if @p sub is zero) extracted
1917       * from the target range and converted to the associated string type.
1918       */
1919      string_type
1920      str(size_type __sub = 0) const
1921      { return _M_matched ? (*this)[__sub].str() : string_type(); }
1922
1923      /**
1924       * @brief Gets a %sub_match reference for the match or submatch.
1925       * @param sub indicates the submatch.
1926       *
1927       * This function gets a reference to the indicated submatch, or the entire
1928       * match if @p sub is zero.
1929       *
1930       * If @p sub >= size() then this function returns a %sub_match with a
1931       * special value indicating no submatch.
1932       */
1933      const_reference
1934      operator[](size_type __sub) const
1935      { return _Base_type::operator[](__sub); }
1936
1937      /**
1938       * @brief Gets a %sub_match representing the match prefix.
1939       *
1940       * This function gets a reference to a %sub_match object representing the
1941       * part of the target range between the start of the target range and the
1942       * start of the match.
1943       */
1944      const_reference
1945      prefix() const
1946      { return _M_prefix; }
1947
1948      /**
1949       * @brief Gets a %sub_match representing the match suffix.
1950       *
1951       * This function gets a reference to a %sub_match object representing the
1952       * part of the target range between the end of the match and the end of
1953       * the target range.
1954       */
1955      const_reference
1956      suffix() const
1957      { return _M_suffix; }
1958
1959      /**
1960       * @brief Gets an iterator to the start of the %sub_match collection.
1961       */
1962      const_iterator
1963      begin() const
1964      { return _Base_type::begin(); }
1965
1966#ifdef _GLIBCXX_INCLUDE_AS_CXX11
1967      /**
1968       * @brief Gets an iterator to the start of the %sub_match collection.
1969       */
1970      const_iterator
1971      cbegin() const
1972      { return _Base_type::begin(); }
1973#endif
1974
1975      /**
1976       * @brief Gets an iterator to one-past-the-end of the collection.
1977       */
1978      const_iterator
1979      end() const
1980      { return _Base_type::end(); }
1981
1982#ifdef _GLIBCXX_INCLUDE_AS_CXX11
1983      /**
1984       * @brief Gets an iterator to one-past-the-end of the collection.
1985       */
1986      const_iterator
1987      cend() const
1988      { return _Base_type::end(); }
1989#endif
1990
1991      ///@}
1992
1993      /**
1994       * @name 10.4 Formatting
1995       *
1996       * These functions perform formatted substitution of the matched
1997       * character sequences into their target.  The format specifiers
1998       * and escape sequences accepted by these functions are
1999       * determined by their @p flags parameter as documented above.
2000       */
2001       ///@{
2002
2003      /**
2004       * @todo Implement this function.
2005       */
2006      template<typename _Out_iter>
2007        _Out_iter
2008        format(_Out_iter __out, const string_type& __fmt,
2009	       regex_constants::match_flag_type __flags
2010	       = regex_constants::format_default) const;
2011
2012      /**
2013       * @todo Implement this function.
2014       */
2015      string_type
2016      format(const string_type& __fmt,
2017	     regex_constants::match_flag_type __flags
2018	     = regex_constants::format_default) const;
2019
2020      ///@}
2021
2022      /**
2023       * @name 10.5 Allocator
2024       */
2025      ///@{
2026
2027      /**
2028       * @brief Gets a copy of the allocator.
2029       */
2030      //allocator_type
2031      //get_allocator() const;
2032      using _Base_type::get_allocator;
2033
2034      ///@}
2035
2036      /**
2037       * @name 10.6 Swap
2038       */
2039       ///@{
2040
2041      /**
2042       * @brief Swaps the contents of two match_results.
2043       */
2044      void
2045      swap(match_results& __that)
2046      {
2047	_Base_type::swap(__that);
2048	std::swap(_M_matched, __that._M_matched);
2049	std::swap(_M_prefix,  __that._M_prefix);
2050	std::swap(_M_suffix,  __that._M_suffix);
2051      }
2052      ///@}
2053
2054    private:
2055      bool       _M_matched;
2056      value_type _M_prefix;
2057      value_type _M_suffix;
2058    };
2059
2060  typedef match_results<const char*>             cmatch;
2061  typedef match_results<string::const_iterator>  smatch;
2062#ifdef _GLIBCXX_USE_WCHAR_T
2063  typedef match_results<const wchar_t*>          wcmatch;
2064  typedef match_results<wstring::const_iterator> wsmatch;
2065#endif
2066
2067  // match_results comparisons
2068  /**
2069   * @brief Compares two match_results for equality.
2070   * @returns true if the two objects refer to the same match,
2071   * false otherwise.
2072   * @todo Implement this function.
2073   */
2074  template<typename _Bi_iter, typename _Allocator>
2075    inline bool
2076    operator==(const match_results<_Bi_iter, _Allocator>& __m1,
2077	       const match_results<_Bi_iter, _Allocator>& __m2);
2078
2079  /**
2080   * @brief Compares two match_results for inequality.
2081   * @returns true if the two objects do not refer to the same match,
2082   * false otherwise.
2083   */
2084  template<typename _Bi_iter, class _Allocator>
2085    inline bool
2086    operator!=(const match_results<_Bi_iter, _Allocator>& __m1,
2087	       const match_results<_Bi_iter, _Allocator>& __m2)
2088    { return !(__m1 == __m2); }
2089
2090  // [7.10.6] match_results swap
2091  /**
2092   * @brief Swaps two match results.
2093   * @param lhs A match result.
2094   * @param rhs A match result.
2095   *
2096   * The contents of the two match_results objects are swapped.
2097   */
2098  template<typename _Bi_iter, typename _Allocator>
2099    inline void
2100    swap(match_results<_Bi_iter, _Allocator>& __lhs,
2101	 match_results<_Bi_iter, _Allocator>& __rhs)
2102    { __lhs.swap(__rhs); }
2103
2104  // [7.11.2] Function template regex_match
2105  /**
2106   * @name Matching, Searching, and Replacing
2107   */
2108  ///@{
2109
2110  /**
2111   * @brief Determines if there is a match between the regular expression @p e
2112   * and all of the character sequence [first, last).
2113   *
2114   * @param first Beginning of the character sequence to match.
2115   * @param last  One-past-the-end of the character sequence to match.
2116   * @param m     The match results.
2117   * @param re    The regular expression.
2118   * @param flags Controls how the regular expression is matched.
2119   *
2120   * @retval true  A match exists.
2121   * @retval false Otherwise.
2122   *
2123   * @throws an exception of type regex_error.
2124   *
2125   * @todo Implement this function.
2126   */
2127  template<typename _Bi_iter, typename _Allocator,
2128	   typename _Ch_type, typename _Rx_traits>
2129    bool
2130    regex_match(_Bi_iter __first, _Bi_iter __last,
2131		match_results<_Bi_iter, _Allocator>& __m,
2132		const basic_regex<_Ch_type, _Rx_traits>& __re,
2133		regex_constants::match_flag_type __flags
2134		= regex_constants::match_default);
2135
2136  /**
2137   * @brief Indicates if there is a match between the regular expression @p e
2138   * and all of the character sequence [first, last).
2139   *
2140   * @param first Beginning of the character sequence to match.
2141   * @param last  One-past-the-end of the character sequence to match.
2142   * @param re    The regular expression.
2143   * @param flags Controls how the regular expression is matched.
2144   *
2145   * @retval true  A match exists.
2146   * @retval false Otherwise.
2147   *
2148   * @throws an exception of type regex_error.
2149   */
2150  template<typename _Bi_iter, typename _Ch_type, typename _Rx_traits>
2151    bool
2152    regex_match(_Bi_iter __first, _Bi_iter __last,
2153		const basic_regex<_Ch_type, _Rx_traits>& __re,
2154		regex_constants::match_flag_type __flags
2155		= regex_constants::match_default)
2156    {
2157      match_results<_Bi_iter> __what;
2158      return regex_match(__first, __last, __what, __re, __flags);
2159    }
2160
2161  /**
2162   * @brief Determines if there is a match between the regular expression @p e
2163   * and a C-style null-terminated string.
2164   *
2165   * @param s  The C-style null-terminated string to match.
2166   * @param m  The match results.
2167   * @param re The regular expression.
2168   * @param f  Controls how the regular expression is matched.
2169   *
2170   * @retval true  A match exists.
2171   * @retval false Otherwise.
2172   *
2173   * @throws an exception of type regex_error.
2174   */
2175  template<typename _Ch_type, typename _Allocator, typename _Rx_traits>
2176    inline bool
2177    regex_match(const _Ch_type* __s,
2178		match_results<const _Ch_type*, _Allocator>& __m,
2179		const basic_regex<_Ch_type, _Rx_traits>& __re,
2180		regex_constants::match_flag_type __f
2181		= regex_constants::match_default)
2182    { return regex_match(__s, __s + _Rx_traits::length(__s), __m, __re, __f); }
2183
2184  /**
2185   * @brief Determines if there is a match between the regular expression @p e
2186   * and a string.
2187   *
2188   * @param s     The string to match.
2189   * @param m     The match results.
2190   * @param re    The regular expression.
2191   * @param flags Controls how the regular expression is matched.
2192   *
2193   * @retval true  A match exists.
2194   * @retval false Otherwise.
2195   *
2196   * @throws an exception of type regex_error.
2197   */
2198  template<typename _Ch_traits, typename _Ch_alloc,
2199	   typename _Allocator, typename _Ch_type, typename _Rx_traits>
2200    inline bool
2201    regex_match(const basic_string<_Ch_type, _Ch_traits, _Ch_alloc>& __s,
2202		match_results<typename basic_string<_Ch_type,
2203		_Ch_traits, _Ch_alloc>::const_iterator, _Allocator>& __m,
2204		const basic_regex<_Ch_type, _Rx_traits>& __re,
2205		regex_constants::match_flag_type __flags
2206		= regex_constants::match_default)
2207    { return regex_match(__s.begin(), __s.end(), __m, __re, __flags); }
2208
2209  /**
2210   * @brief Indicates if there is a match between the regular expression @p e
2211   * and a C-style null-terminated string.
2212   *
2213   * @param s  The C-style null-terminated string to match.
2214   * @param re The regular expression.
2215   * @param f  Controls how the regular expression is matched.
2216   *
2217   * @retval true  A match exists.
2218   * @retval false Otherwise.
2219   *
2220   * @throws an exception of type regex_error.
2221   */
2222  template<typename _Ch_type, class _Rx_traits>
2223    inline bool
2224    regex_match(const _Ch_type* __s,
2225		const basic_regex<_Ch_type, _Rx_traits>& __re,
2226		regex_constants::match_flag_type __f
2227		= regex_constants::match_default)
2228    { return regex_match(__s, __s + _Rx_traits::length(__s), __re, __f); }
2229
2230  /**
2231   * @brief Indicates if there is a match between the regular expression @p e
2232   * and a string.
2233   *
2234   * @param s     [IN] The string to match.
2235   * @param re    [IN] The regular expression.
2236   * @param flags [IN] Controls how the regular expression is matched.
2237   *
2238   * @retval true  A match exists.
2239   * @retval false Otherwise.
2240   *
2241   * @throws an exception of type regex_error.
2242   */
2243  template<typename _Ch_traits, typename _Str_allocator,
2244	   typename _Ch_type, typename _Rx_traits>
2245    inline bool
2246    regex_match(const basic_string<_Ch_type, _Ch_traits, _Str_allocator>& __s,
2247		const basic_regex<_Ch_type, _Rx_traits>& __re,
2248		regex_constants::match_flag_type __flags
2249		= regex_constants::match_default)
2250    { return regex_match(__s.begin(), __s.end(), __re, __flags); }
2251
2252  // [7.11.3] Function template regex_search
2253  /**
2254   * Searches for a regular expression within a range.
2255   * @param first [IN]  The start of the string to search.
2256   * @param last  [IN]  One-past-the-end of the string to search.
2257   * @param m     [OUT] The match results.
2258   * @param re    [IN]  The regular expression to search for.
2259   * @param flags [IN]  Search policy flags.
2260   * @retval true  A match was found within the string.
2261   * @retval false No match was found within the string, the content of %m is
2262   *               undefined.
2263   *
2264   * @throws an exception of type regex_error.
2265   *
2266   * @todo Implement this function.
2267   */
2268  template<typename _Bi_iter, typename _Allocator,
2269	   typename _Ch_type, typename _Rx_traits>
2270    inline bool
2271    regex_search(_Bi_iter __first, _Bi_iter __last,
2272		 match_results<_Bi_iter, _Allocator>& __m,
2273		 const basic_regex<_Ch_type, _Rx_traits>& __re,
2274		 regex_constants::match_flag_type __flags
2275		 = regex_constants::match_default);
2276
2277  /**
2278   * Searches for a regular expression within a range.
2279   * @param first [IN]  The start of the string to search.
2280   * @param last  [IN]  One-past-the-end of the string to search.
2281   * @param re    [IN]  The regular expression to search for.
2282   * @param flags [IN]  Search policy flags.
2283   * @retval true  A match was found within the string.
2284   * @retval false No match was found within the string.
2285   * @doctodo
2286   *
2287   * @throws an exception of type regex_error.
2288   */
2289  template<typename _Bi_iter, typename _Ch_type, typename _Rx_traits>
2290    inline bool
2291    regex_search(_Bi_iter __first, _Bi_iter __last,
2292		 const basic_regex<_Ch_type, _Rx_traits>& __re,
2293		 regex_constants::match_flag_type __flags
2294		 = regex_constants::match_default)
2295    {
2296      match_results<_Bi_iter> __what;
2297      return regex_search(__first, __last, __what, __re, __flags);
2298    }
2299
2300  /**
2301   * @brief Searches for a regular expression within a C-string.
2302   * @param s [IN]  A C-string to search for the regex.
2303   * @param m [OUT] The set of regex matches.
2304   * @param e [IN]  The regex to search for in @p s.
2305   * @param f [IN]  The search flags.
2306   * @retval true  A match was found within the string.
2307   * @retval false No match was found within the string, the content of %m is
2308   *               undefined.
2309   * @doctodo
2310   *
2311   * @throws an exception of type regex_error.
2312   */
2313  template<typename _Ch_type, class _Allocator, class _Rx_traits>
2314    inline bool
2315    regex_search(const _Ch_type* __s,
2316		 match_results<const _Ch_type*, _Allocator>& __m,
2317		 const basic_regex<_Ch_type, _Rx_traits>& __e,
2318		 regex_constants::match_flag_type __f
2319		 = regex_constants::match_default)
2320    { return regex_search(__s, __s + _Rx_traits::length(__s), __m, __e, __f); }
2321
2322  /**
2323   * @brief Searches for a regular expression within a C-string.
2324   * @param s [IN]  The C-string to search.
2325   * @param e [IN]  The regular expression to search for.
2326   * @param f [IN]  Search policy flags.
2327   * @retval true  A match was found within the string.
2328   * @retval false No match was found within the string.
2329   * @doctodo
2330   *
2331   * @throws an exception of type regex_error.
2332   */
2333  template<typename _Ch_type, typename _Rx_traits>
2334    inline bool
2335    regex_search(const _Ch_type* __s,
2336		 const basic_regex<_Ch_type, _Rx_traits>& __e,
2337		 regex_constants::match_flag_type __f
2338		 = regex_constants::match_default)
2339    { return regex_search(__s, __s + _Rx_traits::length(__s), __e, __f); }
2340
2341  /**
2342   * @brief Searches for a regular expression within a string.
2343   * @param s     [IN]  The string to search.
2344   * @param e     [IN]  The regular expression to search for.
2345   * @param flags [IN]  Search policy flags.
2346   * @retval true  A match was found within the string.
2347   * @retval false No match was found within the string.
2348   * @doctodo
2349   *
2350   * @throws an exception of type regex_error.
2351   */
2352  template<typename _Ch_traits, typename _String_allocator,
2353	   typename _Ch_type, typename _Rx_traits>
2354    inline bool
2355    regex_search(const basic_string<_Ch_type, _Ch_traits,
2356		 _String_allocator>& __s,
2357		 const basic_regex<_Ch_type, _Rx_traits>& __e,
2358		 regex_constants::match_flag_type __flags
2359		 = regex_constants::match_default)
2360    { return regex_search(__s.begin(), __s.end(), __e, __flags); }
2361
2362  /**
2363   * @brief Searches for a regular expression within a string.
2364   * @param s [IN]  A C++ string to search for the regex.
2365   * @param m [OUT] The set of regex matches.
2366   * @param e [IN]  The regex to search for in @p s.
2367   * @param f [IN]  The search flags.
2368   * @retval true  A match was found within the string.
2369   * @retval false No match was found within the string, the content of %m is
2370   *               undefined.
2371   *
2372   * @throws an exception of type regex_error.
2373   */
2374  template<typename _Ch_traits, typename _Ch_alloc,
2375	   typename _Allocator, typename _Ch_type,
2376	   typename _Rx_traits>
2377    inline bool
2378    regex_search(const basic_string<_Ch_type, _Ch_traits, _Ch_alloc>& __s,
2379		 match_results<typename basic_string<_Ch_type,
2380		 _Ch_traits, _Ch_alloc>::const_iterator, _Allocator>& __m,
2381		 const basic_regex<_Ch_type, _Rx_traits>& __e,
2382		 regex_constants::match_flag_type __f
2383		 = regex_constants::match_default)
2384    { return regex_search(__s.begin(), __s.end(), __m, __e, __f); }
2385
2386  // tr1 [7.11.4] std [28.11.4] Function template regex_replace
2387  /**
2388   * @doctodo
2389   * @param out
2390   * @param first
2391   * @param last
2392   * @param e
2393   * @param fmt
2394   * @param flags
2395   *
2396   * @returns out
2397   * @throws an exception of type regex_error.
2398   *
2399   * @todo Implement this function.
2400   */
2401  template<typename _Out_iter, typename _Bi_iter,
2402	   typename _Rx_traits, typename _Ch_type>
2403    inline _Out_iter
2404    regex_replace(_Out_iter __out, _Bi_iter __first, _Bi_iter __last,
2405		  const basic_regex<_Ch_type, _Rx_traits>& __e,
2406		  const basic_string<_Ch_type>& __fmt,
2407		  regex_constants::match_flag_type __flags
2408		  = regex_constants::match_default);
2409
2410  /**
2411   * @doctodo
2412   * @param s
2413   * @param e
2414   * @param fmt
2415   * @param flags
2416   *
2417   * @returns a copy of string @p s with replacements.
2418   *
2419   * @throws an exception of type regex_error.
2420   */
2421  template<typename _Rx_traits, typename _Ch_type>
2422    inline basic_string<_Ch_type>
2423    regex_replace(const basic_string<_Ch_type>& __s,
2424		  const basic_regex<_Ch_type, _Rx_traits>& __e,
2425		  const basic_string<_Ch_type>& __fmt,
2426		  regex_constants::match_flag_type __flags
2427		  = regex_constants::match_default)
2428    {
2429      std::string __result;
2430      regex_replace(std::back_inserter(__result),
2431		    __s.begin(), __s.end(), __e, __fmt, __flags);
2432      return __result;
2433    }
2434
2435  ///@}
2436
2437  // tr1 [7.12.1] std [28.12] Class template regex_iterator
2438  /**
2439   * An iterator adaptor that will provide repeated calls of regex_search over
2440   * a range until no more matches remain.
2441   */
2442  template<typename _Bi_iter,
2443	   typename _Ch_type = typename iterator_traits<_Bi_iter>::value_type,
2444	   typename _Rx_traits = regex_traits<_Ch_type> >
2445    class regex_iterator
2446    {
2447    public:
2448      typedef basic_regex<_Ch_type, _Rx_traits>  regex_type;
2449      typedef match_results<_Bi_iter>            value_type;
2450      typedef std::ptrdiff_t                     difference_type;
2451      typedef const value_type*                  pointer;
2452      typedef const value_type&                  reference;
2453      typedef std::forward_iterator_tag          iterator_category;
2454
2455    public:
2456      /**
2457       * @brief Provides a singular iterator, useful for indicating
2458       * one-past-the-end of a range.
2459       * @todo Implement this function.
2460       * @doctodo
2461       */
2462      regex_iterator();
2463
2464      /**
2465       * Constructs a %regex_iterator...
2466       * @param a  [IN] The start of a text range to search.
2467       * @param b  [IN] One-past-the-end of the text range to search.
2468       * @param re [IN] The regular expression to match.
2469       * @param m  [IN] Policy flags for match rules.
2470       * @todo Implement this function.
2471       * @doctodo
2472       */
2473      regex_iterator(_Bi_iter __a, _Bi_iter __b, const regex_type& __re,
2474		     regex_constants::match_flag_type __m
2475		     = regex_constants::match_default);
2476
2477      /**
2478       * Copy constructs a %regex_iterator.
2479       * @todo Implement this function.
2480       * @doctodo
2481       */
2482      regex_iterator(const regex_iterator& __rhs);
2483
2484      /**
2485       * @todo Implement this function.
2486       * @doctodo
2487       */
2488      regex_iterator&
2489      operator=(const regex_iterator& __rhs);
2490
2491      /**
2492       * @todo Implement this function.
2493       * @doctodo
2494       */
2495      bool
2496      operator==(const regex_iterator& __rhs);
2497
2498      /**
2499       * @todo Implement this function.
2500       * @doctodo
2501       */
2502      bool
2503      operator!=(const regex_iterator& __rhs);
2504
2505      /**
2506       * @todo Implement this function.
2507       * @doctodo
2508       */
2509      const value_type&
2510      operator*();
2511
2512      /**
2513       * @todo Implement this function.
2514       * @doctodo
2515       */
2516      const value_type*
2517      operator->();
2518
2519      /**
2520       * @todo Implement this function.
2521       * @doctodo
2522       */
2523      regex_iterator&
2524      operator++();
2525
2526      /**
2527       * @todo Implement this function.
2528       * @doctodo
2529       */
2530      regex_iterator
2531      operator++(int);
2532
2533    private:
2534      // these members are shown for exposition only:
2535      _Bi_iter                         begin;
2536      _Bi_iter                         end;
2537      const regex_type*                pregex;
2538      regex_constants::match_flag_type flags;
2539      match_results<_Bi_iter>          match;
2540    };
2541
2542  typedef regex_iterator<const char*>             cregex_iterator;
2543  typedef regex_iterator<string::const_iterator>  sregex_iterator;
2544#ifdef _GLIBCXX_USE_WCHAR_T
2545  typedef regex_iterator<const wchar_t*>          wcregex_iterator;
2546  typedef regex_iterator<wstring::const_iterator> wsregex_iterator;
2547#endif
2548
2549  // [7.12.2] Class template regex_token_iterator
2550  /**
2551   * Iterates over submatches in a range (or @a splits a text string).
2552   *
2553   * The purpose of this iterator is to enumerate all, or all specified,
2554   * matches of a regular expression within a text range.  The dereferenced
2555   * value of an iterator of this class is a std::tr1::sub_match object.
2556   */
2557  template<typename _Bi_iter,
2558	   typename _Ch_type = typename iterator_traits<_Bi_iter>::value_type,
2559	   typename _Rx_traits = regex_traits<_Ch_type> >
2560    class regex_token_iterator
2561    {
2562    public:
2563      typedef basic_regex<_Ch_type, _Rx_traits> regex_type;
2564      typedef sub_match<_Bi_iter>               value_type;
2565      typedef std::ptrdiff_t                    difference_type;
2566      typedef const value_type*                 pointer;
2567      typedef const value_type&                 reference;
2568      typedef std::forward_iterator_tag         iterator_category;
2569
2570    public:
2571      /**
2572       * @brief Default constructs a %regex_token_iterator.
2573       * @todo Implement this function.
2574       *
2575       * A default-constructed %regex_token_iterator is a singular iterator
2576       * that will compare equal to the one-past-the-end value for any
2577       * iterator of the same type.
2578       */
2579      regex_token_iterator();
2580
2581      /**
2582       * Constructs a %regex_token_iterator...
2583       * @param a          [IN] The start of the text to search.
2584       * @param b          [IN] One-past-the-end of the text to search.
2585       * @param re         [IN] The regular expression to search for.
2586       * @param submatch   [IN] Which submatch to return.  There are some
2587       *                        special values for this parameter:
2588       *                        - -1 each enumerated subexpression does NOT
2589       *                          match the regular expression (aka field
2590       *                          splitting)
2591       *                        - 0 the entire string matching the
2592       *                          subexpression is returned for each match
2593       *                          within the text.
2594       *                        - >0 enumerates only the indicated
2595       *                          subexpression from a match within the text.
2596       * @param m          [IN] Policy flags for match rules.
2597       *
2598       * @todo Implement this function.
2599       * @doctodo
2600       */
2601      regex_token_iterator(_Bi_iter __a, _Bi_iter __b, const regex_type& __re,
2602			   int __submatch = 0,
2603			   regex_constants::match_flag_type __m
2604			   = regex_constants::match_default);
2605
2606      /**
2607       * Constructs a %regex_token_iterator...
2608       * @param a          [IN] The start of the text to search.
2609       * @param b          [IN] One-past-the-end of the text to search.
2610       * @param re         [IN] The regular expression to search for.
2611       * @param submatches [IN] A list of subexpressions to return for each
2612       *                        regular expression match within the text.
2613       * @param m          [IN] Policy flags for match rules.
2614       *
2615       * @todo Implement this function.
2616       * @doctodo
2617       */
2618      regex_token_iterator(_Bi_iter __a, _Bi_iter __b,
2619			   const regex_type& __re,
2620			   const std::vector<int>& __submatches,
2621			   regex_constants::match_flag_type __m
2622			     = regex_constants::match_default);
2623
2624      /**
2625       * Constructs a %regex_token_iterator...
2626       * @param a          [IN] The start of the text to search.
2627       * @param b          [IN] One-past-the-end of the text to search.
2628       * @param re         [IN] The regular expression to search for.
2629       * @param submatches [IN] A list of subexpressions to return for each
2630       *                        regular expression match within the text.
2631       * @param m          [IN] Policy flags for match rules.
2632
2633       * @todo Implement this function.
2634       * @doctodo
2635       */
2636      template<std::size_t _Nm>
2637        regex_token_iterator(_Bi_iter __a, _Bi_iter __b,
2638			     const regex_type& __re,
2639			     const int (&__submatches)[_Nm],
2640			     regex_constants::match_flag_type __m
2641			     = regex_constants::match_default);
2642
2643      /**
2644       * @brief Copy constructs a %regex_token_iterator.
2645       * @param rhs [IN] A %regex_token_iterator to copy.
2646       * @todo Implement this function.
2647       */
2648      regex_token_iterator(const regex_token_iterator& __rhs);
2649
2650      /**
2651       * @brief Assigns a %regex_token_iterator to another.
2652       * @param rhs [IN] A %regex_token_iterator to copy.
2653       * @todo Implement this function.
2654       */
2655      regex_token_iterator&
2656      operator=(const regex_token_iterator& __rhs);
2657
2658      /**
2659       * @brief Compares a %regex_token_iterator to another for equality.
2660       * @todo Implement this function.
2661       */
2662      bool
2663      operator==(const regex_token_iterator& __rhs);
2664
2665      /**
2666       * @brief Compares a %regex_token_iterator to another for inequality.
2667       * @todo Implement this function.
2668       */
2669      bool
2670      operator!=(const regex_token_iterator& __rhs);
2671
2672      /**
2673       * @brief Dereferences a %regex_token_iterator.
2674       * @todo Implement this function.
2675       */
2676      const value_type&
2677      operator*();
2678
2679      /**
2680       * @brief Selects a %regex_token_iterator member.
2681       * @todo Implement this function.
2682       */
2683      const value_type*
2684      operator->();
2685
2686      /**
2687       * @brief Increments a %regex_token_iterator.
2688       * @todo Implement this function.
2689       */
2690      regex_token_iterator&
2691      operator++();
2692
2693      /**
2694       * @brief Postincrements a %regex_token_iterator.
2695       * @todo Implement this function.
2696       */
2697      regex_token_iterator
2698      operator++(int);
2699
2700    private: // data members for exposition only:
2701      typedef regex_iterator<_Bi_iter, _Ch_type, _Rx_traits> position_iterator;
2702
2703      position_iterator __position;
2704      const value_type* __result;
2705      value_type        __suffix;
2706      std::size_t       __n;
2707      std::vector<int>  __subs;
2708    };
2709
2710  /** @brief Token iterator for C-style NULL-terminated strings. */
2711  typedef regex_token_iterator<const char*>             cregex_token_iterator;
2712  /** @brief Token iterator for standard strings. */
2713  typedef regex_token_iterator<string::const_iterator>  sregex_token_iterator;
2714#ifdef _GLIBCXX_USE_WCHAR_T
2715  /** @brief Token iterator for C-style NULL-terminated wide strings. */
2716  typedef regex_token_iterator<const wchar_t*>          wcregex_token_iterator;
2717  /** @brief Token iterator for standard wide-character strings. */
2718  typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;
2719#endif
2720
2721  ///@}
2722}
2723
2724_GLIBCXX_END_NAMESPACE_VERSION
2725}
2726
2727#endif // _GLIBCXX_TR1_REGEX
2728