basic_string.h

Go to the documentation of this file.

// Components for manipulating sequences of characters -*- C++ -*-

// Copyright (C) 1997-2013 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

//
// ISO C++ 14882: 21 Strings library
//

#ifndef _BASIC_STRING_H
#define _BASIC_STRING_H 1

#pragma GCC system_header

#include <ext/atomicity.h>
#include <debug/debug.h>
#if __cplusplus >= 201103L
#include <initializer_list>
#endif

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  // 21.3  Template class basic_string
  template<typename _CharT, typename _Traits, typename _Alloc>
    class basic_string
    {
      typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;

      // Types:
    public:
      typedef _Traits                       traits_type;
      typedef typename _Traits::char_type           value_type;
      typedef _Alloc                        allocator_type;
      typedef typename _CharT_alloc_type::size_type     size_type;
      typedef typename _CharT_alloc_type::difference_type   difference_type;
      typedef typename _CharT_alloc_type::reference     reference;
      typedef typename _CharT_alloc_type::const_reference   const_reference;
      typedef typename _CharT_alloc_type::pointer       pointer;
      typedef typename _CharT_alloc_type::const_pointer     const_pointer;
      typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;
      typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
                                                            const_iterator;
      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
      typedef std::reverse_iterator<iterator>           reverse_iterator;

    private:
      // _Rep: string representation
      //   Invariants:
      //   1. String really contains _M_length + 1 characters: due to 21.3.4
      //      must be kept null-terminated.
      //   2. _M_capacity >= _M_length
      //      Allocated memory is always (_M_capacity + 1) * sizeof(_CharT).
      //   3. _M_refcount has three states:
      //      -1: leaked, one reference, no ref-copies allowed, non-const.
      //       0: one reference, non-const.
      //     n>0: n + 1 references, operations require a lock, const.
      //   4. All fields==0 is an empty string, given the extra storage
      //      beyond-the-end for a null terminator; thus, the shared
      //      empty string representation needs no constructor.

      struct _Rep_base
      {
    size_type       _M_length;
    size_type       _M_capacity;
    _Atomic_word        _M_refcount;
      };

      struct _Rep : _Rep_base
      {
    // Types:
    typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;

    // (Public) Data members:

    // The maximum number of individual char_type elements of an
    // individual string is determined by _S_max_size. This is the
    // value that will be returned by max_size().  (Whereas npos
    // is the maximum number of bytes the allocator can allocate.)
    // If one was to divvy up the theoretical largest size string,
    // with a terminating character and m _CharT elements, it'd
    // look like this:
    // npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
    // Solving for m:
    // m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1
    // In addition, this implementation quarters this amount.
    static const size_type  _S_max_size;
    static const _CharT _S_terminal;

    // The following storage is init'd to 0 by the linker, resulting
        // (carefully) in an empty string with one reference.
        static size_type _S_empty_rep_storage[];

        static _Rep&
        _S_empty_rep()
        { 
      // NB: Mild hack to avoid strict-aliasing warnings.  Note that
      // _S_empty_rep_storage is never modified and the punning should
      // be reasonably safe in this case.
      void* __p = reinterpret_cast<void*>(&_S_empty_rep_storage);
      return *reinterpret_cast<_Rep*>(__p);
    }

        bool
    _M_is_leaked() const
        { return this->_M_refcount < 0; }

        bool
    _M_is_shared() const
        { return this->_M_refcount > 0; }

        void
    _M_set_leaked()
        { this->_M_refcount = -1; }

        void
    _M_set_sharable()
        { this->_M_refcount = 0; }

    void
    _M_set_length_and_sharable(size_type __n)
    {
#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
      if (__builtin_expect(this != &_S_empty_rep(), false))
#endif
        {
          this->_M_set_sharable();  // One reference.
          this->_M_length = __n;
          traits_type::assign(this->_M_refdata()[__n], _S_terminal);
          // grrr. (per 21.3.4)
          // You cannot leave those LWG people alone for a second.
        }
    }

    _CharT*
    _M_refdata() throw()
    { return reinterpret_cast<_CharT*>(this + 1); }

    _CharT*
    _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
    {
      return (!_M_is_leaked() && __alloc1 == __alloc2)
              ? _M_refcopy() : _M_clone(__alloc1);
    }

    // Create & Destroy
    static _Rep*
    _S_create(size_type, size_type, const _Alloc&);

    void
    _M_dispose(const _Alloc& __a)
    {
#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
      if (__builtin_expect(this != &_S_empty_rep(), false))
#endif
        {
          // Be race-detector-friendly.  For more info see bits/c++config.
          _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&this->_M_refcount);
          if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount,
                             -1) <= 0)
        {
          _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&this->_M_refcount);
          _M_destroy(__a);
        }
        }
    }  // XXX MT

    void
    _M_destroy(const _Alloc&) throw();

    _CharT*
    _M_refcopy() throw()
    {
#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
      if (__builtin_expect(this != &_S_empty_rep(), false))
#endif
            __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
      return _M_refdata();
    }  // XXX MT

    _CharT*
    _M_clone(const _Alloc&, size_type __res = 0);
      };

      // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
      struct _Alloc_hider : _Alloc
      {
    _Alloc_hider(_CharT* __dat, const _Alloc& __a)
    : _Alloc(__a), _M_p(__dat) { }

    _CharT* _M_p; // The actual data.
      };

    public:
      // Data Members (public):
      // NB: This is an unsigned type, and thus represents the maximum
      // size that the allocator can hold.
      static const size_type    npos = static_cast<size_type>(-1);

    private:
      // Data Members (private):
      mutable _Alloc_hider  _M_dataplus;

      _CharT*
      _M_data() const
      { return  _M_dataplus._M_p; }

      _CharT*
      _M_data(_CharT* __p)
      { return (_M_dataplus._M_p = __p); }

      _Rep*
      _M_rep() const
      { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }

      // For the internal use we have functions similar to `begin'/`end'
      // but they do not call _M_leak.
      iterator
      _M_ibegin() const
      { return iterator(_M_data()); }

      iterator
      _M_iend() const
      { return iterator(_M_data() + this->size()); }

      void
      _M_leak()    // for use in begin() & non-const op[]
      {
    if (!_M_rep()->_M_is_leaked())
      _M_leak_hard();
      }

      size_type
      _M_check(size_type __pos, const char* __s) const
      {
    if (__pos > this->size())
      __throw_out_of_range(__N(__s));
    return __pos;
      }

      void
      _M_check_length(size_type __n1, size_type __n2, const char* __s) const
      {
    if (this->max_size() - (this->size() - __n1) < __n2)
      __throw_length_error(__N(__s));
      }

      // NB: _M_limit doesn't check for a bad __pos value.
      size_type
      _M_limit(size_type __pos, size_type __off) const
      {
    const bool __testoff =  __off < this->size() - __pos;
    return __testoff ? __off : this->size() - __pos;
      }

      // True if _Rep and source do not overlap.
      bool
      _M_disjunct(const _CharT* __s) const
      {
    return (less<const _CharT*>()(__s, _M_data())
        || less<const _CharT*>()(_M_data() + this->size(), __s));
      }

      // When __n = 1 way faster than the general multichar
      // traits_type::copy/move/assign.
      static void
      _M_copy(_CharT* __d, const _CharT* __s, size_type __n)
      {
    if (__n == 1)
      traits_type::assign(*__d, *__s);
    else
      traits_type::copy(__d, __s, __n);
      }

      static void
      _M_move(_CharT* __d, const _CharT* __s, size_type __n)
      {
    if (__n == 1)
      traits_type::assign(*__d, *__s);
    else
      traits_type::move(__d, __s, __n);   
      }

      static void
      _M_assign(_CharT* __d, size_type __n, _CharT __c)
      {
    if (__n == 1)
      traits_type::assign(*__d, __c);
    else
      traits_type::assign(__d, __n, __c);     
      }

      // _S_copy_chars is a separate template to permit specialization
      // to optimize for the common case of pointers as iterators.
      template<class _Iterator>
        static void
        _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
        {
      for (; __k1 != __k2; ++__k1, ++__p)
        traits_type::assign(*__p, *__k1); // These types are off.
    }

      static void
      _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2)
      { _S_copy_chars(__p, __k1.base(), __k2.base()); }

      static void
      _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
      { _S_copy_chars(__p, __k1.base(), __k2.base()); }

      static void
      _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2)
      { _M_copy(__p, __k1, __k2 - __k1); }

      static void
      _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
      { _M_copy(__p, __k1, __k2 - __k1); }

      static int
      _S_compare(size_type __n1, size_type __n2)
      {
    const difference_type __d = difference_type(__n1 - __n2);

    if (__d > __gnu_cxx::__numeric_traits<int>::__max)
      return __gnu_cxx::__numeric_traits<int>::__max;
    else if (__d < __gnu_cxx::__numeric_traits<int>::__min)
      return __gnu_cxx::__numeric_traits<int>::__min;
    else
      return int(__d);
      }

      void
      _M_mutate(size_type __pos, size_type __len1, size_type __len2);

      void
      _M_leak_hard();

      static _Rep&
      _S_empty_rep()
      { return _Rep::_S_empty_rep(); }

    public:
      // Construct/copy/destroy:
      // NB: We overload ctors in some cases instead of using default
      // arguments, per 17.4.4.4 para. 2 item 2.

      basic_string()
