text: ﻿#ifndef MYTINYSTL_BASIC_STRING_H_
  #define MYTINYSTL_BASIC_STRING_H_
  
  // 这个头文件包含一个模板类 basic_string
  // 用于表示字符串类型
  
  #include <iostream>
  
  #include "iterator.h"
  #include "memory.h"
  #include "functional.h"
  #include "exceptdef.h"
  
  namespace mystl
  {
  
  // char_traits
  
  template <class CharType>
  struct char_traits
  {
    typedef CharType char_type;
    
    static size_t length(const char_type* str)
    {
      size_t len = 0;
      for (; *str != char_type(0); ++str)
        ++len;
      return len;
    }
  
    static int compare(const char_type* s1, const char_type* s2, size_t n)
    {
      for (; n != 0; --n, ++s1, ++s2)
      {
        if (*s1 < *s2)
          return -1;
        if (*s2 < *s1)
          return 1;
      }
      return 0;
    }
  
    static char_type* copy(char_type* dst, const char_type* src, size_t n)
    {
      MYSTL_DEBUG(src + n <= dst || dst + n <= src);
      char_type* r = dst;
      for (; n != 0; --n, ++dst, ++src)
        *dst = *src;
      return r;
    }
  
    static char_type* move(char_type* dst, const char_type* src, size_t n)
    {
      char_type* r = dst;
      if (dst < src)
      {
        for (; n != 0; --n, ++dst, ++src)
          *dst = *src;
      }
      else if (src < dst)
      {
        dst += n;
        src += n;
        for (; n != 0; --n)
          *--dst = *--src;
      }
      return r;
    }
  
    static char_type* fill(char_type* dst, char_type ch, size_t count)
    {
      char_type* r = dst;
      for (; count > 0; --count, ++dst)
        *dst = ch;
      return r;
    }
  };
  
  // Partialized. char_traits<char>
  template <> 
  struct char_traits<char>
  {
    typedef char char_type;
  
    static size_t length(const char_type* str) noexcept
    { return std::strlen(str); }
  
    static int compare(const char_type* s1, const char_type* s2, size_t n) noexcept
    { return std::memcmp(s1, s2, n); }
  
    static char_type* copy(char_type* dst, const char_type* src, size_t n) noexcept
    {
      MYSTL_DEBUG(src + n <= dst || dst + n <= src);
      return static_cast<char_type*>(std::memcpy(dst, src, n));
    }
  
    static char_type* move(char_type* dst, const char_type* src, size_t n) noexcept
    {
      return static_cast<char_type*>(std::memmove(dst, src, n));
    }
  
    static char_type* fill(char_type* dst, char_type ch, size_t count) noexcept
    { 
      return static_cast<char_type*>(std::memset(dst, ch, count));
    }
  };
  
  // Partialized. char_traits<wchar_t>
  template <>
  struct char_traits<wchar_t>
  {
    typedef wchar_t char_type;
  
    static size_t length(const char_type* str) noexcept
    {
      return std::wcslen(str);
    }
  
    static int compare(const char_type* s1, const char_type* s2, size_t n) noexcept
    {
      return std::wmemcmp(s1, s2, n);
    }
  
    static char_type* copy(char_type* dst, const char_type* src, size_t n) noexcept
    {
      MYSTL_DEBUG(src + n <= dst || dst + n <= src);
      return static_cast<char_type*>(std::wmemcpy(dst, src, n));
    }
  
    static char_type* move(char_type* dst, const char_type* src, size_t n) noexcept
    {
      return static_cast<char_type*>(std::wmemmove(dst, src, n));
    }
  
    static char_type* fill(char_type* dst, char_type ch, size_t count) noexcept
    { 
      return static_cast<char_type*>(std::wmemset(dst, ch, count));
    }
  };
  
  // Partialized. char_traits<char16_t>
  template <>
  struct char_traits<char16_t>
  {
    typedef char16_t char_type;
  
    static size_t length(const char_type* str) noexcept
    {
      size_t len = 0;
      for (; *str != char_type(0); ++str)
        ++len;
      return len;
    }
  
    static int compare(const char_type* s1, const char_type* s2, size_t n) noexcept
    {
      for (; n != 0; --n, ++s1, ++s2)
      {
        if (*s1 < *s2)
          return -1;
        if (*s2 < *s1)
          return 1;
      }
      return 0;
    }
  
    static char_type* copy(char_type* dst, const char_type* src, size_t n) noexcept
    {
      MYSTL_DEBUG(src + n <= dst || dst + n <= src);
      char_type* r = dst;
      for (; n != 0; --n, ++dst, ++src)
        *dst = *src;
      return r;
    }
  
    static char_type* move(char_type* dst, const char_type* src, size_t n) noexcept
    {
      char_type* r = dst;
      if (dst < src)
      {
        for (; n != 0; --n, ++dst, ++src)
          *dst = *src;
      }
      else if (src < dst)
      {
        dst += n;
        src += n;
        for (; n != 0; --n)
          *--dst = *--src;
      }
      return r;
    }
  
    static char_type* fill(char_type* dst, char_type ch, size_t count) noexcept
    {
      char_type* r = dst;
      for (; count > 0; --count, ++dst)
        *dst = ch;
      return r;
    }
  };
  
  // Partialized. char_traits<char32_t>
  template <>
  struct char_traits<char32_t>
  {
    typedef char32_t char_type;
  
    static size_t length(const char_type* str) noexcept
    {
      size_t len = 0;
      for (; *str != char_type(0); ++str)
        ++len;
      return len;
    }
  
    static int compare(const char_type* s1, const char_type* s2, size_t n) noexcept
    {
      for (; n != 0; --n, ++s1, ++s2)
      {
        if (*s1 < *s2)
          return -1;
        if (*s2 < *s1)
          return 1;
      }
      return 0;
    }
  
    static char_type* copy(char_type* dst, const char_type* src, size_t n) noexcept
    {
      MYSTL_DEBUG(src + n <= dst || dst + n <= src);
      char_type* r = dst;
      for (; n != 0; --n, ++dst, ++src)
        *dst = *src;
      return r;
    }
  
    static char_type* move(char_type* dst, const char_type* src, size_t n) noexcept
    {
      char_type* r = dst;
      if (dst < src)
      {
        for (; n != 0; --n, ++dst, ++src)
          *dst = *src;
      }
      else if (src < dst)
      {
        dst += n;
        src += n;
        for (; n != 0; --n)
          *--dst = *--src;
      }
      return r;
    }
  
    static char_type* fill(char_type* dst, char_type ch, size_t count) noexcept
    {
      char_type* r = dst;
      for (; count > 0; --count, ++dst)
        *dst = ch;
      return r;
    }
  };
  
  // 初始化 basic_string 尝试分配的最小 buffer 大小，可能被忽略
  #define STRING_INIT_SIZE 32
  
  // 模板类 basic_string
  // 参数一代表字符类型，参数二代表萃取字符类型的方式，缺省使用 mystl::char_traits
  template <class CharType, class CharTraits = mystl::char_traits<CharType>>
  class basic_string
  {
  public:
    typedef CharTraits                               traits_type;
    typedef CharTraits                               char_traits;
  
    typedef mystl::allocator<CharType>               allocator_type;
    typedef mystl::allocator<CharType>               data_allocator;
  
    typedef typename allocator_type::value_type      value_type;
    typedef typename allocator_type::pointer         pointer;
    typedef typename allocator_type::const_pointer   const_pointer;
    typedef typename allocator_type::reference       reference;
    typedef typename allocator_type::const_reference const_reference;
    typedef typename allocator_type::size_type       size_type;
    typedef typename allocator_type::difference_type difference_type;
  
    typedef value_type*                              iterator;
    typedef const value_type*                        const_iterator;
    typedef mystl::reverse_iterator<iterator>        reverse_iterator;
    typedef mystl::reverse_iterator<const_iterator>  const_reverse_iterator;
  
    allocator_type get_allocator() { return allocator_type(); }
  
    static_assert(std::is_pod<CharType>::value, "Character type of basic_string must be a POD");
    static_assert(std::is_same<CharType, typename traits_type::char_type>::value,
                  "CharType must be same as traits_type::char_type");
  
  public:
    // 末尾位置的值，例:
    // if (str.find('a') != string::npos) { /* do something */ }
    static constexpr size_type npos = static_cast<size_type>(-1);
  
  private:
    iterator  buffer_;  // 储存字符串的起始位置
    size_type size_;    // 大小
    size_type cap_;     // 容量
  
  public:
    // 构造、复制、移动、析构函数
  
    basic_string() noexcept
    { try_init(); }
  
    basic_string(size_type n, value_type ch)
      :buffer_(nullptr), size_(0), cap_(0)
    {
      fill_init(n, ch);
    }
  
    basic_string(const basic_string& other, size_type pos)
      :buffer_(nullptr), size_(0), cap_(0)
    {
      init_from(other.buffer_, pos, other.size_ - pos);
    }
    basic_string(const basic_string& other, size_type pos, size_type count)
      :buffer_(nullptr), size_(0), cap_(0)
    {
      init_from(other.buffer_, pos, count);
    }
  
    basic_string(const_pointer str)
      :buffer_(nullptr), size_(0), cap_(0)
    {
      init_from(str, 0, char_traits::length(str));
    }
    basic_string(const_pointer str, size_type count)
      :buffer_(nullptr), size_(0), cap_(0)
    {
      init_from(str, 0, count);
    }
  
    template <class Iter, typename std::enable_if<
      mystl::is_input_iterator<Iter>::value, int>::type = 0>
    basic_string(Iter first, Iter last)
    { copy_init(first, last, iterator_category(first)); }
  
    basic_string(const basic_string& rhs) 
      :buffer_(nullptr), size_(0), cap_(0)
    {
      init_from(rhs.buffer_, 0, rhs.size_);
    }
    basic_string(basic_string&& rhs) noexcept
      :buffer_(rhs.buffer_), size_(rhs.size_), cap_(rhs.cap_)
    {
      rhs.buffer_ = nullptr;
      rhs.size_ = 0;
      rhs.cap_ = 0;
    }
  
    basic_string& operator=(const basic_string& rhs);
    basic_string& operator=(basic_string&& rhs) noexcept;
  
    basic_string& operator=(const_pointer str);
    basic_string& operator=(value_type ch);
  
    ~basic_string() { destroy_buffer(); }
  
  public:
    // 迭代器相关操作
    iterator               begin()         noexcept
    { return buffer_; }
    const_iterator         begin()   const noexcept
    { return buffer_; }
    iterator               end()           noexcept
    { return buffer_ + size_; }
    const_iterator         end()     const noexcept
    { return buffer_ + size_; }
  
    reverse_iterator       rbegin()        noexcept
    { return reverse_iterator(end()); }
    const_reverse_iterator rbegin()  const noexcept
    { return const_reverse_iterator(end()); }
    reverse_iterator       rend()          noexcept
    { return reverse_iterator(begin()); }
    const_reverse_iterator rend()    const noexcept
    { return const_reverse_iterator(begin()); }
  
    const_iterator         cbegin()  const noexcept
    { return begin(); }
    const_iterator         cend()    const noexcept
    { return end(); }
    const_reverse_iterator crbegin() const noexcept
    { return rbegin(); }
    const_reverse_iterator crend()   const noexcept
    { return rend(); }
  
    // 容量相关操作
    bool      empty()    const noexcept
    { return size_ == 0; }
  
    size_type size()     const noexcept
    { return size_; }
    size_type length()   const noexcept
    { return size_; }
    size_type capacity() const noexcept
    { return cap_; }
    size_type max_size() const noexcept
    { return static_cast<size_type>(-1); }
  
    void      reserve(size_type n);
    void      shrink_to_fit();
  
    // 访问元素相关操作
    reference       operator[](size_type n) 
    {
      MYSTL_DEBUG(n <= size_);
      if (n == size_)
        *(buffer_ + n) = value_type();
      return *(buffer_ + n); 
    }
    const_reference operator[](size_type n) const
    { 
      MYSTL_DEBUG(n <= size_);
      if (n == size_)
        *(buffer_ + n) = value_type();
      return *(buffer_ + n);
    }
  
    reference       at(size_type n) 
    { 
      THROW_OUT_OF_RANGE_IF(n >= size_, "basic_string<Char, Traits>::at()"
                            "subscript out of range");
      return (*this)[n]; 
    }
    const_reference at(size_type n) const 
    {
      THROW_OUT_OF_RANGE_IF(n >= size_, "basic_string<Char, Traits>::at()"
                            "subscript out of range");
      return (*this)[n]; 
    }
  
    reference       front() 
    { 
      MYSTL_DEBUG(!empty());
      return *begin(); 
    }
    const_reference front() const 
    { 
      MYSTL_DEBUG(!empty());
      return *begin(); 
    }
  
    reference       back() 
    {
      MYSTL_DEBUG(!empty()); 
      return *(end() - 1); 
    }
    const_reference back()  const
    {
      MYSTL_DEBUG(!empty()); 
      return *(end() - 1);
    }
  
    const_pointer   data()  const noexcept
    { return to_raw_pointer(); }
    const_pointer   c_str() const noexcept
    { return to_raw_pointer(); }
  
    // 添加删除相关操作
  
    // insert
    iterator insert(const_iterator pos, value_type ch);
    iterator insert(const_iterator pos, size_type count, value_type ch);
  
    template <class Iter>
    iterator insert(const_iterator pos, Iter first, Iter last);
  
  
    // push_back / pop_back
    void     push_back(value_type ch)
    { append(1, ch); }
    void     pop_back()
    {
      MYSTL_DEBUG(!empty());
      --size_;
    }
  
    // append
    basic_string& append(size_type count, value_type ch);
  
    basic_string& append(const basic_string& str)
    { return append(str, 0, str.size_); }
    basic_string& append(const basic_string& str, size_type pos)
    { return append(str, pos, str.size_ - pos); }
    basic_string& append(const basic_string& str, size_type pos, size_type count);
  
    basic_string& append(const_pointer s)
    { return append(s, char_traits::length(s)); }
    basic_string& append(const_pointer s, size_type count);
  
    template <class Iter, typename std::enable_if<
      mystl::is_input_iterator<Iter>::value, int>::type = 0>
    basic_string& append(Iter first, Iter last)
    { return append_range(first, last); }
  
    // erase /clear
    iterator erase(const_iterator pos);
    iterator erase(const_iterator first, const_iterator last);
  
    // resize
    void resize(size_type count)
    { resize(count, value_type()); }
    void resize(size_type count, value_type ch);
  
    void     clear() noexcept
    { size_ = 0; }
  
    // basic_string 相关操作
  
    // compare
    int compare(const basic_string& other) const;
    int compare(size_type pos1, size_type count1, const basic_string& other) const;
    int compare(size_type pos1, size_type count1, const basic_string& other,
                size_type pos2, size_type count2 = npos) const;
    int compare(const_pointer s) const;
    int compare(size_type pos1, size_type count1, const_pointer s) const;
    int compare(size_type pos1, size_type count1, const_pointer s, size_type count2) const;
  
    // substr
    basic_string substr(size_type index, size_type count = npos)
    {
      count = mystl::min(count, size_ - index);
      return basic_string(buffer_ + index, buffer_ + index + count);
    }
  
    // replace
    basic_string& replace(size_type pos, size_type count, const basic_string& str)
    {
      THROW_OUT_OF_RANGE_IF(pos > size_, "basic_string<Char, Traits>::replace's pos out of range");
      return replace_cstr(buffer_ + pos, count, str.buffer_, str.size_);
    }
    basic_string& replace(const_iterator first, const_iterator last, const basic_string& str)
    {
      MYSTL_DEBUG(begin() <= first && last <= end() && first <= last);
      return replace_cstr(first, static_cast<size_type>(last - first), str.buffer_, str.size_);
    }
  
    basic_string& replace(size_type pos, size_type count, const_pointer str)
    {
      THROW_OUT_OF_RANGE_IF(pos > size_, "basic_string<Char, Traits>::replace's pos out of range");
      return replace_cstr(buffer_ + pos, count, str, char_traits::length(str));
    }
    basic_string& replace(const_iterator first, const_iterator last, const_pointer str)
    {
      MYSTL_DEBUG(begin() <= first && last <= end() && first <= last);
      return replace_cstr(first, static_cast<size_type>(last - first), str, char_traits::length(str));
    }
  
    basic_string& replace(size_type pos, size_type count, const_pointer str, size_type count2)
    {
      THROW_OUT_OF_RANGE_IF(pos > size_, "basic_string<Char, Traits>::replace's pos out of range");
      return replace_cstr(buffer_ + pos, count, str, count2);
    }
    basic_string& replace(const_iterator first, const_iterator last, const_pointer str, size_type count)
    {
      MYSTL_DEBUG(begin() <= first && last <= end() && first <= last);
      return replace_cstr(first, static_cast<size_type>(last - first), str, count);
  
    }
  
    basic_string& replace(size_type pos, size_type count, size_type count2, value_type ch)
    {
      THROW_OUT_OF_RANGE_IF(pos > size_, "basic_string<Char, Traits>::replace's pos out of range");
      return replace_fill(buffer_ + pos, count, count2, ch);
    }
    basic_string& replace(const_iterator first, const_iterator last, size_type count, value_type ch)
    {
      MYSTL_DEBUG(begin() <= first && last <= end() && first <= last);
      return replace_fill(first, static_cast<size_type>(last - first), count, ch);
    }
  
    basic_string& replace(size_type pos1, size_type count1, const basic_string& str,
                          size_type pos2, size_type count2 = npos)
    {
      THROW_OUT_OF_RANGE_IF(pos1 > size_ || pos2 > str.size_,
                            "basic_string<Char, Traits>::replace's pos out of range");
      return replace_cstr(buffer_ + pos1, count1, str.buffer_ + pos2, count2);
    }
  
    template <class Iter, typename std::enable_if<
      mystl::is_input_iterator<Iter>::value, int>::type = 0>
    basic_string& replace(const_iterator first, const_iterator last, Iter first2, Iter last2)
    {
      MYSTL_DEBUG(begin() <= first && last <= end() && first <= last);
      return replace_copy(first, last, first2, last2);
    }
  
    // reverse
    void reverse() noexcept;
  
    // swap
    void swap(basic_string& rhs) noexcept;
  
    // 查找相关操作
  
    // find
    size_type find(value_type ch, size_type pos = 0)                             const noexcept;
    size_type find(const_pointer str, size_type pos = 0)                         const noexcept;
    size_type find(const_pointer str, size_type pos, size_type count)            const noexcept;
    size_type find(const basic_string& str, size_type pos = 0)                   const noexcept;
  
    // rfind
    size_type rfind(value_type ch, size_type pos = npos)                         const noexcept;
    size_type rfind(const_pointer str, size_type pos = npos)                     const noexcept;
    size_type rfind(const_pointer str, size_type pos, size_type count)           const noexcept;
    size_type rfind(const basic_string& str, size_type pos = npos)               const noexcept;
  
    // find_first_of
    size_type find_first_of(value_type ch, size_type pos = 0)                    const noexcept;
    size_type find_first_of(const_pointer s, size_type pos = 0)                  const noexcept;
    size_type find_first_of(const_pointer s, size_type pos, size_type count)     const noexcept;
    size_type find_first_of(const basic_string& str, size_type pos = 0)          const noexcept;
  
    // find_first_not_of
    size_type find_first_not_of(value_type ch, size_type pos = 0)                const noexcept;
    size_type find_first_not_of(const_pointer s, size_type pos = 0)              const noexcept;
    size_type find_first_not_of(const_pointer s, size_type pos, size_type count) const noexcept;
    size_type find_first_not_of(const basic_string& str, size_type pos = 0)      const noexcept;
  
    // find_last_of
    size_type find_last_of(value_type ch, size_type pos = 0)                     const noexcept;
    size_type find_last_of(const_pointer s, size_type pos = 0)                   const noexcept;
    size_type find_last_of(const_pointer s, size_type pos, size_type count)      const noexcept;
    size_type find_last_of(const basic_string& str, size_type pos = 0)           const noexcept;
  
    // find_last_not_of
    size_type find_last_not_of(value_type ch, size_type pos = 0)                 const noexcept;
    size_type find_last_not_of(const_pointer s, size_type pos = 0)               const noexcept;
    size_type find_last_not_of(const_pointer s, size_type pos, size_type count)  const noexcept;
    size_type find_last_not_of(const basic_string& str, size_type pos = 0)       const noexcept;
  
    // count
    size_type count(value_type ch, size_type pos = 0) const noexcept;
  
  public:
    // 重载 operator+= 
    basic_string& operator+=(const basic_string& str)
    { return append(str); }
    basic_string& operator+=(value_type ch)
    { return append(1, ch); }
    basic_string& operator+=(const_pointer str)
    { return append(str, str + char_traits::length(str)); }
  
    // 重载 operator >> / operatror <<
  
    friend std::istream& operator >> (std::istream& is, basic_string& str)
    {
      value_type* buf = new value_type[4096];
      is >> buf;
      basic_string tmp(buf);
      str = std::move(tmp);
      delete[]buf;
      return is;
    }
  
    friend std::ostream& operator << (std::ostream& os, const basic_string& str)
    {
      for (size_type i = 0; i < str.size_; ++i)
        os << *(str.buffer_ + i);
      return os;
    }
  
  private:
    // helper functions
  
    // init / destroy 
    void          try_init() noexcept;
  
    void          fill_init(size_type n, value_type ch);
  
    template <class Iter>
    void          copy_init(Iter first, Iter last, mystl::input_iterator_tag);
    template <class Iter>
    void          copy_init(Iter first, Iter last, mystl::forward_iterator_tag);
  
    void          init_from(const_pointer src, size_type pos, size_type n);
  
    void          destroy_buffer();
  
    // get raw pointer
    const_pointer to_raw_pointer() const;
  
    // shrink_to_fit
    void          reinsert(size_type size);
  
    // append
    template <class Iter>
    basic_string& append_range(Iter first, Iter last);
  
    // compare
    int compare_cstr(const_pointer s1, size_type n1, const_pointer s2, size_type n2) const;
  
    // replace
    basic_string& replace_cstr(const_iterator first, size_type count1, const_pointer str, size_type count2);
    basic_string& replace_fill(const_iterator first, size_type count1, size_type count2, value_type ch);
    template <class Iter>
    basic_string& replace_copy(const_iterator first, const_iterator last, Iter first2, Iter last2);
  
    // reallocate
    void          reallocate(size_type need);
    iterator      reallocate_and_fill(iterator pos, size_type n, value_type ch);
    iterator      reallocate_and_copy(iterator pos, const_iterator first, const_iterator last);
  };
  
  /*****************************************************************************************/
  
  // 复制赋值操作符
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>&
  basic_string<CharType, CharTraits>::
  operator=(const basic_string& rhs)
  {
    if (this != &rhs)
    {
      basic_string tmp(rhs);
      swap(tmp);
    }
    return *this;
  }
  
  // 移动赋值操作符
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>&
  basic_string<CharType, CharTraits>::
  operator=(basic_string&& rhs) noexcept
  {
    destroy_buffer();
    buffer_ = rhs.buffer_;
    size_ = rhs.size_;
    cap_ = rhs.cap_;
    rhs.buffer_ = nullptr;
    rhs.size_ = 0;
    rhs.cap_ = 0;
    return *this;
  }
  
  // 用一个字符串赋值
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>&
  basic_string<CharType, CharTraits>::
  operator=(const_pointer str)
  {
    const size_type len = char_traits::length(str);
    if (cap_ < len)
    {
      auto new_buffer = data_allocator::allocate(len + 1);
      data_allocator::deallocate(buffer_);
      buffer_ = new_buffer;
      cap_ = len + 1;
    }
    char_traits::copy(buffer_, str, len);
    size_ = len;
    return *this;
  }
  
  // 用一个字符赋值
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>&
  basic_string<CharType, CharTraits>::
  operator=(value_type ch)
  {
    if (cap_ < 1)
    {
      auto new_buffer = data_allocator::allocate(2);
      data_allocator::deallocate(buffer_);
      buffer_ = new_buffer;
      cap_ = 2;
    }
    *buffer_ = ch;
    size_ = 1;
    return *this;
  }
  
  // 预留储存空间
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
  reserve(size_type n)
  {
    if (cap_ < n)
    {
      THROW_LENGTH_ERROR_IF(n > max_size(), "n can not larger than max_size()"
                            "in basic_string<Char,Traits>::reserve(n)");
      auto new_buffer = data_allocator::allocate(n);
      char_traits::move(new_buffer, buffer_, size_);
      buffer_ = new_buffer;
      cap_ = n;
    }
  }
  
  // 减少不用的空间
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
  shrink_to_fit()
  {
    if (size_ != cap_)
    {
      reinsert(size_);
    }
  }
  
  // 在 pos 处插入一个元素
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::iterator
  basic_string<CharType, CharTraits>::
  insert(const_iterator pos, value_type ch)
  {
    iterator r = const_cast<iterator>(pos);
    if (size_ == cap_)
    {
      return reallocate_and_fill(r, 1, ch);
    }
    char_traits::move(r + 1, r, end() - r);
    ++size_;
    *r = ch;
    return r;
  }
  
  // 在 pos 处插入 n 个元素
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::iterator
  basic_string<CharType, CharTraits>::
  insert(const_iterator pos, size_type count, value_type ch)
  {
    iterator r = const_cast<iterator>(pos);
    if (count == 0)
      return r;
    if (cap_ - size_ < count)
    {
      return reallocate_and_fill(r, count, ch);
    }
    if (pos == end())
    {
      char_traits::fill(end(), ch, count);
      size_ += count;
      return r;
    }
    char_traits::move(r + count, r, count);
    char_traits::fill(r, ch, count);
    size_ += count;
    return r;
  }
  
  // 在 pos 处插入 [first, last) 内的元素
  template <class CharType, class CharTraits>
  template <class Iter>
  typename basic_string<CharType, CharTraits>::iterator
  basic_string<CharType, CharTraits>::
  insert(const_iterator pos, Iter first, Iter last)
  {
    iterator r = const_cast<iterator>(pos);
    const size_type len = mystl::distance(first, last);
    if (len == 0)
      return r;
    if (cap_ - size_ < len)
    {
      return reallocate_and_copy(r, first, last);
    }
    if (pos == end())
    {
      mystl::uninitialized_copy(first, last, end());
      size_ += len;
      return r;
    }
    char_traits::move(r + len, r, len);
    mystl::uninitialized_copy(first, last, r);
    size_ += len;
    return r;
  }
  
  // 在末尾添加 count 个 ch
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>& 
  basic_string<CharType, CharTraits>::
  append(size_type count, value_type ch)
  {
    THROW_LENGTH_ERROR_IF(size_ > max_size() - count,
                          "basic_string<Char, Tratis>'s size too big");
    if (cap_ - size_ < count)
    {
      reallocate(count);
    }
    char_traits::fill(buffer_ + size_, ch, count);
    size_ += count;
    return *this;
  }
  
  // 在末尾添加 [str[pos] str[pos+count]) 一段
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>& 
  basic_string<CharType, CharTraits>::
  append(const basic_string& str, size_type pos, size_type count)
  {
    THROW_LENGTH_ERROR_IF(size_ > max_size() - count,
                          "basic_string<Char, Tratis>'s size too big");
    if (count == 0)
      return *this;
    if (cap_ - size_ < count)
    {
      reallocate(count);
    }
    char_traits::copy(buffer_ + size_, str.buffer_ + pos, count);
    size_ += count;
    return *this;
  }
  
  // 在末尾添加 [s, s+count) 一段
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>& 
  basic_string<CharType, CharTraits>::
  append(const_pointer s, size_type count)
  {
    THROW_LENGTH_ERROR_IF(size_ > max_size() - count,
                          "basic_string<Char, Tratis>'s size too big");
    if (cap_ - size_ < count)
    {
      reallocate(count);
    }
    char_traits::copy(buffer_ + size_, s, count);
    size_ += count;
    return *this;
  }
  
  // 删除 pos 处的元素
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::iterator
  basic_string<CharType, CharTraits>::
  erase(const_iterator pos)
  {
    MYSTL_DEBUG(pos != end());
    iterator r = const_cast<iterator>(pos);
    char_traits::move(r, pos + 1, end() - pos - 1);
    --size_;
    return r;
  }
  
  // 删除 [first, last) 的元素
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::iterator
  basic_string<CharType, CharTraits>::
  erase(const_iterator first, const_iterator last)
  {
    if (first == begin() && last == end())
    {
      clear();
      return end();
    }
    const size_type n = end() - last;
    iterator r = const_cast<iterator>(first);
    char_traits::move(r, last, n);
    size_ -= (last - first);
    return r;
  }
  
  // 重置容器大小
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
  resize(size_type count, value_type ch)
  {
    if (count < size_)
    {
      erase(buffer_ + count, buffer_ + size_);
    }
    else
    {
      append(count - size_, ch);
    }
  }
  
  // 比较两个 basic_string，小于返回 -1，大于返回 1，等于返回 0
  template <class CharType, class CharTraits>
  int basic_string<CharType, CharTraits>::
  compare(const basic_string& other) const
  {
    return compare_cstr(buffer_, size_, other.buffer_, other.size_);
  }
  
  // 从 pos1 下标开始的 count1 个字符跟另一个 basic_string 比较
  template <class CharType, class CharTraits>
  int basic_string<CharType, CharTraits>::
  compare(size_type pos1, size_type count1, const basic_string& other) const
  {
    auto n1 = mystl::min(count1, size_ - pos1);
    return compare_cstr(buffer_ + pos1, n1, other.buffer_, other.size_);
  }
  
  // 从 pos1 下标开始的 count1 个字符跟另一个 basic_string 下标 pos2 开始的 count2 个字符比较
  template <class CharType, class CharTraits>
  int basic_string<CharType, CharTraits>::
  compare(size_type pos1, size_type count1, const basic_string& other,
          size_type pos2, size_type count2) const
  {
    auto n1 = mystl::min(count1, size_ - pos1);
    auto n2 = mystl::min(count2, other.size_ - pos2);
    return compare_cstr(buffer_, n1, other.buffer_, n2);
  }
  
  // 跟一个字符串比较
  template <class CharType, class CharTraits>
  int basic_string<CharType, CharTraits>::
  compare(const_pointer s) const
  {
    auto n2 = char_traits::length(s);
    return compare_cstr(buffer_, size_, s, n2);
  }
  
  // 从下标 pos1 开始的 count1 个字符跟另一个字符串比较
  template <class CharType, class CharTraits>
  int basic_string<CharType, CharTraits>::
  compare(size_type pos1, size_type count1, const_pointer s) const
  {
    auto n1 = mystl::min(count1, size_ - pos1);
    auto n2 = char_traits::length(s);
    return compare_cstr(buffer_, n1, s, n2);
  }
  
  // 从下标 pos1 开始的 count1 个字符跟另一个字符串的前 count2 个字符比较
  template <class CharType, class CharTraits>
  int basic_string<CharType, CharTraits>::
  compare(size_type pos1, size_type count1, const_pointer s, size_type count2) const
  {
    auto n1 = mystl::min(count1, size_ - pos1);
    return compare_cstr(buffer_, n1, s, count2);
  }
  
  // 反转 basic_string
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
  reverse() noexcept
  {
    for (auto i = begin(), j = end(); i < j;)
    {
      mystl::iter_swap(i++, --j);
    }
  }
  
  // 交换两个 basic_string
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
  swap(basic_string& rhs) noexcept
  {
    if (this != &rhs)
    {
      mystl::swap(buffer_, rhs.buffer_);
      mystl::swap(size_, rhs.size_);
      mystl::swap(cap_, rhs.cap_);
    }
  }
  
  // 从下标 pos 开始查找字符为 ch 的元素，若找到返回其下标，否则返回 npos
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find(value_type ch, size_type pos) const noexcept
  {
    for (auto i = pos; i < size_; ++i)
    {
      if (*(buffer_ + i) == ch)
        return i;
    }
    return npos;
  }
  
  // 从下标 pos 开始查找字符串 str，若找到返回起始位置的下标，否则返回 npos
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find(const_pointer str, size_type pos) const noexcept
  {
    const auto len = char_traits::length(str);
    if (len == 0)
      return pos;
    if (size_ - pos < len)
      return npos;
    const auto left = size_ - len;
    for (auto i = pos; i <= left; ++i)
    {
      if (*(buffer_ + i) == *str)
      {
        size_type j = 1;
        for (; j < len; ++j)
        {
          if (*(buffer_ + i + j) != *(str + j))
            break;
        }
        if (j == len)
          return i;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始查找字符串 str 的前 count 个字符，若找到返回起始位置的下标，否则返回 npos
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find(const_pointer str, size_type pos, size_type count) const noexcept
  {
    if (count == 0)
      return pos;
    if (size_ - pos < count)
      return npos;
    const auto left = size_ - count;
    for (auto i = pos; i <= left; ++i)
    {
      if (*(buffer_ + i) == *str)
      {
        size_type j = 1;
        for (; j < count; ++j)
        {
          if (*(buffer_ + i + j) != *(str + j))
            break;
        }
        if (j == count)
          return i;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始查找字符串 str，若找到返回起始位置的下标，否则返回 npos
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find(const basic_string& str, size_type pos) const noexcept
  {
    const size_type count = str.size_;
    if (count == 0)
      return pos;
    if (size_ - pos < count)
      return npos;
    const auto left = size_ - count;
    for (auto i = pos; i <= left; ++i)
    {
      if (*(buffer_ + i) == str.front())
      {
        size_type j = 1;
        for (; j < count; ++j)
        {
          if (*(buffer_ + i + j) != str[j])
            break;
        }
        if (j == count)
          return i;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始反向查找值为 ch 的元素，与 find 类似
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  rfind(value_type ch, size_type pos) const noexcept
  {
    if (pos >= size_)
      pos = size_ - 1;
    for (auto i = pos; i != 0; --i)
    {
      if (*(buffer_ + i) == ch)
        return i;
    }
    return front() == ch ? 0 : npos;
  }
  
  // 从下标 pos 开始反向查找字符串 str，与 find 类似
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  rfind(const_pointer str, size_type pos) const noexcept
  {
    if (pos >= size_)
      pos = size_ - 1;
    const size_type len = char_traits::length(str);
    switch (len)
    {
      case 0: 
        return pos;
      case 1: 
      {
        for (auto i = pos; i != 0; --i)
        {
          if (*(buffer_ + i) == *str)
            return i;
        }
        return front() == *str ? 0 : npos;
      }
      default:
      { // len >= 2
        for (auto i = pos; i >= len - 1; --i)
        {
          if (*(buffer_ + i) == *(str + len - 1))
          {
            size_type j = 1;
            for (; j < len; ++j)
            {
              if (*(buffer_ + i - j) != *(str + len - j - 1))
                break;
            }
            if (j == len)
              return i - len + 1;
          }
        }
        break;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始反向查找字符串 str 前 count 个字符，与 find 类似
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  rfind(const_pointer str, size_type pos, size_type count) const noexcept
  {
    if (count == 0)
      return pos;
    if (pos >= size_)
      pos = size_ - 1;
    if (pos < count - 1)
      return npos;
    for (auto i = pos; i >= count - 1; --i)
    {
      if (*(buffer_ + i) == *(str + count - 1))
      {
        size_type j = 1;
        for (; j < count; ++j)
        {
          if (*(buffer_ + i - j) != *(str + count - j - 1))
            break;
        }
        if (j == count)
          return i - count + 1;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始反向查找字符串 str，与 find 类似
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  rfind(const basic_string& str, size_type pos) const noexcept
  {
    const size_type count = str.size_;
    if (pos >= size_)
      pos = size_ - 1;
    if (count == 0)
      return pos;
    if (pos < count - 1)
      return npos;
    for (auto i = pos; i >= count - 1; --i)
    {
      if (*(buffer_ + i) == str[count - 1])
      {
        size_type j = 1;
        for (; j < count; ++j)
        {
          if (*(buffer_ + i - j) != str[count - j - 1])
            break;
        }
        if (j == count)
          return i - count + 1;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始查找 ch 出现的第一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_first_of(value_type ch, size_type pos) const noexcept
  {
    for (auto i = pos; i < size_; ++i)
    {
      if (*(buffer_ + i) == ch)
        return i;
    }
    return npos;
  }
  
  // 从下标 pos 开始查找字符串 s 其中的一个字符出现的第一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_first_of(const_pointer s, size_type pos) const noexcept
  {
    const size_type len = char_traits::length(s);
    for (auto i = pos; i < size_; ++i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < len; ++j)
      {
        if (ch == *(s + j))
          return i;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始查找字符串 s 
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_first_of(const_pointer s, size_type pos, size_type count) const noexcept
  {
    for (auto i = pos; i < size_; ++i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < count; ++j)
      {
        if (ch == *(s + j))
          return i;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始查找字符串 str 其中一个字符出现的第一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_first_of(const basic_string& str, size_type pos) const noexcept
  {
    for (auto i = pos; i < size_; ++i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < str.size_; ++j)
      {
        if (ch == str[j])
          return i;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始查找与 ch 不相等的第一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_first_not_of(value_type ch, size_type pos) const noexcept
  {
    for (auto i = pos; i < size_; ++i)
    {
      if (*(buffer_ + i) != ch)
        return i;
    }
    return npos;
  }
  
  // 从下标 pos 开始查找与字符串 s 其中一个字符不相等的第一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_first_not_of(const_pointer s, size_type pos) const noexcept
  {
    const size_type len = char_traits::length(s);
    for (auto i = pos; i < size_; ++i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < len; ++j)
      {
        if (ch != *(s + j))
          return i;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始查找与字符串 s 前 count 个字符中不相等的第一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_first_not_of(const_pointer s, size_type pos, size_type count) const noexcept
  {
    for (auto i = pos; i < size_; ++i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < count; ++j)
      {
        if (ch != *(s + j))
          return i;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始查找与字符串 str 的字符中不相等的第一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_first_not_of(const basic_string& str, size_type pos) const noexcept
  {
    for (auto i = pos; i < size_; ++i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < str.size_; ++j)
      {
        if (ch != str[j])
          return i;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始查找与 ch 相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_last_of(value_type ch, size_type pos) const noexcept
  {
    for (auto i = size_ - 1; i >= pos; --i)
    {
      if (*(buffer_ + i) == ch)
        return i;
    }
    return npos;
  }
  
  // 从下标 pos 开始查找与字符串 s 其中一个字符相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_last_of(const_pointer s, size_type pos) const noexcept
  {
    const size_type len = char_traits::length(s);
    for (auto i = size_ - 1; i >= pos; --i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < len; ++j)
      {
        if (ch == *(s + j))
          return i;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始查找与字符串 s 前 count 个字符中相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_last_of(const_pointer s, size_type pos, size_type count) const noexcept
  {
    for (auto i = size_ - 1; i >= pos; --i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < count; ++j)
      {
        if (ch == *(s + j))
          return i;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始查找与字符串 str 字符中相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_last_of(const basic_string& str, size_type pos) const noexcept
  {
    for (auto i = size_ - 1; i >= pos; --i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < str.size_; ++j)
      {
        if (ch == str[j])
          return i;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始查找与 ch 字符不相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_last_not_of(value_type ch, size_type pos) const noexcept
  {
    for (auto i = size_ - 1; i >= pos; --i)
    {
      if (*(buffer_ + i) != ch)
        return i;
    }
    return npos;
  }
  
  // 从下标 pos 开始查找与字符串 s 的字符中不相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_last_not_of(const_pointer s, size_type pos) const noexcept
  {
    const size_type len = char_traits::length(s);
    for (auto i = size_ - 1; i >= pos; --i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < len; ++j)
      {
        if (ch != *(s + j))
          return i;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始查找与字符串 s 前 count 个字符中不相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_last_not_of(const_pointer s, size_type pos, size_type count) const noexcept
  {
    for (auto i = size_ - 1; i >= pos; --i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < count; ++j)
      {
        if (ch != *(s + j))
          return i;
      }
    }
    return npos;
  }
  
  // 从下标 pos 开始查找与字符串 str 字符中不相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  find_last_not_of(const basic_string& str, size_type pos) const noexcept
  {
    for (auto i = size_ - 1; i >= pos; --i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < str.size_; ++j)
      {
        if (ch != str[j])
          return i;
      }
    }
    return npos;
  }
  
  // 返回从下标 pos 开始字符为 ch 的元素出现的次数
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
  count(value_type ch, size_type pos) const noexcept
  {
    size_type n = 0;
    for (auto i = pos; i < size_; ++i)
    {
      if (*(buffer_ + i) == ch)
        ++n;
    }
    return n;
  }
  
  /*****************************************************************************************/
  // helper function
  
  // 尝试初始化一段 buffer，若分配失败则忽略，不会抛出异常
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
  try_init() noexcept
  {
    try
    {
      buffer_ = data_allocator::allocate(static_cast<size_type>(STRING_INIT_SIZE));
      size_ = 0;
      cap_ = 0;
    }
    catch (...)
    {
      buffer_ = nullptr;
      size_ = 0;
      cap_ = 0;
      // no throw
    }
  }
  
  // fill_init 函数
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
  fill_init(size_type n, value_type ch)
  {
    const auto init_size = mystl::max(static_cast<size_type>(STRING_INIT_SIZE), n + 1);
    buffer_ = data_allocator::allocate(init_size);
    char_traits::fill(buffer_, ch, n);
    size_ = n;
    cap_ = init_size;
  }
  
  // copy_init 函数
  template <class CharType, class CharTraits>
  template <class Iter>
  void basic_string<CharType, CharTraits>::
  copy_init(Iter first, Iter last, mystl::input_iterator_tag)
  {
    size_type n = mystl::distance(first, last);
    const auto init_size = mystl::max(static_cast<size_type>(STRING_INIT_SIZE), n + 1);
    try
    {
      buffer_ = data_allocator::allocate(init_size);
      size_ = n;
      cap_ = init_size;
    }
    catch (...)
    {
      buffer_ = nullptr;
      size_ = 0;
      cap_ = 0;
      throw;
    }
    for (; n > 0; --n, ++first)
      append(*first);
  }
  
  template <class CharType, class CharTraits>
  template <class Iter>
  void basic_string<CharType, CharTraits>::
  copy_init(Iter first, Iter last, mystl::forward_iterator_tag)
  {
    const size_type n = mystl::distance(first, last);
    const auto init_size = mystl::max(static_cast<size_type>(STRING_INIT_SIZE), n + 1);
    try
    {
      buffer_ = data_allocator::allocate(init_size);
      size_ = n;
      cap_ = init_size;
      mystl::uninitialized_copy(first, last, buffer_);
    }
    catch (...)
    {
      buffer_ = nullptr;
      size_ = 0;
      cap_ = 0;
      throw;
    }
  }
  
  // init_from 函数
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
  init_from(const_pointer src, size_type pos, size_type count)
  {
    const auto init_size = mystl::max(static_cast<size_type>(STRING_INIT_SIZE), count + 1);
    buffer_ = data_allocator::allocate(init_size);
    char_traits::copy(buffer_, src + pos, count);
    size_ = count;
    cap_ = init_size;
  }
  
  // destroy_buffer 函数
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
  destroy_buffer()
  {
    if (buffer_ != nullptr)
    {
      data_allocator::deallocate(buffer_, cap_);
      buffer_ = nullptr;
      size_ = 0;
      cap_ = 0;
    }
  }
  
  // to_raw_pointer 函数
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::const_pointer
  basic_string<CharType, CharTraits>::
  to_raw_pointer() const
  {
    *(buffer_ + size_) = value_type();
    return buffer_;
  }
  
  // reinsert 函数
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
  reinsert(size_type size)
  {
    auto new_buffer = data_allocator::allocate(size);
    try
    {
      char_traits::move(new_buffer, buffer_, size);
    }
    catch (...)
    {
      data_allocator::deallocate(new_buffer);
    }
    buffer_ = new_buffer;
    size_ = size;
    cap_ = size;
  }
  
  // append_range，末尾追加一段 [first, last) 内的字符
  template <class CharType, class CharTraits>
  template <class Iter>
  basic_string<CharType, CharTraits>&
  basic_string<CharType, CharTraits>::
  append_range(Iter first, Iter last)
  {
    const size_type n = mystl::distance(first, last);
    THROW_LENGTH_ERROR_IF(size_ > max_size() - n,
                          "basic_string<Char, Tratis>'s size too big");
    if (cap_ - size_ < n)
    {
      reallocate(n);
    }
    mystl::uninitialized_copy_n(first, n, buffer_ + size_);
    size_ += n;
    return *this;
  }
  
  template <class CharType, class CharTraits>
  int basic_string<CharType, CharTraits>::
  compare_cstr(const_pointer s1, size_type n1, const_pointer s2, size_type n2) const
  {
    auto rlen = mystl::min(n1, n2);
    auto res = char_traits::compare(s1, s2, rlen);
    if (res != 0) return res;
    if (n1 < n2) return -1;
    if (n1 > n2) return 1;
    return 0;
  }
  
  // 把 first 开始的 count1 个字符替换成 str 开始的 count2 个字符
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>& 
  basic_string<CharType, CharTraits>::
  replace_cstr(const_iterator first, size_type count1, const_pointer str, size_type count2)
  {
    if (static_cast<size_type>(cend() - first) < count1)
    {
      count1 = cend() - first;
    }
    if (count1 < count2)
    {
      const size_type add = count2 - count1;
      THROW_LENGTH_ERROR_IF(size_ > max_size() - add,
                            "basic_string<Char, Traits>'s size too big");
      if (size_ > cap_ - add)
      {
        reallocate(add);
      }
      pointer r = const_cast<pointer>(first);
      char_traits::move(r + count2, first + count1, end() - (first + count1));
      char_traits::copy(r, str, count2);
      size_ += add;
    }
    else
    {
      pointer r = const_cast<pointer>(first);
      char_traits::move(r + count2, first + count1, end() - (first + count1));
      char_traits::copy(r, str, count2);
      size_ -= (count1 - count2);
    }
    return *this;
  }
  
  // 把 first 开始的 count1 个字符替换成 count2 个 ch 字符
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>&
  basic_string<CharType, CharTraits>::
  replace_fill(const_iterator first, size_type count1, size_type count2, value_type ch)
  {
    if (static_cast<size_type>(cend() - first) < count1)
    {
      count1 = cend() - first;
    }
    if (count1 < count2)
    {
      const size_type add = count2 - count1;
      THROW_LENGTH_ERROR_IF(size_ > max_size() - add,
                            "basic_string<Char, Traits>'s size too big");
      if (size_ > cap_ - add)
      {
        reallocate(add);
      }
      pointer r = const_cast<pointer>(first);
      char_traits::move(r + count2, first + count1, end() - (first + count1));
      char_traits::fill(r, ch, count2);
      size_ += add;
    }
    else
    {
      pointer r = const_cast<pointer>(first);
      char_traits::move(r + count2, first + count1, end() - (first + count1));
      char_traits::fill(r, ch, count2);
      size_ -= (count1 - count2);
    }
    return *this;
  }
  
  // 把 [first, last) 的字符替换成 [first2, last2)
  template <class CharType, class CharTraits>
  template <class Iter>
  basic_string<CharType, CharTraits>&
  basic_string<CharType, CharTraits>::
  replace_copy(const_iterator first, const_iterator last, Iter first2, Iter last2)
  {
    size_type len1 = last - first;
    size_type len2 = last2 - first2;
    if (len1 < len2)
    {
      const size_type add = len2 - len1;
      THROW_LENGTH_ERROR_IF(size_ > max_size() - add,
                            "basic_string<Char, Traits>'s size too big");
      if (size_ > cap_ - add)
      {
        reallocate(add);
      }
      pointer r = const_cast<pointer>(first);
      char_traits::move(r + len2, first + len1, end() - (first + len1));
      char_traits::copy(r, first2, len2);
      size_ += add;
    }
    else
    {
      pointer r = const_cast<pointer>(first);
      char_traits::move(r + len2, first + len1, end() - (first + len1));
      char_traits::copy(r, first2, len2);
      size_ -= (len1 - len2);
    }
    return *this;
  }
  
  // reallocate 函数
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
  reallocate(size_type need)
  {
    const auto new_cap = mystl::max(cap_ + need, cap_ + (cap_ >> 1));
    auto new_buffer = data_allocator::allocate(new_cap);
    char_traits::move(new_buffer, buffer_, size_);
    data_allocator::deallocate(buffer_);
    buffer_ = new_buffer;
    cap_ = new_cap;
  }
  
  // reallocate_and_fill 函数
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::iterator
  basic_string<CharType, CharTraits>::
  reallocate_and_fill(iterator pos, size_type n, value_type ch)
  {
    const auto r = pos - buffer_;
    const auto old_cap = cap_;
    const auto new_cap = mystl::max(old_cap + n, old_cap + (old_cap >> 1));
    auto new_buffer = data_allocator::allocate(new_cap);
    auto e1 = char_traits::move(new_buffer, buffer_, r) + r;
    auto e2 = char_traits::fill(e1, ch, n) + n;
    char_traits::move(e2, buffer_ + r, size_ - r);
    data_allocator::deallocate(buffer_, old_cap);
    buffer_ = new_buffer;
    size_ += n;
    cap_ = new_cap;
    return buffer_ + r;
  }
  
  // reallocate_and_copy 函数
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::iterator
  basic_string<CharType, CharTraits>::
  reallocate_and_copy(iterator pos, const_iterator first, const_iterator last)
  {
    const auto r = pos - buffer_;
    const auto old_cap = cap_;
    const size_type n = mystl::distance(first, last);
    const auto new_cap = mystl::max(old_cap + n, old_cap + (old_cap >> 1));
    auto new_buffer = data_allocator::allocate(new_cap);
    auto e1 = char_traits::move(new_buffer, buffer_, r) + r;
    auto e2 = mystl::uninitialized_copy_n(first, n, e1) + n;
    char_traits::move(e2, buffer_ + r, size_ - r);
    data_allocator::deallocate(buffer_, old_cap);
    buffer_ = new_buffer;
    size_ += n;
    cap_ = new_cap;
    return buffer_ + r;
  }
  
  /*****************************************************************************************/
  // 重载全局操作符
  
  // 重载 operator+
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(const basic_string<CharType, CharTraits>& lhs, 
            const basic_string<CharType, CharTraits>& rhs)
  {
    basic_string<CharType, CharTraits> tmp(lhs);
    tmp.append(rhs);
    return tmp;
  }
  
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(const CharType* lhs, const basic_string<CharType, CharTraits>& rhs)
  {
    basic_string<CharType, CharTraits> tmp(lhs);
    tmp.append(rhs);
    return tmp;
  }
  
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(CharType ch, const basic_string<CharType, CharTraits>& rhs)
  {
    basic_string<CharType, CharTraits> tmp(1, ch);
    tmp.append(rhs);
    return tmp;
  }
  
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(const basic_string<CharType, CharTraits>& lhs, const CharType* rhs)
  {
    basic_string<CharType, CharTraits> tmp(lhs);
    tmp.append(rhs);
    return tmp;
  }
  
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(const basic_string<CharType, CharTraits>& lhs, CharType ch)
  {
    basic_string<CharType, CharTraits> tmp(lhs);
    tmp.append(1, ch);
    return tmp;
  }
  
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(basic_string<CharType, CharTraits>&& lhs,
            const basic_string<CharType, CharTraits>& rhs)
  {
    basic_string<CharType, CharTraits> tmp(mystl::move(lhs));
    tmp.append(rhs);
    return tmp;
  }
  
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(const basic_string<CharType, CharTraits>& lhs,
            basic_string<CharType, CharTraits>&& rhs)
  {
    basic_string<CharType, CharTraits> tmp(mystl::move(rhs));
    tmp.insert(tmp.begin(), lhs.begin(), lhs.end());
    return tmp;
  }
  
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(basic_string<CharType, CharTraits>&& lhs,
            basic_string<CharType, CharTraits>&& rhs)
  {
    basic_string<CharType, CharTraits> tmp(mystl::move(lhs));
    tmp.append(rhs);
    return tmp;
  }
  
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(const CharType* lhs, basic_string<CharType, CharTraits>&& rhs)
  {
    basic_string<CharType, CharTraits> tmp(mystl::move(rhs));
    tmp.insert(tmp.begin(), lhs, lhs + char_traits<CharType>::length(lhs));
    return tmp;
  }
  
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(CharType ch, basic_string<CharType, CharTraits>&& rhs)
  {
    basic_string<CharType, CharTraits> tmp(mystl::move(rhs));
    tmp.insert(tmp.begin(), ch);
    return tmp;
  }
  
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(basic_string<CharType, CharTraits>&& lhs, const CharType* rhs)
  {
    basic_string<CharType, CharTraits> tmp(mystl::move(lhs));
    tmp.append(rhs);
    return tmp;
  }
  
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(basic_string<CharType, CharTraits>&& lhs, CharType ch)
  {
    basic_string<CharType, CharTraits> tmp(mystl::move(lhs));
    tmp.append(1, ch);
    return tmp;
  }
  
  // 重载比较操作符
  template <class CharType, class CharTraits>
  bool operator==(const basic_string<CharType, CharTraits>& lhs,
                  const basic_string<CharType, CharTraits>& rhs)
  {
    return lhs.size() == rhs.size() && lhs.compare(rhs) == 0;
  }
  
  template <class CharType, class CharTraits>
  bool operator!=(const basic_string<CharType, CharTraits>& lhs,
                  const basic_string<CharType, CharTraits>& rhs)
  {
    return lhs.size() != rhs.size() || lhs.compare(rhs) != 0;
  }
  
  template <class CharType, class CharTraits>
  bool operator<(const basic_string<CharType, CharTraits>& lhs,
                 const basic_string<CharType, CharTraits>& rhs)
  {
    return lhs.compare(rhs) < 0;
  }
  
  template <class CharType, class CharTraits>
  bool operator<=(const basic_string<CharType, CharTraits>& lhs,
                  const basic_string<CharType, CharTraits>& rhs)
  {
    return lhs.compare(rhs) <= 0;
  }
  
  template <class CharType, class CharTraits>
  bool operator>(const basic_string<CharType, CharTraits>& lhs,
                 const basic_string<CharType, CharTraits>& rhs)
  {
    return lhs.compare(rhs) > 0;
  }
  
  template <class CharType, class CharTraits>
  bool operator>=(const basic_string<CharType, CharTraits>& lhs,
                  const basic_string<CharType, CharTraits>& rhs)
  {
    return lhs.compare(rhs) >= 0;
  }
  
  // 重载 mystl 的 swap
  template <class CharType, class CharTraits>
  void swap(basic_string<CharType, CharTraits>& lhs,
            basic_string<CharType, CharTraits>& rhs) noexcept
  {
    lhs.swap(rhs);
  }
  
  // 特化 mystl::hash
  template <class CharType, class CharTraits>
  struct hash<basic_string<CharType, CharTraits>>
  {
    size_t operator()(const basic_string<CharType, CharTraits>& str)
    {
      return bitwise_hash((const unsigned char*)str.c_str(),
                          str.size() * sizeof(CharType));
    }
  };
  
  } // namespace mystl
  #endif // !MYTINYSTL_BASIC_STRING_H_
  
  