LCOM1920-T02G10

// -*- C++ -*-

//===--------------------------- string -----------------------------------===//

//

//                     The LLVM Compiler Infrastructure

//

// This file is distributed under the University of Illinois Open Source

// License. See LICENSE.TXT for details.

//

//===----------------------------------------------------------------------===//

#ifndef _LIBCPP_STRING

#define _LIBCPP_STRING

/*

    string synopsis

namespace std

{

template <class stateT>

class fpos

{

private:

    stateT st;

public:

    fpos(streamoff = streamoff());

    operator streamoff() const;

    stateT state() const;

    void state(stateT);

    fpos& operator+=(streamoff);

    fpos  operator+ (streamoff) const;

    fpos& operator-=(streamoff);

    fpos  operator- (streamoff) const;

};

template <class stateT> streamoff operator-(const fpos<stateT>& x, const fpos<stateT>& y);

template <class stateT> bool operator==(const fpos<stateT>& x, const fpos<stateT>& y);

template <class stateT> bool operator!=(const fpos<stateT>& x, const fpos<stateT>& y);

template <class charT>

struct char_traits

{

    typedef charT     char_type;

    typedef ...       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) noexcept;

    static constexpr bool eq(char_type c1, char_type c2) noexcept;

    static constexpr bool lt(char_type c1, char_type c2) noexcept;

    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, size_t 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 constexpr int_type  not_eof(int_type c) noexcept;

    static constexpr char_type to_char_type(int_type c) noexcept;

    static constexpr int_type  to_int_type(char_type c) noexcept;

    static constexpr bool      eq_int_type(int_type c1, int_type c2) noexcept;

    static constexpr int_type  eof() noexcept;

};

template <> struct char_traits<char>;

template <> struct char_traits<wchar_t>;

template<class charT, class traits = char_traits<charT>, class Allocator = allocator<charT> >

class basic_string

{

public:

// types:

    typedef traits traits_type;

    typedef typename traits_type::char_type value_type;

    typedef Allocator allocator_type;

    typedef typename allocator_type::size_type size_type;

    typedef typename allocator_type::difference_type difference_type;

    typedef typename allocator_type::reference reference;

    typedef typename allocator_type::const_reference const_reference;

    typedef typename allocator_type::pointer pointer;

    typedef typename allocator_type::const_pointer const_pointer;

    typedef implementation-defined iterator;

    typedef implementation-defined const_iterator;

    typedef std::reverse_iterator<iterator> reverse_iterator;

    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    static const size_type npos = -1;

    basic_string()

        noexcept(is_nothrow_default_constructible<allocator_type>::value);

    explicit basic_string(const allocator_type& a);

    basic_string(const basic_string& str);

    basic_string(basic_string&& str)

        noexcept(is_nothrow_move_constructible<allocator_type>::value);

    basic_string(const basic_string& str, size_type pos, size_type n = npos,

                 const allocator_type& a = allocator_type());

    basic_string(const value_type* s, const allocator_type& a = allocator_type());

    basic_string(const value_type* s, size_type n, const allocator_type& a = allocator_type());

    basic_string(size_type n, value_type c, const allocator_type& a = allocator_type());

    template<class InputIterator>

        basic_string(InputIterator begin, InputIterator end,

                     const allocator_type& a = allocator_type());

    basic_string(initializer_list<value_type>, const Allocator& = Allocator());

    basic_string(const basic_string&, const Allocator&);

    basic_string(basic_string&&, const Allocator&);

    ~basic_string();

    basic_string& operator=(const basic_string& str);

    basic_string& operator=(basic_string&& str)

        noexcept(

             allocator_type::propagate_on_container_move_assignment::value ||

             allocator_type::is_always_equal::value ); // C++17

    basic_string& operator=(const value_type* s);

    basic_string& operator=(value_type c);

    basic_string& operator=(initializer_list<value_type>);

    iterator       begin() noexcept;

    const_iterator begin() const noexcept;

    iterator       end() noexcept;

    const_iterator end() const noexcept;

    reverse_iterator       rbegin() noexcept;

    const_reverse_iterator rbegin() const noexcept;

    reverse_iterator       rend() noexcept;

    const_reverse_iterator rend() const noexcept;

    const_iterator         cbegin() const noexcept;

    const_iterator         cend() const noexcept;

    const_reverse_iterator crbegin() const noexcept;

    const_reverse_iterator crend() const noexcept;

    size_type size() const noexcept;

    size_type length() const noexcept;

    size_type max_size() const noexcept;

    size_type capacity() const noexcept;

    void resize(size_type n, value_type c);

    void resize(size_type n);

    void reserve(size_type res_arg = 0);

    void shrink_to_fit();

    void clear() noexcept;

    bool empty() const noexcept;

    const_reference operator[](size_type pos) const;

    reference       operator[](size_type pos);

    const_reference at(size_type n) const;

    reference       at(size_type n);

    basic_string& operator+=(const basic_string& str);

    basic_string& operator+=(const value_type* s);

    basic_string& operator+=(value_type c);

    basic_string& operator+=(initializer_list<value_type>);

    basic_string& append(const basic_string& str);

    basic_string& append(const basic_string& str, size_type pos, size_type n=npos); //C++14

    basic_string& append(const value_type* s, size_type n);

    basic_string& append(const value_type* s);

    basic_string& append(size_type n, value_type c);

    template<class InputIterator>

        basic_string& append(InputIterator first, InputIterator last);

    basic_string& append(initializer_list<value_type>);

    void push_back(value_type c);

    void pop_back();

    reference       front();

    const_reference front() const;

    reference       back();

    const_reference back() const;

    basic_string& assign(const basic_string& str);

    basic_string& assign(basic_string&& str);

    basic_string& assign(const basic_string& str, size_type pos, size_type n=npos); // C++14

    basic_string& assign(const value_type* s, size_type n);

    basic_string& assign(const value_type* s);

    basic_string& assign(size_type n, value_type c);

    template<class InputIterator>

        basic_string& assign(InputIterator first, InputIterator last);

    basic_string& assign(initializer_list<value_type>);

    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 value_type* s, size_type n=npos); //C++14

    basic_string& insert(size_type pos, const value_type* s);

    basic_string& insert(size_type pos, size_type n, value_type c);

    iterator      insert(const_iterator p, value_type c);

    iterator      insert(const_iterator p, size_type n, value_type c);

    template<class InputIterator>

        iterator insert(const_iterator p, InputIterator first, InputIterator last);

    iterator      insert(const_iterator p, initializer_list<value_type>);

    basic_string& erase(size_type pos = 0, size_type n = npos);

    iterator      erase(const_iterator position);

    iterator      erase(const_iterator first, const_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=npos); // C++14

    basic_string& replace(size_type pos, size_type n1, const value_type* s, size_type n2);

    basic_string& replace(size_type pos, size_type n1, const value_type* s);

    basic_string& replace(size_type pos, size_type n1, size_type n2, value_type c);

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

    basic_string& replace(const_iterator i1, const_iterator i2, const value_type* s, size_type n);

    basic_string& replace(const_iterator i1, const_iterator i2, const value_type* s);

    basic_string& replace(const_iterator i1, const_iterator i2, size_type n, value_type c);

    template<class InputIterator>

        basic_string& replace(const_iterator i1, const_iterator i2, InputIterator j1, InputIterator j2);

    basic_string& replace(const_iterator i1, const_iterator i2, initializer_list<value_type>);

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

    basic_string substr(size_type pos = 0, size_type n = npos) const;

    void swap(basic_string& str)

        noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||

                 allocator_traits<allocator_type>::is_always_equal::value);  // C++17

    const value_type* c_str() const noexcept;

    const value_type* data() const noexcept;

    allocator_type get_allocator() const noexcept;

    size_type find(const basic_string& str, size_type pos = 0) const noexcept;

    size_type find(const value_type* s, size_type pos, size_type n) const noexcept;

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

    size_type find(value_type c, size_type pos = 0) const noexcept;

    size_type rfind(const basic_string& str, size_type pos = npos) const noexcept;

    size_type rfind(const value_type* s, size_type pos, size_type n) const noexcept;

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

    size_type rfind(value_type c, size_type pos = npos) const noexcept;

    size_type find_first_of(const basic_string& str, size_type pos = 0) const noexcept;

    size_type find_first_of(const value_type* s, size_type pos, size_type n) const noexcept;

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

    size_type find_first_of(value_type c, size_type pos = 0) const noexcept;

    size_type find_last_of(const basic_string& str, size_type pos = npos) const noexcept;

    size_type find_last_of(const value_type* s, size_type pos, size_type n) const noexcept;

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

    size_type find_last_of(value_type c, size_type pos = npos) const noexcept;

    size_type find_first_not_of(const basic_string& str, size_type pos = 0) const noexcept;

    size_type find_first_not_of(const value_type* s, size_type pos, size_type n) const noexcept;

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

    size_type find_first_not_of(value_type c, size_type pos = 0) const noexcept;

    size_type find_last_not_of(const basic_string& str, size_type pos = npos) const noexcept;

    size_type find_last_not_of(const value_type* s, size_type pos, size_type n) const noexcept;

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

    size_type find_last_not_of(value_type c, size_type pos = npos) const noexcept;

    int compare(const basic_string& str) const noexcept;

    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=npos) const; // C++14

    int compare(const value_type* s) const noexcept;

    int compare(size_type pos1, size_type n1, const value_type* s) const;

    int compare(size_type pos1, size_type n1, const value_type* s, size_type n2) const;

    bool __invariants() const;

};

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) noexcept;

template<class charT, class traits, class Allocator>

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

template<class charT, class traits, class Allocator>

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

template<class charT, class traits, class Allocator>

bool operator!=(const basic_string<charT,traits,Allocator>& lhs,

                const basic_string<charT, traits, Allocator>& rhs) noexcept;

template<class charT, class traits, class Allocator>

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

template<class charT, class traits, class Allocator>

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

template<class charT, class traits, class Allocator>

bool operator< (const basic_string<charT, traits, Allocator>& lhs,

                const basic_string<charT, traits, Allocator>& rhs) noexcept;

template<class charT, class traits, class Allocator>

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

template<class charT, class traits, class Allocator>

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

template<class charT, class traits, class Allocator>

bool operator> (const basic_string<charT, traits, Allocator>& lhs,

                const basic_string<charT, traits, Allocator>& rhs) noexcept;

template<class charT, class traits, class Allocator>

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

template<class charT, class traits, class Allocator>

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

template<class charT, class traits, class Allocator>

bool operator<=(const basic_string<charT, traits, Allocator>& lhs,

                const basic_string<charT, traits, Allocator>& rhs) noexcept;

template<class charT, class traits, class Allocator>

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

template<class charT, class traits, class Allocator>

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

template<class charT, class traits, class Allocator>

bool operator>=(const basic_string<charT, traits, Allocator>& lhs,

                const basic_string<charT, traits, Allocator>& rhs) noexcept;

template<class charT, class traits, class Allocator>

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

template<class charT, class traits, class Allocator>

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

template<class charT, class traits, class Allocator>

void swap(basic_string<charT, traits, Allocator>& lhs,

          basic_string<charT, traits, Allocator>& rhs)

            noexcept(noexcept(lhs.swap(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;

typedef basic_string<char16_t> u16string;

typedef basic_string<char32_t> u32string;

int                stoi  (const string& str, size_t* idx = 0, int base = 10);

long               stol  (const string& str, size_t* idx = 0, int base = 10);

unsigned long      stoul (const string& str, size_t* idx = 0, int base = 10);

long long          stoll (const string& str, size_t* idx = 0, int base = 10);

unsigned long long stoull(const string& str, size_t* idx = 0, int base = 10);

float       stof (const string& str, size_t* idx = 0);

double      stod (const string& str, size_t* idx = 0);

long double stold(const string& str, size_t* idx = 0);

string to_string(int val);

string to_string(unsigned val);

string to_string(long val);

string to_string(unsigned long val);

string to_string(long long val);

string to_string(unsigned long long val);

string to_string(float val);

string to_string(double val);

string to_string(long double val);

int                stoi  (const wstring& str, size_t* idx = 0, int base = 10);

long               stol  (const wstring& str, size_t* idx = 0, int base = 10);

unsigned long      stoul (const wstring& str, size_t* idx = 0, int base = 10);

long long          stoll (const wstring& str, size_t* idx = 0, int base = 10);

unsigned long long stoull(const wstring& str, size_t* idx = 0, int base = 10);

float       stof (const wstring& str, size_t* idx = 0);

double      stod (const wstring& str, size_t* idx = 0);

long double stold(const wstring& str, size_t* idx = 0);

wstring to_wstring(int val);

wstring to_wstring(unsigned val);

wstring to_wstring(long val);

wstring to_wstring(unsigned long val);

wstring to_wstring(long long val);

wstring to_wstring(unsigned long long val);

wstring to_wstring(float val);

wstring to_wstring(double val);

wstring to_wstring(long double val);

template <> struct hash<string>;

template <> struct hash<u16string>;

template <> struct hash<u32string>;

template <> struct hash<wstring>;

basic_string<char>     operator "" s( const char *str,     size_t len ); // C++14

basic_string<wchar_t>  operator "" s( const wchar_t *str,  size_t len ); // C++14

basic_string<char16_t> operator "" s( const char16_t *str, size_t len ); // C++14

basic_string<char32_t> operator "" s( const char32_t *str, size_t len ); // C++14

}  // std

*/