#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
      : _M_dataplus(_S_empty_rep()._M_refdata(), _Alloc()) { }
#else
      : _M_dataplus(_S_construct(size_type(), _CharT(), _Alloc()), _Alloc()){ }
#endif

      explicit
      basic_string(const _Alloc& __a);

      // NB: per LWG issue 42, semantics different from IS:
      basic_string(const basic_string& __str);
      basic_string(const basic_string& __str, size_type __pos,
           size_type __n = npos);
      basic_string(const basic_string& __str, size_type __pos,
           size_type __n, const _Alloc& __a);

      basic_string(const _CharT* __s, size_type __n,
           const _Alloc& __a = _Alloc());
      basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());
      basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());

#if __cplusplus >= 201103L

      basic_string(basic_string&& __str) noexcept
      : _M_dataplus(__str._M_dataplus)
      {
#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
    __str._M_data(_S_empty_rep()._M_refdata());
#else
    __str._M_data(_S_construct(size_type(), _CharT(), get_allocator()));
#endif
      }

      basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc());
#endif // C++11

      template<class _InputIterator>
        basic_string(_InputIterator __beg, _InputIterator __end,
             const _Alloc& __a = _Alloc());

      ~basic_string() _GLIBCXX_NOEXCEPT
      { _M_rep()->_M_dispose(this->get_allocator()); }

      basic_string&
      operator=(const basic_string& __str) 
      { return this->assign(__str); }

      basic_string&
      operator=(const _CharT* __s) 
      { return this->assign(__s); }

      basic_string&
      operator=(_CharT __c) 
      { 
    this->assign(1, __c); 
    return *this;
      }

