______________________________________________________________________

  21   Strings library                                     [lib.strings]

  ______________________________________________________________________

1 This clause describes components for manipulating sequences of  "char-
  acters,"  where characters may be of any POD (_basic.types_) type.  In
  this clause such types are called  char-like  types,  and  objects  of
  char-like types are called char-like objects or simply "characters."

2 The  following  subclauses describe a character traits class, a string
  class, and null-terminated sequence utilities, as summarized in  Table
  1:

                     Table 1--Strings library summary

     +---------------------------------------------------------------+
     |                    Subclause                        Header(s) |
     +---------------------------------------------------------------+
     |_lib.char.traits_ Character traits                   <string>  |
     +---------------------------------------------------------------+
     |_lib.string.classes_ String classes                  <string>  |
     +---------------------------------------------------------------+
     |                                                     <cctype>  |
     |                                                     <cwctype> |
     |_lib.c.strings_ Null-terminated sequence utilities   <cstring> |
     |                                                     <cwchar>  |
     |                                                     <cstdlib> |
     +---------------------------------------------------------------+

  21.1  Character traits                               [lib.char.traits]

1 This  subclause defines requirements on classes representing character
  traits, and defines a class template  char_traits<charT>,  along  with
  two  specializations, char_traits<char> and char_traits<wchar_t>, that
  satisfy those requirements.

