探究C++中string類(lèi)的實(shí)現(xiàn)原理以及擴(kuò)展使用

更新時(shí)間：2015年12月17日 14:32:59 作者：passion_wu128

這篇文章主要介紹了C++中string類(lèi)的實(shí)現(xiàn)原理以及擴(kuò)展使用,從內(nèi)存分配角度進(jìn)行了深入探究,需要的朋友可以參考下

C++程序員編碼過(guò)程中經(jīng)常會(huì)使用string(wstring)類(lèi)，你是否思考過(guò)它的內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。比如這個(gè)類(lèi)的迭代器是如何實(shí)現(xiàn)的？對(duì)象占多少字節(jié)的內(nèi)存空間？?jī)?nèi)部有沒(méi)有虛函數(shù)？?jī)?nèi)存是如何分配的？構(gòu)造和析構(gòu)的成本有多大？筆者綜合這兩天閱讀的源代碼及個(gè)人理解簡(jiǎn)要介紹之，錯(cuò)誤的地方望讀者指出。

首先看看string和wstring類(lèi)的定義：

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

從這個(gè)定義可以看出string和wstring分別是模板類(lèi)basic_string對(duì)char和wchar_t的特化。

再看看basic_string類(lèi)的繼承關(guān)系（類(lèi)方法未列出）：

20151217142549352.png (411×442)

最頂層的類(lèi)是_Container_base，它也是STL容器的基類(lèi)，Debug下包含一個(gè)_Iterator_base*的成員，指向容器的最開(kāi)始的元素，這樣就能遍歷容器了，并定義了了兩個(gè)函數(shù)

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

Release下_Container_base只是一個(gè)空的類(lèi)。

_String_base類(lèi)沒(méi)有數(shù)據(jù)成員，只定義了異常處理的三個(gè)函數(shù)：

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

_String_val包含一個(gè)alloctor的對(duì)象，這個(gè)類(lèi)也非常簡(jiǎn)單，除了構(gòu)造函數(shù)沒(méi)有定義其它函數(shù)。
上面三個(gè)基類(lèi)都定義得很簡(jiǎn)單，而basic_string類(lèi)的實(shí)現(xiàn)非常復(fù)雜。不過(guò)它的設(shè)計(jì)和大多數(shù)標(biāo)準(zhǔn)庫(kù)一樣，把復(fù)雜的功能分成幾部分去實(shí)現(xiàn)，充分體現(xiàn)了模塊的低耦合。
迭代器有關(guān)的操作交給_String_iterator類(lèi)去實(shí)現(xiàn)，元素相關(guān)的操作交給char_traits類(lèi)去實(shí)現(xiàn)，內(nèi)存分配交給allocator類(lèi)去實(shí)現(xiàn)。

_String_iterator類(lèi)的繼承關(guān)系如下圖：

20151217142657254.png (472×431)

這個(gè)類(lèi)實(shí)現(xiàn)了迭代器的通用操作，比如：

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

有了迭代器的實(shí)現(xiàn)，就可以很方便的使用算法庫(kù)里面的函數(shù)了，比如將所有字符轉(zhuǎn)換為小寫(xiě)：

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

char_traits類(lèi)圖如下：

20151217142733106.png (554×330)

這個(gè)類(lèi)定義了字符的賦值，拷貝，比較等操作，如果有特殊需求也可以重新定義這個(gè)類(lèi)。

allocator類(lèi)圖如下：

20151217142752706.png (524×204)

這個(gè)類(lèi)使用new和delete完成內(nèi)存的分配與釋放等操作。你也可以定義自己的allocator，msdn上有介紹哪些方法是必須定義的。

再看看basic_string類(lèi)的數(shù)據(jù)成員：

_Mysize表示實(shí)際的元素個(gè)數(shù)，初始值為0；

_Myres表示當(dāng)前可以存儲(chǔ)的最大元素個(gè)數(shù)(超過(guò)這個(gè)大小就要重新分配內(nèi)存)，初始值是_BUF_SIZE-1；

_BUF_SIZE是一個(gè)enum類(lèi)型：

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

從這個(gè)定義可以得出，針對(duì)char和wchar_t它的值分別是16和8。
_Bxty是一個(gè)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); 
}

這個(gè)函數(shù)返回basic_string內(nèi)部的元素指針（c_str函數(shù)就是調(diào)用這個(gè)函數(shù)）。
所以當(dāng)元素個(gè)數(shù)小于_BUF_SIZE時(shí)不用分配內(nèi)存，直接使用_Buf數(shù)組，_Myptr返回_Buf。否則就要分配內(nèi)存了，_Myptr返回_Ptr。

不過(guò)內(nèi)存分配策略又是怎樣的呢？看下面這段代碼：

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。這段代碼看起來(lái)有點(diǎn)復(fù)雜，簡(jiǎn)單描述就是：最開(kāi)始_Myres每次增加_BUF_SIZE，當(dāng)值達(dá)到一定大小時(shí)每次增加一半。
針對(duì)char和wchar_t，每次分配內(nèi)存的臨界值分別是(超過(guò)這些值就要重新分配)：

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。。。

重新分配后都會(huì)先將舊的元素拷貝到新的內(nèi)存地址。所以當(dāng)處理一個(gè)長(zhǎng)度會(huì)不斷增長(zhǎng)而又大概知道最大大小時(shí)可以先調(diào)用reserve函數(shù)預(yù)分配內(nèi)存以提高效率。