#if __cplusplus >= 201103L

      basic_string&
      operator=(basic_string&& __str)
      {
    // NB: DR 1204.
    this->swap(__str);
    return *this;
      }

      basic_string&
      operator=(initializer_list<_CharT> __l)
      {
    this->assign(__l.begin(), __l.size());
    return *this;
      }
#endif // C++11

      // Iterators:
      iterator
      begin() _GLIBCXX_NOEXCEPT
      {
    _M_leak();
    return iterator(_M_data());
      }

      const_iterator
      begin() const _GLIBCXX_NOEXCEPT
      { return const_iterator(_M_data()); }

      iterator
      end() _GLIBCXX_NOEXCEPT
      {
    _M_leak();
    return iterator(_M_data() + this->size());
      }

      const_iterator
      end() const _GLIBCXX_NOEXCEPT
      { return const_iterator(_M_data() + this->size()); }

      reverse_iterator
      rbegin() _GLIBCXX_NOEXCEPT
      { return reverse_iterator(this->end()); }

      const_reverse_iterator
      rbegin() const _GLIBCXX_NOEXCEPT
      { return const_reverse_iterator(this->end()); }

      reverse_iterator
      rend() _GLIBCXX_NOEXCEPT
      { return reverse_iterator(this->begin()); }

      const_reverse_iterator
      rend() const _GLIBCXX_NOEXCEPT
      { return const_reverse_iterator(this->begin()); }

#if __cplusplus >= 201103L

      const_iterator
      cbegin() const noexcept
      { return const_iterator(this->_M_data()); }

      const_iterator
      cend() const noexcept
      { return const_iterator(this->_M_data() + this->size()); }

      const_reverse_iterator
      crbegin() const noexcept
      { return const_reverse_iterator(this->end()); }

      const_reverse_iterator
      crend() const noexcept
      { return const_reverse_iterator(this->begin()); }
#endif

    public:
      // Capacity:
      size_type
      size() const _GLIBCXX_NOEXCEPT
      { return _M_rep()->_M_length; }

      size_type
      length() const _GLIBCXX_NOEXCEPT
      { return _M_rep()->_M_length; }

      size_type
      max_size() const _GLIBCXX_NOEXCEPT
      { return _Rep::_S_max_size; }

      void
      resize(size_type __n, _CharT __c);

      void
      resize(size_type __n)
      { this->resize(__n, _CharT()); }

#if __cplusplus >= 201103L
      void
      shrink_to_fit()
      {
    if (capacity() > size())
      {
        __try
          { reserve(0); }
        __catch(...)
          { }
      }
      }
#endif

      size_type
      capacity() const _GLIBCXX_NOEXCEPT
      { return _M_rep()->_M_capacity; }

      void
      reserve(size_type __res_arg = 0);

      void
      clear() _GLIBCXX_NOEXCEPT
      { _M_mutate(0, this->size(), 0); }

      bool
      empty() const _GLIBCXX_NOEXCEPT
      { return this->size() == 0; }

      // Element access:
      const_reference
      operator[] (size_type __pos) const
      {
    _GLIBCXX_DEBUG_ASSERT(__pos <= size());
    return _M_data()[__pos];
      }

      reference
      operator[](size_type __pos)
      {
        // allow pos == size() as v3 extension:
    _GLIBCXX_DEBUG_ASSERT(__pos <= size());
        // but be strict in pedantic mode:
    _GLIBCXX_DEBUG_PEDASSERT(__pos < size());
    _M_leak();
    return _M_data()[__pos];
      }

      const_reference
      at(size_type __n) const
      {
    if (__n >= this->size())
      __throw_out_of_range(__N("basic_string::at"));
    return _M_data()[__n];
      }

      reference
      at(size_type __n)
      {
    if (__n >= size())
      __throw_out_of_range(__N("basic_string::at"));
    _M_leak();
    return _M_data()[__n];
      }

#if __cplusplus >= 201103L

      reference
      front()
      { return operator[](0); }

      const_reference
      front() const
      { return operator[](0); }

      reference
      back()
      { return operator[](this->size() - 1); }

      const_reference
      back() const
      { return operator[](this->size() - 1); }
#endif

      // Modifiers:
      basic_string&
      operator+=(const basic_string& __str)
      { return this->append(__str); }

      basic_string&
      operator+=(const _CharT* __s)
      { return this->append(__s); }

      basic_string&
      operator+=(_CharT __c)
      { 
    this->push_back(__c);
    return *this;
      }

#if __cplusplus >= 201103L

      basic_string&
      operator+=(initializer_list<_CharT> __l)
      { return this->append(__l.begin(), __l.size()); }
#endif // C++11

      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)
      {
    __glibcxx_requires_string(__s);
    return this->append(__s, traits_type::length(__s));
      }

      basic_string&
      append(size_type __n, _CharT __c);

#if __cplusplus >= 201103L

      basic_string&
      append(initializer_list<_CharT> __l)
      { return this->append(__l.begin(), __l.size()); }
