/**
 *  @file   ya_basic_string.h
 *  @brief  std::string の交替品.
 *  @author tenk* (Masashi Kitamura)
 *  @date   2008-2010
 *  @note
 *  - c_str() 向けの'\0'の付加は、c_str()時に行う。
 *    ただしresize()等では余分に1確保して、なるべく c_str()時にresize()を
 *    発生させないようにしている.
 *  - 極力、一度確保したメモリはサイズがあふれない限り使いまわす.
 *    確保メモリを縮めたい場合は、自前でswapするなりなんなり.
 *  - 一応、例外を投げるのがデフォルトだが、例外はstd::stringを使うため、
 *    本末転倒ぎみ. UNUSE_THROW が定義されてたらassertチェックに変更.
 *  - エラー時の例外やassertはvc8あたりを真似ているが、適当もあるので注意.
 *  - 元々、例外を投げない状態での利用も考えているため、範囲外指定は
 *    適当に辻褄をあわせる..が徹底していないので注意.
 *  - 基本的にコピーはTRAITS::copyで行っているが
 *    イテレータによる入力の場合は std::copy を使っている.
 *    ※マルチバイト系の処理をデフォのchar_traits仕様のままでは吸収できない
 *      ので気にする必要なかったかも.
 *  - Public Domain Software
 */
#ifndef YA_STRING_H
#define YA_STRING_H

#pragma once

#include <cstddef>
#include <cstring>
#include <iterator>
#include <algorithm>
#include <vector>
#ifndef assert
#include <cassert>
#endif
#ifndef UNUSE_THROW
#include <stdexcept>
#endif

#if defined __WATCOMC__ || defined __DMC__
#define YA_STRING_NO_MEMBER_TEMPLATES
#endif


// ============================================================================
// アロケータ
// ============================================================================

#ifndef YA_ALLOCATOR_INCLUDED
#define YA_ALLOCATOR_INCLUDED
template< typename T >
class ya_allocator {
public:
    typedef T               value_type;
    typedef T*              pointer;
    typedef const T*        const_pointer;
    typedef T&              reference;
    typedef const T&        const_reference;
    //typedef std::size_t   size_type;
    typedef unsigned        size_type;              // 64ビットCPU時もサイズは32ビット以内とする.
    typedef std::ptrdiff_t  difference_type;
    template <class U> struct rebind { typedef class ya_allocator<U> other; };

    ya_allocator() {}
    ya_allocator(const ya_allocator&) {}
  #ifndef YA_STRING_NO_MEMBER_TEMPLATES // メンバーテンプレートサポートの場合.
    template<class U> ya_allocator(const ya_allocator<U>&) {}
  #endif
    ~ya_allocator() throw() {}

    static pointer          address(reference       x) {return &x;}
    static const_pointer    address(const_reference x) {return &x;}

    static pointer allocate(size_type n)              {return (pointer)::operator new(sizeof(T)*n);}
    static pointer allocate(size_type n,const void *) {return allocate(n);}

    static void deallocate(pointer p)               {::operator delete(p);}
    static void deallocate(pointer p, size_type)    {deallocate(p);}

    static void construct(pointer p, const T& val)  {new((void*)p) T(val);}
    static void construct(pointer p)                {new((void*)p) T;}
    static void destroy(pointer p)                  {p->~T();}

    static size_type max_size() throw() {return ~0U; }

  #ifndef YA_STRING_NO_MEMBER_TEMPLATES // メンバーテンプレートサポートの場合.
    template<class U> bool operator ==(const ya_allocator<U>& r) const {return true;}
    template<class U> bool operator !=(const ya_allocator<U>& r) const {return !(*this == r);}
  #else
    bool operator ==(const ya_allocator& r) const {return true;}
    bool operator !=(const ya_allocator& r) const {return !(*this == r);}
  #endif
};
#endif  // YA_ALLOCATOR_INCLUDED



// ============================================================================
// 文字特性クラス.
// ============================================================================

#ifndef YA_CHAR_TRAITS_DEFINED
#define YA_CHAR_TRAITS_DEFINED

/// basic_v_stringで扱う文字に関する traits. ほぼ std::char_traitsと同様.
template<typename charT>
class ya_char_traits {
    //typedef ucharT                char_cmp_type;
    typedef charT                   char_cmp_type;

public:
    typedef charT                   char_type;
    typedef int                     int_type;
    typedef unsigned                pos_type;
    typedef int                     off_type;
    typedef unsigned                state_type;
    typedef typename std::size_t    size_type;

    static int_type         eof() { return -1; }
    static int_type         not_eof( const int_type& c ) { return c >= 0 ? c : 0; }
    static bool             eq( const char_type& a, const char_type& b ) {return (a == b); }

    static bool             eq_int_type( const int_type& a, const int_type& b ) { return (a == b); }
    static bool             lt( const char_type& a, const char_type& b ) { return char_cmp_type(a) < char_cmp_type(b); }
    static void             assign( char_type& d, const char_type& s ) { d = s; }

    static char_type        to_char_type( const int_type& c ) { return char_type(c); }
    static int_type         to_int_type( const char_type& c ) { return char_cmp_type(c); }

    static char_type*       assign( char_type* dst, std::size_t n, const char_type& c );
    static char_type*       copy( char_type* dst, const char_type* s, std::size_t n );
    static char_type*       move( char_type* dst, const char_type* s, std::size_t n );
    static size_type        length( const char_type *str );
    static int              compare( const char_type* a, const char_type* b, std::size_t n );
    static const char_type* find( const char_type* str, std::size_t n, const char_type& k );
};



template<typename charT>
charT* ya_char_traits<charT>::assign(charT* dst, std::size_t n, const charT& c)
{
    assert(dst != NULL);
    if (n) {
        charT *d = dst;
        charT *e = d + n;
        do {
            *d++ = c;
        } while (d != e);
    }
    return dst;
}


template<typename charT>
charT* ya_char_traits<charT>::copy(charT* dst, const charT* s, std::size_t n)
{
    assert(dst != NULL);
    assert(s   != NULL);
    if (n) {
        charT *d = dst;
        charT *e = d + n;
        do {
            *d++ = *s++;
        } while (d != e);
    }
    return dst;
}


template<typename charT>
charT* ya_char_traits<charT>::move(charT* dst, const charT* s, std::size_t n)
{
    assert(dst != NULL && s != NULL);
    if ((n != 0) & (dst != 0)) {
        charT *d = dst;
        if (d < s) {
            charT *e = d + n;
            do {
                *d++ = *s++;
            } while (d != e);
        } else if (d > s) {
            d += n;
            s += n;
            do {
                *--d = *--s;
            } while (d != dst);
        }
    }
    return dst;
}



template<typename charT>
std::size_t ya_char_traits<charT>::length(const charT *str)
{
    size_type   l  = 0;
    const charT *s = str;
    if (s) {
        while (*s != charT())
            ++s;
        l = s - str;
    }
    return l;
}



template<typename charT>
int     ya_char_traits<charT>::compare(
        const charT*    a,
        const charT*    b,
        std::size_t     n
){
    assert(a != NULL && b != NULL);
    const char_cmp_type *l = (const char_cmp_type *)a;
    const char_cmp_type *r = (const char_cmp_type *)b;
    const char_cmp_type *e = l + n;
    int c = 0;
    while (l != e && ((c = *l - *r++) == 0) && (*l != charT()))
        ++l;
    return c;
}



template<typename charT>
const charT* ya_char_traits<charT>::find(const charT* src, std::size_t n, const charT& key)
{
    if (n && src) {
        const char_cmp_type *s = (const char_cmp_type *)src;
        const char_cmp_type *e = s + n;
        const char_cmp_type  k = char_cmp_type(key);
        do {
            if (*s == k)
                return reinterpret_cast<const charT *>(s);
            ++s;
        } while (s != e);
    }
    return NULL;
}



// ---------------------------------------------------------
// char 専用の実装.
#if 1
/// char専用版のya_char_traits.
template<>
class ya_char_traits<char> {
    typedef unsigned char   char_cmp_type;

public:
    typedef char            char_type;
    typedef int             int_type;
    typedef unsigned        pos_type;
    typedef int             off_type;
    typedef unsigned        state_type;
    typedef std::size_t     size_type;

    static int_type         eof()                               { return -1; }
    static int_type         not_eof( int_type c )               { return c >= 0 ? c : 0; }
    static bool             eq( char_type a, char_type b )      { return (a == b); }
    static bool             eq_int_type(int_type a, int_type b) { return (a == b); }
    static bool             lt( char_type a, char_type b )      { return char_cmp_type(a) < char_cmp_type(b); }
    static void             assign( char_type& d, char_type s ) { d = s; }
    static char_type        to_char_type( int_type c )          { return char_type(c) ; }
    static int_type         to_int_type( char_type c )          { return char_cmp_type(c); }

    static size_type        length( const char_type *str )                            { return ::strlen(str); }
    static char_type*       assign( char_type* d, size_type n, char_type c )          { return (char_type*)::memset (d,c,n);}
    static char_type*       copy( char_type* d, const char_type* s, size_type n )     { return (char_type*)::memcpy (d,s,n);}
    static char_type*       move( char_type* d, const char_type* s, size_type n )     { return (char_type*)::memmove(d,s,n);}
    static int              compare(const char_type* a,const char_type* b,size_type n){ return ::memcmp(a,b,n); }
    static const char_type* find( const char_type* s, size_type n, char_type key )    { return (char_type*)::memchr(s,key,n);}
};
#endif

#endif      // YA_CHAR_TRAITS_DEFINED



// ============================================================================
// 文字列クラス.
// ============================================================================

template< typename C, class T=ya_char_traits<C>, class A=ya_allocator<C> >
class ya_basic_string : protected A {
    typedef ya_basic_string this_type;
    enum {  ALIGN_BIT       = 4 };
public:
    // 型
    typedef C                                       char_type;
    typedef typename A::size_type                   size_type;
    typedef typename A::difference_type             difference_type;
    typedef typename A::pointer                     pointer;
    typedef typename A::const_pointer               const_pointer;
    typedef typename A::reference                   reference;
    typedef typename A::const_reference             const_reference;
    typedef pointer                                 iterator;
    typedef const_pointer                           const_iterator;
    typedef std::reverse_iterator<iterator>         reverse_iterator;
    typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;
    typedef A                                       allocator_type;
    static const std::size_t                        npos;