2 Most   classes   specified   in   clauses   _lib.string.classes_   and
  _lib.input.output_  need  a set of related types and functions to com-
  plete the definition of their semantics.  These  types  and  functions
  are provided as a set of member typedefs and functions in the template
  parameter `traits' used by each such template.  This subclause defines
  the semantics guaranteed by these members.

3 To  specialize  those templates to generate a string or iostream class
  to handle a particular character container type CharT,  that  and  its

  related  character  traits class Traits is passed as a pair of parame-
  ters to the string or iostream template as formal parameters charT and
  traits.

4 This  subclause  specifies a struct template, char_traits<charT>, with
  no members, to appear in the header <string> along with  two  explicit
  specializations  of  it,  char_traits<char>  and  char_traits<wchar_t>
  which satisfy the requirements below.

  21.1.1  Definitions                             [lib.char.traits.defs]

1 Additional definitions of terms:

  --character:  In  clauses   _lib.strings_,   _lib.localization_,   and
    _lib.input.output_,  the term character means any object which, when
    treated sequentially, can represent text.  The term  does  not  only
    mean  char  and  wchar_t  objects, but any value which can be repre-
    sented by a type which provides the definitions  specified  in  this
    clause.

  --character container type: A character container type is a class or a
    type used to represent a character.  It is used for one of the  tem-
    plate  parameters  of  the  string  and iostream class templates.  A
    character container class shall be a POD (_basic.types_) type.

  --traits: Traits is a class which encapsulates a set  of  the  defined
    types  and functions necessary for handling character objects in any
    implementation of the string and iostream libraries.

  --NTCTS: A null-terminated character type  string  is  a  sequence  of
    character  type,  that  precede  the termination null character type
    value charT(0).

  21.1.2  Character traits requirements        [lib.char.traits.require]

1 In Table 2, X denotes a Traits class defining types and functions  for
  the  character  container  type  CharT;  c and d denote values of type
  CharT; p and q denote values of type const CharT*; s denotes  a  value
  of  type  CharT*;  n,  i  and  j denote values of type size_t; e and f
  denote values of  type  X::int_type;  pos  denotes  a  value  of  type
  X::pos_type; and state denotes a value of type X::state_type;

                       Table 2--Traits requirements

  -------------------------------------------------------------------------------------------
     expression      return type                assertion/note                  complexity
                                              pre/post-condition
  -------------------------------------------------------------------------------------------
   X::char_type      charT         (described in _lib.char.traits.typedefs_)   compile-time
  -------------------------------------------------------------------------------------------
   X::int_type                     (described in _lib.char.traits.typedefs_)   compile-time
  -------------------------------------------------------------------------------------------
   X::off_type                     (described in _lib.char.traits.typedefs_)   compile-time
  -------------------------------------------------------------------------------------------
   X::pos_type                     (described in _lib.char.traits.typedefs_)   compile-time
  -------------------------------------------------------------------------------------------
   X::state_type                   (described in _lib.char.traits.typedefs_)   compile-time
  -------------------------------------------------------------------------------------------
   X::assign(c,d)    (not used)    assigns c=d.                                constant
  -------------------------------------------------------------------------------------------
   X::eq(c,d)        bool          yields: whether c is to be treated as       constant
                                   equal to d.
  -------------------------------------------------------------------------------------------
   X::lt(c,d)        bool          yields: whether c is to be treated as       constant
                                   less than d.
  -------------------------------------------------------------------------------------------
   X::compare        int           yields: 0 if for each i in [0,n),           linear
   (p,q,n)                         X::eq(p[i],q[i]) is true; else, a nega-
                                   tive value if, for some j in [0,n),
                                   X::lt(p[j],q[j]) is true and for each i
                                   in [0,j) X::eq(p[i],q[i]) is true; else a
                                   positive value.
  -------------------------------------------------------------------------------------------
   X::length(p)      size_t        yields: the smallest i such that            linear
                                   X::eq(p[i],charT(0)) is true.
  -------------------------------------------------------------------------------------------
   X::find(p,n,c)    const X::     yields: the smallest q in [p,p+n) such      linear
                     char_type*    that X::eq(q,c) is true, zero otherwise.
  -------------------------------------------------------------------------------------------
   X::move(s,p,n)    X::           for each i in [0,n), performs X::as-        linear
                     char_type*    sign(s[i],p[i]).  Copies correctly even
                                   where p is in [s,s+n).  yields: s+n.
  -------------------------------------------------------------------------------------------
   X::copy(s,p,n)    X::           pre: p not in [s,s+n).  yields: s+n.  for   linear
                     char_type*    each i in [0,n), performs X::as-
                                   sign(s[i],p[i]).
  -------------------------------------------------------------------------------------------
   X::assign         X::           for each i in [0,n), performs X::as-        linear
   (s,n,c)           char_type*    sign(s[i],c).  yields: s.
  -------------------------------------------------------------------------------------------
   X::not_eof(e)     int_type      yields: e if X::eq(e,X::eof()) is false,    constant
                                   otherwise a value f such that

  |                                                                                         |
  |                                                                                         |
  |                                                                                         |
  |                                                                                         |
  |                                X::eq(f,X::eof()) is false.                              |
  +-----------------------------------------------------------------------------------------+
  |X::               X::           yields: if for some c,                      constant     |
  |to_char_type(e)   char_type     X::eq_int_type(e,X::to_int_type(c)) is                   |
  |                                true, c; else some unspecified value.                    |
  +-----------------------------------------------------------------------------------------+
  |X::to_int_type    X::           yields: some value e, constrained by the    constant     |
  |(c)               int_type      definitions of to_char_type and                          |
  |                                eq_int_type.                                             |
  +-----------------------------------------------------------------------------------------+
  |X::eq_int_type    bool          yields: for all c and d, X::eq(c,d) is      constant     |
  |(e,f)                           equal to                                                 |
  |                                X::eq_int_type(X::to_int_type(c),                        |
  |                                  X::to_int_type(d)); otherwise, yields                  |
  |                                true if e and f are both copies of                       |
  |                                X::eof().                                                |
  +-----------------------------------------------------------------------------------------+
  |X::get_state      X::           yields: state representing the conversion   constant     |
  |(pos)             state_type    state in pos.                                            |
  +-----------------------------------------------------------------------------------------+
  |X::eof()          X::           yields: a value e such that                 constant     |
  |                  int_type      X::eq_int_type(e,X::to_int_type(c)) is                   |
  |                                false for all values c.                                  |
  +-----------------------------------------------------------------------------------------+

2 The struct template
  template<class charT> struct char_traits { };
  shall be provided in the header <string> as a basis for  explicit spe-
  cializations.

3 In  the following subclauses, the token charT represents the parameter
  of the traits template.

  21.1.3  traits typedefs                     [lib.char.traits.typedefs]

  typedef CHAR_T char_type;

1 The type char_type is used to refer to the character container type in
  the    implementation    of    the    library   classes   defined   in
  _lib.string.classes_ and _lib.input.output_.

  typedef INT_T int_type;

  Requires:
    For a certain character container type  char_type,  a  related  con-
    tainer  type  INT_T shall be a type or class which can represent all
    of the valid characters converted from the  corresponding  char_type
    values,  as  well as an end-of-file value, eof().  The type int_type
    represents another character container type which can  hold  end-of-
    file  to be used as a return type of the iostream class member func-
    tions.

  typedef OFF_T off_type;

  Requires:
    For a streambuf or its derived classes specialized  for  CHAR_T  and
    TRAIT_T,  a  type  or class, OFF_T is used to define off_type in the
    traits and represents offsets to positional information for the spe-
    cialized streambuf (or its derived) class.1)

2 It is used to represent:

  --a signed displacement, measured  in  characters,  from  a  specified
    position within a sequence.

  --an absolute position within a sequence.

3 The value OFF_T(-1) can be used as an error indicator.

4 The  effect  of passing to any function in _lib.input.output_ an OFF_T
  value not obtained from a function defined in that clause  (for  exam-
  ple,  an arbitrary integer) is undefined except where otherwise noted.

5 Convertible to type POS_T.  But no validity  of  the  resulting  POS_T
  value is ensured, whether or not the OFF_T value is valid.2)

  typedef POS_T pos_type;

  Requires:
    For  a  streambuf  or its derived classed specialized for CHAR_T and
    TRAIT_T, a type or class, POS_T is used to define pos_type  for  the
    seek  operation.  It can hold all the information necessary to repo-
    sition the specialized streambuf (or its derived) class.

6 The type pos_type represents the type used for the seek  operation  in
  the  implementation  of  streambuf  and  its  derived  classes in this
  library.

  typedef STATE_T state_type;

  Requires:
    For a streambuf or its derived classes whose underlying stream is  a
    multibyte character stream and specialized for CHAR_T and TRAIT_T, a
    type or class STATE_T is used to define state_type in the traits and
    represents  the  conversion  state type or class which is applied to
    the codecvt<> facet defined in _lib.localization_.

  _________________________
  1)  It is usually a synonym for one of the signed basic integral types
  whose representation has at least as many bits as type long.
  2) An implementation may use the same type for both OFF_T and POS_T.

  21.1.4  char_traits                  [lib.char.traits.specializations]
       specializations
  namespace std {
    template<> struct char_traits<char>;
    template<> struct char_traits<wchar_t>;
  }

1 The  header  <string> declares two structs that are specializations of
  the template struct char_traits.

2 The struct char_traits<char> is the char type  specialization  of  the
  template struct char_traits, which contains all of the types and func-
  tions  necessary  to  ensure  the  behaviours  of   the   classes   in
  _lib.string.classes_ and _lib.input.output_.

3 The  types  and  static  member  functions  are described in detail in
  _lib.char.traits.require_.

  21.1.4.1  struct                [lib.char.traits.specializations.char]
       char_traits<char>
  namespace std {
    template<>
    struct char_traits<char> {
      typedef char        char_type;
      typedef int         int_type;
      typedef streamoff   off_type;
      typedef streampos   pos_type;
      typedef mbstate_t   state_type;

      static void assign(char_type& c1, const char_type& c2);
      static bool eq(const char_type& c1, const char_type& c2);
      static bool lt(const char_type& c1, const char_type& c2);

      static int compare(const char_type* s1, const char_type* s2, size_t n);
      static size_t length(const char_type* s);
      static const char_type* find(const char_type* s, int n,
                                   const char_type& a);
      static char_type* move(char_type* s1, const char_type* s2, size_t n);
      static char_type* copy(char_type* s1, const char_type* s2, size_t n);
      static char_type* assign(char_type* s, size_t n, char_type a);

      static int_type not_eof(const int_type& c);
      static char_type to_char_type(const int_type& c);
      static int_type to_int_type(const char_type& c);
      static bool eq_int_type(const int_type& c1, const int_type& c2);
      static state_type get_state(pos_type pos);
      static int_type eof();
    };
  }

1 The  header  <string> (_lib.string.classes_) declares a specialization
  of the template struct char_traits for char.  It  is  for  narrow-ori-
  ented iostream classes.

2 The defined types for int_type, pos_type, off_type, and state_type are
  int, streampos, streamoff, and mbstate_t respectively.

3 The type streampos is an implementation-defined  type  that  satisfies
  the requirements for POS_T in _lib.char.traits.typedefs_.

4 The  type  streamoff  is an implementation-defined type that satisfies
  the requirements for OFF_T in _lib.char.traits.typedefs_.

5 The type mbstate_t is defined in <cwchar> and can represent any of the
  conversion  states  possible to occur in an implementation-defined set
  of supported multibyte character encoding rules.

6 The two-argument members assign, eq, and lt are defined identically to
  the built-in operators =, ==, and < respectively.

  21.1.4.2  struct             [lib.char.traits.specializations.wchar.t]
       char_traits<wchar_t>
  namespace std {
    template<>
    struct char_traits<wchar_t> {
      typedef wchar_t      char_type;
      typedef wint_t       int_type;
      typedef wstreamoff   off_type;
      typedef wstreampos   pos_type;
      typedef mbstate_t    state_type;

      static void assign(char_type& c1, const char_type& c2);
      static bool eq(const char_type& c1, const char_type& c2);
      static bool lt(const char_type& c1, const char_type& c2);

      static int compare(const char_type* s1, const char_type* s2, size_t n);
      static size_t length(const char_type* s);
      static const char_type* find(const char_type* s, int n,
                                   const char_type& a);
      static char_type* move(char_type* s1, const char_type* s2, size_t n);
      static char_type* copy(char_type* s1, const char_type* s2, size_t n);
      static char_type* assign(char_type* s, size_t n, char_type a);

      static int_type not_eof(const int_type& c);
      static char_type to_char_type(const int_type& c);
      static int_type to_int_type(const char_type& c);
      static bool eq_int_type(const int_type& c1, const int_type& c2);
      static state_type get_state(pos_type pos);
      static int_type eof();
    };
  }
  The  header  <string> (_lib.string.classes_) declares a specialization
  of the template struct char_traits for wchar_t.  It is  for  wide-ori-
  ented iostream classes.

1 The defined types for int_type, pos_type, off_type, and state_type are
  wint_t, wstreampos, wstreamoff, and mbstate_t respectively.

2 The type wstreampos is an implementation-defined type  that  satisfies
  the requirements for POS_T in _lib.char.traits.typedefs_.

3 The  type  wstreamoff is an implementation-defined type that satisfies
  the requirements for OFF_T in _lib.char.traits.typedefs_.

4 The pairs  of  types  streampos  and  wstreampos,  and  streamoff  and
  wstreamoff  may  be  different  if  such implementations that adopt no
  shift encoding in narrow-oriented iostreams but supports one  or  more
  shift encodings in wide-oriented streams.

5 The type mbstate_t is defined in <cwchar> and can represent any of the
  conversion states possible to occur in an  implementation-defined  set
  of supported multibyte character encoding rules.

6 The two-argument members assign, eq, and lt are defined identically to
  the built-in operators =, ==, and < respectively.

  21.2  String classes                              [lib.string.classes]

1 The header <string> defines a basic  string  class  template  and  its
  traits  that  can  handle all char-like (_lib.strings_) template argu-
  ments with several function signatures for manipulating varying-length
  sequences of char-like objects.

2 The  header <string> also defines two specific template classes string
  and wstring and their special traits.

  Header <string> synopsis

  namespace std {
  // subclause _lib.char.traits_, character traits:
    template<class charT>
      struct char_traits;
    template <> struct char_traits<char>;
    template <> struct char_traits<wchar_t>;

  // subclause _lib.basic.string_, basic_string:
    template<class charT, class traits = char_traits<charT>,
             class Allocator = allocator<charT> >
      class basic_string;

    template<class charT, class traits, class Allocator>
      basic_string<charT,traits,Allocator>
        operator+(const basic_string<charT,traits,Allocator>& lhs,
                  const basic_string<charT,traits,Allocator>& rhs);
    template<class charT, class traits, class Allocator>
      basic_string<charT,traits,Allocator>
        operator+(const charT* lhs,
                  const basic_string<charT,traits,Allocator>& rhs);
    template<class charT, class traits, class Allocator>
      basic_string<charT,traits,Allocator>
        operator+(charT lhs, const basic_string<charT,traits,Allocator>& rhs);
    template<class charT, class traits, class Allocator>
      basic_string<charT,traits,Allocator>
        operator+(const basic_string<charT,traits,Allocator>& lhs,
                  const charT* rhs);
    template<class charT, class traits, class Allocator>
      basic_string<charT,traits,Allocator>
        operator+(const basic_string<charT,traits,Allocator>& lhs, charT rhs);
    template<class charT, class traits, class Allocator>
      bool operator==(const basic_string<charT,traits,Allocator>& lhs,
                      const basic_string<charT,traits,Allocator>& rhs);
    template<class charT, class traits, class Allocator>
      bool operator==(const charT* lhs,
                      const basic_string<charT,traits,Allocator>& rhs);
    template<class charT, class traits, class Allocator>
      bool operator==(const basic_string<charT,traits,Allocator>& lhs,
                      const charT* rhs);
    template<class charT, class traits, class Allocator>
      bool operator!=(const basic_string<charT,traits,Allocator>& lhs,
                      const basic_string<charT,traits,Allocator>& rhs);
    template<class charT, class traits, class Allocator>
      bool operator!=(const charT* lhs,
                      const basic_string<charT,traits,Allocator>& rhs);
    template<class charT, class traits, class Allocator>
      bool operator!=(const basic_string<charT,traits,Allocator>& lhs,
                      const charT* rhs);
    template<class charT, class traits, class Allocator>
      bool operator< (const basic_string<charT,traits,Allocator>& lhs,
                      const basic_string<charT,traits,Allocator>& rhs);
    template<class charT, class traits, class Allocator>
      bool operator< (const basic_string<charT,traits,Allocator>& lhs,
                      const charT* rhs);
    template<class charT, class traits, class Allocator>
      bool operator< (const charT* lhs,
                      const basic_string<charT,traits,Allocator>& rhs);
    template<class charT, class traits, class Allocator>
      bool operator> (const basic_string<charT,traits,Allocator>& lhs,
                      const basic_string<charT,traits,Allocator>& rhs);
    template<class charT, class traits, class Allocator>
      bool operator> (const basic_string<charT,traits,Allocator>& lhs,
                      const charT* rhs);
    template<class charT, class traits, class Allocator>
      bool operator> (const charT* lhs,
                      const basic_string<charT,traits,Allocator>& rhs);

    template<class charT, class traits, class Allocator>
      bool operator<=(const basic_string<charT,traits,Allocator>& lhs,
                      const basic_string<charT,traits,Allocator>& rhs);
    template<class charT, class traits, class Allocator>
      bool operator<=(const basic_string<charT,traits,Allocator>& lhs,
                      const charT* rhs);
    template<class charT, class traits, class Allocator>
      bool operator<=(const charT* lhs,
                      const basic_string<charT,traits,Allocator>& rhs);
    template<class charT, class traits, class Allocator>
      bool operator>=(const basic_string<charT,traits,Allocator>& lhs,
                      const basic_string<charT,traits,Allocator>& rhs);
    template<class charT, class traits, class Allocator>
      bool operator>=(const basic_string<charT,traits,Allocator>& lhs,
                      const charT* rhs);
    template<class charT, class traits, class Allocator>
      bool operator>=(const charT* lhs,
                      const basic_string<charT,traits,Allocator>& rhs);
  // subclause _lib.string.special_:
    template<class charT, class traits, class Allocator>
       void swap(basic_string<charT,traits,Allocator>& lhs,
                 basic_string<charT,traits,Allocator>& rhs);
    template<class charT, class traits, class Allocator>
     basic_istream<charT,traits>&
      operator>>(basic_istream<charT,traits>& is,
                 basic_string<charT,traits,Allocator>& str);
    template<class charT, class traits, class Allocator>
     basic_ostream<charT, traits>&
      operator<<(basic_ostream<charT, traits>& os,
                 const basic_string<charT,traits,Allocator>& str);
    template<class charT, class traits, class Allocator>
     basic_istream<charT,traits>&
       getline(basic_istream<charT,traits>& is,
               basic_string<charT,traits,Allocator>& str,
               charT delim);
    template<class charT, class traits, class Allocator>
     basic_istream<charT,traits>&
       getline(basic_istream<charT,traits>& is,
               basic_string<charT,traits,Allocator>& str);
    typedef basic_string<char> string;
    typedef basic_string<wchar_t> wstring;
  }

  21.3  Template class basic_string                   [lib.basic.string]

1 For a char-like type charT, the template class basic_string  describes
  objects  that  can  store a sequence consisting of a varying number of
  arbitrary char-like objects (_lib.strings_).  The first element of the
  sequence  is  at  position  zero.   Such  a  sequence is also called a
  "string" if the given char-like type is clear  from  context.  In  the
  rest of this clause, charT denotes such a given char-like type.  Stor-
  age for the string is allocated and freed as necessary by  the  member
  functions of class basic_string.

2 The  template  class  basic_string  conforms  to the requirements of a
  Sequence,  as  specified  in  (_lib.sequence.reqmts_).   Additionally,
  because  the  iterators  supported  by  basic_string are random access
  iterators (_lib.random.access.iterators_),  basic_string  conforms  to
  the  the  requirements  of  a  Reversible  Container,  as specified in
  (_lib.container.requirements_).

3 In all cases, size() <= capacity().

4 The functions described in this clause can report two kinds of errors,
  each associated with a distinct exception:

  --a  length  error  is associated with exceptions of type length_error
    (_lib.length.error_);

  --an  out-of-range  error  is  associated  with  exceptions  of   type
    out_of_range (_lib.out.of.range_).
      namespace std {
        template<class charT, class traits = char_traits<charT>,
                 class Allocator = allocator<charT> >
        class basic_string {
        public:
        // types:
          typedef          traits                     traits_type;
          typedef typename traits::char_type          value_type;
          typedef          Allocator                  allocator_type;
          typedef typename Allocator::size_type       size_type;
          typedef typename Allocator::difference_type difference_type;
          typedef typename Allocator::reference       reference;
          typedef typename Allocator::const_reference const_reference;
          typedef typename Allocator::pointer         pointer;
          typedef typename Allocator::const_pointer   const_pointer;
          typedef implementation defined             iterator;       // See _lib.container.requirements_
          typedef implementation defined             const_iterator; // See _lib.container.requirements_
          typedef std::reverse_iterator<iterator> reverse_iterator;
          typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
          static const size_type npos = -1;
        // _lib.string.cons_ construct/copy/destroy:
          explicit basic_string(const Allocator& a = Allocator());
          basic_string(const basic_string& str, size_type pos = 0,
                       size_type n = npos, const Allocator& a = Allocator());
          basic_string(const charT* s, size_type n, const Allocator& a = Allocator());
          basic_string(const charT* s, const Allocator& a = Allocator());
          basic_string(size_type n, charT c, const Allocator& a = Allocator());
          template<class InputIterator>
            basic_string(InputIterator begin, InputIterator end,
                         const Allocator& a = Allocator());
         ~basic_string();
          basic_string& operator=(const basic_string& str);
          basic_string& operator=(const charT* s);
          basic_string& operator=(charT c);

        // _lib.string.iterators_ iterators:
          iterator       begin();
          const_iterator begin() const;
          iterator       end();
          const_iterator end() const;

          reverse_iterator       rbegin();
          const_reverse_iterator rbegin() const;
          reverse_iterator       rend();
          const_reverse_iterator rend() const;
        // _lib.string.capacity_ capacity:
          size_type size() const;
          size_type length() const;
          size_type max_size() const;
          void resize(size_type n, charT c);
          void resize(size_type n);
          size_type capacity() const;
          void reserve(size_type res_arg = 0);
          void clear();
          bool empty() const;
        // _lib.string.access_ element access:
          const_reference operator[](size_type pos) const;
          reference       operator[](size_type pos);
          const_reference at(size_type n) const;
          reference       at(size_type n);
        // _lib.string.modifiers_ modifiers:
          basic_string& operator+=(const basic_string& str);
          basic_string& operator+=(const charT* s);
          basic_string& operator+=(charT c);
          basic_string& append(const basic_string& str);
          basic_string& append(const basic_string& str, size_type pos,
                               size_type n);
          basic_string& append(const charT* s, size_type n);
          basic_string& append(const charT* s);
          basic_string& append(size_type n, charT c);
          template<class InputIterator>
            basic_string& append(InputIterator first, InputIterator last);
          basic_string& assign(const basic_string&);
          basic_string& assign(const basic_string& str, size_type pos,
                               size_type n);
          basic_string& assign(const charT* s, size_type n);
          basic_string& assign(const charT* s);
          basic_string& assign(size_type n, charT c);
          template<class InputIterator>
            basic_string& assign(InputIterator first, InputIterator last);

          basic_string& insert(size_type pos1, const basic_string& str);
          basic_string& insert(size_type pos1, const basic_string& str,
                               size_type pos2, size_type n);
          basic_string& insert(size_type pos, const charT* s, size_type n);
          basic_string& insert(size_type pos, const charT* s);
          basic_string& insert(size_type pos, size_type n, charT c);
          iterator insert(iterator p, charT c = charT());
          void     insert(iterator p, size_type n, charT c);
          template<class InputIterator>
            void insert(iterator p, InputIterator first, InputIterator last);
          basic_string& erase(size_type pos = 0, size_type n = npos);
          iterator erase(iterator position);
          iterator erase(iterator first, iterator last);
          basic_string& replace(size_type pos1, size_type n1, const basic_string& str);
          basic_string& replace(size_type pos1, size_type n1, const basic_string& str,
                                size_type pos2, size_type n2);
          basic_string& replace(size_type pos, size_type n1, const charT* s,
                                size_type n2);
          basic_string& replace(size_type pos, size_type n1, const charT* s);
          basic_string& replace(size_type pos, size_type n1, size_type n2, charT c);
          basic_string& replace(iterator i1, iterator i2, const basic_string& str);
          basic_string& replace(iterator i1, iterator i2, const charT* s, size_type n);
          basic_string& replace(iterator i1, iterator i2, const charT* s);
          basic_string& replace(iterator i1, iterator i2,
                                size_type n, charT c);
          template<class InputIterator>
            basic_string& replace(iterator i1, iterator i2,
                                  InputIterator j1, InputIterator j2);
          size_type copy(charT* s, size_type n, size_type pos = 0) const;
          void swap(basic_string<charT,traits,Allocator>&);
        // _lib.string.ops_ string operations:
          const charT* c_str() const;  // explicit
          const charT* data() const;
          allocator_type get_allocator() const;
          size_type find (const basic_string& str, size_type pos = 0) const;
          size_type find (const charT* s, size_type pos, size_type n) const;
          size_type find (const charT* s, size_type pos = 0) const;
          size_type find (charT c, size_type pos = 0) const;
          size_type rfind(const basic_string& str, size_type pos = npos) const;
          size_type rfind(const charT* s, size_type pos, size_type n) const;
          size_type rfind(const charT* s, size_type pos = npos) const;
          size_type rfind(charT c, size_type pos = npos) const;
          size_type find_first_of(const basic_string& str, size_type pos = 0) const;
          size_type find_first_of(const charT* s, size_type pos, size_type n) const;
          size_type find_first_of(const charT* s, size_type pos = 0) const;
          size_type find_first_of(charT c, size_type pos = 0) const;
          size_type find_last_of (const basic_string& str,
                                  size_type pos = npos) const;
          size_type find_last_of (const charT* s, size_type pos, size_type n) const;
          size_type find_last_of (const charT* s, size_type pos = npos) const;
          size_type find_last_of (charT c, size_type pos = npos) const;

          size_type find_first_not_of(const basic_string& str,
                                      size_type pos = 0) const;
          size_type find_first_not_of(const charT* s, size_type pos,
                                      size_type n) const;
          size_type find_first_not_of(const charT* s, size_type pos = 0) const;
          size_type find_first_not_of(charT c, size_type pos = 0) const;
          size_type find_last_not_of (const basic_string& str,
                                      size_type pos = npos) const;
          size_type find_last_not_of (const charT* s, size_type pos,
                                      size_type n) const;
          size_type find_last_not_of (const charT* s, size_type pos = npos) const;
          size_type find_last_not_of (charT c, size_type pos = npos) const;
          basic_string substr(size_type pos = 0, size_type n = npos) const;
          int compare(const basic_string& str) const;
          int compare(size_type pos1, size_type n1,
                      const basic_string& str) const;
          int compare(size_type pos1, size_type n1,
                      const basic_string& str,
                      size_type pos2, size_type n2) const;
          int compare(const charT* s) const;
          int compare(size_type pos1, size_type n1,
                      const charT* s, size_type n2 = npos) const;
        };
      }

  21.3.1  basic_string constructors                    [lib.string.cons]

1 In  all basic_string constructors, a copy of the Allocator argument is
  used for any memory allocation performed by the constructor or  member
  functions during the lifetime of the object.

  explicit basic_string(const Allocator& a = Allocator());

  Effects:
    Constructs  an  object of class basic_string.  The postconditions of
    this function are indicated in Table 3:

              Table 3--basic_string(const Allocator&) effects

  +----------------------------------------------------------------------------+
  | Element                                 Value                              |
  +----------------------------------------------------------------------------+
  |data()       a non-null pointer that is copyable and can have 0 added to it |
  |size()       0                                                              |
  |capacity()   an unspecified value                                           |
  +----------------------------------------------------------------------------+

  basic_string(const basic_string<charT,traits,Allocator>& str,
               size_type pos = 0, size_type n = npos,
               const Allocator& a = Allocator());

  Requires:
    pos <= str.size()
  Throws:
    out_of_range if pos > str.size().
  Effects:
    Constructs an object of class basic_string and determines the effec-
    tive length rlen of the initial string value as the smaller of n and
    str.size() - pos, as indicated in Table 4:

    Table 4--basic_string(basic_string,size_type,size_type,const Allocator&) effects

          +------------------------------------------------------+
          |    Element                      Value                |
          +------------------------------------------------------+
          |data()            points at the first element  of  an |
          |                  allocated  copy of rlen consecutive |
          |                  elements of the  string  controlled |
          |                  by str beginning at position pos    |
          |size()            rlen                                |
          |capacity()        a value at least as large as size() |
          |get_allocator()   str.get_allocator()                 |
          +------------------------------------------------------+

  basic_string(const charT* s, size_type n,
               const Allocator& a = Allocator());

  Requires:
    s shall not be a null pointer and n < npos.
  Throws:
    out_of_range if n == npos.
  Effects:
    Constructs  an  object of class basic_string and determines its ini-
    tial string value from the array of charT of length  n  whose  first
    element is designated by s, as indicated in Table 5:

    Table 5--basic_string(const charT*,size_type, const Allocator&) effects

             +-------------------------------------------------+
             | Element                    Value                |
             +-------------------------------------------------+
             |data()       points  at  the first element of an |
             |             allocated copy of the  array  whose |
             |             first element is pointed at by s    |
             |size()       n                                   |
             |capacity()   a value at least as large as size() |
             +-------------------------------------------------+

  basic_string(const charT* s, const Allocator& a = Allocator());

  Requires:
    s shall not be a null pointer.
  Effects:
    Constructs  an  object of class basic_string and determines its ini-
    tial  string   value   from   the   array   of   charT   of   length
    traits::length(s)  whose first element is designated by  s, as indi-
    cated in Table 6:

        Table 6--basic_string(const charT*,const Allocator&) effects

             +-------------------------------------------------+
             | Element                    Value                |
             +-------------------------------------------------+
             |data()       points at the first element  of  an |
             |             allocated  copy  of the array whose |
             |             first element is pointed at by s    |
             |size()       traits::length(s)                   |
             |capacity()   a value at least as large as size() |
             +-------------------------------------------------+
  Notes:
    Uses traits::length().

  basic_string(size_type n, charT c, const Allocator& a = Allocator());

  Requires:
    n < npos
  Throws:
    length_error if n == npos.
  Effects:
    Constructs an object of class basic_string and determines  its  ini-
    tial string value by repeating the char-like object c for all n ele-
    ments, as indicated in Table 7:

      Table 7--basic_string(size_type,charT,const Allocator&) effects

             +-------------------------------------------------+
             | Element                    Value                |
             +-------------------------------------------------+
             |data()       points at the first element  of  an |
             |             allocated array of n elements, each |
             |             storing the initial value c         |
             |size()       n                                   |
             |capacity()   a value at least as large as size() |
             +-------------------------------------------------+

  template<class InputIterator>
    basic_string(InputIterator begin, InputIterator end,
                 const Allocator& a = Allocator());

  Effects:
    Constructs a string from the values in the range  [begin,  end),  as
    indicated in Table 8:

    Table 8--basic_string(InputIterator,InputIterator,const Allocator&) effects

             +-------------------------------------------------+
             | Element                    Value                |
             +-------------------------------------------------+
             |data()       points  at  the first element of an |
             |             allocated copy of the  elements  in |
             |             the range [begin,end)               |
             |size()       distance between begin and end      |
             |capacity()   a value at least as large as size() |
             +-------------------------------------------------+
  Notes:
    see clause _lib.sequence.reqmts_.

  basic_string<charT,traits,Allocator>&
    operator=(const basic_string<charT,traits,Allocator>& str);

  Effects:
    If *this and str are not the same object, modifies *this as shown in
    Table 9:

    Table 9--operator=(const basic_string<charT,traits,Allocator>&) effects

             +-------------------------------------------------+
             | Element                    Value                |
             +-------------------------------------------------+
             |data()       points at the first element  of  an |
             |             allocated  copy  of the array whose |
             |             first  element  is  pointed  at  by |
             |             str.data()                          |
             |size()       str.size()                          |
             |capacity()   a value at least as large as size() |
             +-------------------------------------------------+
    If *this and str are the same object, the member has no effect.
  Returns:
    *this

  basic_string<charT,traits,Allocator>&
    operator=(const charT* s);

  Returns:
    *this = basic_string<charT,traits,Allocator>(s).
  Notes:
    Uses traits::length().

  basic_string<charT,traits,Allocator>& operator=(charT c);

  Returns:
    *this = basic_string<charT,traits,Allocator>(1,c).

  21.3.2  basic_string iterator support           [lib.string.iterators]

  iterator       begin();
  const_iterator begin() const;

  Returns:
    an iterator referring to the first character in the string.

  iterator       end();
  const_iterator end() const;

  Returns:
    an iterator which is the past-the-end value.

  reverse_iterator       rbegin();
  const_reverse_iterator rbegin() const;

  Returns:
    an  iterator  which  is  semantically  equivalent  to reverse_itera-
    tor(end()).

  reverse_iterator       rend();
  const_reverse_iterator rend() const;

  Returns:
    an iterator  which  is  semantically  equivalent  to  reverse_itera-
    tor(begin()).

  21.3.3  basic_string capacity                    [lib.string.capacity]

  size_type size() const;

  Returns:
    a  count of the number of char-like objects currently in the string.

  size_type length() const;

  Returns:
    size().

  size_type max_size() const;

  Returns:
    The maximum size of the string.

  void resize(size_type n, charT c);

  Requires:
    n <= max_size()
  Throws:
    length_error if n > max_size().
  Effects:
    Alters the length of the string designated by *this as follows:

  --If n <= size(), the function replaces the string designated by *this
    with  a  string of length n whose elements are a copy of the initial
    elements of the original string designated by *this.

  --If n > size(), the function replaces the string designated by  *this
    with  a string of length n whose first size() elements are a copy of
    the original string designated by *this, and  whose  remaining  ele-
    ments are all initialized to c.

  void resize(size_type n);

  Effects:
    resize(n,charT()).

  size_type capacity() const;

  Returns:
    the size of the allocated storage in the string.

  void reserve(size_type res_arg=0);

1 The   member   function  reserve()  is  a  directive  that  informs  a
  basic_string object of a planned change in size, so that it can manage
  the storage allocation accordingly.
  Effects:
    After  reserve(),  capacity() is greater or equal to the argument of
    reserve.  Reallocation invalidates all the references, pointers, and
    iterators referring to the elements in the sequence.

  void clear();

  Effects:
    Behaves as if the function calls:

  erase(begin(), end());

  bool empty() const;

  Returns:
    size() == 0.

  21.3.4  basic_string element access                [lib.string.access]

  const_reference operator[](size_type pos) const;
  reference       operator[](size_type pos);

  Effects:
    The  reference  returned  is  invalid  after  any subsequent call to
    c_str(), data(), or any non-const member function for the object.
  Returns:
    If pos < size(), returns data()[pos].  Otherwise, if pos ==  size(),
    the const version returns traits::eos().  Otherwise, the behavior is
    undefined.

  const_reference at(size_type pos) const;
  reference       at(size_type pos);

  Requires:
    pos < size()
  Throws:
    out_of_range if pos >= size().
  Returns:
    operator[](pos).

  21.3.5  basic_string modifiers                  [lib.string.modifiers]

  21.3.5.1  basic_string::operator+=                  [lib.string::op+=]

  basic_string<charT,traits,Allocator>&
    operator+=(const basic_string<charT,traits,Allocator>& str);

  Returns:
    append(str).

  basic_string<charT,traits,Allocator>& operator+=(const charT* s);

  Returns:
    *this += basic_string<charT,traits,Allocator>(s).
  Notes:
    Uses traits::length().

  basic_string<charT,traits,Allocator>& operator+=(charT c);

  Returns:
    *this += basic_string<charT,traits,Allocator>(1,c).

  21.3.5.2  basic_string::append                    [lib.string::append]

  basic_string<charT,traits,Allocator>&
    append(const basic_string<charT,traits>& str);

  Returns:
    append(str, 0, npos).

  basic_string<charT,traits,Allocator>&
    append(const basic_string<charT,traits>& str, size_type pos, size_type n);

  Requires:
    pos <= str.size()
  Throws:
    out_of_range if pos > str.size().

  Effects:
    Determines the effective length rlen of the string to append as  the
    smaller  of  n  and  str.size()  -  pos.   The  function then throws
    length_error if size() >= npos - rlen.
    Otherwise, the function replaces the string controlled by *this with
    a  string  of length size() + rlen whose first size() elements are a
    copy of the original string controlled by *this and whose  remaining
    elements are a copy of the initial elements of the string controlled
    by str beginning at position pos.
  Returns:
    *this.

  basic_string<charT,traits,Allocator>&
    append(const charT* s, size_type n);

  Returns:
    append(basic_string<charT,traits,Allocator>(s,n)).

  basic_string<charT,traits,Allocator>& append(const charT* s);

  Returns:
    append(basic_string<charT,traits,Allocator>(s)).
  Notes:
    Uses traits::length().

  basic_string<charT,traits,Allocator>&
    append(size_type n, charT c);

  Returns:
    append(basic_string<charT,traits,Allocator>(n,c)).

  template<class InputIterator>
    basic_string& append(InputIterator first, InputIterator last);

  Returns:
    append(basic_string<charT,traits,Allocator>(first,last)).

  21.3.5.3  basic_string::assign                    [lib.string::assign]

  basic_string<charT,traits,Allocator>&
    assign(const basic_string<charT,traits>& str);

  Returns:
    assign(str, 0, npos).

  basic_string<charT,traits,Allocator>&
    assign(const basic_string<charT,traits>& str, size_type pos,
           size_type n);

  Requires:
    pos <= str.size()
  Throws:
    out_of_range if pos > str.size().
  Effects:
    Determines the effective length rlen of the string to assign as  the
    smaller of n and str.size() - pos.
    The  function  then  replaces  the string controlled by *this with a
    string of length rlen whose elements are a copy of the  string  con-
    trolled by str beginning at position pos.
  Returns:
    *this.

  basic_string<charT,traits,Allocator>&
    assign(const charT* s, size_type n);

  Returns:
    assign(basic_string<charT,traits,Allocator>(s,n)).

  basic_string<charT,traits,Allocator>& assign(const charT* s);

  Returns:
    assign(basic_string<charT, traits, Allocator>(s)).
  Notes:
    Uses traits::length().

  basic_string<charT,traits,Allocator>&
    assign(size_type n, charT c);

  Returns:
    assign(basic_string<charT,traits,Allocator>(n,c)).

  template<class InputIterator>
    basic_string& assign(InputIterator first, InputIterator last);

  Returns:
    assign(basic_string<charT,traits,Allocator>(first,last)).

  21.3.5.4  basic_string::insert                    [lib.string::insert]

  basic_string<charT,traits,Allocator>&
    insert(size_type pos1,
           const basic_string<charT,traits,Allocator>& str);

  Returns:
    insert(pos1,str,0,npos).

  basic_string<charT,traits,Allocator>&
    insert(size_type pos1,
           const basic_string<charT,traits,Allocator>& str,
           size_type pos2, size_type n);

  Requires
    pos1 <= size() and pos2 <= str.size()
  Throws:
    out_of_range if pos1 > size() or pos2 > str.size().
  Effects:
    Determines  the effective length rlen of the string to insert as the
    smaller of n and str.size() - pos2.   Then  throws  length_error  if
    size() >= npos - rlen.
    Otherwise, the function replaces the string controlled by *this with
    a string of length size() + rlen whose first  pos1  elements  are  a
    copy  of  the  initial elements of the original string controlled by
    *this, whose next rlen elements are a copy of the  elements  of  the
    string  controlled  by  str  beginning  at  position pos2, and whose
    remaining elements are a copy of the remaining elements of the orig-
    inal string controlled by *this.
  Returns:
    *this.

  basic_string<charT,traits,Allocator>&
    insert(size_type pos, const charT* s, size_type n);

  Returns:
    insert(pos,basic_string<charT,traits,Allocator>(s,n)).

  basic_string<charT,traits,Allocator>&
    insert(size_type pos, const charT* s);

  Returns:
    insert(pos,basic_string<charT,traits,Allocator>(s)).
  Notes:
    Uses traits::length().

  basic_string<charT,traits,Allocator>&
    insert(size_type pos, size_type n, charT c);

  Returns:
    insert(pos,basic_string<charT,traits,Allocator>(n,c)).

  iterator insert(iterator p, charT c);

  Requires:
    p is a valid iterator on *this.
  Effects:
    inserts a copy of c before the character referred to by p.
  Returns:
    an iterator which refers to the copy of the inserted character.

  void insert(iterator p, size_type n, charT c);

  Requires:
    p is a valid iterator on *this.
  Effects:
    inserts n copies of c before the character referred to by p.

  template<class InputIterator>
    void insert(iterator p, InputIterator first, InputIterator last);

  Requires:
    p is a valid iterator on *this.  [first,last) is a valid range.
  Effects:
    inserts  copies  of  the characters in the range [first,last) before
    the character referred to by p.

  21.3.5.5  basic_string::erase                      [lib.string::erase]

  basic_string<charT,traits,Allocator>&
    erase(size_type pos = 0, size_type n = npos);

  Requires:
    pos  <= size()
  Throws:
    out_of_range if pos  > size().
  Effects:
    Determines the effective length xlen of the string to be removed  as
    the smaller of n and size() - pos.
    The  function  then  replaces  the string controlled by *this with a
    string of length size() - xlen whose first pos elements are  a  copy
    of  the initial elements of the original string controlled by *this,
    and whose remaining elements are a copy of the elements of the orig-
    inal string controlled by *this beginning at position pos + xlen.
  Returns:
    *this.

  iterator erase(iterator p);

  Requires:
    p is a valid iterator on *this.
  Effects:
    removes the character referred to by p.

  Returns:
    an  iterator  which  points  to  the element immediately following p
    prior to the element being erased.  If no such element exists, end()
    is returned.

  iterator erase(iterator first, iterator last);

  Requires:
    first  and  last  are  valid  iterators  on  *this, defining a range
    [first,last).
  Effects:
    removes the characters in the range [first,last).
  Returns:
    an iterator which points to the element immediately  following  last
    prior to the element being erased.  If no such element exists, end()
    is returned.

  21.3.5.6  basic_string::replace                  [lib.string::replace]

  basic_string<charT,traits,Allocator>&
    replace(size_type pos1, size_type n1,
            const basic_string<charT,traits,Allocator>& str);

  Returns:
    replace(pos1, n1, str, 0, npos).

  basic_string<charT,traits,Allocator>&
    replace(size_type pos1, size_type n1,
            const basic_string<charT,traits,Allocator>& str,
            size_type pos2, size_type n2);

  Requires:
    pos1 <= size() && pos2 <= str.size().
  Throws:
    out_of_range if pos1 > size() or pos2 > str.size().
  Effects:
    Determines the effective length xlen of the string to be removed  as
    the  smaller of n1 and size() - pos1.  It also determines the effec-
    tive length rlen of the string to be inserted as the smaller  of  n2
    and str.size() - pos2 .
    Throws length_error if size() - xlen >= npos - rlen.
    Otherwise, the function replaces the string controlled by *this with
    a string of length size() - xlen + rlen whose  first  pos1  elements
    are a copy of the initial elements of the original string controlled
    by *this, whose next rlen elements are a copy of  the  initial  ele-
    ments  of  the  string controlled by str beginning at position pos2,
    and whose remaining elements are a copy of the elements of the orig-
    inal string controlled by *this beginning at position pos1 + xlen.
  Returns:
    *this.

  basic_string<charT,traits,Allocator>&
    replace(size_type pos, size_type n1, const charT* s, size_type n2);

  Returns:
    replace(pos,n1,basic_string<charT,traits,Allocator>(s,n2)).

  basic_string<charT,traits,Allocator>&
    replace(size_type pos, size_type n1, const charT* s);

  Returns:
    replace(pos,n1,basic_string<charT,traits,Allocator>(s)).
  Notes:
    Uses traits::length().

  basic_string<charT,traits,Allocator>&
    replace(size_type pos, size_type n1,
            size_type n2, charT c);

  Returns:
    replace(pos,n1,basic_string<charT,traits,Allocator>(n2,c)).

  basic_string& replace(iterator i1, iterator i2, const basic_string& str);

  Requires:
    The  iterators  i1  and  i2 are valid iterators on *this, defining a
    range [i1,i2).
  Effects:
    Replaces the string controlled by *this  with  a  string  of  length
    size()  -  (i2  - i1) + str.size() whose first begin() - i1 elements
    are a copy of the initial elements of the original string controlled
    by  *this,  whose  next str.size() elements are a copy of the string
    controlled by str, and whose remaining elements are a  copy  of  the
    elements  of  the  original  string controlled by *this beginning at
    position i2.
  Returns:
    *this.
  Notes:
    After the call, the  length  of  the  string  will  be  changed  by:
    str.size() - (i2 - i1).

  basic_string&
    replace(iterator i1, iterator i2, const charT* s, size_type n);

  Returns:
    replace(i1,i2,basic_string(s,n)).
  Notes:
    Length change: n - (i2 - i1).

  basic_string& replace(iterator i1, iterator i2, const charT* s);

  Returns:
    replace(i1,i2,basic_string(s)).
  Notes:
    Length change: traits::length(s) - (i2 - i1).
    Uses traits::length().

  basic_string& replace(iterator i1, iterator i2, size_type n,
                        charT c);

  Returns:
    replace(i1,i2,basic_string(n,c)).
  Notes:
    Length change: n - (i2 - i1).

  template<class InputIterator>
    basic_string& replace(iterator i1, iterator i2,
                          InputIterator j1, InputIterator j2);

  Returns:
    replace(i1,i2,basic_string(j1,j2)).
  Notes:
    Length change: j2 - j1 - (i2 - i1).

  21.3.5.7  basic_string::copy                        [lib.string::copy]

  size_type copy(charT* s, size_type n, size_type pos = 0) const;

  Requires:
    pos <= size()
  Throws:
    out_of_range if pos > size().
  Effects:
    Determines  the  effective  length rlen of the string to copy as the
    smaller of n and size() - pos.  s shall designate  an  array  of  at
    least rlen elements.
    The  function then replaces the string designated by s with a string
    of length rlen whose elements are a copy of the string controlled by
    *this beginning at position pos.
    The  function does not append a null object to the string designated
    by s.
  Returns:
    rlen.

  21.3.5.8  basic_string::swap                        [lib.string::swap]

  void swap(basic_string<charT,traits,Allocator>& s);

  Effects:
    Swaps the contents of the two strings.
  Postcondition:
    *this contains the characters that were in s, s contains the charac-
    ters that were in *this.
  Complexity:
    constant time.

  21.3.6  basic_string string operations                [lib.string.ops]

  const charT* c_str() const;

  Returns:
    A  pointer  to  the initial element of an array of length size() + 1
    whose first size() elements equal the corresponding elements of  the
    string  controlled by *this and whose last element is a null charac-
    ter specified by traits::eos().
  Requires:
    The program shall not alter any of the values stored in  the  array.
    Nor  shall  the  program treat the returned value as a valid pointer
    value after any subsequent call to a non-const  member  function  of
    the class basic_string that designates the same object as this.
  Notes:
    Uses traits::eos().

  const charT* data() const;

  Returns:
    If  size()  is  nonzero, the member returns a pointer to the initial
    element of an array whose first size()  elements  equal  the  corre-
    sponding  elements  of the string controlled by *this.  If size() is
    zero, the member returns a non-null pointer that is copyable and can
    have zero added to it.
  Requires:
    The  program shall not alter any of the values stored in the charac-
    ter array.  Nor shall the program treat  the  returned  value  as  a
    valid pointer value after any subsequent call to a non- const member
    function of basic_string that designates the same object as this.

  allocator_type get_allocator() const;

  Returns:
    a copy of the Allocator object used to construct the string.

  21.3.6.1  basic_string::find                        [lib.string::find]

  size_type find(const basic_string<charT,traits,Allocator>& str,
                 size_type pos = 0) const;

  Effects:
    Determines the lowest position xpos, if possible, such that both  of
    the following conditions obtain:

  --pos <= xpos and xpos + str.size() <= size();

  --at(xpos+I)  == str.at(I) for all elements I of the string controlled
    by str.
  Returns:
    xpos if the function can determine such a value  for  xpos.   Other-
    wise, returns npos.
  Notes:
    Uses traits::eq().

  size_type find(const charT* s, size_type pos, size_type n) const;

  Returns:
    find(basic_string<charT,traits,Allocator>(s,n),pos).

  size_type find(const charT* s, size_type pos = 0) const;

  Returns:
    find(basic_string<charT,traits,Allocator>(s),pos).
  Notes:
    Uses traits::length().

  size_type find(charT c, size_type pos = 0) const;

  Returns:
    find(basic_string<charT,traits,Allocator>(1,c),pos).

  21.3.6.2  basic_string::rfind                      [lib.string::rfind]

  size_type rfind(const basic_string<charT,traits,Allocator>& str,
                  size_type pos = npos) const;

  Effects:
    Determines the highest position xpos, if possible, such that both of
    the following conditions obtain:

  --xpos <= pos and xpos + str.size() <= size();

  --at(xpos+I) == str.at(I) for all elements I of the string  controlled

    by str.
  Returns:
    xpos  if  the  function can determine such a value for xpos.  Other-
    wise, returns npos.
  Notes:
    Uses traits::eq().

  size_type rfind(const charT* s, size_type pos, size_type n) const;

  Returns:
    rfind(basic_string<charT,traits,Allocator>(s,n),pos).

  size_type rfind(const charT* s, size_type pos = npos) const;

  Returns:
    rfind(basic_string<charT,traits,Allocator>(s),pos).
  Notes:
    Uses traits::length().

  size_type rfind(charT c, size_type pos = npos) const;

  Returns:
    rfind(basic_string<charT,traits,Allocator>(1,c),pos).

  21.3.6.3  basic_string::find_first_of      [lib.string::find.first.of]

  size_type
    find_first_of(const basic_string<charT,traits,Allocator>& str,
                  size_type pos = 0) const;

  Effects:
    Determines  the lowest position xpos, if possible, such that both of
    the following conditions obtain:

  --pos <= xpos and xpos < size();

  --at(xpos) == str.at(I) for some element I of the string controlled by
    str.
  Returns:
    xpos  if  the  function can determine such a value for xpos.  Other-
    wise, returns npos.
  Notes:
    Uses traits::eq().

  size_type
    find_first_of(const charT* s, size_type pos, size_type n) const;

  Returns:
    find_first_of(basic_string<charT,traits,Allocator>(s,n),pos).

  size_type find_first_of(const charT* s, size_type pos = 0) const;

  Returns:
    find_first_of(basic_string<charT,traits,Allocator>(s),pos).
  Notes:
    Uses traits::length().

  size_type find_first_of(charT c, size_type pos = 0) const;

  Returns:
    find_first_of(basic_string<charT,traits,Allocator>(1,c),pos).

  21.3.6.4  basic_string::find_last_of        [lib.string::find.last.of]

  size_type
    find_last_of(const basic_string<charT,traits,Allocator>& str,
                 size_type pos = npos) const;

  Effects:
    Determines the highest position xpos, if possible, such that both of
    the following conditions obtain:

  --xpos <= pos and pos < size();

  --at(xpos) == str.at(I) for some element I of the string controlled by
    str.
  Returns:
    xpos if the function can determine such a value  for  xpos.   Other-
    wise, returns npos.
  Notes:
    Uses traits::eq().

  size_type find_last_of(const charT* s, size_type pos, size_type n) const;

  Returns:
    find_last_of(basic_string<charT,traits,Allocator>(s,n),pos).

  size_type find_last_of(const charT* s, size_type pos = npos) const;

  Returns:
    find_last_of(basic_string<charT,traits,Allocator>(s),pos).
  Notes:
    Uses traits::length().

  size_type find_last_of(charT c, size_type pos = npos) const;

  Returns:
    find_last_of(basic_string<charT,traits,Allocator>(1,c),pos).

  21.3.6.5                               [lib.string::find.first.not.of]
       basic_string::find_first_not_of

  size_type
    find_first_not_of(const basic_string<charT,traits,Allocator>& str,
                      size_type pos = 0) const;

  Effects:
    Determines  the lowest position xpos, if possible, such that both of
    the following conditions obtain:

  --pos <= xpos and xpos < size();

  --at(xpos) == str.at(I) for no element I of the string  controlled  by
    str.
  Returns:
    xpos  if  the  function can determine such a value for xpos.  Other-
    wise, returns npos.
  Notes:
    Uses traits::eq().

  size_type
    find_first_not_of(const charT* s, size_type pos, size_type n) const;

  Returns:
    find_first_not_of(basic_string<charT,traits,Allocator>(s,n),pos).

  size_type find_first_not_of(const charT* s, size_type pos = 0) const;

  Returns:
    find_first_not_of(basic_string<charT,traits,Allocator>(s),pos).
  Notes:
    Uses traits::length().

  size_type find_first_not_of(charT c, size_type pos = 0) const;

  Returns:
    find_first_not_of(basic_string<charT,traits,Allocator>(1,c),pos).

  21.3.6.6                                [lib.string::find.last.not.of]
       basic_string::find_last_not_of

  size_type
    find_last_not_of(const basic_string<charT,traits,Allocator>& str,
                     size_type pos = npos) const;

  Effects:
    Determines the highest position xpos, if possible, such that both of
    the following conditions obtain:

  --xpos <= pos and pos < size();

  --at(xpos)  == str.at(I)) for no element I of the string controlled by
    str.
  Returns:
    xpos if the function can determine such a value  for  xpos.   Other-
    wise, returns npos.
  Notes:
    Uses traits::eq().

  size_type find_last_not_of(const charT* s, size_type pos,
                             size_type n) const;

  Returns:
    find_last_not_of(basic_string<charT,traits,Allocator>(s,n),pos).

  size_type find_last_not_of(const charT* s, size_type pos = npos) const;

  Returns:
    find_last_not_of(basic_string<charT,traits,Allocator>(s),pos).
  Notes:
    Uses traits::length().

  size_type find_last_not_of(charT c, size_type pos = npos) const;

  Returns:
    find_last_not_of(basic_string<charT,traits,Allocator>(1,c),pos).

  21.3.6.7  basic_string::substr                    [lib.string::substr]

  basic_string<charT,traits,Allocator>
    substr(size_type pos = 0, size_type n = npos) const;

  Requires:
    pos <= size()
  Throws:
    out_of_range if pos > size().
  Effects:
    Determines  the  effective  length rlen of the string to copy as the
    smaller of n and size() - pos.

  Returns:
    basic_string<charT,traits,Allocator>(data()+pos,rlen).

  21.3.6.8  basic_string::compare                  [lib.string::compare]

  int compare(const basic_string<charT,traits,Allocator>& str)

  Effects:
    Determines the effective length rlen of the strings  to  compare  as
    the  smallest  of size() and str.size().  The function then compares
    the  two  strings  by  calling  traits::compare(data(),  str.data(),
    rlen).
  Returns:
    the nonzero result if the result of the comparison is nonzero.  Oth-
    erwise, returns a value as indicated in Table 10:

                        Table 10--compare() results

                   +------------------------------------+
                   |     Condition         Return Value |
                   +------------------------------------+
                   |size() <  str.size()   < 0          |
                   |size() == str.size()     0          |
                   |size() >  str.size()   > 0          |
                   +------------------------------------+

  int compare(size_type pos1, size_type n1,
              const basic_string<charT,traits,Allocator>& str) const;

  Returns:

  basic_string<charT,traits,Allocator>(*this,pos1,n1).compare(
               str) .

  int compare(size_type pos1, size_type n1,
              const basic_string<charT,traits,Allocator>& str,
              size_type pos2, size_type n2) const;

  Returns:

  basic_string<charT,traits,Allocator>(*this,pos1,n1).compare(
               basic_string<charT,traits,Allocator>(str,pos2,n2)) .

  int compare(const charT *s) const;

  Returns:
    this->compare(basic_string<charT,traits,Allocator>(s)).

  int compare(size_type pos, size_type n1,
              charT *s, size_type n2 = npos) const;

  Returns:

  basic_string<charT,traits,Allocator>(*this,pos,n1).compare(
               basic_string<charT,traits,Allocator>(s,n2))

  21.3.7  basic_string non-member functions      [lib.string.nonmembers]

  21.3.7.1  operator+                                  [lib.string::op+]

  template<class charT, class traits, class Allocator>
    basic_string<charT,traits,Allocator>
      operator+(const basic_string<charT,traits,Allocator>& lhs,
                const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    basic_string<charT,traits,Allocator>(lhs).append(rhs)

  template<class charT, class traits, class Allocator>
    basic_string<charT,traits,Allocator>
      operator+(const charT* lhs,
                const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    basic_string<charT,traits,Allocator>(lhs) + rhs.
  Notes:
    Uses traits::length().

  template<class charT, class traits, class Allocator>
    basic_string<charT,traits,Allocator>
      operator+(charT lhs,
                const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    basic_string<charT,traits,Allocator>(1,lhs) + rhs.

  template<class charT, class traits, class Allocator>
    basic_string<charT,traits,Allocator>
      operator+(const basic_string<charT,traits,Allocator>& lhs,
                const charT* rhs);

  Returns:
    lhs + basic_string<charT,traits,Allocator>(rhs).
  Notes:
    Uses traits::length().

  template<class charT, class traits, class Allocator>
    basic_string<charT,traits,Allocator>
      operator+(const basic_string<charT,traits,Allocator>& lhs,
                charT rhs);

  Returns:
    lhs + basic_string<charT,traits,Allocator>(1,rhs).

  21.3.7.2  operator==                          [lib.string::operator==]

  template<class charT, class traits, class Allocator>
    bool operator==(const basic_string<charT,traits,Allocator>& lhs,
                    const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    lhs.compare(rhs) == 0.

  template<class charT, class traits, class Allocator>
    bool operator==(const charT* lhs,
                    const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    basic_string<charT,traits,Allocator>(lhs) == rhs.

  template<class charT, class traits, class Allocator>
    bool operator==(const basic_string<charT,traits,Allocator>& lhs,
                    const charT* rhs);

  Returns:
    lhs == basic_string<charT,traits,Allocator>(rhs).
  Notes:
    Uses traits::length().

  21.3.7.3  operator!=                                [lib.string::op!=]

  template<class charT, class traits, class Allocator>
    bool operator!=(const basic_string<charT,traits,Allocator>& lhs,
                    const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    !(lhs == rhs).

  template<class charT, class traits, class Allocator>
    bool operator!=(const charT* lhs,
                    const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    basic_string<charT,traits,Allocator>(lhs) != rhs.

  template<class charT, class traits, class Allocator>
    bool operator!=(const basic_string<charT,traits,Allocator>& lhs,
                    const charT* rhs);

  Returns:
    lhs != basic_string<charT,traits,Allocator>(rhs).
  Notes:
    Uses traits::length().

  21.3.7.4  operator<                                  [lib.string::op<]

  template<class charT, class traits, class Allocator>
    bool operator< (const basic_string<charT,traits,Allocator>& lhs,
                    const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    lhs.compare(rhs) < 0.

  template<class charT, class traits, class Allocator>
    bool operator< (const charT* lhs,
                    const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    basic_string<charT,traits,Allocator>(lhs) < rhs.

  template<class charT, class traits, class Allocator>
    bool operator< (const basic_string<charT,traits,Allocator>& lhs,
                    const charT* rhs);

  Returns:
    lhs < basic_string<charT,traits,Allocator>(rhs).

  21.3.7.5  operator>                                  [lib.string::op>]

  template<class charT, class traits, class Allocator>
    bool operator> (const basic_string<charT,traits,Allocator>& lhs,
                    const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    lhs.compare(rhs) > 0.

  template<class charT, class traits, class Allocator>
    bool operator> (const charT* lhs,
                    const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    basic_string<charT,traits,Allocator>(lhs) > rhs.

  template<class charT, class traits, class Allocator>
    bool operator> (const basic_string<charT,traits,Allocator>& lhs,
                    const charT* rhs);

  Returns:
    lhs > basic_string<charT,traits,Allocator>(rhs).

  21.3.7.6  operator<=                                [lib.string::op<=]

  template<class charT, class traits, class Allocator>
    bool operator<=(const basic_string<charT,traits,Allocator>& lhs,
                    const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    lhs.compare(rhs) <= 0.

  template<class charT, class traits, class Allocator>
    bool operator<=(const charT* lhs,
                    const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    basic_string<charT,traits,Allocator>(lhs) <= rhs.

  template<class charT, class traits, class Allocator>
    bool operator<=(const basic_string<charT,traits,Allocator>& lhs,
                    const charT* rhs);

  Returns:
    lhs <= basic_string<charT,traits,Allocator>(rhs).

  21.3.7.7  operator>=                                [lib.string::op>=]

  template<class charT, class traits, class Allocator>
    bool operator>=(const basic_string<charT,traits,Allocator>& lhs,
                    const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    lhs.compare(rhs) >= 0.

  template<class charT, class traits, class Allocator>
    bool operator>=(const charT* lhs,
                    const basic_string<charT,traits,Allocator>& rhs);

  Returns:
    basic_string<charT,traits,Allocator>(lhs) >= rhs.

  template<class charT, class traits, class Allocator>
    bool operator>=(const basic_string<charT,traits,Allocator>& lhs,
                    const charT* rhs);

  Returns:
    lhs >= basic_string<charT,traits,Allocator>(rhs).

  21.3.7.8  swap                                    [lib.string.special]
    template<class charT, class traits, class Allocator>
       void swap(basic_string<charT,traits,Allocator>& lhs,
                 basic_string<charT,traits,Allocator>& rhs);
  Effects:
    lhs.swap(rhs);

  21.3.7.9  Inserters and extractors                     [lib.string.io]

  template<class charT, class traits, class Allocator>
    basic_istream<charT,traits>&
      operator>>(basic_istream<charT,traits>& is,
                 basic_string<charT,traits,Allocator>& str);

  Effects:
    Begins by constructing a sentry object k as if k were constructed by
    basic_istream<charT,traits>::sentry k(is).  If bool(k) is  true,  it
    calls  str.erase()  and then extracts characters from is and appends
    them to str as if by  calling  str.append(1,c).   If  is.width()  is
    greater  than  zero,  the maximum number n of characters appended is
    is.width(); otherwise n is str.max_size().  Characters are extracted
    and appended until any of the following occurs:

  --n characters are stored;

  --end-of-file occurs on the input sequence;

  --isspace(c,getloc())  is  true for the next available input character
    c.  After the last character (if any) is extracted,  is.width(0)  is
    called and the sentry object k is destroyed.
  Returns:
    is

  template<class charT, class traits, class Allocator>
    basic_ostream<charT, traits>&
      operator<<(basic_ostream<charT, traits>& os,
                 const basic_string<charT,traits,Allocator>& str);

  Effects:
    Begins by constructing a sentry object k as if k were constructed by
    basic_ostream<charT,traits>::sentry  k(os).   If  bool(k)  is  true,
    inserts  characters  as  if by calling os.rdbuf()->sputn(str.data(),
    n), padding as described in stage 3 of _lib.facet.num.put.virtuals_,
    where  n  is  the  smaller  of os.width() and str.size(); then calls
    os.width(0).   If  the  call   to   sputn   fails,   calls   os.set-
    state(ios_base::failbit).
  Returns:
    os

  template<class charT, class traits, class Allocator>
    basic_istream<charT,traits>&
      getline(basic_istream<charT,traits>& is,
              basic_string<charT,traits,Allocator>& str,
              charT delim);

  Effects:
    Begins    by   constructing   a   sentry   object   k   as   if   by
    basic_istream<charT,traits>::sentry k(is).  If bool(k) is  true,  it
    calls  str.erase()  and then extracts characters from is and appends
    them to str as if by calling str.append(1,c) until any of  the  fol-
    lowing occurs:

  --end-of-file occurs on the input sequence (in which case, the getline
    function calls is.setstate(ios_base::eofbit)).

  --c == delim for the next available input character c (in which  case,
    c is extracted but not appended) (_lib.iostate.flags_)

  --str.max_size()  characters  are  stored (in which case, the function
    calls is.setstate(ios_base::failbit) (_lib.iostate.flags_)

1 The conditions are tested in the order shown.  In any case, after  the
  last character is extracted, the sentry object k is destroyed.

2 If   the   function   extracts   no   characters,   it  calls  is.set-
  state(ios_base::failbit)    which    may    throw    ios_base::failure
  (_lib.iostate.flags_).
  Returns:
    is.

  template<class charT, class traits, class Allocator>
    basic_istream<charT,traits>&
      getline(basic_istream<charT,traits>& is,
              basic_string<charT,traits,Allocator>& str)

  Returns:
    getline(is,str,is.widen('\n'))

  21.4  Null-terminated sequence utilities               [lib.c.strings]

1 Tables  11,  12,  13, 14, and 15 describe headers <cctype>, <cwctype>,
  <cstring>, <cwchar>, and <cstdlib>  (multibyte  conversions),  respec-
  tively.

                    Table 11--Header <cctype> synopsis

            +-------------------------------------------------+
            | Type                    Name(s)                 |
            +-------------------------------------------------+
            |Functions:                                       |
            |isalnum   isdigit   isprint   isupper    tolower |
            |isalpha   isgraph   ispunct   isxdigit   toupper |
            |iscntrl   islower   isspace                      |
            +-------------------------------------------------+

                   Table 12--Header <cwctype> synopsis

   +------------------------------------------------------------------+
   |  Type                            Name(s)                         |
   +------------------------------------------------------------------+
   |Macro:     WEOF <cwctype>                                         |
   +------------------------------------------------------------------+
   |Types:     wctrans_t   wctype_t   wint_t <cwctype>                |
   +------------------------------------------------------------------+
   |Functions:                                                        |
   |iswalnum   iswctype    iswlower   iswspace    towctrans   wctrans |
   |iswalpha   iswdigit    iswprint   iswupper    towlower    wctype  |
   |iswcntrl   iswgraph    iswpunct   iswxdigit   towupper            |
   +------------------------------------------------------------------+

                   Table 13--Header <cstring> synopsis

            +-------------------------------------------------+
            | Type                    Name(s)                 |
            +-------------------------------------------------+
            |Macro:    NULL <cstring>                         |
            +-------------------------------------------------+
            |Type:     size_t <cstring>                       |
            +-------------------------------------------------+
            |Functions:                                       |
            |memchr    strcat    strcspn    strncpy   strtok  |
            |memcmp    strchr    strerror   strpbrk   strxfrm |
            |memcpy    strcmp    strlen     strrchr           |
            |memmove   strcoll   strncat    strspn            |
            |memset    strcpy    strncmp    strstr            |
            +-------------------------------------------------+

                    Table 14--Header <cwchar> synopsis

  +------------------------------------------------------------------------------+
  |  Type                                  Name(s)                               |
  +------------------------------------------------------------------------------+
  |Macros:    NULL <cwchar>   WCHAR_MAX         WCHAR_MIN   WEOF <cwchar>        |
  +------------------------------------------------------------------------------+
  |Types:     mbstate_t       wint_t <cwchar>   size_t                           |
  +------------------------------------------------------------------------------+
  |Functions:                                                                    |
  |btowc      getwchar        ungetwc           wcscpy      wcsrtombs   wmemchr  |
  |fgetwc     mbrlen          vfwprintf         wcscspn     wcsspn      wmemcmp  |
  |fgetws     mbrtowc         vswprintf         wcsftime    wcsstr      wmemcpy  |
  |fputwc     mbsinit         vwprintf          wcslen      wcstod      wmemmove |
  |fputws     mbsrtowcs       wcrtomb           wcsncat     wcstok      wmemset  |
  |fwide      putwc           wcscat            wcsncmp     wcstol      wprintf  |
  |fwprintf   putwchar        wcschr            wcsncpy     wcstoul     wscanf   |
  |fwscanf    swprintf        wcscmp            wcspbrk     wcsxfrm              |
  |getwc      swscanf         wcscoll           wcsrchr     wctob                |
  +------------------------------------------------------------------------------+

                   Table 15--Header <cstdlib> synopsis

               +------------------------------------------+
               | Type                 Name(s)             |
               +------------------------------------------+
               |Macros:   MB_CUR_MAX                      |
               +------------------------------------------+
               |Functions:                                |
               |atol      mblen        strtod    wctomb   |
               |atof      mbstowcs     strtol    wcstombs |
               |atoi      mbtowc       strtoul            |
               +------------------------------------------+

2 The  contents  of these headers are the same as the Standard C library
  headers  <type.h>,  <wctype.h>,  <string.h>,  <wchar.h>and  <stdlib.h>
  respectively, with the following modifications:

3 None of the headers shall define the type wchar_t (_lex.key_).

4 The function signature strchr(const char*, int) is replaced by the two
  declarations:

  const char* strchr(const char* s, int c);
        char* strchr(      char* s, int c);

5 both of which have the same behavior as the original declaration.

6 The function signature strpbrk(const char*, const char*)  is  replaced
  by the two declarations:

  const char* strpbrk(const char* s1, const char* s2);
        char* strpbrk(      char* s1, const char* s2);

7 both of which have the same behavior as the original declaration.

8 The  function  signature  strrchr(const char*, int) is replaced by the
  two declarations:

  const char* strrchr(const char* s, int c);
        char* strrchr(      char* s, int c);

9 both of which have the same behavior as the original declaration.

10The function signature strstr(const char*, const char*) is replaced by
  the two declarations:

  const char* strstr(const char* s1, const char* s2);
        char* strstr(      char* s1, const char* s2);

11both of which have the same behavior as the original declaration.

12The function signature memchr(const void*, int, size_t) is replaced by
  the two declarations:

  const void* memchr(const void* s, int c, size_t n);
        void* memchr(      void* s, int c, size_t n);

13both of which have the same behavior as the original declaration.

14The function signature wcschr(const wchar_t*, wchar_t) is replaced  by
  the two declarations:

  const wchar_t* wcschr(const wchar_t* s, wchar_t c);
        wchar_t* wcschr(      wchar_t* s, wchar_t c);

15both of which have the same behavior as the original declaration.

16The  function  signature  wcspbrk(const wchar_t*,  const wchar_t*)  is
  replaced by the two declarations:

  const wchar_t* wcspbrk(const wchar_t* s1, const wchar_t* s2);
        wchar_t* wcspbrk(      wchar_t* s1, const wchar_t* s2);

17both of which have the same behavior as the original declaration.

18The function signature wcsrchr(const wchar_t*, wchar_t) is replaced by
  the two declarations:

  const wchar_t* wcsrchr(const wchar_t* s, wchar_t c);
        wchar_t* wcsrchr(      wchar_t* s, wchar_t c);

19both of which have the same behavior as the original declaration.

20The   function  signature  wcsstr(const wchar_t*,  const wchar_t*)  is
  replaced by the two declarations:

  const wchar_t* wcsstr(const wchar_t* s1, const wchar_t* s2);
        wchar_t* wcsstr(      wchar_t* s1, const wchar_t* s2);

21both of which have the same behavior as the original declaration.

22The  function  signature  wmemchr(const wwchar_t*,  int,  size_t)   is
  replaced by the two declarations:

  const wchar_t* wmemchr(const wchar_t* s, wchar_t c, size_t n);
        wchar_t* wmemchr(      wchar_t* s, wchar_t c, size_t n);

23both of which have the same behavior as the original declaration.

  SEE ALSO:  ISO C subclauses 7.3, 7.10.7, 7.10.8, and  7.11.  Amendment
  1 subclauses 4.4, 4.5, and 4.6.