探究C++中string类的实现原理以及扩展使用

C++程序员编码过程中经常会使用string(wstring)类，你是否思考过它的内部实现细节。比如这个类的迭代器是如何实现的？对象占多少字节的内存空间？内部有没有虚函数？内存是如何分配的？构造和析构的成本有多大？笔者综合这两天阅读的源代码及个人理解简要介绍之，错误的地方望读者指出。

首先看看string和wstring类的定义：

typedef basic_string<char, char_traits<char>, allocator<char> > string;
typedef basic_string<wchar_t, char_traits<wchar_t> allocator<wchar_t> > wstring;

从这个定义可以看出string和wstring分别是模板类basic_string对char和wchar_t的特化。

再看看basic_string类的继承关系（类方法未列出）：

最顶层的类是_Container_base，它也是STL容器的基类，Debug下包含一个_Iterator_base*的成员，指向容器的最开始的元素，这样就能遍历容器了，并定义了了两个函数

void _Orphan_all() const;  // orphan all iterators
void _Swap_all(_Container_base_secure&) const; // swaps all iterators

Release下_Container_base只是一个空的类。

_String_base类没有数据成员，只定义了异常处理的三个函数：

static void _Xlen();  // report a length_error
static void _Xran();  // report an out_of_range error
static void _Xinvarg();

_String_val包含一个alloctor的对象，这个类也非常简单，除了构造函数没有定义其它函数。
上面三个基类都定义得很简单，而basic_string类的实现非常复杂。不过它的设计和大多数标准库一样，把复杂的功能分成几部分去实现，充分体现了模块的低耦合。
迭代器有关的操作交给_String_iterator类去实现，元素相关的操作交给char_traits类去实现，内存分配交给allocator类去实现。

_String_iterator类的继承关系如下图：

这个类实现了迭代器的通用操作，比如：

reference operator*() const;
pointer operator->() const
_String_iterator & operator++()
_String_iterator operator++(int)
_String_iterator& operator--()
_String_iterator operator--(int)
_String_iterator& operator+=(difference_type _Off)
_String_iterator operator+(difference_type _Off) const
_String_iterator& operator-=(difference_type _Off)
_String_iterator operator-(difference_type _Off) const
difference_type operator-(const _Mybase& _Right) const
reference operator[](difference_type _Off) const

有了迭代器的实现，就可以很方便的使用算法库里面的函数了，比如将所有字符转换为小写：

string s("Hello String");
transform(s.begin(), s.end(), s.begin(), tolower);

char_traits类图如下：

这个类定义了字符的赋值，拷贝，比较等操作，如果有特殊需求也可以重新定义这个类。

allocator类图如下：

这个类使用new和delete完成内存的分配与释放等操作。你也可以定义自己的allocator，msdn上有介绍哪些方法是必须定义的。

再看看basic_string类的数据成员：

_Mysize表示实际的元素个数，初始值为0；

_Myres表示当前可以存储的最大元素个数(超过这个大小就要重新分配内存)，初始值是_BUF_SIZE-1；

_BUF_SIZE是一个enum类型：

enum
{  // length of internal buffer, [1, 16]
  _BUF_SIZE = 16 / sizeof (_Elem) < 1 ? 1: 16 / sizeof(_Elem)
};

从这个定义可以得出，针对char和wchar_t它的值分别是16和8。
_Bxty是一个union：

union _Bxty
{  // storage for small buffer or pointer to larger one
  _Elem _Buf[_BUF_SIZE];
  _Elem *_Ptr;
} _Bx;

为什么要那样定义_Bxty呢，看下面这段代码：

_Elem * _Myptr()
{  // determine current pointer to buffer for mutable string
  return (_BUF_SIZE <= _Myres ? _Bx._Ptr : _Bx._Buf);
}

 
这个函数返回basic_string内部的元素指针（c_str函数就是调用这个函数）。
所以当元素个数小于_BUF_SIZE时不用分配内存，直接使用_Buf数组，_Myptr返回_Buf。否则就要分配内存了，_Myptr返回_Ptr。

不过内存分配策略又是怎样的呢？看下面这段代码：

void _Copy(size_type _Newsize, size_type _Oldlen)
{  // copy _Oldlen elements to newly allocated buffer
  size_type _Newres = _Newsize | _ALLOC_MASK;
  if (max_size() < _Newres)
    _Newres = _Newsize; // undo roundup if too big
  else if (_Newres / 3 < _Myres / 2 && _Myres <= max_size() - _Myres / 2)
    _Newres = _Myres + _Myres / 2; // grow exponentially if possible
  //other code
}