    // コンストラクタデストラクタ
    ya_basic_string() : ptr_(0), size_(0), capa_(0) {}                                  ///< デフォルトコンストラクタ
    explicit ya_basic_string(std::size_t n) :ptr_(0),size_(0),capa_(0) {resize(n,C());} ///< n文字の空
    ya_basic_string(std::size_t n,char_type c):ptr_(0),size_(0),capa_(0) {resize(n,c);} ///< n文字のcで初期化
    ya_basic_string(const char_type* cstr);                                             ///< 文字列sの終わりまで
    ya_basic_string(const char_type* cary, std::size_t n);                              ///< 文字列sからn文字
    ya_basic_string(const ya_basic_string& str);                                        ///< コピーコンストラクタ
    ya_basic_string(const ya_basic_string& str, std::size_t pos, std::size_t n=npos);   ///< strのpos文字目からn文字
    // ~ya_basic_string() {}                                                            ///< デストラクタ

    // サイズ
    bool            empty()    const { return size_ == 0; }                             ///< 空ならtrue
    std::size_t     size()     const { return size_; }                                  ///< 文字数を返す
    std::size_t     length()   const { return size_; }                                  ///< 文字数を返す
    std::size_t     max_size() const { return capa_; }                                  ///< 確保可能な最大文字数を返す
    void            resize(std::size_t n, char_type c=C());                             ///< 長さをn文字に変え、増えたらcで埋める.
    std::size_t     capacity() const { return capa_; }                                  ///< 現在のバッファサイズ.
    void            reserve(std::size_t l);                                             ///< バッファサイズを変更.

    // アクセス
    const char_type*    c_str() const;                                                  ///< '\0'終端文字列のアドレスを返す.
    char_type*          data()            { return ptr_; }                              ///< 文字列データ本体をそのまま返す.
    const char_type*    data() const      { return ptr_; }                              ///< 文字列データ本体をそのまま返す.
    const_reference operator[](std::size_t n) const {assert(n<size_);return ptr_[n];}   ///< n文字目の文字を返す.
    reference       operator[](std::size_t n)       {assert(n<size_);return ptr_[n];}   ///< n文字目の文字を返す.
    const_reference at(std::size_t n) const {if (n>=size_) outOfRng();return ptr_[n];}  ///< n文字目の文字を返す. 範囲外なら例外発生.
    reference       at(std::size_t n)       {if (n>=size_) outOfRng();return ptr_[n];}  ///< n文字目の文字を返す. 範囲外なら例外発生.

    // イテレータ
    iterator               begin()        { return ptr_; }                              ///< 先頭へのイテレータを返す
    const_iterator         begin() const  { return ptr_; }                              ///< 先頭へのイテレータを返す
    iterator               end()          { return ptr_+size_; }                        ///< 終端(の次)を指すイテレータを返す
    const_iterator         end()   const  { return ptr_+size_; }                        ///< 終端(の次)を指すイテレータを返す
    reverse_iterator       rbegin()       { return reverse_iterator( end() );}          ///< 先頭を指す逆イテレータを返す
    const_reverse_iterator rbegin() const { return const_reverse_iterator(end());}      ///< 先頭を指す逆イテレータを返す
    reverse_iterator       rend()         { return reverse_iterator( begin() ); }       ///< 終端(の次)を指す逆イテレータを返す
    const_reverse_iterator rend()   const { return const_reverse_iterator(begin());}    ///< 終端(の次)を指す逆イテレータを返す

    const_iterator         cbegin() const { return ptr_; }                              ///< 先頭へのイテレータを返す
    const_iterator         cend()   const { return ptr_+size_; }                        ///< 終端(の次)を指すイテレータを返す
    const_reverse_iterator crbegin()const { return const_reverse_iterator(end());}      ///< 先頭を指す逆イテレータを返す
    const_reverse_iterator crend()  const { return const_reverse_iterator(begin());}    ///< 終端(の次)を指す逆イテレータを返す

    // 比較
    int compare(const ya_basic_string& str) const;
    int compare(std::size_t pos1, std::size_t n1, const ya_basic_string& str) const;
    int compare(std::size_t pos1, std::size_t n1, const ya_basic_string& str, std::size_t pos2, std::size_t n2) const;
    int compare(const char_type* s) const;
    int compare(const char_type* s, std::size_t n) const;
    int compare(std::size_t pos1, std::size_t n1, const char_type* cstr) const;
    int compare(std::size_t pos1, std::size_t n1, const char_type* cary, std::size_t n2) const;

    // 代入
    ya_basic_string& operator=(const ya_basic_string& str);
    ya_basic_string& operator=(const char_type* cstr);
    ya_basic_string& operator=(char_type c);

    ya_basic_string& assign(const ya_basic_string& str);
    ya_basic_string& assign(const ya_basic_string& str, std::size_t pos, std::size_t n=npos);
    ya_basic_string& assign(const char_type* cstr);
    ya_basic_string& assign(const char_type* cary, std::size_t n);
    ya_basic_string& assign(std::size_t n, char_type c);

    // 追加
    ya_basic_string& operator+=(const ya_basic_string& str);
    ya_basic_string& operator+=(const char_type* cstr);
    ya_basic_string& operator+=(char_type c);

    ya_basic_string& append(const ya_basic_string& str);
    ya_basic_string& append(const ya_basic_string& str, std::size_t pos, std::size_t n=npos);
    ya_basic_string& append(const char_type* cstr);
    ya_basic_string& append(const char_type* cary, std::size_t n);
    ya_basic_string& append(std::size_t n, char_type c);

    // 挿入
    ya_basic_string& insert(std::size_t pos1, const ya_basic_string& str, std::size_t pos2 = 0, std::size_t n = npos);
    ya_basic_string& insert(std::size_t pos, const char_type* cstr, std::size_t n);
    ya_basic_string& insert(std::size_t pos, const char_type* cary);
    ya_basic_string& insert(std::size_t pos, std::size_t n, char_type c);
    iterator         insert(iterator p, char_type c);
    iterator         insert(iterator p, std::size_t n, char_type c);

    // 削除
    ya_basic_string& erase() { destruct(ptr_, size_); size_ = 0; return *this; }
    ya_basic_string& erase(std::size_t pos, std::size_t n = npos);
    iterator         erase(iterator pos);
    iterator         erase(iterator first, iterator last);

    // 置換
    //ya_basic_string& replace(std::size_t pos1, std::size_t n1, const ya_basic_string& str2);
    ya_basic_string& replace(std::size_t pos1, std::size_t n1, const ya_basic_string& str2, std::size_t pos2 = 0, std::size_t n2 = npos);
    ya_basic_string& replace(std::size_t pos1, std::size_t n1, const char_type* cstr2);
    ya_basic_string& replace(std::size_t pos1, std::size_t n1, const char_type* cary2, std::size_t n2);
    ya_basic_string& replace(std::size_t pos1, std::size_t n1, std::size_t n2, char_type c2);
    ya_basic_string& replace(iterator fi, iterator li, const ya_basic_string& str);
    ya_basic_string& replace(iterator fi, iterator li, const char_type* cstr);
    ya_basic_string& replace(iterator fi, iterator li, const char_type* cary, std::size_t n);
    ya_basic_string& replace(iterator fi, iterator li, std::size_t n, char_type c);


    // 文字(列)の順検索
    std::size_t find(char_type c2) const;
    std::size_t find(char_type c2, std::size_t pos1) const;
    std::size_t find(const ya_basic_string& str2) const;
    std::size_t find(const ya_basic_string& str2, std::size_t pos1) const;
    std::size_t find(const char_type* cstr2) const;
    std::size_t find(const char_type* cstr2, std::size_t pos1) const;
    std::size_t find(const char_type* cary2, std::size_t pos1, std::size_t n2) const;

    // 文字(列)の逆順検索
    std::size_t rfind(char_type c) const;
    std::size_t rfind(char_type c, std::size_t pos) const;
    std::size_t rfind(const ya_basic_string& str) const;
    std::size_t rfind(const ya_basic_string& str, std::size_t pos) const;
    std::size_t rfind(const char_type* cstr) const;
    std::size_t rfind(const char_type* cstr, std::size_t pos) const;
    std::size_t rfind(const char_type* cstr, std::size_t pos, std::size_t n) const;

    // 指定文字の順検索
    std::size_t find_first_of(char_type c) const;
    std::size_t find_first_of(char_type c, std::size_t pos) const;
    std::size_t find_first_of(const ya_basic_string& str) const;
    std::size_t find_first_of(const ya_basic_string& str, std::size_t pos) const;
    std::size_t find_first_of(const char_type *cstr) const;
    std::size_t find_first_of(const char_type *cstr, std::size_t pos) const;
    std::size_t find_first_of(const char_type *cstr, std::size_t pos, std::size_t n) const;

    // 指定文字の逆順検索
    std::size_t find_last_of(char_type c) const;
    std::size_t find_last_of(char_type c, std::size_t pos) const;
    std::size_t find_last_of(const ya_basic_string& str) const;
    std::size_t find_last_of(const ya_basic_string& str, std::size_t pos) const;
    std::size_t find_last_of(const char_type *cstr) const;
    std::size_t find_last_of(const char_type *cstr, std::size_t pos) const;
    std::size_t find_last_of(const char_type *cstr, std::size_t pos, std::size_t n) const;

    // 指定文字以外の順検索
    std::size_t find_first_not_of(char_type c) const;
    std::size_t find_first_not_of(char_type c, std::size_t pos) const;
    std::size_t find_first_not_of(const ya_basic_string& str) const;
    std::size_t find_first_not_of(const ya_basic_string& str, std::size_t pos) const;
    std::size_t find_first_not_of(const char_type *cstr) const;
    std::size_t find_first_not_of(const char_type *cstr, std::size_t pos) const;
    std::size_t find_first_not_of(const char_type *cstr, std::size_t pos, std::size_t n) const;

