mstl_basic_string.hpp

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

    size_type find_last_of( const char_type* str, size_type pos = npos ) const
        {  return find_last_of( str, pos, traits_type::length(str) );  }
    size_type find_last_of( char_type c, size_type pos = npos ) const
        {  return rfind( c, pos );  }


    size_type find_first_not_of( const char_type* str,
                                 size_type pos, size_type count ) const;
    size_type find_first_not_of( char_type c, size_type pos = 0 ) const;
    size_type find_first_not_of( const char_type* str, size_type pos = 0 ) const
        {  return find_first_not_of( str, pos, traits_type::length(str) );  }
    size_type find_first_not_of( const self& str, size_type pos = 0 ) const
        {  return find_first_not_of( str.data(), pos, str.size() );  }


    size_type find_last_not_of( const char_type* str,
                                size_type pos, size_type count ) const;
    size_type find_last_not_of( char_type c, size_type pos = npos ) const;
    size_type find_last_not_of( const char_type* str, size_type pos = npos ) const
        {  return find_last_not_of( str, pos, traits_type::length(str) );  }
    size_type find_last_not_of( const self& str, size_type pos = npos ) const
        {  return find_last_not_of( str.data(), pos, str.size() );  }

protected:
    size_type string_bytes( size_type n );
    void alloc_data( size_type n );

    void dealloc_data()
    {
        if( m_data )
            m_alloc.deallocate( m_data, ++m_capacity );
    }

    void data_copy( size_type pos, const char_type* source, size_type count )
    {
        if( count > 0 )
            traits_type::copy( m_data + pos, source, count );
    }

    void data_move( size_type pos, const char_type* source, size_type count )
    {
        if( count > 0 )
            traits_type::move( m_data + pos, source, count );
    }

    void data_set( size_type pos, const char_type& c, size_type count )
    {
        if( count > 0 )
            traits_type::assign( m_data + pos, count, c );
    }

    size_type find_char( const char_type* str, const char_type& c,
                         size_type pos, size_type end ) const
    {
        if( pos < end )
        {
            const char_type* p = traits_type::find( str + pos, end - pos, c );
            if( p )
                return ( p - str );
        }
        return npos;
    }

};  //end class

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

template< typename CharT, typename Traits, typename Allocator >
inline typename basic_string<CharT, Traits, Allocator>::size_type
basic_string<CharT, Traits, Allocator>::string_bytes( size_type n )
{
    size_type n_bytes = n * sizeof( char_type );
    size_type i_bytes = 64;

    while( i_bytes < n_bytes )
        i_bytes *= 2;

    return i_bytes;
}
//-----------------------------------------------------------------------------

template< typename CharT, typename Traits, typename Allocator >
void basic_string<CharT, Traits, Allocator>::alloc_data( size_type n )
{
    if( n < 1 )
        init();
    else
    {
        if( n > max_size() )
            throw_length_error( "basic_string::alloc_data()" );
        size_type bytes = string_bytes( n + 1 );
        m_length = 0;
        m_capacity = bytes / sizeof( char_type );
        m_data = m_alloc.allocate( m_capacity );
        --m_capacity;
    }
}
//-----------------------------------------------------------------------------

template< typename CharT, typename Traits, typename Allocator >
basic_string<CharT, Traits, Allocator>::basic_string( const self& rhs,
                                                      size_type pos,
                                                      size_type count )
{
    if( pos > rhs.size() )
        throw_length_error( "basic_string::basic_string" );
    count = min( rhs.size() - pos, count );
    alloc_data( count );
    data_copy( 0, rhs.data() + pos, count );
    m_length = count;
}
//-----------------------------------------------------------------------------

template< typename CharT, typename Traits, typename Allocator >
basic_string<CharT, Traits, Allocator>&
basic_string<CharT, Traits, Allocator>::operator=( const self& rhs )
{
    if( m_data != rhs.m_data )
    {
        if( capacity() < rhs.size() )
        {
            self temp( rhs, 0, rhs.size() );
            swap( temp );
        }
        else
            data_copy( 0, rhs.data(), rhs.size() );

        m_length = rhs.size();
    }
    return *this;
}
//-----------------------------------------------------------------------------

//replace:1
template< typename CharT, typename Traits, typename Allocator >
inline basic_string<CharT, Traits, Allocator>&
basic_string<CharT, Traits, Allocator>::replace( size_type pos,
                                                 size_type before_count,
                                                 const self& str,
                                                 size_type str_pos,
                                                 size_type after_count )
{
    const size_type str_len = str.size();

    if( pos == 0 && before_count >= size()
        && str_pos == 0 && after_count >= str_len )
        return operator=( str );

    if( str_pos > str_len )
        throw_out_of_range( "basic_string::replace()" );

    if( after_count > str_len - str_pos )
        after_count = str_len - str_pos;

    return replace( pos, before_count, str.data() + str_pos, after_count );
}
//-----------------------------------------------------------------------------

//replace:2
template< typename CharT, typename Traits, typename Allocator >
basic_string<CharT, Traits, Allocator>&
basic_string<CharT, Traits, Allocator>::replace( size_type pos,
                                                 size_type before_count,
                                                 const char_type* str,
                                                 size_type after_count )
{
    const size_type old_len = size();
    if( pos > old_len )
        throw_out_of_range( "basic_string::replace()" );

    if( before_count > old_len - pos )
        before_count = old_len - pos;

    if( old_len - before_count > max_size() - after_count )
        throw_length_error( "basic_string::replace()" );
    size_type new_len = old_len - before_count + after_count;

    if( capacity() < new_len )
    {
    	self temp( new_len );
        temp.data_copy( 0, data(), pos );
        temp.data_copy( pos + after_count, data() + pos + before_count,
                        old_len - (pos + before_count) );
        temp.data_copy( pos, str, after_count );
        swap( temp );
    }
    else
    {
    	data_move( pos + after_count, data() + pos + before_count,
    	           old_len - (pos + before_count) );
    	data_copy( pos, str, after_count );
    }

    m_length = new_len;
    return *this;
}
//-----------------------------------------------------------------------------