_ALLOC_MASK的值是_BUF_SIZE-1。这段代码看起来有点复杂，简单描述就是：最开始_Myres每次增加_BUF_SIZE，当值达到一定大小时每次增加一半。
针对char和wchar_t，每次分配内存的临界值分别是(超过这些值就要重新分配)：

char：15，31，47，70，105，157，235，352，528，792，1188，1782。。。
wchar_t：7, 15, 23, 34, 51, 76, 114, 171, 256, 384, 576, 864, 1296, 1944。。。

重新分配后都会先将旧的元素拷贝到新的内存地址。所以当处理一个长度会不断增长而又大概知道最大大小时可以先调用reserve函数预分配内存以提高效率。

string类占多少字节的内存空间呢？

_Container_base Debug下含有一个指针，4字节，Release下是空类，0字节。_String_val类含有一个allocator对象。string类使用默认的allocator类，这个类没有数据成员，不过按字节对齐的原则，它占4字节。basic_string类的成员加起来是24，所以总共是32字节（Debug）或28字节（Relase)。wstring也是32或28，至于原因文中已经分析。

综上所述：string和wstring类借助_String_iterator实现迭代器操作，都占32(Debug)或28(Release)字节的内存空间，没有虚函数，构造和析构开销较低，内存分配比较灵活。

扩展string类
在实际开发过程中，C++string类使用起来有很多不方便的地方，笔者根据根据这些不足简单的扩展了这个类，如增加与数字之间的相互转化和格式化字符串。不足的地方望指正。读者也可以根据自己需求继续扩展。

头文件：exstring.h

/*
Author: wuqiang
Email: [e-mail]
Description:exstring is a subclass of basic_string.It is added some userful
operations,such as toUpper,toLower,toNumber,fromNumber,format,etc.It can also
convert between basic_string seamlessly,which is very important for compatibility.
And it is almostly a wrapper of some C++ standard library,so there should be no bugs.
If you find some,please let me known.It is totally free,you can use it in any way you desire.
*/
#pragma once

#include <string>
#include <stdarg.h>
#include <algorithm>
#include <sstream>
#include <iomanip>

using namespace std;

#ifndef INLINE
#define INLINE inline
#endif //INLINE

static ios_base::fmtflags BaseFlag(int base)
{
  return (base == 16) ? (ios_base::hex) :
    ( (base == 8) ? (ios_base::oct) : (ios_base::dec) );
}

template<class _Elem> struct ex_char_traits
{
};

template<> struct ex_char_traits<char>
{
  static INLINE int ct_vscprintf(const char* format, va_list argptr )
  {
    return _vscprintf(format, argptr);
  }
  static INLINE int ct_vstprintf_s(char* buffer, size_t numberOfElements,
    const char* format, va_list argptr)
  {
    return vsprintf_s(buffer, numberOfElements, format, argptr);
  }
};

template<> struct ex_char_traits<wchar_t>
{
  static INLINE int ct_vscprintf(const wchar_t* format, va_list argptr )
  {
    return _vscwprintf(format, argptr);
  }
  static INLINE int ct_vstprintf_s(wchar_t* buffer, size_t numberOfElements,
    const wchar_t* format, va_list argptr)
  {
    return vswprintf_s(buffer, numberOfElements, format, argptr);
  }
};

template<class _Elem, class _Traits, class _Ax, class Type>
Type ConvertToNumber(basic_stringstream<_Elem, _Traits, _Ax>& ss,
           Type t, int base)
{
  ss.setf(BaseFlag(base), ios_base::basefield);
  ss >> t;
  return t;
}

template<class _Elem, class _Traits, class _Ax>
float ConvertToNumber(basic_stringstream<_Elem, _Traits, _Ax>& ss,
           float t, int/*ignore base*/)
{
  ss >> t;
  return t;
}

template<class _Elem, class _Traits, class _Ax>
double ConvertToNumber(basic_stringstream<_Elem, _Traits, _Ax>& ss,
            double t, int/*ignore base*/)
{
  ss >> t;
  return t;
}