    // 指定文字以外の逆順検索
    std::size_t find_last_not_of(char_type c) const;
    std::size_t find_last_not_of(char_type c, std::size_t pos) const;
    std::size_t find_last_not_of(const ya_basic_string& str) const;
    std::size_t find_last_not_of(const ya_basic_string& str, std::size_t pos) const;
    std::size_t find_last_not_of(const char_type *cstr) const;
    std::size_t find_last_not_of(const char_type *cstr, std::size_t pos) const;
    std::size_t find_last_not_of(const char_type *cstr, std::size_t pos, std::size_t n) const;

    // sにpos文字目からn文字コピー
    std::size_t copy(char_type* cary, std::size_t n, std::size_t pos = 0) const;

    // sとの入れ換え
    void swap(ya_basic_string& r) { std::swap(ptr_,r.ptr_); std::swap(size_,r.size_); std::swap(capa_,r.capa_); }

    // pos文字目からn文字を、新規文字列を作って返す.
    ya_basic_string substr(std::size_t pos = 0, std::size_t n = npos) const;

    // // アロケータを返す.
    A&          get_allocator() const { return *(A*)this; }

    // メンバーテンプレート関係.
  #ifndef YA_STRING_NO_MEMBER_TEMPLATES // メンバーテンプレートサポートの場合.
    template<class InpIte> ya_basic_string(InpIte first, InpIte last);                  ///< イテレータで初期化
    template<class InpIte> ya_basic_string& assign(InpIte first, InpIte last);
    template<class InpIte> ya_basic_string& append(InpIte first, InpIte last);
    template<typename InpIte> iterator insert(iterator p, InpIte first, InpIte last);
    template<class InpIte> ya_basic_string& replace(iterator fi1, iterator li1, InpIte fi2, InpIte li2);
  #else                                 // メンバーテンプレート未サポートの場合.
    ya_basic_string(const C* first, const C* last);                                     ///< イテレータで初期化
    ya_basic_string& assign(const C* first, const C* last);
    ya_basic_string& append(const C* first, const C* last);
    iterator         insert(iterator p, const C* first, const C* last);
    ya_basic_string& replace(iterator fi1, iterator li1, const C* fi2, const C* li2);
  #endif

private:
    pointer         ptr(std::size_t pos)        { return ptr_ + pos; }
    const_pointer   ptr(std::size_t pos) const  { return ptr_ + pos; }
    iterator        ite(std::size_t pos)        { return ptr_ + pos; }
    const_iterator  ite(std::size_t pos) const  { return ptr_ + pos; }

    void            check_pos(std::size_t& pos) const;
    void            check_pos_len(std::size_t& pos, std::size_t& len) const;
    void            check_pos(iterator& pos) const;
    void            check_range(iterator& first, iterator& last) const;

    static std::size_t  find_1(const char_type* cary1, std::size_t ofs1, std::size_t n1, char_type c2);
    static std::size_t  find_str(const char_type* cary1, std::size_t ofs1, std::size_t n1, const char_type* cary2, std::size_t n2);
    static std::size_t  rfind_1(const char_type* cary1, std::size_t n1, char_type c2);
    static std::size_t  rfind_str(const char_type* cary1, std::size_t n1, const char_type* cary2, std::size_t n2);
    static std::size_t  fnd_first_of(const char_type* cary1, std::size_t ofs1, std::size_t n1, const char_type* cary2, std::size_t n2);
    static std::size_t  fnd_last_of(const char_type* cary1, std::size_t n1, const char_type* cary2, std::size_t n2);
    static std::size_t  fnd_first_not_of(const char_type* cary1, std::size_t ofs1, std::size_t n1, char_type c2);
    static std::size_t  fnd_first_not_of(const char_type* cary1, std::size_t ofs1, std::size_t n1, const char_type* cary2, std::size_t n2);
    static std::size_t  fnd_last_not_of(const char_type* cary1, std::size_t n1, char_type c2);
    static std::size_t  fnd_last_not_of(const char_type* cary1, std::size_t n1, const char_type* cary2, std::size_t n2);

  #ifndef YA_STRING_NO_MEMBER_TEMPLATES // メンバーテンプレートサポートの場合.
    template<typename InpIte> inline
    void    copy_construct(C* d, InpIte s, InpIte e);
  #else                                 // メンバーテンプレート未サポートの場合.
    void    copy_construct(C* d, const C* s, const C* e);
  #endif

    void    set_construct(C* a, const C& t, std::size_t sz);
    void    destruct(C* a, std::size_t sz);

  #ifdef UNUSE_THROW
    void outOfRng() const { assert(0 && "out of range in ya_basic_string"); }
  #else
    void outOfRng() const { throw std::out_of_range("out of range in ya_basic_string"); }
  #endif

private:
    C*              ptr_;               ///< メモリ.
    size_type       size_;              ///< 個数.
    size_type       capa_;              ///< ptr_の領域サイズ.
};



//---------------------------------------------------------------------------------
// 実装
//---------------------------------------------------------------------------------

template< typename C, class T, class A >
const std::size_t       ya_basic_string<C,T,A>::npos = std::size_t(-1);


// -------------------------------
// private
// -------------------------------

/// アドレス dからsz個をtで埋める.
/// [private]
template< typename C, class T, class A > inline
void ya_basic_string<C,T,A>::set_construct(C* a, const C& t, std::size_t sz) {
    if (sz) {
        assert(a != 0);
        C* e = a + sz;
        do {
            A::construct(a, t);
        } while (++a != e);
    }
}



/// [s,e)をコピーコンストラクタを使って、アドレスdへコピー.
/// [private]
#ifndef YA_STRING_NO_MEMBER_TEMPLATES   // メンバーテンプレートサポートの場合.
template< typename C, class T, class A >
template<typename InpIte> inline
void ya_basic_string<C,T,A>::copy_construct(C* d, InpIte s, InpIte e)
#else
template< typename C, class T, class A >
void ya_basic_string<C,T,A>::copy_construct(C* d, const C* s, const C* e)
#endif
{
    assert(d != 0);
    while (s != e) {
        A::construct(d++, *s);
        ++s;
    }
}



/// アドレス aからsz個、デストラクタを実行.
/// [private]
template< typename C, class T, class A > inline
void ya_basic_string<C,T,A>::destruct(C* a, std::size_t sz) {
    // assert(sz > 0);
    if (sz) {
        assert(a != 0);
        C* e = a + sz;
        do {
            A::destroy(a);
        } while (++a != e);
    }
}




// -----------------------------------


/// 位置指定posが範囲外かどうかチェックし、範囲外ならstd::out_of_rangeを投げる.
/// [private]
template< typename C, class T, class A > inline
void ya_basic_string<C,T,A>::check_pos(std::size_t& pos) const {
    if (pos > size_) {
        outOfRng();
        pos = size_;
    }
}


/// 位置情報が範囲外なら例外を投げる. また、長さが長すぎれば調整する.
/// [private]
template< typename C, class T, class A > inline
void ya_basic_string<C,T,A>::check_pos_len(std::size_t& pos, std::size_t& len) const
{
    std::size_t l = size_;
    if (pos > l) {
        outOfRng();
        pos = l;
    }
    if (len > l - pos) {
        len = l - pos;
    }
}


/// 位置指定posが範囲外かどうかチェックし、範囲外ならstd::out_of_rangeを投げる.
/// [private]
template< typename C, class T, class A > inline
void ya_basic_string<C,T,A>::check_pos(typename ya_basic_string<C,T,A>::iterator& pos) const
{
    if (pos < begin() || end() < pos) {
        outOfRng();
        pos = const_cast< this_type* >(this)->end();
    }
}



/// 範囲指定[first,last)が範囲外かどうかチェック&調整.
/// [private]
template< typename C, class T, class A > inline
void ya_basic_string<C,T,A>::check_range(
        typename ya_basic_string<C,T,A>::iterator&  first,
        typename ya_basic_string<C,T,A>::iterator&  last
) const
{
  #ifdef UNUSE_THROW
    if (first < begin()) {
        outOfRng();
        first = const_cast< this_type* >(this)->begin();
    } else if (end() < first) {
        outOfRng();
        first = const_cast< this_type* >(this)->end();
    }
    if (last < begin()) {
        outOfRng();
        last = const_cast< this_type* >(this)->begin();
    } else if (end() < last) {
        outOfRng();
        last = const_cast< this_type* >(this)->end();
    }
  #else
    if (   first > last
        || first < begin() || end() < first
        || last  < begin() || end() < last
    ) {
        outOfRng();
    }
  #endif
}



// -------------------------------
// サイズ関係.

template< typename C, class T, class A >
void ya_basic_string<C,T,A>::reserve( std::size_t capa ) {
    if (capa > capa_) {
        std::size_t algn_msk    = (1 << ALIGN_BIT) - 1;
        capa    = (capa + algn_msk) & ~algn_msk;
        C*  a = A::allocate( capa );
        assert(a != NULL);
        if (a) {
            if (ptr_) {
                std::uninitialized_copy(ptr_, ptr_+capa, a);
                A::deallocate( ptr_ );
            }
            ptr_ = a;
        }
        capa_ = capa;
    }
}


/** 文字列の長さ(length)をn文字に変えて、大きくなった分はcで埋める.
 */
template< typename C, class T, class A >
void ya_basic_string<C,T,A>::resize( std::size_t sz, C c) {
    std::size_t size = size_;
    if (sz < size) {
        destruct(ptr_+sz, size - sz);
    } else if (sz > size) {
        if (sz > capa_) {
            reserve( sz+1 );    // どうせ確保するなら予め'\0'の分も確保.
        }
        set_construct(ptr_+size, c, sz - size);
    }
    size_ = sz;
}



// -------------------------------

/** '\0'終端文字列へのポインタを返す.
 *  ※ const関数にしてるが、実際には暗黙の\0を書き込む処理が入る.
 *    場合によってはresize()も行われる.
 */