string類(lèi)占多少字節(jié)的內(nèi)存空間呢？

_Container_base Debug下含有一個(gè)指針，4字節(jié)，Release下是空類(lèi)，0字節(jié)。_String_val類(lèi)含有一個(gè)allocator對(duì)象。string類(lèi)使用默認(rèn)的allocator類(lèi)，這個(gè)類(lèi)沒(méi)有數(shù)據(jù)成員，不過(guò)按字節(jié)對(duì)齊的原則，它占4字節(jié)。basic_string類(lèi)的成員加起來(lái)是24，所以總共是32字節(jié)（Debug）或28字節(jié)（Relase)。wstring也是32或28，至于原因文中已經(jīng)分析。

綜上所述：string和wstring類(lèi)借助_String_iterator實(shí)現(xiàn)迭代器操作，都占32(Debug)或28(Release)字節(jié)的內(nèi)存空間，沒(méi)有虛函數(shù)，構(gòu)造和析構(gòu)開(kāi)銷(xiāo)較低，內(nèi)存分配比較靈活。

擴(kuò)展string類(lèi)
在實(shí)際開(kāi)發(fā)過(guò)程中，C++string類(lèi)使用起來(lái)有很多不方便的地方，筆者根據(jù)根據(jù)這些不足簡(jiǎn)單的擴(kuò)展了這個(gè)類(lèi)，如增加與數(shù)字之間的相互轉(zhuǎn)化和格式化字符串。不足的地方望指正。讀者也可以根據(jù)自己需求繼續(xù)擴(kuò)展。

頭文件：exstring.h

/* 
Author: wuqiang 
Email: debugroot@126.com 
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" 
 
  //所有構(gòu)造函數(shù)的行為同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)轉(zhuǎn)化為exstring(exwstring) 
  INLINE _Myt(const _Mybase& base) 
    :_Mybase(base) 
  { 
 
  } 
#pragma endregion //constructor 
 
 
#pragma region "general operation" 
 
  //所有字符轉(zhuǎn)為大寫(xiě)，改變自身 
  _Myt& toUpper() 
  { 
    transform(begin(), end(), begin(), toupper); 
    return *this; 
  } 
 
  //所有字符轉(zhuǎn)為大寫(xiě)，不改變自身 
  _Myt toUpper() const 
  { 
    _Myt s; 
    transform(begin(), end(), s.begin(), toupper); 
    return s; 
  } 
 
  //所有字符轉(zhuǎn)為小寫(xiě)，改變自身 
  _Myt& toLower() 
  { 
    transform(begin(), end(), begin(), tolower); 
    return *this; 
  } 
 
  //所有字符轉(zhuǎn)為大寫(xiě)，不改變自身 
  _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個(gè)字符，count大于總長(zhǎng)度則返回整個(gè)字符串 
  _Myt left(size_type count) const 
  { 
    return substr( 0, count ); 
  } 
 
  //返回右邊count個(gè)字符，count大于總長(zhǎng)度則返回整個(gè)字符串 
  _Myt right(size_type count) const 
  { 
    return substr( _Mysize < count ? 0 : _Mysize - count ); 
  } 
 
  //忽略大小寫(xiě)判斷兩個(gè)字符串是否相等 
  int compareNoCase(const _Myt& rhs) const 
  { 
    return toLower().compare(rhs.toLower()); 
  } 
 
  //判斷字符串是否以制定字符串開(kāi)頭 
  bool beginWith(const _Myt& rhs) const 
  { 
    return find(rhs) == size_type(0); 
  } 
 
  //判斷字符串是否以制定字符串結(jié)尾 
  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" 
   
  //將字符串轉(zhuǎn)為數(shù)字 
  //base:進(jìn)制數(shù)?？梢詾?,10,16，如果其它值則強(qiáng)制為10。浮點(diǎn)數(shù)則忽略此參數(shù) 
  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); 
  } 
 
  //將整數(shù)轉(zhuǎn)化為字符串 
  //base:進(jìn)制數(shù)。可以為8,10,16，如果其它值則強(qiáng)制為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轉(zhuǎn)化為字符串 
  //f:格式化參數(shù)?？梢詾?f','e','E','g','G'。'f'為定點(diǎn)數(shù),'e'或'E'表示科學(xué)計(jì)數(shù)法 
  // 'g'或‘G'表示格式化為定點(diǎn)數(shù)或科學(xué)計(jì)數(shù)法，看哪一個(gè)表示方便。 
  //prec:小數(shù)點(diǎn)后的位數(shù)(定點(diǎn)數(shù)表示法)或總的有效位數(shù)(科學(xué)計(jì)數(shù)法) 
  static _Myt fromNumber ( float number, _Elem f = _Elem('g'), int prec = 6 ) 
  { 
    return fromNumber(static_cast<double>(number), f, prec); 
  } 
 
  //將double轉(zhuǎn)化為字符串，參數(shù)解釋同上 
  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格式化為字符串，參數(shù)解釋同sprintf 
  void format(const _Elem* szFormat, ...) 
  { 
    if(!szFormat) 
      return; 
    va_list argList; 
    va_start(argList, szFormat); 
    formatV(szFormat, argList); 
    va_end(argList); 
  } 
 
  //將szFormat格式化為字符串，參數(shù)解釋同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; 
}

輸出：

20151217143022071.png (461×314)