template<class _Elem, class _Traits, class _Ax, class _ExTraits>
class basic_exstring : public basic_string<_Elem, _Traits, _Ax>
{
public:
  typedef basic_exstring<_Elem, _Traits, _Ax, _ExTraits> _Myt;
  typedef basic_string<_Elem, _Traits, _Ax> _Mybase;

#pragma region "constructor"

  //所有构造函数的行为同basic_string

  explicit INLINE _Myt(const _Ax& al = _Ax())
    :_Mybase(al)
  {
  }
  INLINE _Myt(const _Myt& rhs)
    :_Mybase(rhs)
  {
  }
  INLINE _Myt(const _Myt& rhs, size_type pos, size_type n,const _Ax& al = _Ax())
    :_Mybase(rhs, pos, n, al)
  {
  }
  INLINE _Myt(const _Elem *s, size_type n, const _Ax& al = _Ax())
    :_Mybase(s, n, al)
  {
  }
  INLINE _Myt(const _Elem *s, const _Ax& al = _Ax())
    :_Mybase(s, al)
  {
  }
  INLINE _Myt(size_type n, _Elem c, const _Ax& al = _Ax())
    :_Mybase(n, c, al)
  {
  }
  INLINE _Myt(const_iterator first, const_iterator last,const _Ax& al = _Ax())
    :_Mybase(first, last, al)
  {
  }

  //string(wstring)转化为exstring(exwstring)
  INLINE _Myt(const _Mybase& base)
    :_Mybase(base)
  {

  }
#pragma endregion //constructor


#pragma region "general operation"

  //所有字符转为大写，改变自身
  _Myt& toUpper()
  {
    transform(begin(), end(), begin(), toupper);
    return *this;
  }

  //所有字符转为大写，不改变自身
  _Myt toUpper() const
  {
    _Myt s;
    transform(begin(), end(), s.begin(), toupper);
    return s;
  }

  //所有字符转为小写，改变自身
  _Myt& toLower()
  {
    transform(begin(), end(), begin(), tolower);
    return *this;
  }

  //所有字符转为大写，不改变自身
  _Myt toLower() const
  {
    _Myt s(_Mysize, _Elem());
    transform(begin(), end(), s.begin(), tolower);
    return s;
  }

  //将所有oldStr替换为newStr
  _Myt& replace(const _Myt& oldStr, const _Myt& newStr)
  {
    if (oldStr.empty())
      return *this;
    size_type index;
    while ( (index = find(oldStr)) != npos )
      _Mybase::replace(index, oldStr.size(), newStr);
    return *this;
  }

  //删除左边所有包含在target中的字符
  _Myt& trimLeft(const _Myt& target)
  {
    while (!empty() && (target.find(*begin()) != npos))
      erase(begin());
    return *this;
  }

  //删除右边所有包含在target中的字符
  _Myt& trimRight(const _Myt& target)
  {
    while (!empty() && target.find(*rbegin()) != npos)
      erase(--end());
    return *this;
  }

  //返回左边count个字符，count大于总长度则返回整个字符串
  _Myt left(size_type count) const
  {
    return substr( 0, count );
  }

  //返回右边count个字符，count大于总长度则返回整个字符串
  _Myt right(size_type count) const
  {
    return substr( _Mysize < count ? 0 : _Mysize - count );
  }

  //忽略大小写判断两个字符串是否相等
  int compareNoCase(const _Myt& rhs) const
  {
    return toLower().compare(rhs.toLower());
  }

  //判断字符串是否以制定字符串开头
  bool beginWith(const _Myt& rhs) const
  {
    return find(rhs) == size_type(0);
  }

  //判断字符串是否以制定字符串结尾
  bool endWith(const _Myt& rhs) const
  {
    if(rhs.size() > _Mysize)
      return false;
    return compare(_Mysize - rhs.size(), rhs.size(), rhs) == 0;
  }
#pragma endregion //general operation


#pragma region "convert between numbers"

  //将字符串转为数字
  //base:进制数。可以为8,10,16，如果其它值则强制为10。浮点数则忽略此参数
  template<typename T>
  T toNumber (int base = 10) const
  {
    T t = T();
    basic_stringstream<_Elem, _Traits, _Ax> ss(_Myptr());
    return ConvertToNumber<_Elem, _Traits, _Ax>(ss, t, base);
  }