#endif // C++11

      template<class _InputIterator>
        basic_string&
        append(_InputIterator __first, _InputIterator __last)
        { return this->replace(_M_iend(), _M_iend(), __first, __last); }

      void
      push_back(_CharT __c)
      { 
    const size_type __len = 1 + this->size();
    if (__len > this->capacity() || _M_rep()->_M_is_shared())
      this->reserve(__len);
    traits_type::assign(_M_data()[this->size()], __c);
    _M_rep()->_M_set_length_and_sharable(__len);
      }

      basic_string&
      assign(const basic_string& __str);

#if __cplusplus >= 201103L

      basic_string&
      assign(basic_string&& __str)
      {
    this->swap(__str);
    return *this;
      }
#endif // C++11

      basic_string&
      assign(const basic_string& __str, size_type __pos, size_type __n)
      { return this->assign(__str._M_data()
                + __str._M_check(__pos, "basic_string::assign"),
                __str._M_limit(__pos, __n)); }

      basic_string&
      assign(const _CharT* __s, size_type __n);

      basic_string&
      assign(const _CharT* __s)
      {
    __glibcxx_requires_string(__s);
    return this->assign(__s, traits_type::length(__s));
      }

      basic_string&
      assign(size_type __n, _CharT __c)
      { return _M_replace_aux(size_type(0), this->size(), __n, __c); }

      template<class _InputIterator>
        basic_string&
        assign(_InputIterator __first, _InputIterator __last)
        { return this->replace(_M_ibegin(), _M_iend(), __first, __last); }

#if __cplusplus >= 201103L

      basic_string&
      assign(initializer_list<_CharT> __l)
      { return this->assign(__l.begin(), __l.size()); }
#endif // C++11

      void
      insert(iterator __p, size_type __n, _CharT __c)
      { this->replace(__p, __p, __n, __c);  }

      template<class _InputIterator>
        void
        insert(iterator __p, _InputIterator __beg, _InputIterator __end)
        { this->replace(__p, __p, __beg, __end); }

#if __cplusplus >= 201103L

      void
      insert(iterator __p, initializer_list<_CharT> __l)
      {
    _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
    this->insert(__p - _M_ibegin(), __l.begin(), __l.size());
      }
#endif // C++11

      basic_string&
      insert(size_type __pos1, const basic_string& __str)
      { return this->insert(__pos1, __str, size_type(0), __str.size()); }

      basic_string&
      insert(size_type __pos1, const basic_string& __str,
         size_type __pos2, size_type __n)
      { return this->insert(__pos1, __str._M_data()
                + __str._M_check(__pos2, "basic_string::insert"),
                __str._M_limit(__pos2, __n)); }

      basic_string&
      insert(size_type __pos, const _CharT* __s, size_type __n);

      basic_string&
      insert(size_type __pos, const _CharT* __s)
      {
    __glibcxx_requires_string(__s);
    return this->insert(__pos, __s, traits_type::length(__s));
      }

      basic_string&
      insert(size_type __pos, size_type __n, _CharT __c)
      { return _M_replace_aux(_M_check(__pos, "basic_string::insert"),
                  size_type(0), __n, __c); }

      iterator
      insert(iterator __p, _CharT __c)
      {
    _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
    const size_type __pos = __p - _M_ibegin();
    _M_replace_aux(__pos, size_type(0), size_type(1), __c);
    _M_rep()->_M_set_leaked();
    return iterator(_M_data() + __pos);
      }

      basic_string&
      erase(size_type __pos = 0, size_type __n = npos)
      { 
    _M_mutate(_M_check(__pos, "basic_string::erase"),
          _M_limit(__pos, __n), size_type(0));
    return *this;
      }

      iterator
      erase(iterator __position)
      {
    _GLIBCXX_DEBUG_PEDASSERT(__position >= _M_ibegin()
                 && __position < _M_iend());
    const size_type __pos = __position - _M_ibegin();
    _M_mutate(__pos, size_type(1), size_type(0));
    _M_rep()->_M_set_leaked();
    return iterator(_M_data() + __pos);
      }

      iterator
      erase(iterator __first, iterator __last);
 
#if __cplusplus >= 201103L

      void
      pop_back()
      { erase(size()-1, 1); }
#endif // C++11

      basic_string&
      replace(size_type __pos, size_type __n, const basic_string& __str)
      { return this->replace(__pos, __n, __str._M_data(), __str.size()); }

      basic_string&
      replace(size_type __pos1, size_type __n1, const basic_string& __str,
          size_type __pos2, size_type __n2)
      { return this->replace(__pos1, __n1, __str._M_data()
                 + __str._M_check(__pos2, "basic_string::replace"),
                 __str._M_limit(__pos2, __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)
      {
    __glibcxx_requires_string(__s);
    return this->replace(__pos, __n1, __s, traits_type::length(__s));
      }

      basic_string&
      replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
      { return _M_replace_aux(_M_check(__pos, "basic_string::replace"),
                  _M_limit(__pos, __n1), __n2, __c); }

      basic_string&
      replace(iterator __i1, iterator __i2, const basic_string& __str)
      { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }

      basic_string&
      replace(iterator __i1, iterator __i2, const _CharT* __s, size_type __n)
      {
    _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
                 && __i2 <= _M_iend());
    return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n);
      }

      basic_string&
      replace(iterator __i1, iterator __i2, const _CharT* __s)
      {
    __glibcxx_requires_string(__s);
    return this->replace(__i1, __i2, __s, traits_type::length(__s));
      }

      basic_string&
      replace(iterator __i1, iterator __i2, size_type __n, _CharT __c)
      {
    _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
                 && __i2 <= _M_iend());
    return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __c);
      }

      template<class _InputIterator>
        basic_string&
        replace(iterator __i1, iterator __i2,
        _InputIterator __k1, _InputIterator __k2)
        {
      _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
                   && __i2 <= _M_iend());
      __glibcxx_requires_valid_range(__k1, __k2);
      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
      return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral());
    }

      // Specializations for the common case of pointer and iterator:
      // useful to avoid the overhead of temporary buffering in _M_replace.
      basic_string&
      replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
      {
    _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
                 && __i2 <= _M_iend());
    __glibcxx_requires_valid_range(__k1, __k2);
    return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
                 __k1, __k2 - __k1);
      }

      basic_string&
      replace(iterator __i1, iterator __i2,
          const _CharT* __k1, const _CharT* __k2)
      {
    _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
                 && __i2 <= _M_iend());
    __glibcxx_requires_valid_range(__k1, __k2);
    return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
                 __k1, __k2 - __k1);
      }

      basic_string&
      replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
      {
    _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
                 && __i2 <= _M_iend());
    __glibcxx_requires_valid_range(__k1, __k2);
    return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
                 __k1.base(), __k2 - __k1);
      }

      basic_string&
      replace(iterator __i1, iterator __i2,
          const_iterator __k1, const_iterator __k2)
      {
    _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
                 && __i2 <= _M_iend());
    __glibcxx_requires_valid_range(__k1, __k2);
    return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
                 __k1.base(), __k2 - __k1);
      }
      