template< typename C, class T, class A > inline
const C* ya_basic_string<C,T,A>::c_str() const {
    std::size_t      sz  = size_;
    if (sz >= capa_)
        const_cast< ya_basic_string* >(this)->reserve( sz + 1 );
    const_cast< ya_basic_string* >(this)->ptr_[sz] = char_type();
    return ptr_;
}



// -------------------------------
// コンストラクタ.

/** 文字列cstrをコピーするコンストラクタ.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>::ya_basic_string(const C* cstr)
    : ptr_(0), size_(0), capa_(0)
{
    std::size_t l = 0;
    if (cstr)
        l = T::length(cstr);
    if (l) {
        resize(l);
        T::copy(ptr_, cstr, l);
    }
}



/** caryからn文字コピーするコンストラクタ.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>::ya_basic_string(const C* cary, std::size_t n)
    : ptr_(0), size_(0), capa_(0)
{
    if (n) {
        resize(n);
        T::copy(ptr_, cary, n);
    }
}



/** コピーコンストラクタ.
 */
template< typename C, class T, class A > inline
ya_basic_string<C,T,A>::ya_basic_string(const ya_basic_string<C,T,A>& str)
    : ptr_(0), size_(0), capa_(0)
{
    std::size_t l = str.size_;
    if (l) {
        resize(l);
        T::copy( ptr_, str.ptr_, l);
    }
}


/** strのpos文字目からn文字をコピーするコンストラクタ.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>::ya_basic_string( const ya_basic_string<C,T,A>& str, std::size_t pos, std::size_t n )
    : ptr_(0), size_(0), capa_(0)
{
    str.check_pos_len(pos, n);
    if (n) {
        resize(n);
        T::copy( ptr_, str.ptr(pos), n);
    }
}



/** イテレータで初期化するコンストラクタ.
 */
#ifndef YA_STRING_NO_MEMBER_TEMPLATES   // メンバーテンプレートサポートの場合.
template< typename C, class T, class A >
template<class InpIte>
inline ya_basic_string<C,T,A>::ya_basic_string(InpIte first2, InpIte last2)
    : ptr_(0), size_(0), capa_(0)
{
    std::size_t l2 = std::distance(first2, last2);
    if (l2) {
        resize(l2);
        std::copy(first2, last2, ptr_);
    }
}
#else
template< typename C, class T, class A >
ya_basic_string<C,T,A>::ya_basic_string(const C* first2, const C* last2)
    : ptr_(0), size_(0), capa_(0)
{
    std::size_t l2 = last2 - first2;
    if (l2) {
        resize(l2);
        T::copy(ptr_, first2, l2 );
    }
}
#endif



// -------------------------------
// 代入

/** strを代入.
 */
template< typename C, class T, class A > inline
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::operator=(const ya_basic_string<C,T,A>& str) {
    return assign(str);
}


/** cstrを代入.
 */
template< typename C, class T, class A > inline
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::operator=(const C* cstr) {
    return assign(cstr);
}


/** 文字cを代入.
 */
template< typename C, class T, class A > inline
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::operator=(C c) {
    resize(1);
    ptr_[0] = c;
    return *this;
}


/** n文字のcを代入.
 */
template< typename C, class T, class A > inline
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::assign(std::size_t n, C c) {
    resize(n);
    if (n)
        T::assign(ptr_, n, c);
    return *this;
}



/** strを代入.
 */
template< typename C, class T, class A > inline
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::assign( const ya_basic_string<C,T,A>& str ) {
    if (this != &str)
        return assign(str.ptr_, str.size());
    return *this;
}


/** cstr を代入.
 */
template< typename C, class T, class A > inline
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::assign(const C* cstr) {
    return assign(cstr, T::length(cstr));
}


/** caryからのn文字を代入.
 */
template< typename C, class T, class A > inline
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::assign(const C* cary, std::size_t n) {
    resize(n);
    if (n) {
        assert(cary != NULL);
        // if (ptr_ != cary)
        T::copy( ptr_, cary, n);
    }
    return *this;
}


/** strから、pos文字目から、n文字を取り出して設定.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::assign( const ya_basic_string<C,T,A>& str, std::size_t  pos, std::size_t n ) {
    str.check_pos_len(pos, n);
    resize(n);
    if (n) {
        T::copy( ptr_, str.ptr(pos), n);
    }
    return *this;
}


/** イテレータからの入力を代入.
 */
#ifndef YA_STRING_NO_MEMBER_TEMPLATES   // メンバーテンプレートサポートの場合.
template< typename C, class T, class A >
template<class InpIte>
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::assign(InpIte first, InpIte last)
#else
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::assign(const C* first, const C* last)
#endif
{
    std::size_t l = std::distance(first, last);
    resize(l);
    if (l) {
        std::copy(first, last, ptr_);
    }
    return *this;
}



/** ary に pos文字目からの n文字をコピー.
 */
template< typename C, class T, class A >
std::size_t
ya_basic_string<C,T,A>::copy(C* ary, std::size_t n, std::size_t pos) const {
    if (ary == 0) {
        outOfRng();
        return 0;
    }
    if (n == 0)
        return 0;
    check_pos_len(pos, n);
    if (n)
        T::copy(ary, ptr(pos), n);
    return n;
}




/** pos文字目からn文字を、新規文字列を作って返す.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>
ya_basic_string<C,T,A>::substr(std::size_t pos, std::size_t n) const {
    check_pos_len(pos, n);
    return ya_basic_string<C,T,A>( ptr(pos), n );
}



// -------------------------------
// 比較.
// a.compare(b) aとbとの比較. 結果はstrcmp()と同じく、負ならa<b、0ならa==b, 正ならa>bを表す.


/** str2 と比較する.
 * @return      負,0,正(strcmp()に同じ)
 */
template< typename C, class T, class A >
int ya_basic_string<C,T,A>::compare(const ya_basic_string<C,T,A>& str2) const {
    std::size_t     l1 = size_;
    std::size_t     l2 = str2.size_;
    difference_type d  = difference_type(l1 - l2);
    if (d > 0)
        l1 = l2;
    int c = 0;
    if (l1 > 0)
        c = T::compare(ptr_, str2.ptr_, l1);
    if (c == 0)
        c = d;
    return c;
}



/* pos1文字目からn1文字を str2 と比較.
 * @return      負,0,正(strcmp()に同じ)
 */
template< typename C, class T, class A >
int ya_basic_string<C,T,A>::compare(std::size_t pos1, std::size_t n1, const ya_basic_string<C,T,A>& str2) const
{
    std::size_t l1 = size_;
    std::size_t l2 = str2.size_;
    if (pos1 > l1) {
        outOfRng();
        pos1 = l1;
    }
    if (n1 > l1 - pos1)
        n1 = l1 - pos1;
    difference_type d = difference_type (n1 - l2);
    if (d > 0)
        n1 = l2;
    int c = 0;
    if (n1 > 0)
        c = T::compare(ptr(pos1), str2.ptr_, n1);
    if (c == 0)
        c = d;
    return c;
}



/** pos1文字目からn1文字をstr2のpos2文字目からn2文字と比較.
 * @return      負,0,正(strcmp()に同じ)
 */
template< typename C, class T, class A >
int ya_basic_string<C,T,A>::compare(
        std::size_t                     pos1,
        std::size_t                     n1,
        const ya_basic_string<C,T,A>&   str2,
        std::size_t                     pos2,
        std::size_t                     n2
) const
{
    std::size_t l1 = size_;
    std::size_t l2 = str2.size_;
    if (pos1 > l1) {
        outOfRng();
        pos1 = l1;
    }
    if (n1 > l1 - pos1)
        n1 = l1 - pos1;
    if (pos2 > l2) {
        outOfRng();
        pos2 = l2;
    }
    if (n2 > l2 - pos2)
        n2 = l2 - pos2;
    difference_type d = difference_type(n1 - n2);
    if (d > 0)
        n1 = n2;
    int c = 0;
    if (n1 > 0)
        c = T::compare(ptr(pos1), str2.ptr(pos2), n1);
    if (c == 0)
        c = d;
    return c;
}



/** cstr2 との比較を行う.
 * @return      負,0,正(strcmp()に同じ)
 */
template< typename C, class T, class A >
int ya_basic_string<C,T,A>::compare(const C* cstr2) const
{
    std::size_t     l1 = size_;
    std::size_t     l2 = T::length(cstr2);
    difference_type d  = difference_type(l1 - l2);
    if (d > 0)
        l1 = l2;
    int c = 0;
    if (l1 > 0)
        c = T::compare(ptr_, cstr2, l1);
    if (c == 0)
        c = d;
    return c;
}



/** cary2 の n文字と比較.
 * @return      負,0,正(strcmp()に同じ)
 */
template< typename C, class T, class A >
int ya_basic_string<C,T,A>::compare(const C* cary2, std::size_t n2) const
{
    std::size_t     n1 = size_;
    difference_type d  = difference_type(n1 - n2);
    if (d > 0)
        n1 = n2;
    int c = 0;
    if (n1 > 0)
        c = T::compare(ptr_, cary2, n1);
    if (c == 0)
        c = d;
    return c;
}



/** pos1文字目からn1文字 と cstr2 を比較.
 * @return      負,0,正(strcmp()に同じ)
 */
template< typename C, class T, class A >
int ya_basic_string<C,T,A>::compare(std::size_t pos1, std::size_t n1, const C* cstr2) const
{
    std::size_t l1 = size_;
    std::size_t n2 = T::length(cstr2);
    if (pos1 > l1) {
        outOfRng();
        pos1 = l1;
    }
    if (n1 > l1 - pos1)
        n1 = l1 - pos1;
    difference_type d = difference_type(n1 - n2);
    if (d > 0)
        n1 = n2;
    int c = 0;
    if (n1 > 0)
        c = T::compare(ptr(pos1), cstr2, n1);
    if (c == 0)
        c = d;
    return c;
}



/** pos1文字目からn1文字と cary2 の n2文字と比較.
 * @return      負,0,正(strcmp()に同じ)
 */