#include <__config>

#include <iosfwd>

#include <cstring>

#include <cstdio>  // For EOF.

#include <cwchar>

#include <algorithm>

#include <iterator>

#include <utility>

#include <memory>

#include <stdexcept>

#include <type_traits>

#include <initializer_list>

#include <__functional_base>

#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS

#include <cstdint>

#endif

#if defined(_LIBCPP_NO_EXCEPTIONS)

#include <cassert>

#endif

#include <__undef_min_max>

#include <__debug>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

#pragma GCC system_header

#endif

_LIBCPP_BEGIN_NAMESPACE_STD

// fpos

template <class _StateT>

class _LIBCPP_TYPE_VIS_ONLY fpos

{

private:

    _StateT __st_;

    streamoff __off_;

public:

    _LIBCPP_INLINE_VISIBILITY fpos(streamoff __off = streamoff()) : __st_(), __off_(__off) {}

    _LIBCPP_INLINE_VISIBILITY operator streamoff() const {return __off_;}

    _LIBCPP_INLINE_VISIBILITY _StateT state() const {return __st_;}

    _LIBCPP_INLINE_VISIBILITY void state(_StateT __st) {__st_ = __st;}

    _LIBCPP_INLINE_VISIBILITY fpos& operator+=(streamoff __off) {__off_ += __off; return *this;}

