C++ string實現原理
C++程序員編碼過程中經常會使用string(wstring)類，你是否思考過它的內部實現細節。比如這個類的迭代器是如何實現的？對象占多少字節的內存空間？內部有沒有虛函數？內存是如何分配的？構造和析構的成本有多大？筆者綜合這兩天閱讀的源代碼及個人理解簡要介紹之，錯誤的地方望讀者指出。
首先看看string和wstring類的定義：
typedef basic_string, allocator > string;
typedef basic_string allocator > wstring;
從這個定義可以看出string和wstring分別是模板類basic_string對char和wchar_t的特化。
再看看basic_string類的繼承關系（類方法未列出）：
最頂層的類是_Container_base，它也是STL容器的基類，包含一個_Iterator_base*的成員，指向容器的最開始的元素，這樣就能遍歷容器了。
這個類其實只定義了兩個函數
void _Orphan_all() const; // orphan all iterators
void _Swap_all(_Container_base_secure&) const; // swaps all iterators
_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。
不過內存分配策略又是怎樣的呢，像vector那樣每次增加一倍？答案是否定的，看下面這段代碼：
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含有一個指針，4字節。_String_val類含有一個allocator對象。string類使用默認的allocator類，這個類沒有數據成員，不過按字節對齊的原則，它占4字節。basic_string類的成員加起來是24，所以總共是32字節。wstring也是32字節，至於原因文中已經分析。
綜上所述：string和wstring類借助_String_iterator實現迭代器操作，都占32字節的內存空間，沒有虛函數，構造和析構開銷較低，內存分配比較靈活。
實際使用string類時也有很多不方便的地方，筆者寫了一個擴展類，歡迎提出寶貴意見。