template< typename C, class T, class A >
int ya_basic_string<C,T,A>::compare(std::size_t pos1, std::size_t n1, const C* cary2, std::size_t n2) const
{
    std::size_t l1 = size_;
    if (pos1 > l1) {
        outOfRng();
        pos1 = l1;
    }
    if (n1 > l1 - pos1)
        n1 = l1 - pos1;
    difference_type d = difference_type(n1 - n2);
    if (d > 0)
        n1 = n2;
    int c = 0;
    if (n1 > 0)
        c = T::compare(ptr(pos1), cary2, n1);
    if (c == 0)
        c = d;
    return c;
}



// -------------------------------
// 追加.

/** strを追加.
 */
template< typename C, class T, class A > inline
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::operator+=(const ya_basic_string<C,T,A>& str)
{
    return append(str);
}


/** cstrの追加.
 */
template< typename C, class T, class A > inline
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::operator+=(const C* cstr)
{
    return append(cstr);
}


/** 文字cの追加.
 */
template< typename C, class T, class A > inline
ya_basic_string<C,T,A>& ya_basic_string<C,T,A>::operator+=(C c) {
    if (size_+1 >= capa_) {
        reserve(size_+1);
    }
    ptr_[size_] = c;
    ++size_;
    return *this;
}


/** cをn文字追加.
 */
template< typename C, class T, class A > inline
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::append(std::size_t n, C c)
{
    if (n) {
        std::size_t l1 = size_;
        resize(l1 + n);
        T::assign(ptr(l1), n, c);
    }
    return *this;
}


/** cstrの追加.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::append(const C* cstr2)
{
    std::size_t l2 = T::length(cstr2);
    if (l2) {
        std::size_t l1 = size_;
        resize(l1 + l2);
        T::copy(ptr(l1), cstr2, l2);
    }
    return *this;
}


/** caryのn文字を追加.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::append(const C* cary2, std::size_t n2)
{
    if (n2) {
        std::size_t l1 = size_;
        resize(l1 + n2);
        T::copy(ptr(l1), cary2, n2);
    }
    return *this;
}


/** str2を追加.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::append( const ya_basic_string<C,T,A>& str2)
{
    std::size_t l2 = str2.size_;
    if (l2) {
        std::size_t l1 = size_;
        resize(l1+l2);
        T::copy(ptr(l1), str2.ptr_ , l2 );
    }
    return *this;
}


/** str2のpos2桁からn2文字を追加.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::append( const ya_basic_string<C,T,A>& str2, std::size_t pos2, std::size_t n2 )
{
    str2.check_pos_len(pos2, n2);
    if (n2) {
        std::size_t l1 = size_;
        resize(l1+n2);
        T::copy( ptr(l1), str2.ptr(pos2), n2 );
    }
    return *this;
}


/** イテレータで追加.
 */
#ifndef YA_STRING_NO_MEMBER_TEMPLATES   // メンバーテンプレートサポートの場合.
template< typename C, class T, class A >
template<class InpIte>
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::append(InpIte first, InpIte last)
#else
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::append(const C* first, const C* last)
#endif
{
    std::size_t l2 = std::distance(first, last);
    if (l2) {
        std::size_t     l1 = size_;
        resize(l1+l2);
        std::copy(first, last, ptr(l1));
    }
    return *this;
}



// -------------------------------
// 削除

/** pos文字目からn文字削除
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::erase(std::size_t pos, std::size_t n)
{
    assert(ptr_ != 0);
    std::size_t sz = size_;
    C*  ptr= ptr_;
    C*  b  = ptr + pos;
    if (n == npos || pos+n >= sz) {
        if (pos >= sz)
            return *this;   //ptr + sz;
        destruct(b, sz - pos);
        size_ = pos;
        return *this; //b;
    }
    C*  e = b + n;
    for (C* d = b; d != e; ++d) {
        *d = *(d+n);
    }
    destruct(e, n);
    size_ = sz - n;
    return *this;   // e;
}



/** pos文字目の1文字を削除
 */
template< typename C, class T, class A >
typename ya_basic_string<C,T,A>::iterator
ya_basic_string<C,T,A>::erase(typename ya_basic_string<C,T,A>::iterator pos)
{
    C*  b = begin();
    C*  e = end();
    if (pos <  b || e <= pos) {         // ※ pos=end()はエラーじゃない.
        assert(b <= pos && pos <= e);
        return e;
    }
    --e;
    for (C* p = pos; p != e; ++p)
        *p = *(p+1);
    A::destroy(e);
    --size_;
    return pos;
}



/** firstからlast直前までの文字を削除
 */
template< typename C, class T, class A >
typename ya_basic_string<C,T,A>::iterator
ya_basic_string<C,T,A>::erase(
        typename ya_basic_string<C,T,A>::iterator first,
        typename ya_basic_string<C,T,A>::iterator last)
{
    C*  b = begin();
    C*  e = end();
    if (first > last || first < b || last > e) {
        assert(first <= last && b <= first && last <= e);
        return e;
    }
    std::size_t l = last - first;
    if (l) {
        e -= l;
        for (C* p = first; p != e; ++p)
            *p = *(p+l);
        destruct(e, l);
        size_ -= l;
    }
    return first;
}




// -------------------------------
// 挿入

/** 文字cを1文字、pos1からに挿入.
 */
template< typename C, class T, class A >
typename ya_basic_string<C,T,A>::iterator
ya_basic_string<C,T,A>::insert(typename ya_basic_string<C,T,A>::iterator pos, C c)
{
    return insert(pos, 1U, c);
}


/** 文字c2をn2文字、pos1からに挿入.
 */
template< typename C, class T, class A >
typename ya_basic_string<C,T,A>::iterator
ya_basic_string<C,T,A>::insert(
        typename ya_basic_string<C,T,A>::iterator   pos,
        std::size_t                                 n,
        C                                           c)
{
    if (n == 0)
        return pos;

    C*  b = ptr_;
    if (size_ + n > capa_) {
        difference_type     diff = pos - b;
        reserve( size_ + n );
        b   = ptr_;
        pos = b + diff;
    }
    C*  e = b + size_;
    if (pos < b || pos > e) {
        outOfRng();
        return e;
    }
    size_ += n;
    for (C* p = e; --p >= pos;) {
        A::construct(p+n, *p);
        A::destroy(p);
    }
    e = pos + n;
    while (pos < e)
        A::construct(pos++, c);
    return pos;
}



/** [first,last) 範囲をposへ挿入.
 */
#ifndef YA_STRING_NO_MEMBER_TEMPLATES   // メンバーテンプレートサポートの場合.
template< typename C, class T, class A >
template <typename InpIte>
typename ya_basic_string<C,T,A>::iterator
ya_basic_string<C,T,A>::insert(typename ya_basic_string<C,T,A>::iterator pos, InpIte first, InpIte last)
#else
template< typename C, class T, class A >
typename ya_basic_string<C,T,A>::iterator
ya_basic_string<C,T,A>::insert(typename ya_basic_string<C,T,A>::iterator pos, const C* first, const C* last)
#endif
{
    std::size_t n = std::distance(first, last);
    if (n == 0)
        return pos;
    C*  b = ptr_;
    if (size_ + n > capa_) {
        difference_type     diff = pos - b;
        reserve( size_ + n );
        b   = ptr_;
        pos = b + diff;
    }
    C*  e = b + size_;
    if (pos < b || pos > e) {
        outOfRng();
        return e;
    }
    size_ += n;
    for (C* p = e; --p >= pos;) {
        A::construct(p+n, *p);
        A::destroy(p);
    }
    e = pos + n;
    while (pos < e) {
        A::construct(pos++, *first);
        ++first;
    }
    return pos;
}



/** str2のpos2からのn2文字を、pos1からに挿入.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::insert(
        std::size_t                     pos1,
        const ya_basic_string<C,T,A>&   str2,
        std::size_t                     pos2,
        std::size_t                     n2  )
{
    str2.check_pos_len(pos2, n2);
    if (n2) {
        check_pos(pos1);
        insert( ite(pos1), str2.ptr(pos2), str2.ptr(pos2+n2) );
    }
    return *this;
}


/** 文字c2をn2文字、pos1からに挿入.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::insert(std::size_t pos1, std::size_t n2, C c2)
{
    if (n2) {
        check_pos(pos1);
        insert(ite(pos1), n2, c2);
    }
    return *this;
}


/** cstr2を、pos1からに挿入.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::insert(std::size_t pos1, const C* cstr2)
{
    check_pos(pos1);
    std::size_t l2 = T::length(cstr2);
    if (l2) {
        insert(ite(pos1), &cstr2[0], &cstr2[l2]);
    } else {
        resize(pos1);
    }
    return *this;
}


/** cary2のn2文字を、pos1からに挿入.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::insert(std::size_t pos1, const C* cary2, std::size_t n2)
{
    check_pos(pos1);
    if (n2) {
        insert(ite(pos1), &cary2[0], &cary2[n2]);
    } else {
        resize(pos1);
    }
    return *this;
}



// -------------------------------
// 置換
#if 1
/** pos1からのn1文字を、str2のpos2からのn2文字に、置換.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::replace(
        std::size_t                     pos1,
        std::size_t                     n1  ,
        const ya_basic_string<C,T,A>&   str2,
        std::size_t                     pos2,
        std::size_t                     n2  )
{
    str2.check_pos_len(pos2, n2);
    check_pos_len(pos1, n1);
    erase( ite(pos1), ite(pos1+n1) );
    insert( ite(pos1), str2.ite(pos2), str2.ite(pos2+n2) );
    return *this;
}
#endif



/** pos1からのn1文字を、文字c2をn2文字に、置換.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::replace(std::size_t pos1, std::size_t n1, std::size_t n2, C c2)
{
    check_pos_len(pos1, n1);
    erase( ite(pos1), ite(pos1+n1) );
    insert(ite(pos1), n2, c2);
    return *this;
}


/** pos1からのn1文字を、cstr2に、置換.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::replace(std::size_t pos1, std::size_t n1, const C* cstr2)
{
    check_pos_len(pos1, n1);
    erase( ite(pos1), ite(pos1+n1) );
    std::size_t l2 = T::length(cstr2);
    insert(ite(pos1), &cstr2[0], &cstr2[l2]);
    return *this;
}


/** pos1からのn1文字を、cary2のn2文字に、置換.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::replace(std::size_t pos1, std::size_t n1, const C* cary2, std::size_t n2)
{
    check_pos_len(pos1, n1);
    erase( ite(pos1), ite(pos1+n1) );
    insert(ite(pos1), &cary2[0], &cary2[n2]);
    return *this;
}




/** [first1,last1)の範囲を、str2に、置換.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::replace(
    typename ya_basic_string<C,T,A>::iterator   first1,
    typename ya_basic_string<C,T,A>::iterator   last1,
    const ya_basic_string<C,T,A>&               str2)
{
    check_range(first1, last1);
    erase(first1, last1);
    insert( first1, str2.begin(), str2.end() );
    return *this;
}



/** [first1,last1)の範囲を、cstrに、置換.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::replace(
    typename ya_basic_string<C,T,A>::iterator   first1,
    typename ya_basic_string<C,T,A>::iterator   last1,
    const C*                                    cstr2)
{
    check_range(first1, last1);
    erase(first1, last1);
    std::size_t l2 = T::length(cstr2);
    insert( first1, &cstr2[0], &cstr2[l2] );
    return *this;
}



/** [first1,last1)の範囲を、caryのn文字に、置換.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::replace(
    typename ya_basic_string<C,T,A>::iterator   first1,
    typename ya_basic_string<C,T,A>::iterator   last1,
    const C*                                    cary2,
    std::size_t                                 n2  )
{
    check_range(first1, last1);
    erase(first1, last1);
    insert( first1, &cary2[0], &cary2[n2] );
    return *this;
}



/** [first1,last1)の範囲を、文字c2をn2文字に、置換.
 */
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::replace(
    typename ya_basic_string<C,T,A>::iterator   first1,
    typename ya_basic_string<C,T,A>::iterator   last1,
    std::size_t                                 n2,
    C                                           c2)
{
    check_range(first1, last1);
    erase(first1, last1);
    insert(first1, n2, c2);
    return *this;
}