    _LIBCPP_INLINE_VISIBILITY fpos  operator+ (streamoff __off) const {fpos __t(*this); __t += __off; return __t;}

    _LIBCPP_INLINE_VISIBILITY fpos& operator-=(streamoff __off) {__off_ -= __off; return *this;}

    _LIBCPP_INLINE_VISIBILITY fpos  operator- (streamoff __off) const {fpos __t(*this); __t -= __off; return __t;}

};

template <class _StateT>

inline _LIBCPP_INLINE_VISIBILITY

streamoff operator-(const fpos<_StateT>& __x, const fpos<_StateT>& __y)

    {return streamoff(__x) - streamoff(__y);}

template <class _StateT>

inline _LIBCPP_INLINE_VISIBILITY

bool operator==(const fpos<_StateT>& __x, const fpos<_StateT>& __y)

    {return streamoff(__x) == streamoff(__y);}

template <class _StateT>

inline _LIBCPP_INLINE_VISIBILITY

bool operator!=(const fpos<_StateT>& __x, const fpos<_StateT>& __y)

    {return streamoff(__x) != streamoff(__y);}

// char_traits

template <class _CharT>

struct _LIBCPP_TYPE_VIS_ONLY char_traits

{

    typedef _CharT    char_type;

    typedef int       int_type;

    typedef streamoff off_type;

    typedef streampos pos_type;

    typedef mbstate_t state_type;

    static inline void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT

        {__c1 = __c2;}

    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT

        {return __c1 == __c2;}

    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT

        {return __c1 < __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, size_t __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 inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT

        {return eq_int_type(__c, eof()) ? ~eof() : __c;}

    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT

        {return char_type(__c);}

    static inline _LIBCPP_CONSTEXPR int_type  to_int_type(char_type __c) _NOEXCEPT

        {return int_type(__c);}

    static inline _LIBCPP_CONSTEXPR bool      eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT

        {return __c1 == __c2;}

    static inline _LIBCPP_CONSTEXPR int_type  eof() _NOEXCEPT

        {return int_type(EOF);}

};

template <class _CharT>

int

char_traits<_CharT>::compare(const char_type* __s1, const char_type* __s2, size_t __n)

{

    for (; __n; --__n, ++__s1, ++__s2)

    {

        if (lt(*__s1, *__s2))

            return -1;

        if (lt(*__s2, *__s1))

            return 1;

    }

    return 0;

}

template <class _CharT>

inline _LIBCPP_INLINE_VISIBILITY

size_t

char_traits<_CharT>::length(const char_type* __s)

{

    size_t __len = 0;

    for (; !eq(*__s, char_type(0)); ++__s)

        ++__len;

    return __len;

}

template <class _CharT>

inline _LIBCPP_INLINE_VISIBILITY

const _CharT*

char_traits<_CharT>::find(const char_type* __s, size_t __n, const char_type& __a)

{

    for (; __n; --__n)

    {

        if (eq(*__s, __a))

            return __s;

        ++__s;

    }

    return 0;

}

template <class _CharT>

_CharT*

char_traits<_CharT>::move(char_type* __s1, const char_type* __s2, size_t __n)

{

    char_type* __r = __s1;

    if (__s1 < __s2)

    {

        for (; __n; --__n, ++__s1, ++__s2)

            assign(*__s1, *__s2);

    }

    else if (__s2 < __s1)

    {

        __s1 += __n;

        __s2 += __n;

        for (; __n; --__n)

            assign(*--__s1, *--__s2);

    }

    return __r;

}

template <class _CharT>

inline _LIBCPP_INLINE_VISIBILITY

_CharT*

char_traits<_CharT>::copy(char_type* __s1, const char_type* __s2, size_t __n)

{

    _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");

    char_type* __r = __s1;

    for (; __n; --__n, ++__s1, ++__s2)

        assign(*__s1, *__s2);

    return __r;

}

template <class _CharT>

inline _LIBCPP_INLINE_VISIBILITY

_CharT*

char_traits<_CharT>::assign(char_type* __s, size_t __n, char_type __a)

{

    char_type* __r = __s;

    for (; __n; --__n, ++__s)

        assign(*__s, __a);

    return __r;

}

// char_traits<char>

template <>

struct _LIBCPP_TYPE_VIS_ONLY 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 inline void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT

        {__c1 = __c2;}

    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT

            {return __c1 == __c2;}

    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT

        {return (unsigned char)__c1 < (unsigned char)__c2;}

    static inline int compare(const char_type* __s1, const char_type* __s2, size_t __n)

        {return __n == 0 ? 0 : memcmp(__s1, __s2, __n);}

    static inline size_t length(const char_type* __s) {return strlen(__s);}

    static inline const char_type* find(const char_type* __s, size_t __n, const char_type& __a)

        {return __n == 0 ? NULL : (const char_type*) memchr(__s, to_int_type(__a), __n);}

    static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n)

        {return __n == 0 ? __s1 : (char_type*) memmove(__s1, __s2, __n);}

    static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n)

        {

            _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");

            return __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n);

        }

    static inline char_type* assign(char_type* __s, size_t __n, char_type __a)

        {return __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n);}

    static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT

        {return eq_int_type(__c, eof()) ? ~eof() : __c;}

    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT

        {return char_type(__c);}

    static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT

        {return int_type((unsigned char)__c);}

    static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT

        {return __c1 == __c2;}

    static inline _LIBCPP_CONSTEXPR int_type  eof() _NOEXCEPT

        {return int_type(EOF);}

};

// char_traits<wchar_t>

template <>

struct _LIBCPP_TYPE_VIS_ONLY char_traits<wchar_t>

{

    typedef wchar_t   char_type;

    typedef wint_t    int_type;

    typedef streamoff off_type;

    typedef streampos pos_type;

    typedef mbstate_t state_type;

    static inline void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT

        {__c1 = __c2;}

    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT

        {return __c1 == __c2;}

    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT

        {return __c1 < __c2;}

    static inline int compare(const char_type* __s1, const char_type* __s2, size_t __n)

        {return __n == 0 ? 0 : wmemcmp(__s1, __s2, __n);}

    static inline size_t length(const char_type* __s)

        {return wcslen(__s);}

    static inline const char_type* find(const char_type* __s, size_t __n, const char_type& __a)

        {return __n == 0 ? NULL : (const char_type*)wmemchr(__s, __a, __n);}

    static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n)

        {return __n == 0 ? __s1 : (char_type*)wmemmove(__s1, __s2, __n);}

    static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n)

        {

            _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");

            return __n == 0 ? __s1 : (char_type*)wmemcpy(__s1, __s2, __n);

        }

    static inline char_type* assign(char_type* __s, size_t __n, char_type __a)

        {return __n == 0 ? __s : (char_type*)wmemset(__s, __a, __n);}

    static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT

        {return eq_int_type(__c, eof()) ? ~eof() : __c;}

    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT

        {return char_type(__c);}

    static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT

        {return int_type(__c);}

    static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT

        {return __c1 == __c2;}

    static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT

        {return int_type(WEOF);}

};

#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS

template <>

struct _LIBCPP_TYPE_VIS_ONLY char_traits<char16_t>

{

    typedef char16_t       char_type;

    typedef uint_least16_t int_type;

    typedef streamoff      off_type;

    typedef u16streampos   pos_type;

    typedef mbstate_t      state_type;

    static inline void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT

        {__c1 = __c2;}

    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT

        {return __c1 == __c2;}

    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT

        {return __c1 < __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, size_t __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 inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT

        {return eq_int_type(__c, eof()) ? ~eof() : __c;}

    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT

        {return char_type(__c);}

    static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT

        {return int_type(__c);}

    static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT

        {return __c1 == __c2;}

    static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT

        {return int_type(0xFFFF);}

};

inline _LIBCPP_INLINE_VISIBILITY

int

char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n)

{

    for (; __n; --__n, ++__s1, ++__s2)

    {

        if (lt(*__s1, *__s2))

            return -1;

        if (lt(*__s2, *__s1))

            return 1;

    }

    return 0;

}

inline _LIBCPP_INLINE_VISIBILITY

size_t

char_traits<char16_t>::length(const char_type* __s)

{

    size_t __len = 0;

    for (; !eq(*__s, char_type(0)); ++__s)

        ++__len;

    return __len;

}

inline _LIBCPP_INLINE_VISIBILITY

const char16_t*

char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a)

{

    for (; __n; --__n)

    {

        if (eq(*__s, __a))

            return __s;

        ++__s;

    }

    return 0;

}

inline _LIBCPP_INLINE_VISIBILITY

char16_t*

char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n)

{

    char_type* __r = __s1;

    if (__s1 < __s2)

    {

        for (; __n; --__n, ++__s1, ++__s2)

            assign(*__s1, *__s2);

    }

    else if (__s2 < __s1)

    {

        __s1 += __n;

        __s2 += __n;

        for (; __n; --__n)

            assign(*--__s1, *--__s2);

    }

    return __r;

}

inline _LIBCPP_INLINE_VISIBILITY

char16_t*

char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n)

{

    _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");

    char_type* __r = __s1;

    for (; __n; --__n, ++__s1, ++__s2)

        assign(*__s1, *__s2);

    return __r;

}

inline _LIBCPP_INLINE_VISIBILITY

char16_t*

char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a)

{

    char_type* __r = __s;

    for (; __n; --__n, ++__s)

        assign(*__s, __a);

    return __r;

}

template <>

struct _LIBCPP_TYPE_VIS_ONLY char_traits<char32_t>