#if __cplusplus >= 201103L

      basic_string& replace(iterator __i1, iterator __i2,
                initializer_list<_CharT> __l)
      { return this->replace(__i1, __i2, __l.begin(), __l.end()); }
#endif // C++11

    private:
      template<class _Integer>
    basic_string&
    _M_replace_dispatch(iterator __i1, iterator __i2, _Integer __n,
                _Integer __val, __true_type)
        { return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __val); }

      template<class _InputIterator>
    basic_string&
    _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
                _InputIterator __k2, __false_type);

      basic_string&
      _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
             _CharT __c);

      basic_string&
      _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
              size_type __n2);

      // _S_construct_aux is used to implement the 21.3.1 para 15 which
      // requires special behaviour if _InIter is an integral type
      template<class _InIterator>
        static _CharT*
        _S_construct_aux(_InIterator __beg, _InIterator __end,
             const _Alloc& __a, __false_type)
    {
          typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
          return _S_construct(__beg, __end, __a, _Tag());
    }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 438. Ambiguity in the "do the right thing" clause
      template<class _Integer>
        static _CharT*
        _S_construct_aux(_Integer __beg, _Integer __end,
             const _Alloc& __a, __true_type)
        { return _S_construct_aux_2(static_cast<size_type>(__beg),
                    __end, __a); }

      static _CharT*
      _S_construct_aux_2(size_type __req, _CharT __c, const _Alloc& __a)
      { return _S_construct(__req, __c, __a); }

      template<class _InIterator>
        static _CharT*
        _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
    {
      typedef typename std::__is_integer<_InIterator>::__type _Integral;
      return _S_construct_aux(__beg, __end, __a, _Integral());
        }

      // For Input Iterators, used in istreambuf_iterators, etc.
      template<class _InIterator>
        static _CharT*
         _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
              input_iterator_tag);

      // For forward_iterators up to random_access_iterators, used for
      // string::iterator, _CharT*, etc.
      template<class _FwdIterator>
        static _CharT*
        _S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
             forward_iterator_tag);

      static _CharT*
      _S_construct(size_type __req, _CharT __c, const _Alloc& __a);

    public:

      size_type
      copy(_CharT* __s, size_type __n, size_type __pos = 0) const;

      void
      swap(basic_string& __s);

      // String operations:
      const _CharT*
      c_str() const _GLIBCXX_NOEXCEPT
      { return _M_data(); }

      const _CharT*
      data() const _GLIBCXX_NOEXCEPT
      { return _M_data(); }

      allocator_type
      get_allocator() const _GLIBCXX_NOEXCEPT
      { return _M_dataplus; }

      size_type
      find(const _CharT* __s, size_type __pos, size_type __n) const;

      size_type
      find(const basic_string& __str, size_type __pos = 0) const
    _GLIBCXX_NOEXCEPT
      { return this->find(__str.data(), __pos, __str.size()); }

      size_type
      find(const _CharT* __s, size_type __pos = 0) const
      {
    __glibcxx_requires_string(__s);
    return this->find(__s, __pos, traits_type::length(__s));
      }

      size_type
      find(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT;

      size_type
      rfind(const basic_string& __str, size_type __pos = npos) const
    _GLIBCXX_NOEXCEPT
      { return this->rfind(__str.data(), __pos, __str.size()); }

      size_type
      rfind(const _CharT* __s, size_type __pos, size_type __n) const;

      size_type
      rfind(const _CharT* __s, size_type __pos = npos) const
      {
    __glibcxx_requires_string(__s);
    return this->rfind(__s, __pos, traits_type::length(__s));
      }

      size_type
      rfind(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT;

      size_type
      find_first_of(const basic_string& __str, size_type __pos = 0) const
    _GLIBCXX_NOEXCEPT
      { return this->find_first_of(__str.data(), __pos, __str.size()); }

      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
      {
    __glibcxx_requires_string(__s);
    return this->find_first_of(__s, __pos, traits_type::length(__s));
      }

      size_type
      find_first_of(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT
      { return this->find(__c, __pos); }

      size_type
      find_last_of(const basic_string& __str, size_type __pos = npos) const
    _GLIBCXX_NOEXCEPT
      { return this->find_last_of(__str.data(), __pos, __str.size()); }

      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
      {
    __glibcxx_requires_string(__s);
    return this->find_last_of(__s, __pos, traits_type::length(__s));
      }

      size_type
      find_last_of(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT
      { return this->rfind(__c, __pos); }

      size_type
      find_first_not_of(const basic_string& __str, size_type __pos = 0) const
    _GLIBCXX_NOEXCEPT
      { return this->find_first_not_of(__str.data(), __pos, __str.size()); }

      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
      {
    __glibcxx_requires_string(__s);
    return this->find_first_not_of(__s, __pos, traits_type::length(__s));
      }

      size_type
      find_first_not_of(_CharT __c, size_type __pos = 0) const
    _GLIBCXX_NOEXCEPT;

      size_type
      find_last_not_of(const basic_string& __str, size_type __pos = npos) const
    _GLIBCXX_NOEXCEPT
      { return this->find_last_not_of(__str.data(), __pos, __str.size()); }

      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
      {
    __glibcxx_requires_string(__s);
    return this->find_last_not_of(__s, __pos, traits_type::length(__s));
      }

      size_type
      find_last_not_of(_CharT __c, size_type __pos = npos) const
    _GLIBCXX_NOEXCEPT;

      basic_string
      substr(size_type __pos = 0, size_type __n = npos) const
      { return basic_string(*this,
                _M_check(__pos, "basic_string::substr"), __n); }

      int
      compare(const basic_string& __str) const
      {
    const size_type __size = this->size();
    const size_type __osize = __str.size();
    const size_type __len = std::min(__size, __osize);

    int __r = traits_type::compare(_M_data(), __str.data(), __len);
    if (!__r)
      __r = _S_compare(__size, __osize);
    return __r;
      }

      int
      compare(size_type __pos, size_type __n, 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;

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 5 String::compare specification questionable
      int
      compare(size_type __pos, size_type __n1, const _CharT* __s) const;

      int
      compare(size_type __pos, size_type __n1, const _CharT* __s,
          size_type __n2) const;
  };

  // operator+
  template<typename _CharT, typename _Traits, typename _Alloc>
    basic_string<_CharT, _Traits, _Alloc>
    operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
          const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    {
      basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
      __str.append(__rhs);
      return __str;
    }

  template<typename _CharT, typename _Traits, typename _Alloc>
    basic_string<_CharT,_Traits,_Alloc>
    operator+(const _CharT* __lhs,
          const basic_string<_CharT,_Traits,_Alloc>& __rhs);

  template<typename _CharT, typename _Traits, typename _Alloc>
    basic_string<_CharT,_Traits,_Alloc>
    operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline basic_string<_CharT, _Traits, _Alloc>
    operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
         const _CharT* __rhs)
    {
      basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
      __str.append(__rhs);
      return __str;
    }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline basic_string<_CharT, _Traits, _Alloc>
    operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
    {
      typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
      typedef typename __string_type::size_type     __size_type;
      __string_type __str(__lhs);
      __str.append(__size_type(1), __rhs);
      return __str;
    }

#if __cplusplus >= 201103L
  template<typename _CharT, typename _Traits, typename _Alloc>
    inline basic_string<_CharT, _Traits, _Alloc>
    operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
          const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return std::move(__lhs.append(__rhs)); }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline basic_string<_CharT, _Traits, _Alloc>
    operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
          basic_string<_CharT, _Traits, _Alloc>&& __rhs)
    { return std::move(__rhs.insert(0, __lhs)); }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline basic_string<_CharT, _Traits, _Alloc>
    operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
          basic_string<_CharT, _Traits, _Alloc>&& __rhs)
    {
      const auto __size = __lhs.size() + __rhs.size();
      const bool __cond = (__size > __lhs.capacity()
               && __size <= __rhs.capacity());
      return __cond ? std::move(__rhs.insert(0, __lhs))
                : std::move(__lhs.append(__rhs));
    }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline basic_string<_CharT, _Traits, _Alloc>
    operator+(const _CharT* __lhs,
          basic_string<_CharT, _Traits, _Alloc>&& __rhs)
    { return std::move(__rhs.insert(0, __lhs)); }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline basic_string<_CharT, _Traits, _Alloc>
    operator+(_CharT __lhs,
          basic_string<_CharT, _Traits, _Alloc>&& __rhs)
    { return std::move(__rhs.insert(0, 1, __lhs)); }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline basic_string<_CharT, _Traits, _Alloc>
    operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
          const _CharT* __rhs)
    { return std::move(__lhs.append(__rhs)); }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline basic_string<_CharT, _Traits, _Alloc>
    operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
          _CharT __rhs)
    { return std::move(__lhs.append(1, __rhs)); }