/** [first1,last1)の範囲を、入力イテレータ[first2,last2)の文字列に、置換.
 */
#ifndef YA_STRING_NO_MEMBER_TEMPLATES   // メンバーテンプレートサポートの場合.
template< typename C, class T, class A >
template< typename InpIte >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::replace(
    typename ya_basic_string<C,T,A>::iterator   first1,
    typename ya_basic_string<C,T,A>::iterator   last1,
    InpIte                                      first2,
    InpIte                                      last2)
#else
template< typename C, class T, class A >
ya_basic_string<C,T,A>&
ya_basic_string<C,T,A>::replace(
    typename ya_basic_string<C,T,A>::iterator   first1,
    typename ya_basic_string<C,T,A>::iterator   last1,
    const C*                                    first2,
    const C*                                    last2)
#endif
{
    check_range(first1, last1);
    erase(first1,   last1);
    insert(first1, first2, last2);
    return *this;
}



// -------------------------------
// 順検索


/** 文字 c2の見つかった位置を、無ければnposを、返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find(C c2) const {
    return find_1(ptr_, 0, size_, c2);
}



/** pos1以降で 文字 c2 の見つかった位置を、無ければnposを、返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find(C c2, std::size_t pos1) const {
    std::size_t l1 = size_;
    if (pos1 > l1)
        pos1 = l1;
    l1 -= pos1;
    return find_1(ptr_, pos1, l1, c2);
}


/** str2を探索、見つかった位置を返す. 無ければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find(const ya_basic_string<C,T,A>& str2) const
{
    //x return find(str2.ptr_, 0, str2.size_);
    return find_str( ptr_, 0, size_, str2.ptr_, str2.size_ );
}


/** pos1 から str2を探索、見つかった位置を返す. 無ければnposを返す
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find(const ya_basic_string<C,T,A>& str2, std::size_t pos1) const
{
    return find(str2.ptr_, pos1, str2.size_);
}


/** cstr2 を探索、見つかった位置を返す. 無ければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find(const C* cstr2) const
{
    std::size_t l2 = cstr2 ? T::length(cstr2) : 0;
    //x return find(cstr2, 0, l2);
    return find_str(ptr_, 0, size_, cstr2, l2);
}


/** pos1 から cstr2 を探索、見つかった位置を返す. 無ければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find(const C* cstr2, std::size_t pos1) const
{
    std::size_t l2 = cstr2 ? T::length(cstr2) : 0;
    return find(cstr2, pos1, l2);
}


/** pos1 から cary2からのn文字を探索、見つかった位置を返す. 無ければnposを返す.
 */
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::find(const C* cary2, std::size_t pos1, std::size_t n2) const
{
    std::size_t     n1 = size_;
    if (pos1 > n1)
        return npos;    // pos1 = n1;
    n1 -= pos1;
    return find_str(ptr_, pos1, n1, cary2, n2);
}



/// pos1 から cary2からのn文字を探索、見つかった位置を返す. 無ければnposを返す.
/// [private]
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::find_str(const C* cary1, std::size_t ofs1, std::size_t n1, const C* cary2, std::size_t n2)
{
    if (ofs1 > n1)
        return npos;    // pos1 = n1;

    // 探す文字がなければ、0 (でよい?)
    if (n2 == 0 || cary2 == NULL)
        return ofs1;

    if (n1 == 0)    // n1 が0なら見つからないはず...
        return npos;

    if (n2 > n1)    // n2のほうが長けりゃ見つかるはずがない
        return npos;

    if (n2 == 1)    // 1文字だけだったら1字専用処理へ
        return find_1(cary1, ofs1, n1, cary2[0]);

    const C*    src1     = cary1+ofs1;
    const C*    cary1end = src1 + n1 - n2;
    const C*    key2     = cary2;
    const C*    key2end  = key2 + n2;
    C           k2       = *key2++;     // パターンの最初の

  RETRY:
    while (src1 <= cary1end) {
        int c = *src1++;
        if (c == k2) {
            const C* s1  = src1;
            const C* kp2 = key2;
            // if (k2 != key2end)       // keyE - key >= 1 なので、このif不要
            {
                do {
                    //x if (t == se) return npos;
                    c = *s1++;
                    c = c - *kp2++;
                    if (c)
                        goto RETRY;
                } while (kp2 != key2end);
            }
            return src1 - 1 - cary1;
        }
    }
    return npos;
}


/// 文字 c2の見つかった位置を、無ければnposを、返す
/// [private]
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::find_1(const C* cary1, std::size_t ofs1, std::size_t n1, C c2)
{
    if (n1 == 0 || cary1 == 0)
        return npos;
    const C*    p1 = T::find(cary1+ofs1, n1, c2);
    std::size_t n  = npos;
    if (p1)
        n = p1 - cary1;
    return n;
}



//-----------------------
// 逆順探索

/** 逆順で 文字 c2の見つかった位置を、無ければnposを、返す
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::rfind(C c2) const {
    return rfind_1(ptr_, size_, c2);
}



/** 逆順で pos1 から 文字 c2 の見つかった位置を、無ければnposを、返す
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::rfind(C c2, std::size_t pos1) const {
    if (pos1 < npos)
        ++pos1;
    std::size_t l1 = size_;
    if (l1 > pos1)
        l1 = pos1;
    return rfind_1(ptr_, l1, c2);
}



/** 逆順で str2 を探索、見つかった位置を返す. 無ければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::rfind(const ya_basic_string<C,T,A>& str2) const
{
    return rfind_str( ptr_, size_, str2.ptr_, str2.size_ );
}


/** 逆順で pos1 から str2を探索、見つかった位置を返す. 無ければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::rfind(const ya_basic_string<C,T,A>& str2, std::size_t pos1) const
{
    return rfind(str2.ptr_, pos1, str2.size_);
}


/** 逆順で cstr2 を探索、見つかった位置を返す. 無ければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::rfind(const C* cstr2) const
{
    std::size_t l2 = cstr2 ? T::length(cstr2) : 0;
    return rfind_str(ptr_, size_, cstr2, l2);
}


/** 逆順で pos1 から cstr2 を探索、見つかった位置を返す. 無ければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::rfind(const C* cstr2, std::size_t pos1) const
{
    std::size_t l2 = cstr2 ? T::length(cstr2) : 0;
    return rfind(cstr2, pos1, l2);
}


/** 逆順で pos1 から cary2からのn文字を探索、見つかった位置を返す. 無ければnposを返す.
 */
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::rfind(const C* cary2, std::size_t pos1, std::size_t n2) const
{
    if (pos1 < npos)
        ++pos1;
    std::size_t     n1 = size_;
    if (n1 > pos1)
        n1 = pos1;
    return rfind_str(ptr_, n1, cary2, n2);
}


/// 逆順で pos1 から cary2からのn文字を探索、見つかった位置を返す. 無ければnposを返す.
/// [private]
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::rfind_str(const C* cary1, std::size_t n1, const C* cary2, std::size_t n2)
{
    // 探す文字がなければ、0 (でよい?)
    if (n2 == 0 || cary2 == NULL)
        return 0;

    if (n1 == 0)    // n1 が0なら見つからないはず...
        return npos;

    if (n2 > n1)    // n2のほうが長けりゃ見つかるはずがない
        return npos;

    if (n2 == 1)    // 1文字だけだったら1字専用処理へ
        return rfind_1(cary1, n1, cary2[0]);

    //const C*  cary1end = cary1 + n1 - n2;
    const C*    cary1end = cary1 + n1; // - n2;
    const C*    src1     = cary1end;
    const C*    key2     = cary2;
    const C*    key2end  = key2 + n2;
    C           k2       = *key2++;     // パターンの最初の

  RETRY:
    while (--src1 >= cary1) {
        int c = *src1;
        if (c == k2) {
            const C* s1  = src1+1;
            const C* kp2 = key2;
            // if (k2 != key2end)       // keyE - key >= 1 なので、このif不要
            {
                do {
                    //x if (t == se) return npos;
                    c = *s1++;
                    c = c - *kp2++;
                    if (c)
                        goto RETRY;
                } while (kp2 != key2end);
            }
            return src1 - cary1;
        }
    }
    return npos;
}