{

    typedef char32_t       char_type;

    typedef uint_least32_t int_type;

    typedef streamoff      off_type;

    typedef u32streampos   pos_type;

    typedef mbstate_t      state_type;

    static inline void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT

        {__c1 = __c2;}

    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT

        {return __c1 == __c2;}

    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT

        {return __c1 < __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, size_t __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 inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT

        {return eq_int_type(__c, eof()) ? ~eof() : __c;}

    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT

        {return char_type(__c);}

    static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT

        {return int_type(__c);}

    static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT

        {return __c1 == __c2;}

    static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT

        {return int_type(0xFFFFFFFF);}

};

inline _LIBCPP_INLINE_VISIBILITY

int

char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n)

{

    for (; __n; --__n, ++__s1, ++__s2)

    {

        if (lt(*__s1, *__s2))

            return -1;

        if (lt(*__s2, *__s1))

            return 1;

    }

    return 0;

}

inline _LIBCPP_INLINE_VISIBILITY

size_t

char_traits<char32_t>::length(const char_type* __s)

{

    size_t __len = 0;

    for (; !eq(*__s, char_type(0)); ++__s)

        ++__len;

    return __len;

}

inline _LIBCPP_INLINE_VISIBILITY

const char32_t*

char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a)

{

    for (; __n; --__n)

    {

        if (eq(*__s, __a))

            return __s;

        ++__s;

    }

    return 0;

}

inline _LIBCPP_INLINE_VISIBILITY

char32_t*

char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n)

{

    char_type* __r = __s1;

    if (__s1 < __s2)

    {

        for (; __n; --__n, ++__s1, ++__s2)

            assign(*__s1, *__s2);

    }

    else if (__s2 < __s1)

    {

        __s1 += __n;

        __s2 += __n;

        for (; __n; --__n)

            assign(*--__s1, *--__s2);

    }

    return __r;

}

inline _LIBCPP_INLINE_VISIBILITY

char32_t*

char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n)

{

    _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");

    char_type* __r = __s1;

    for (; __n; --__n, ++__s1, ++__s2)

        assign(*__s1, *__s2);

    return __r;

}

inline _LIBCPP_INLINE_VISIBILITY

char32_t*

char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a)

{

    char_type* __r = __s;

    for (; __n; --__n, ++__s)

        assign(*__s, __a);

    return __r;

}

#endif  // _LIBCPP_HAS_NO_UNICODE_CHARS

// helper fns for basic_string

// __str_find

template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>

_SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY

__str_find(const _CharT *__p, _SizeT __sz, 

             _CharT __c, _SizeT __pos) _NOEXCEPT

{

    if (__pos >= __sz)

        return __npos;

    const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);

    if (__r == 0)

        return __npos;

    return static_cast<_SizeT>(__r - __p);

}

template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>

_SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY

__str_find(const _CharT *__p, _SizeT __sz, 

       const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT

{

    if (__pos > __sz || __sz - __pos < __n)

        return __npos;

    if (__n == 0)

        return __pos;

    const _CharT* __r = 

        _VSTD::__search(__p + __pos, __p + __sz,

                        __s, __s + __n, _Traits::eq,

                        random_access_iterator_tag(), random_access_iterator_tag());

    if (__r == __p + __sz)

        return __npos;

    return static_cast<_SizeT>(__r - __p);

}

// __str_rfind

template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>

_SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY

__str_rfind(const _CharT *__p, _SizeT __sz, 

              _CharT __c, _SizeT __pos) _NOEXCEPT

{

    if (__sz < 1)

        return __npos;

    if (__pos < __sz)

        ++__pos;

    else

        __pos = __sz;

    for (const _CharT* __ps = __p + __pos; __ps != __p;)

    {

        if (_Traits::eq(*--__ps, __c))

            return static_cast<_SizeT>(__ps - __p);

    }

    return __npos;

}

template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>

_SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY

__str_rfind(const _CharT *__p, _SizeT __sz, 

        const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT

{

    __pos = _VSTD::min(__pos, __sz);

    if (__n < __sz - __pos)

        __pos += __n;

    else

        __pos = __sz;

    const _CharT* __r = _VSTD::__find_end(

                  __p, __p + __pos, __s, __s + __n, _Traits::eq, 

                        random_access_iterator_tag(), random_access_iterator_tag());

    if (__n > 0 && __r == __p + __pos)

        return __npos;

    return static_cast<_SizeT>(__r - __p);

}

// __str_find_first_of

template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>

_SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY

__str_find_first_of(const _CharT *__p, _SizeT __sz,

                const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT

{

    if (__pos >= __sz || __n == 0)

        return __npos;

    const _CharT* __r = _VSTD::__find_first_of_ce

        (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq );

    if (__r == __p + __sz)

        return __npos;

    return static_cast<_SizeT>(__r - __p);

}

// __str_find_last_of

template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>

_SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 

__str_find_last_of(const _CharT *__p, _SizeT __sz,

               const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT

    {

    if (__n != 0)

    {

        if (__pos < __sz)

            ++__pos;

        else

            __pos = __sz;

        for (const _CharT* __ps = __p + __pos; __ps != __p;)

        {

            const _CharT* __r = _Traits::find(__s, __n, *--__ps);

            if (__r)

                return static_cast<_SizeT>(__ps - __p);

        }

    }

    return __npos;

}

// __str_find_first_not_of

template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>

_SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY

__str_find_first_not_of(const _CharT *__p, _SizeT __sz,

                    const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT

{

    if (__pos < __sz)

    {

        const _CharT* __pe = __p + __sz;

        for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)

            if (_Traits::find(__s, __n, *__ps) == 0)

                return static_cast<_SizeT>(__ps - __p);

    }

    return __npos;

}

template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>

_SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY

__str_find_first_not_of(const _CharT *__p, _SizeT __sz,

                          _CharT __c, _SizeT __pos) _NOEXCEPT

{

    if (__pos < __sz)

    {

        const _CharT* __pe = __p + __sz;

        for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)

            if (!_Traits::eq(*__ps, __c))

                return static_cast<_SizeT>(__ps - __p);

    }

    return __npos;

}

// __str_find_last_not_of

template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>

_SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY

__str_find_last_not_of(const _CharT *__p, _SizeT __sz,

                   const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT

{

    if (__pos < __sz)

        ++__pos;

    else

        __pos = __sz;

    for (const _CharT* __ps = __p + __pos; __ps != __p;)

        if (_Traits::find(__s, __n, *--__ps) == 0)

            return static_cast<_SizeT>(__ps - __p);

    return __npos;

}

template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>

_SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY

__str_find_last_not_of(const _CharT *__p, _SizeT __sz,

                         _CharT __c, _SizeT __pos) _NOEXCEPT

{

    if (__pos < __sz)

        ++__pos;

    else

        __pos = __sz;

    for (const _CharT* __ps = __p + __pos; __ps != __p;)

        if (!_Traits::eq(*--__ps, __c))

            return static_cast<_SizeT>(__ps - __p);

    return __npos;

}

template<class _Ptr>

size_t _LIBCPP_INLINE_VISIBILITY __do_string_hash(_Ptr __p, _Ptr __e)

{

    typedef typename iterator_traits<_Ptr>::value_type value_type;

    return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type));

}

// basic_string

template<class _CharT, class _Traits, class _Allocator>

basic_string<_CharT, _Traits, _Allocator>

operator+(const basic_string<_CharT, _Traits, _Allocator>& __x,

          const basic_string<_CharT, _Traits, _Allocator>& __y);

template<class _CharT, class _Traits, class _Allocator>

basic_string<_CharT, _Traits, _Allocator>

operator+(const _CharT* __x, const basic_string<_CharT,_Traits,_Allocator>& __y);

template<class _CharT, class _Traits, class _Allocator>

basic_string<_CharT, _Traits, _Allocator>

operator+(_CharT __x, const basic_string<_CharT,_Traits,_Allocator>& __y);

template<class _CharT, class _Traits, class _Allocator>

basic_string<_CharT, _Traits, _Allocator>

operator+(const basic_string<_CharT, _Traits, _Allocator>& __x, const _CharT* __y);

template<class _CharT, class _Traits, class _Allocator>

basic_string<_CharT, _Traits, _Allocator>

operator+(const basic_string<_CharT, _Traits, _Allocator>& __x, _CharT __y);

template <bool>

class _LIBCPP_TYPE_VIS_ONLY __basic_string_common

{

protected:

    void __throw_length_error() const;

    void __throw_out_of_range() const;

};

template <bool __b>

void

__basic_string_common<__b>::__throw_length_error() const

{

#ifndef _LIBCPP_NO_EXCEPTIONS

    throw length_error("basic_string");

#else

    assert(!"basic_string length_error");

#endif

}

template <bool __b>

void

__basic_string_common<__b>::__throw_out_of_range() const

{

#ifndef _LIBCPP_NO_EXCEPTIONS

    throw out_of_range("basic_string");

#else

    assert(!"basic_string out_of_range");

#endif

}

#ifdef _LIBCPP_MSVC

#pragma warning( push )

#pragma warning( disable: 4231 )

#endif // _LIBCPP_MSVC

_LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_TYPE_VIS __basic_string_common<true>)

#ifdef _LIBCPP_MSVC

#pragma warning( pop )

#endif // _LIBCPP_MSVC

#ifdef _LIBCPP_ALTERNATE_STRING_LAYOUT

template <class _CharT, size_t = sizeof(_CharT)>

struct __padding

{

    unsigned char __xx[sizeof(_CharT)-1];

};

template <class _CharT>

struct __padding<_CharT, 1>

{

};

#endif  // _LIBCPP_ALTERNATE_STRING_LAYOUT

template<class _CharT, class _Traits, class _Allocator>

class _LIBCPP_TYPE_VIS_ONLY basic_string

    : private __basic_string_common<true>

{

public:

    typedef basic_string                                 __self;

    typedef _Traits                                      traits_type;

    typedef typename traits_type::char_type              value_type;

    typedef _Allocator                                   allocator_type;

    typedef allocator_traits<allocator_type>             __alloc_traits;

    typedef typename __alloc_traits::size_type           size_type;

    typedef typename __alloc_traits::difference_type     difference_type;

    typedef value_type&                                  reference;

    typedef const value_type&                            const_reference;

    typedef typename __alloc_traits::pointer             pointer;

    typedef typename __alloc_traits::const_pointer       const_pointer;

    static_assert(is_pod<value_type>::value, "Character type of basic_string must be a POD");

    static_assert((is_same<_CharT, value_type>::value),

                  "traits_type::char_type must be the same type as CharT");

    static_assert((is_same<typename allocator_type::value_type, value_type>::value),

                  "Allocator::value_type must be same type as value_type");

#if defined(_LIBCPP_RAW_ITERATORS)

    typedef pointer                                      iterator;

    typedef const_pointer                                const_iterator;

#else  // defined(_LIBCPP_RAW_ITERATORS)

    typedef __wrap_iter<pointer>                         iterator;

    typedef __wrap_iter<const_pointer>                   const_iterator;

#endif  // defined(_LIBCPP_RAW_ITERATORS)

    typedef _VSTD::reverse_iterator<iterator>             reverse_iterator;

    typedef _VSTD::reverse_iterator<const_iterator>       const_reverse_iterator;

private:

#ifdef _LIBCPP_ALTERNATE_STRING_LAYOUT

    struct __long

    {

        pointer   __data_;

        size_type __size_;

        size_type __cap_;

    };

#if _LIBCPP_BIG_ENDIAN

    enum {__short_mask = 0x01};

    enum {__long_mask  = 0x1ul};

#else  // _LIBCPP_BIG_ENDIAN

    enum {__short_mask = 0x80};

    enum {__long_mask  = ~(size_type(~0) >> 1)};

#endif  // _LIBCPP_BIG_ENDIAN

    enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?

                      (sizeof(__long) - 1)/sizeof(value_type) : 2};

    struct __short

    {

        value_type __data_[__min_cap];

        struct

            : __padding<value_type>

        {

            unsigned char __size_;

        };

    };

#else

    struct __long

    {

        size_type __cap_;

        size_type __size_;

        pointer   __data_;

    };

#if _LIBCPP_BIG_ENDIAN

    enum {__short_mask = 0x80};

    enum {__long_mask  = ~(size_type(~0) >> 1)};

#else  // _LIBCPP_BIG_ENDIAN

    enum {__short_mask = 0x01};

    enum {__long_mask  = 0x1ul};

#endif  // _LIBCPP_BIG_ENDIAN

    enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?

                      (sizeof(__long) - 1)/sizeof(value_type) : 2};

    struct __short

    {

        union

        {

            unsigned char __size_;

            value_type __lx;

        };

        value_type __data_[__min_cap];

    };