//replace:3
template< typename CharT, typename Traits, typename Allocator >
basic_string<CharT, Traits, Allocator>&
basic_string<CharT, Traits, Allocator>::replace( size_type pos,
                                                 size_type before_count,
                                                 size_type after_count,
                                                 char_type c )
{
    const size_type old_len = size();
    if( pos > old_len )
        throw_out_of_range( "basic_string::replace()" );

    if( before_count > old_len - pos )
        before_count = old_len - pos;

    //检查留下的数据长度和新的数据长度的和是否会超过max_size()
    if( old_len - before_count > max_size() - after_count )
        throw_length_error( "basic_string::replace()" );
    size_type new_len = old_len - before_count + after_count;

    if( capacity() < new_len )
    {
        self temp( new_len );
        temp.data_copy( 0, data(), pos );
        temp.data_copy( pos + after_count, data() + pos + before_count,
                        old_len - (pos + before_count) );
        temp.data_set( pos, c, after_count );
        swap( temp );
    }
    else
    {
        data_move( pos + after_count, data() + pos + before_count,
                   old_len - (pos + before_count) );
        data_set( pos, c, after_count );
    }

    m_length = new_len;
    return *this;
}
//-----------------------------------------------------------------------------

template< typename CharT, typename Traits, typename Allocator >
template< typename InputIterator >
basic_string<CharT, Traits, Allocator>&
basic_string<CharT, Traits, Allocator>::replace( iterator first_pos,
                                                 iterator last_pos,
                                                 InputIterator first,
                                                 InputIterator last )
{
    if( first == last )
        return *this;

    const size_type old_len = size();
    size_type pos = first_pos - begin();
    if( pos > old_len )
        throw_out_of_range( "basic_string::replace()" );

    size_type before_count = last_pos - first_pos;
    size_type after_count = distance( first, last );

    if( before_count > old_len - pos )
        before_count = old_len - pos;

    if( old_len - before_count > max_size() - after_count )
        throw_length_error( "basic_string::replace()" );
    size_type new_len = old_len - before_count + after_count;

    if( capacity() < new_len )
    {
        self temp( new_len );
        temp.data_copy( 0, data(), pos );
        temp.data_copy( pos + after_count, data() + pos + before_count,
                        old_len - (pos + before_count) );
        for( ; after_count > 0; ++first,++pos,--after_count )
            traits_type::assign( *(m_data + pos), *first );
        swap( temp );
    }
    else
    {
        data_move( pos + after_count, data() + pos + before_count,
                   old_len - (pos + before_count) );
        for( ; after_count > 0; ++first,++pos,--after_count )
            traits_type::assign( *(m_data + pos), *first );
    }

    m_length = new_len;
    return *this;
}
//-----------------------------------------------------------------------------

template< typename CharT, typename Traits, typename Allocator >
inline
int basic_string<CharT, Traits, Allocator>::compare( const self& str ) const
{
    int result = traits_type::compare( data(), str.data(),
                                       min( size(), str.size() ) );

    if( result == 0 )  //如果等长的部分相等，则比较哪个字符串更长
        result = size() - str.size();

    return result;
}
//-----------------------------------------------------------------------------

template< typename CharT, typename Traits, typename Allocator >
inline
int basic_string<CharT, Traits, Allocator>::compare( const char_type* str ) const
{
    size_type str_len = traits_type::length( str );

    int result = traits_type::compare( data(), str, min(size(), str_len) );

    if( result == 0 )
        result = size() - str_len;

    return result;
}
//-----------------------------------------------------------------------------

template< typename CharT, typename Traits, typename Allocator >
int basic_string<CharT, Traits, Allocator>::compare( size_type pos,
                                                     size_type count,
                                                     const self& str,
                                                     size_type str_pos,
                                                     size_type str_count ) const
{
    if( pos > size() || str_pos > str.size() )
        throw_out_of_range( "basic_string::compare()" );

    size_type str_len = min( str.size() - str_pos, str_count );
    size_type this_len = min( size() - pos, count );

    int result = traits_type::compare( data() + pos, str.data() + str_pos,
                                       min(str_len, this_len) );

    if( result == 0 )
        result = this_len - str_len;

    return result;
}
//-----------------------------------------------------------------------------

template< typename CharT, typename Traits, typename Allocator >
int basic_string<CharT, Traits, Allocator>::compare( size_type pos,
                                                     size_type count,
                                                     const char_type* str,
                                                     size_type str_count ) const
{
    if( pos > size() )
        throw_out_of_range( "basic_string::compare()" );

    size_type str_len = min( traits_type::length(str), str_count );
    size_type this_len = min( size() - pos, count );

    int result = traits_type::compare( data() + pos, str,
                                       min(str_len, this_len) );

    if( result == 0 )
        result = this_len - str_len;

    return result;
}
//-----------------------------------------------------------------------------

template< typename CharT, typename Traits, typename Allocator >
typename basic_string<CharT, Traits, Allocator>::size_type
basic_string<CharT, Traits, Allocator>::find( const char_type* str,
                                              size_type pos,
                                              size_type count ) const
{
    for( ; pos + count <= size(); ++pos )
    {
        if( traits_type::eq( data()[pos], *str )
            && traits_type::compare( data() + pos, str, count ) == 0 )
            return pos;
    }