/// 逆順探索で cary1からのn1文字中に 文字 c2があればその位置を、無ければnposを、返す.
/// [private]
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::rfind_1(const C* cary1, std::size_t n1, C c2)
{
    if (n1 == 0 || cary1 == 0)
        return npos;
    const C*    s1 = cary1 + n1;
    do {
        --s1;
        if (*s1 == c2)
            return s1 - cary1;
    } while (s1 >= cary1);
    return npos;
}



//------------------------
// 指定文字列中のいづれか一文字とマッチするものを探索.


/** 文字 cの見つかった位置を、無ければnposを、返す
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_first_of(C c) const {
    return find(c);
}


/** pos1以降で 文字 c2 の見つかった位置を、無ければnposを、返す
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_first_of(C c2, std::size_t pos1) const {
    return find(c2, pos1);
}



/** pos1文字目からのn1文字の中に、cary2中のn2文字の何れかの1文字があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_first_of(const C* cary2, std::size_t pos1, std::size_t n2) const
{
    std::size_t     n1 = size_;
    if (pos1 > n1)
        return npos;    // pos1 = n1;
    n1 -= pos1;
    return fnd_first_of(ptr_, pos1, n1, cary2, n2);
}



/** pos1文字目からのn1文字の中に、str2中の何れかの1文字があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_first_of(const ya_basic_string<C,T,A>& str2) const
{
    return fnd_first_of(ptr_, 0U, size_, str2.ptr_, str2.size_);
}



/** pos1文字目からのn1文字の中に、str2中の何れかの1文字があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_first_of(const ya_basic_string<C,T,A>& str2, std::size_t pos1) const
{
    return find_first_of(str2.ptr_, pos1, str2.size_);
}




/** pos1文字目からのn1文字の中に、cstr2中の何れかの1文字があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::find_first_of(const C* cstr2) const
{
    std::size_t     n2 = cstr2 ? T::length(cstr2) : 0;
    std::size_t     n1 = size_;
    return fnd_first_of(ptr_, 0, n1, cstr2, n2);
}



/** pos1文字目からのn1文字の中に、cstr2中の何れかの1文字があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::find_first_of(const C* cstr2, std::size_t pos1) const
{
    std::size_t     n2 = cstr2 ? T::length(cstr2) : 0;
    return find_first_of( cstr2, pos1, n2 );
}



/// cary1のofs1文字目からn1文字の中にn2文字のcary2中の何れかの文字があるか探索.
/// あればその位置を、なければnposを返す.
/// [private]
template<typename C, class T, class A>
std::size_t
ya_basic_string<C,T,A>::fnd_first_of(
        const C*    cary1,
        std::size_t ofs1,
        std::size_t n1,
        const C*    cary2,
        std::size_t n2)
{
    // 探す文字がなければ、npos (でよい?)
    if (n2 == 0 || cary2 == NULL)
        return npos;

    if (n1 == 0)    // n1 が0なら見つからないはず...
        return npos;

    if (n2 == 1)    // 1文字だけだったら1字専用処理へ
        return find_1(cary1, ofs1, n1, cary2[0]);

    const C*    s1 = cary1+ofs1;
    do {
        char_type c1 = *s1++;
        const C* p = T::find(cary2, n2, c1);
        if (p)  // 見つかったら帰る
            return  s1-1-cary1;
    } while (--n1);
    return npos;
}



//------------------------
// 指定文字列中のいづれか一文字とマッチするものを逆順探索.


/** 文字 cの見つかった位置を、無ければnposを、返す
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_last_of(C c) const {
    return rfind(c);
}


/** pos1以降で 文字 c2 の見つかった位置を、無ければnposを、返す
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_last_of(C c2, std::size_t pos1) const {
    return rfind(c2, pos1);
}


/** pos1文字目からのn1文字の中に、cary2中のn2文字の何れかの1文字があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_last_of(const C* cary2, std::size_t pos1, std::size_t n2) const
{
    if (pos1 < npos)
        ++pos1;
    std::size_t     n1 = size_;
    if (n1 > pos1)
        n1 = pos1;
    //n1 -= pos1;
    return fnd_last_of(ptr_, n1, cary2, n2);
}


/** pos1文字目からのn1文字の中に、str2中の何れかの1文字があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_last_of(const ya_basic_string<C,T,A>& str2) const
{
    return fnd_last_of(ptr_, size_, str2.ptr_, str2.size_);
}


/** pos1文字目からのn1文字の中に、str2中の何れかの1文字があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_last_of(const ya_basic_string<C,T,A>& str2, std::size_t pos1) const
{
    return find_last_of(str2.ptr_, pos1, str2.size_);
}



/** pos1文字目からのn1文字の中に、cstr2中の何れかの1文字があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::find_last_of(const C* cstr2) const
{
    std::size_t     n2 = cstr2 ? T::length(cstr2) : 0;
    return fnd_last_of(ptr_, size_, cstr2, n2);
}


/** pos1文字目からのn1文字の中に、cstr2中の何れかの1文字があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::find_last_of(const C* cstr2, std::size_t pos1) const
{
    std::size_t     n2 = cstr2 ? T::length(cstr2) : 0;
    return find_last_of( cstr2, pos1, n2 );
}


/// cary1のofs1文字目からn1文字の中にn2文字のcary2中の何れかの文字があるか探索.
/// あればその位置を、なければnposを返す.
/// [private]
template<typename C, class T, class A>
std::size_t
ya_basic_string<C,T,A>::fnd_last_of(
        const C*    cary1,
        std::size_t n1,
        const C*    cary2,
        std::size_t n2)
{
    // 探す文字がなければ、npos (でよい?)
    if (n2 == 0 || cary2 == NULL)
        return npos;

    if (n1 == 0)    // n1 が0なら見つからないはず...
        return npos;

    if (n2 == 1)    // 1文字だけだったら1字専用処理へ
        return rfind_1(cary1, n1, cary2[0]);

    const C*    s1 = cary1+n1;
    do {
        char_type c1 = *--s1;
        const C* p = T::find(cary2, n2, c1);
        if (p)  // 見つかったら帰る
            return  s1-cary1;
    } while (s1 > cary1);
    return npos;
}




//------------------------
// 指定文字列中のいづれの一文字ともマッチしないものを探索.


/** 文字 c以外の見つかった位置を、無ければnposを、返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_first_not_of(C c) const {
    return fnd_first_not_of(ptr_, 0, size_, c);
}


/** pos1以降で 文字 c2 以外の見つかった位置を、無ければnposを、返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_first_not_of(C c2, std::size_t pos1) const {
    std::size_t n1 = size_;
    if (pos1 > n1)
        return npos;    //x pos1 = l1;
    n1 -= npos;
    return fnd_first_not_of(ptr_, pos1, n1, c2);
}


/** pos1文字目からのn1文字の中に、cary2中のn2文字の何れの1文字以外があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_first_not_of(const C* cary2, std::size_t pos1, std::size_t n2) const
{
    std::size_t     n1 = size_;
    if (pos1 > n1)
        return npos;    // pos1 = n1;
    n1 -= pos1;
    return fnd_first_not_of(ptr_, pos1, n1, cary2, n2);
}


/** pos1文字目からのn1文字の中に、str2中の何れの1文字以外があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_first_not_of(const ya_basic_string<C,T,A>& str2) const
{
    return fnd_first_not_of(ptr_, 0U, size_, str2.ptr_, str2.size_);
}


/** pos1文字目からのn1文字の中に、str2中の何れの1文字以外があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_first_not_of(const ya_basic_string<C,T,A>& str2, std::size_t pos1) const
{
    return find_first_not_of(str2.ptr_, pos1, str2.size_);
}


/** pos1文字目からのn1文字の中に、cstr2中の何れの1文字以外があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::find_first_not_of(const C* cstr2) const
{
    std::size_t     n2 = cstr2 ? T::length(cstr2) : 0;
    std::size_t     n1 = size_;
    return fnd_first_not_of(ptr_, 0, n1, cstr2, n2);
}


/** pos1文字目からのn1文字の中に、cstr2中の何れの1文字以外があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::find_first_not_of(const C* cstr2, std::size_t pos1) const
{
    std::size_t     n2 = cstr2 ? T::length(cstr2) : 0;
    return find_first_not_of( cstr2, pos1, n2 );
}


/// cary1のofs1文字目からn1文字の中にn2文字のcary2中の何れかの文字があるか探索.
/// あればその位置を、なければnposを返す.
/// [private]
template<typename C, class T, class A>
std::size_t
ya_basic_string<C,T,A>::fnd_first_not_of(
        const C*    cary1,
        std::size_t ofs1,
        std::size_t n1,
        const C*    cary2,
        std::size_t n2)
{
    // 探す文字がなければ、npos (でよい?)
    if (n2 == 0 || cary2 == NULL)
        return ofs1;

    if (n1 == 0)    // n1 が0なら見つからないはず...
        return npos;

    if (n2 == 1)    // 1文字だけだったら1字専用処理へ
        return fnd_first_not_of(cary1, ofs1, n1, cary2[0]);

    const C*    s1 = cary1+ofs1;
    do {
        char_type c1 = *s1++;
        const C* p = T::find(cary2, n2, c1);
        if (p == 0) // 見つかったら帰る
            return  s1-1-cary1;
    } while (--n1);
    return npos;
}


/// 文字 c以外の見つかった位置を、無ければnposを、返す.
/// [private]
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::fnd_first_not_of(const C* cary1, std::size_t ofs1, std::size_t n1, C c2)
{
    if (cary1 == 0 || n1 == 0)
        return npos;
    const C* s = cary1 + ofs1;
    const C* e = s + n1;
    do {
        if (*s != c2)
            return s - cary1;
        ++s;
    } while (s != e);
    return npos;
}



//------------------------
// 指定文字列中のいづれの一文字ともマッチしないものを逆順探索.


/** 逆順で、文字 c以外の見つかった位置を、無ければnposを、返す
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_last_not_of(C c) const {
    return fnd_last_not_of(ptr_, size_, c);
}


/** 逆順で、pos1以前で 文字 c2 以外の見つかった位置を、無ければnposを、返す
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_last_not_of(C c2, std::size_t pos1) const {
    if (pos1 < npos)
        ++pos1;
    std::size_t     n1 = size_;
    if (n1 > pos1)
        n1 = pos1;
    return fnd_last_not_of(ptr_, n1, c2);
}


/** 逆順で、pos1文字目以前に、cary2中のn2文字の何れの1文字以外があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_last_not_of(const C* cary2, std::size_t pos1, std::size_t n2) const
{
    if (pos1 < npos)
        ++pos1;
    std::size_t     n1 = size_;
    if (n1 > pos1)
        n1 = pos1;
    return fnd_last_not_of(ptr_, n1, cary2, n2);
}


/** 逆順で、str2中の何れの1文字以外があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_last_not_of(const ya_basic_string<C,T,A>& str2) const
{
    return fnd_last_not_of(ptr_, size_, str2.ptr_, str2.size_);
}


/** 逆順で、str2中の何れの1文字以外があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A> inline
std::size_t     ya_basic_string<C,T,A>::find_last_not_of(const ya_basic_string<C,T,A>& str2, std::size_t pos1) const
{
    return find_last_not_of(str2.ptr_, pos1, str2.size_);
}


/** 逆順で、cstr2中の何れの1文字以外があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::find_last_not_of(const C* cstr2) const
{
    std::size_t     n2 = cstr2 ? T::length(cstr2) : 0;
    std::size_t     n1 = size_;
    return fnd_last_not_of(ptr_, n1, cstr2, n2);
}


/** 逆順で、cstr2中の何れの1文字以外があるか探索.
 *  あればその位置を、なければnposを返す.
 */
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::find_last_not_of(const C* cstr2, std::size_t pos1) const
{
    std::size_t     n2 = cstr2 ? T::length(cstr2) : 0;
    return find_last_not_of( cstr2, pos1, n2 );
}