#endif  // _LIBCPP_ALTERNATE_STRING_LAYOUT

    union __ulx{__long __lx; __short __lxx;};

    enum {__n_words = sizeof(__ulx) / sizeof(size_type)};

    struct __raw

    {

        size_type __words[__n_words];

    };

    struct __rep

    {

        union

        {

            __long  __l;

            __short __s;

            __raw   __r;

        };

    };

    __compressed_pair<__rep, allocator_type> __r_;

public:

    static const size_type npos = -1;

    _LIBCPP_INLINE_VISIBILITY basic_string()

        _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);

    _LIBCPP_INLINE_VISIBILITY explicit basic_string(const allocator_type& __a)

#if _LIBCPP_STD_VER <= 14

        _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value);

#else

        _NOEXCEPT;

#endif

    basic_string(const basic_string& __str);

    basic_string(const basic_string& __str, const allocator_type& __a);

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

    _LIBCPP_INLINE_VISIBILITY

    basic_string(basic_string&& __str)

#if _LIBCPP_STD_VER <= 14

        _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);

#else

        _NOEXCEPT;

#endif

    _LIBCPP_INLINE_VISIBILITY

    basic_string(basic_string&& __str, const allocator_type& __a);

#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES

    _LIBCPP_INLINE_VISIBILITY basic_string(const value_type* __s);

    _LIBCPP_INLINE_VISIBILITY

    basic_string(const value_type* __s, const allocator_type& __a);

    _LIBCPP_INLINE_VISIBILITY

    basic_string(const value_type* __s, size_type __n);

    _LIBCPP_INLINE_VISIBILITY

    basic_string(const value_type* __s, size_type __n, const allocator_type& __a);

    _LIBCPP_INLINE_VISIBILITY

    basic_string(size_type __n, value_type __c);

    _LIBCPP_INLINE_VISIBILITY

    basic_string(size_type __n, value_type __c, const allocator_type& __a);

    basic_string(const basic_string& __str, size_type __pos, size_type __n = npos,

                 const allocator_type& __a = allocator_type());

    template<class _InputIterator>

        _LIBCPP_INLINE_VISIBILITY

        basic_string(_InputIterator __first, _InputIterator __last);

    template<class _InputIterator>

        _LIBCPP_INLINE_VISIBILITY

        basic_string(_InputIterator __first, _InputIterator __last, const allocator_type& __a);

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    _LIBCPP_INLINE_VISIBILITY

    basic_string(initializer_list<value_type> __il);

    _LIBCPP_INLINE_VISIBILITY

    basic_string(initializer_list<value_type> __il, const allocator_type& __a);

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    ~basic_string();

    basic_string& operator=(const basic_string& __str);

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

    _LIBCPP_INLINE_VISIBILITY

    basic_string& operator=(basic_string&& __str)

        _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));

#endif

    _LIBCPP_INLINE_VISIBILITY basic_string& operator=(const value_type* __s) {return assign(__s);}

    basic_string& operator=(value_type __c);

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    _LIBCPP_INLINE_VISIBILITY

    basic_string& operator=(initializer_list<value_type> __il) {return assign(__il.begin(), __il.size());}

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

#if _LIBCPP_DEBUG_LEVEL >= 2

    _LIBCPP_INLINE_VISIBILITY

    iterator begin() _NOEXCEPT

        {return iterator(this, __get_pointer());}

    _LIBCPP_INLINE_VISIBILITY

    const_iterator begin() const _NOEXCEPT

        {return const_iterator(this, __get_pointer());}

    _LIBCPP_INLINE_VISIBILITY

    iterator end() _NOEXCEPT

        {return iterator(this, __get_pointer() + size());}

    _LIBCPP_INLINE_VISIBILITY

    const_iterator end() const _NOEXCEPT

        {return const_iterator(this, __get_pointer() + size());}

#else

    _LIBCPP_INLINE_VISIBILITY

    iterator begin() _NOEXCEPT

        {return iterator(__get_pointer());}

    _LIBCPP_INLINE_VISIBILITY

    const_iterator begin() const _NOEXCEPT

        {return const_iterator(__get_pointer());}

    _LIBCPP_INLINE_VISIBILITY

    iterator end() _NOEXCEPT

        {return iterator(__get_pointer() + size());}

    _LIBCPP_INLINE_VISIBILITY

    const_iterator end() const _NOEXCEPT

        {return const_iterator(__get_pointer() + size());}