#endif

  // operator ==
  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return __lhs.compare(__rhs) == 0; }

  template<typename _CharT>
    inline
    typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, bool>::__type
    operator==(const basic_string<_CharT>& __lhs,
           const basic_string<_CharT>& __rhs)
    { return (__lhs.size() == __rhs.size()
          && !std::char_traits<_CharT>::compare(__lhs.data(), __rhs.data(),
                            __lhs.size())); }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator==(const _CharT* __lhs,
           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return __rhs.compare(__lhs) == 0; }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
           const _CharT* __rhs)
    { return __lhs.compare(__rhs) == 0; }

  // operator !=
  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return !(__lhs == __rhs); }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator!=(const _CharT* __lhs,
           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return !(__lhs == __rhs); }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
           const _CharT* __rhs)
    { return !(__lhs == __rhs); }

  // operator <
  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
          const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return __lhs.compare(__rhs) < 0; }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
          const _CharT* __rhs)
    { return __lhs.compare(__rhs) < 0; }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator<(const _CharT* __lhs,
          const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return __rhs.compare(__lhs) > 0; }

  // operator >
  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
          const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return __lhs.compare(__rhs) > 0; }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
          const _CharT* __rhs)
    { return __lhs.compare(__rhs) > 0; }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator>(const _CharT* __lhs,
          const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return __rhs.compare(__lhs) < 0; }

  // operator <=
  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return __lhs.compare(__rhs) <= 0; }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
           const _CharT* __rhs)
    { return __lhs.compare(__rhs) <= 0; }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator<=(const _CharT* __lhs,
           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return __rhs.compare(__lhs) >= 0; }

  // operator >=
  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return __lhs.compare(__rhs) >= 0; }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
           const _CharT* __rhs)
    { return __lhs.compare(__rhs) >= 0; }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator>=(const _CharT* __lhs,
         const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return __rhs.compare(__lhs) <= 0; }

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline void
    swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
     basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { __lhs.swap(__rhs); }

  template<typename _CharT, typename _Traits, typename _Alloc>
    basic_istream<_CharT, _Traits>&
    operator>>(basic_istream<_CharT, _Traits>& __is,
           basic_string<_CharT, _Traits, _Alloc>& __str);

  template<>
    basic_istream<char>&
    operator>>(basic_istream<char>& __is, basic_string<char>& __str);

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline basic_ostream<_CharT, _Traits>&
    operator<<(basic_ostream<_CharT, _Traits>& __os,
           const basic_string<_CharT, _Traits, _Alloc>& __str)
    {
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 586. string inserter not a formatted function
      return __ostream_insert(__os, __str.data(), __str.size());
    }

  template<typename _CharT, typename _Traits, typename _Alloc>
    basic_istream<_CharT, _Traits>&
    getline(basic_istream<_CharT, _Traits>& __is,
        basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);

  template<typename _CharT, typename _Traits, typename _Alloc>
    inline basic_istream<_CharT, _Traits>&
    getline(basic_istream<_CharT, _Traits>& __is,
        basic_string<_CharT, _Traits, _Alloc>& __str)
    { return getline(__is, __str, __is.widen('\n')); }

  template<>
    basic_istream<char>&
    getline(basic_istream<char>& __in, basic_string<char>& __str,
        char __delim);