  //将整数转化为字符串
  //base:进制数。可以为8,10,16，如果其它值则强制为10
  template<typename T>
  static _Myt fromNumber ( T number, int base = 10 )
  {
    basic_stringstream<_Elem, _Traits, _Ax> ss;
    ss.setf(BaseFlag(base), ios_base::basefield);
    ss << number;
    return ss.str();
  }

  //将float转化为字符串
  //f:格式化参数。可以为'f','e','E','g','G'。'f'为定点数,'e'或'E'表示科学计数法
  // 'g'或‘G'表示格式化为定点数或科学计数法，看哪一个表示方便。
  //prec:小数点后的位数(定点数表示法)或总的有效位数(科学计数法)
  static _Myt fromNumber ( float number, _Elem f = _Elem('g'), int prec = 6 )
  {
    return fromNumber(static_cast<double>(number), f, prec);
  }

  //将double转化为字符串，参数解释同上
  static _Myt fromNumber ( double number, _Elem f = _Elem('g'), int prec = 6 )
  {
    basic_stringstream<_Elem, _Traits, _Ax> ss;
    ss << setprecision(prec);
    if ( _Traits::eq(f, _Elem('f')) )
      ss << setiosflags(ios_base::fixed);
    else if ( _Traits::eq(f, _Elem('e')) || _Traits::eq(f, _Elem('E')) )
      ss << setiosflags(ios_base::scientific);
    ss << number;
    return ss.str();
  }
#pragma endregion //convert between numbers


#pragma region "format string"

  //将szFormat格式化为字符串，参数解释同sprintf
  void format(const _Elem* szFormat, ...)
  {
    if(!szFormat)
      return;
    va_list argList;
    va_start(argList, szFormat);
    formatV(szFormat, argList);
    va_end(argList);
  }

  //将szFormat格式化为字符串，参数解释同sprintf
  void formatV(const _Elem* szFormat, va_list argList)
  {
    if(!szFormat)
      return;
    int nLength = _ExTraits::ct_vscprintf(szFormat, argList);
    if(nLength < 0)
      return;
    resize(nLength);
    _ExTraits::ct_vstprintf_s(_Myptr(), nLength + 1, szFormat, argList);
    va_end(argList);
  }
#pragma endregion //format string
};

typedef basic_exstring<char, char_traits<char>,
  allocator<char>, ex_char_traits<char> > exstring;

typedef basic_exstring<wchar_t, char_traits<wchar_t>,
  allocator<wchar_t>, ex_char_traits<wchar_t> > exwstring;

使用举例：

#include <iostream>
#include <tchar.h>
#include "exstring.h"

#ifdef _UNICODE
typedef exwstring tstring;
#define tcout wcout
#else
typedef exstring tstring;
#define tcout cout
#endif //_UNICODE

int main(int argc, char* argv[])
{
  tstring s(_T("\t Hello ExString\r\n"));
  tcout << _T("result of triming left:") << s.trimLeft(_T("\t ")) << endl;
  tcout << _T("result of triming right:") << s.trimRight(_T("\r\n")) << endl;
  tcout << _T("result of compare") << s.compareNoCase(_T("hello exstring")) << endl;
  tcout << _T("result of converting to upper:") << s.toUpper() << endl;
  tcout << _T("result of converting to lower:") << s.toLower() << endl;

  tcout << _T("the left 5 chars:") << s.left(5) << endl;
  tcout << _T("the right 8 chars:") << s.right(8) << endl;
  tcout << _T("result of appending:") << s.append(_T(",exstring is practical")) << endl;
  tcout << _T("result of replacing:") << s.replace(_T("exstring"), _T("Exstring")) << endl;

  s.format(_T("sizeof(%s) is %d(0x%x)"), _T("exstring"), sizeof(exstring), sizeof(exstring));
  tcout << _T("result of formating:") << s << endl;

  tcout << tstring(_T("0xFF")).toNumber<int>(16) << endl;
  tcout << tstring(_T("-1")).toNumber<unsigned __int64>() << endl;
  tcout << tstring(_T("12.3456789")).toNumber<float>() << endl;

  tcout << tstring::fromNumber(255) << endl;
  tcout << _T("0x") << tstring::fromNumber(__int64(-1), 16).toUpper() << endl;
  tcout << tstring::fromNumber(12.3456789, _T('f'), 4) << endl;
  tcout << tstring::fromNumber(12.3456789, _T('E'), 4) << endl;

  return 0;
}

输出：