#endif  // _LIBCPP_DEBUG_LEVEL >= 2

    _LIBCPP_INLINE_VISIBILITY

    reverse_iterator rbegin() _NOEXCEPT

        {return reverse_iterator(end());}

    _LIBCPP_INLINE_VISIBILITY

    const_reverse_iterator rbegin() const _NOEXCEPT

        {return const_reverse_iterator(end());}

    _LIBCPP_INLINE_VISIBILITY

    reverse_iterator rend() _NOEXCEPT

        {return reverse_iterator(begin());}

    _LIBCPP_INLINE_VISIBILITY

    const_reverse_iterator rend() const _NOEXCEPT

        {return const_reverse_iterator(begin());}

    _LIBCPP_INLINE_VISIBILITY

    const_iterator cbegin() const _NOEXCEPT

        {return begin();}

    _LIBCPP_INLINE_VISIBILITY

    const_iterator cend() const _NOEXCEPT

        {return end();}

    _LIBCPP_INLINE_VISIBILITY

    const_reverse_iterator crbegin() const _NOEXCEPT

        {return rbegin();}

    _LIBCPP_INLINE_VISIBILITY

    const_reverse_iterator crend() const _NOEXCEPT

        {return rend();}

    _LIBCPP_INLINE_VISIBILITY size_type size() const _NOEXCEPT

        {return __is_long() ? __get_long_size() : __get_short_size();}

    _LIBCPP_INLINE_VISIBILITY size_type length() const _NOEXCEPT {return size();}

    _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT;

    _LIBCPP_INLINE_VISIBILITY size_type capacity() const _NOEXCEPT

        {return (__is_long() ? __get_long_cap() : __min_cap) - 1;}

    void resize(size_type __n, value_type __c);

    _LIBCPP_INLINE_VISIBILITY void resize(size_type __n) {resize(__n, value_type());}

    void reserve(size_type res_arg = 0);

    _LIBCPP_INLINE_VISIBILITY

    void shrink_to_fit() _NOEXCEPT {reserve();}

    _LIBCPP_INLINE_VISIBILITY

    void clear() _NOEXCEPT;

    _LIBCPP_INLINE_VISIBILITY bool empty() const _NOEXCEPT {return size() == 0;}

    _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __pos) const;

    _LIBCPP_INLINE_VISIBILITY reference       operator[](size_type __pos);

    const_reference at(size_type __n) const;

    reference       at(size_type __n);

    _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(const basic_string& __str) {return append(__str);}

    _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(const value_type* __s)         {return append(__s);}

    _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(value_type __c)            {push_back(__c); return *this;}

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(initializer_list<value_type> __il) {return append(__il);}

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    _LIBCPP_INLINE_VISIBILITY

    basic_string& append(const basic_string& __str);

    basic_string& append(const basic_string& __str, size_type __pos, size_type __n=npos);

    basic_string& append(const value_type* __s, size_type __n);

    basic_string& append(const value_type* __s);

    basic_string& append(size_type __n, value_type __c);

    template<class _InputIterator>

        typename enable_if

        <

             __is_input_iterator  <_InputIterator>::value &&

            !__is_forward_iterator<_InputIterator>::value,

            basic_string&

        >::type

        append(_InputIterator __first, _InputIterator __last);

    template<class _ForwardIterator>

        typename enable_if

        <

            __is_forward_iterator<_ForwardIterator>::value,

            basic_string&

        >::type

        append(_ForwardIterator __first, _ForwardIterator __last);

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    _LIBCPP_INLINE_VISIBILITY

    basic_string& append(initializer_list<value_type> __il) {return append(__il.begin(), __il.size());}

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    void push_back(value_type __c);

    _LIBCPP_INLINE_VISIBILITY

    void pop_back();

    _LIBCPP_INLINE_VISIBILITY reference       front();

    _LIBCPP_INLINE_VISIBILITY const_reference front() const;

    _LIBCPP_INLINE_VISIBILITY reference       back();

    _LIBCPP_INLINE_VISIBILITY const_reference back() const;

    _LIBCPP_INLINE_VISIBILITY

    basic_string& assign(const basic_string& __str);

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

    _LIBCPP_INLINE_VISIBILITY

    basic_string& assign(basic_string&& str)

        {*this = _VSTD::move(str); return *this;}

#endif

    basic_string& assign(const basic_string& __str, size_type __pos, size_type __n=npos);

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

    basic_string& assign(const value_type* __s);

    basic_string& assign(size_type __n, value_type __c);

    template<class _InputIterator>

        typename enable_if

        <

             __is_input_iterator  <_InputIterator>::value &&

            !__is_forward_iterator<_InputIterator>::value,

            basic_string&

        >::type

        assign(_InputIterator __first, _InputIterator __last);

    template<class _ForwardIterator>

        typename enable_if

        <

            __is_forward_iterator<_ForwardIterator>::value,

            basic_string&

        >::type

        assign(_ForwardIterator __first, _ForwardIterator __last);

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    _LIBCPP_INLINE_VISIBILITY

    basic_string& assign(initializer_list<value_type> __il) {return assign(__il.begin(), __il.size());}

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    _LIBCPP_INLINE_VISIBILITY

    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=npos);

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

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

    basic_string& insert(size_type __pos, size_type __n, value_type __c);

    iterator      insert(const_iterator __pos, value_type __c);

    _LIBCPP_INLINE_VISIBILITY

    iterator      insert(const_iterator __pos, size_type __n, value_type __c);

    template<class _InputIterator>

        typename enable_if

        <

             __is_input_iterator  <_InputIterator>::value &&

            !__is_forward_iterator<_InputIterator>::value,

            iterator

        >::type

        insert(const_iterator __pos, _InputIterator __first, _InputIterator __last);

    template<class _ForwardIterator>

        typename enable_if

        <

            __is_forward_iterator<_ForwardIterator>::value,

            iterator

        >::type

        insert(const_iterator __pos, _ForwardIterator __first, _ForwardIterator __last);

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    _LIBCPP_INLINE_VISIBILITY

    iterator insert(const_iterator __pos, initializer_list<value_type> __il)

                    {return insert(__pos, __il.begin(), __il.end());}

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    basic_string& erase(size_type __pos = 0, size_type __n = npos);

    _LIBCPP_INLINE_VISIBILITY

    iterator      erase(const_iterator __pos);

    _LIBCPP_INLINE_VISIBILITY

    iterator      erase(const_iterator __first, const_iterator __last);

    _LIBCPP_INLINE_VISIBILITY

    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=npos);

    basic_string& replace(size_type __pos, size_type __n1, const value_type* __s, size_type __n2);

    basic_string& replace(size_type __pos, size_type __n1, const value_type* __s);

    basic_string& replace(size_type __pos, size_type __n1, size_type __n2, value_type __c);

    _LIBCPP_INLINE_VISIBILITY

    basic_string& replace(const_iterator __i1, const_iterator __i2, const basic_string& __str);

    _LIBCPP_INLINE_VISIBILITY

    basic_string& replace(const_iterator __i1, const_iterator __i2, const value_type* __s, size_type __n);

    _LIBCPP_INLINE_VISIBILITY