#ifdef _GLIBCXX_USE_WCHAR_T
  template<>
    basic_istream<wchar_t>&
    getline(basic_istream<wchar_t>& __in, basic_string<wchar_t>& __str,
        wchar_t __delim);
#endif  

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace

#if ((__cplusplus >= 201103L) && defined(_GLIBCXX_USE_C99) \
     && !defined(_GLIBCXX_HAVE_BROKEN_VSWPRINTF))

#include <ext/string_conversions.h>

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  // 21.4 Numeric Conversions [string.conversions].
  inline int
  stoi(const string& __str, size_t* __idx = 0, int __base = 10)
  { return __gnu_cxx::__stoa<long, int>(&std::strtol, "stoi", __str.c_str(),
                    __idx, __base); }

  inline long
  stol(const string& __str, size_t* __idx = 0, int __base = 10)
  { return __gnu_cxx::__stoa(&std::strtol, "stol", __str.c_str(),
                 __idx, __base); }

  inline unsigned long
  stoul(const string& __str, size_t* __idx = 0, int __base = 10)
  { return __gnu_cxx::__stoa(&std::strtoul, "stoul", __str.c_str(),
                 __idx, __base); }

  inline long long
  stoll(const string& __str, size_t* __idx = 0, int __base = 10)
  { return __gnu_cxx::__stoa(&std::strtoll, "stoll", __str.c_str(),
                 __idx, __base); }

  inline unsigned long long
  stoull(const string& __str, size_t* __idx = 0, int __base = 10)
  { return __gnu_cxx::__stoa(&std::strtoull, "stoull", __str.c_str(),
                 __idx, __base); }

  // NB: strtof vs strtod.
  inline float
  stof(const string& __str, size_t* __idx = 0)
  { return __gnu_cxx::__stoa(&std::strtof, "stof", __str.c_str(), __idx); }

  inline double
  stod(const string& __str, size_t* __idx = 0)
  { return __gnu_cxx::__stoa(&std::strtod, "stod", __str.c_str(), __idx); }

  inline long double
  stold(const string& __str, size_t* __idx = 0)
  { return __gnu_cxx::__stoa(&std::strtold, "stold", __str.c_str(), __idx); }

  // NB: (v)snprintf vs sprintf.

  // DR 1261.
  inline string
  to_string(int __val)
  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(int),
                       "%d", __val); }

  inline string
  to_string(unsigned __val)
  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
                       4 * sizeof(unsigned),
                       "%u", __val); }

  inline string
  to_string(long __val)
  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(long),
                       "%ld", __val); }

  inline string
  to_string(unsigned long __val)
  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
                       4 * sizeof(unsigned long),
                       "%lu", __val); }

  inline string
  to_string(long long __val)
  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
                       4 * sizeof(long long),
                       "%lld", __val); }

  inline string
  to_string(unsigned long long __val)
  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
                       4 * sizeof(unsigned long long),
                       "%llu", __val); }

  inline string
  to_string(float __val)
  {
    const int __n = 
      __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
    return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
                       "%f", __val);
  }

  inline string
  to_string(double __val)
  {
    const int __n = 
      __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
    return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
                       "%f", __val);
  }

  inline string
  to_string(long double __val)
  {
    const int __n = 
      __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
    return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
                       "%Lf", __val);
  }

