OSDN Git Service

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