/// 逆順で、cary1のn1文字の中にn2文字のcary2中の何れかの文字があるか探索.
/// あればその位置を、なければnposを返す.
/// [private]
template<typename C, class T, class A>
std::size_t
ya_basic_string<C,T,A>::fnd_last_not_of(
        const C*    cary1,
        std::size_t n1,
        const C*    cary2,
        std::size_t n2)
{
    // 探す文字がなければ、npos (でよい?)
    if (n2 == 0 || cary2 == NULL)
        return n1-1;    //npos;

    if (n1 == 0)    // n1 が0なら見つからないはず...
        return npos;

    if (n2 == 1)    // 1文字だけだったら1字専用処理へ
        return fnd_last_not_of(cary1, n1, cary2[0]);

    const C*        s1 = cary1+n1;
    do {
        char_type   c1 = *--s1;
        const C*    p  = T::find(cary2, n2, c1);
        if (p == 0) // 見つからなかったらok
            return  s1-cary1;
    } while (--n1);
    return npos;
}


/// 文字 c以外の見つかった位置を、無ければnposを、返す
/// [private]
template<typename C, class T, class A>
std::size_t     ya_basic_string<C,T,A>::fnd_last_not_of(const C* cary1, std::size_t n1, C c2)
{
    if (cary1 == 0 || n1 == 0)
        return npos;
    const C* s = cary1 + n1;
    do {
        --s;
        if (*s != c2)
            return s - cary1;
    } while (s != cary1);
    return npos;
}




//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
// 非メンバー関数

/** string + string
 */
template<typename C, class T, class A> inline
ya_basic_string<C,T,A> operator+(const ya_basic_string<C,T,A>& lhs, const ya_basic_string<C,T,A>& rhs) {
    return ya_basic_string<C,T,A>(lhs) += rhs;
}

/** C* + string
 */
template<typename C, class T, class A> inline
ya_basic_string<C,T,A> operator+(const C* lhs, const ya_basic_string<C,T,A>& rhs) {
    return ya_basic_string<C,T,A>(lhs) += rhs;
}

/** C + string
 */
template<typename C, class T, class A> inline
ya_basic_string<C,T,A> operator+(C lhs, const ya_basic_string<C,T,A>& rhs) {
    return ya_basic_string<C,T,A>(1, lhs) += rhs;
}

/** string + C*
 */
template<typename C, class T, class A> inline
ya_basic_string<C,T,A> operator+(const ya_basic_string<C,T,A>& lhs, const C* rhs) {
    return ya_basic_string<C,T,A>(lhs) += rhs;
}

/** string + C
 */
template<typename C, class T, class A> inline
ya_basic_string<C,T,A> operator+(const ya_basic_string<C,T,A>& lhs, C rhs) {
    return ya_basic_string<C,T,A>(lhs) += rhs;
}



/** string == string
 */
template<typename C, class T, class A> inline
bool operator==(const ya_basic_string<C,T,A>& lhs, const ya_basic_string<C,T,A>& rhs) {
    return lhs.compare(rhs) == 0;
}

/** string == C*
 */
template<typename C, class T, class A> inline
bool operator==(const ya_basic_string<C,T,A>& lhs, const C* rhs) {
    return lhs.compare(rhs) == 0;
}

/** C* == string
 */
template<typename C, class T, class A> inline
bool operator==(const C* lhs, const ya_basic_string<C,T,A>& rhs) {
    return rhs.compare(lhs) == 0;
}



/** string != string
 */
template<typename C, class T, class A> inline
bool operator!=(const ya_basic_string<C,T,A>& lhs, const ya_basic_string<C,T,A>& rhs) {
    return lhs.compare(rhs) != 0;
}

/** string != C*
 */
template<typename C, class T, class A> inline
bool operator!=(const ya_basic_string<C,T,A>& lhs, const C* rhs) {
    return lhs.compare(rhs) != 0;
}

/** C* != string
 */
template<typename C, class T, class A> inline
bool operator!=(const C* lhs, const ya_basic_string<C,T,A>& rhs) {
    return rhs.compare(lhs) != 0;
}



/** string < string
 */
template<typename C, class T, class A> inline
bool operator < (const ya_basic_string<C,T,A>& lhs, const ya_basic_string<C,T,A>& rhs) {
    return lhs.compare(rhs) < 0;
}

/** string < C*
 */
template<typename C, class T, class A> inline
bool operator < (const ya_basic_string<C,T,A>& lhs, const C* rhs) {
    return lhs.compare(rhs) < 0;
}

/** C* < string
 */
template<typename C, class T, class A> inline
bool operator < (const C* lhs, const ya_basic_string<C,T,A>& rhs) {
    return rhs.compare(lhs) > 0;
}



/** string > string
 */
template<typename C, class T, class A> inline
bool operator > (const ya_basic_string<C,T,A>& lhs, const ya_basic_string<C,T,A>& rhs) {
    return lhs.compare(rhs) > 0;
}

/** string > C*
 */
template<typename C, class T, class A> inline
bool operator > (const ya_basic_string<C,T,A>& lhs, const C* rhs) {
    return lhs.compare(rhs) > 0;
}

/** C* > string
 */
template<typename C, class T, class A> inline
bool operator > (const C* lhs, const ya_basic_string<C,T,A>& rhs) {
    return rhs.compare(lhs) < 0;
}


/** string <= string
 */
template<typename C, class T, class A> inline
bool operator <= (const ya_basic_string<C,T,A>& lhs, const ya_basic_string<C,T,A>& rhs) {
    return lhs.compare(rhs) <= 0;
}

/** string <= C*
 */
template<typename C, class T, class A> inline
bool operator <= (const ya_basic_string<C,T,A>& lhs, const C* rhs) {
    return lhs.compare(rhs) <= 0;
}

/** C* <= string
 */
template<typename C, class T, class A> inline
bool operator <= (const C* lhs, const ya_basic_string<C,T,A>& rhs) {
    return rhs.compare(lhs) >= 0;
}



/** string >= string
 */
template<typename C, class T, class A> inline
bool operator >= (const ya_basic_string<C,T,A>& lhs, const ya_basic_string<C,T,A>& rhs) {
    return lhs.compare(rhs) >= 0;
}

/** string >= C*
 */
template<typename C, class T, class A> inline
bool operator >= (const ya_basic_string<C,T,A>& lhs, const C* rhs) {
    return lhs.compare(rhs) >= 0;
}

/** C* >= string
 */
template<typename C, class T, class A> inline
bool operator >= (const C* lhs, const ya_basic_string<C,T,A>& rhs) {
    return rhs.compare(lhs) <= 0;
}


#ifndef __WATCOMC__
namespace std {
/** 交換.
 */
template<typename C, class T, class A> inline
void swap(ya_basic_string<C,T,A>& lhs, ya_basic_string<C,T,A>& rhs) {
    lhs.swap(rhs);
}
}
#else
/** 交換.
 */
template<typename C, class T, class A> inline
void swap(ya_basic_string<C,T,A>& lhs, ya_basic_string<C,T,A>& rhs) {
    lhs.swap(rhs);
}
#endif


#if 0   // iostream関係はターゲットで使わないので未実装.

/// ostream << ya_basic_string
template<typename C, class T, class A>
basic_ostream<C, T>& operator<<(basic_ostream<C, T>& os, const ya_basic_string<C,T,A>& str) {
    return os << str.c_str();
}

/// istream >> ya_basic_string
template<typename C, class T, class T2, class A>
basic_istream<C,T>& operator>>(basic_istream<C, T>& is, ya_basic_string<C,T2,A>& str);

/// istreamからの入力をya_basic_stringで受け取る. デフォルトで改行まで.
template<class charT, class traits, class Allocator>
std::basic_istream<charT, traits>&
getline(std::basic_istream<charT, traits>& is,
        ya_basic_string<charT, traits, Allocator>& str,
      charT delim = '\n');

#endif



typedef ya_basic_string< char   , ya_char_traits<char   >, ya_allocator<char>   >   ya_string;
typedef ya_basic_string< wchar_t, ya_char_traits<wchar_t>, ya_allocator<wchar_t> >  ya_wstring;



#endif      // YA_STRING_H