#ifdef _GLIBCXX_USE_WCHAR_T
  inline int 
  stoi(const wstring& __str, size_t* __idx = 0, int __base = 10)
  { return __gnu_cxx::__stoa<long, int>(&std::wcstol, "stoi", __str.c_str(),
                    __idx, __base); }

  inline long 
  stol(const wstring& __str, size_t* __idx = 0, int __base = 10)
  { return __gnu_cxx::__stoa(&std::wcstol, "stol", __str.c_str(),
                 __idx, __base); }

  inline unsigned long
  stoul(const wstring& __str, size_t* __idx = 0, int __base = 10)
  { return __gnu_cxx::__stoa(&std::wcstoul, "stoul", __str.c_str(),
                 __idx, __base); }

  inline long long
  stoll(const wstring& __str, size_t* __idx = 0, int __base = 10)
  { return __gnu_cxx::__stoa(&std::wcstoll, "stoll", __str.c_str(),
                 __idx, __base); }

  inline unsigned long long
  stoull(const wstring& __str, size_t* __idx = 0, int __base = 10)
  { return __gnu_cxx::__stoa(&std::wcstoull, "stoull", __str.c_str(),
                 __idx, __base); }

  // NB: wcstof vs wcstod.
  inline float
  stof(const wstring& __str, size_t* __idx = 0)
  { return __gnu_cxx::__stoa(&std::wcstof, "stof", __str.c_str(), __idx); }

  inline double
  stod(const wstring& __str, size_t* __idx = 0)
  { return __gnu_cxx::__stoa(&std::wcstod, "stod", __str.c_str(), __idx); }

  inline long double
  stold(const wstring& __str, size_t* __idx = 0)
  { return __gnu_cxx::__stoa(&std::wcstold, "stold", __str.c_str(), __idx); }

  // DR 1261.
  inline wstring
  to_wstring(int __val)
  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(int),
                        L"%d", __val); }

  inline wstring
  to_wstring(unsigned __val)
  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
                        4 * sizeof(unsigned),
                        L"%u", __val); }

  inline wstring
  to_wstring(long __val)
  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(long),
                        L"%ld", __val); }

  inline wstring
  to_wstring(unsigned long __val)
  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
                        4 * sizeof(unsigned long),
                        L"%lu", __val); }

  inline wstring
  to_wstring(long long __val)
  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
                        4 * sizeof(long long),
                        L"%lld", __val); }

  inline wstring
  to_wstring(unsigned long long __val)
  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
                        4 * sizeof(unsigned long long),
                        L"%llu", __val); }

  inline wstring
  to_wstring(float __val)
  {
    const int __n =
      __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
    return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
                        L"%f", __val);
  }

  inline wstring
  to_wstring(double __val)
  {
    const int __n =
      __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
    return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
                        L"%f", __val);
  }

  inline wstring
  to_wstring(long double __val)
  {
    const int __n =
      __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
    return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
                        L"%Lf", __val);
  }
#endif

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace

#endif /* C++11 && _GLIBCXX_USE_C99 ... */

#if __cplusplus >= 201103L

#include <bits/functional_hash.h>

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  // DR 1182.

#ifndef _GLIBCXX_COMPATIBILITY_CXX0X
  template<>
    struct hash<string>
    : public __hash_base<size_t, string>
    {
      size_t
      operator()(const string& __s) const noexcept
      { return std::_Hash_impl::hash(__s.data(), __s.length()); }
    };

  template<>
    struct __is_fast_hash<hash<string>> : std::false_type
    { };

#ifdef _GLIBCXX_USE_WCHAR_T
  template<>
    struct hash<wstring>
    : public __hash_base<size_t, wstring>
    {
      size_t
      operator()(const wstring& __s) const noexcept
      { return std::_Hash_impl::hash(__s.data(),
                                     __s.length() * sizeof(wchar_t)); }
    };

  template<>
    struct __is_fast_hash<hash<wstring>> : std::false_type
    { };
#endif
#endif /* _GLIBCXX_COMPATIBILITY_CXX0X */

#ifdef _GLIBCXX_USE_C99_STDINT_TR1
  template<>
    struct hash<u16string>
    : public __hash_base<size_t, u16string>
    {
      size_t
      operator()(const u16string& __s) const noexcept
      { return std::_Hash_impl::hash(__s.data(),
                                     __s.length() * sizeof(char16_t)); }
    };

  template<>
    struct __is_fast_hash<hash<u16string>> : std::false_type
    { };

  template<>
    struct hash<u32string>
    : public __hash_base<size_t, u32string>
    {
      size_t
      operator()(const u32string& __s) const noexcept
      { return std::_Hash_impl::hash(__s.data(),
                                     __s.length() * sizeof(char32_t)); }
    };

  template<>
    struct __is_fast_hash<hash<u32string>> : std::false_type
    { };
#endif

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace

#endif // C++11

#endif /* _BASIC_STRING_H */