OSDN Git Service

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