C++ string 的兩種實做

本文內容採用創用 CC 姓名標示-非商業性-相同方式分享 3.0 台灣 授權條款授權.

---

最近在玩一些比較老舊的程式碼的時候，發現 g++ 5 前後的 sizeof(std::string) 的大小有相當大的差異，在 64-bit 平台下，有 g++ 5 之前是 8 bytes，之後是 32 bytes。這其中的差異蠻有趣的，尤其是舊版的 string 只要一個 pointer 的大小，於是就找了一下資料並記錄下來。

從 API 來從推論 std::string 的實做，最低限度要有這三個元素：

• 字串資料的指標 (char* string::data())
• 字串大小 (size_t string::size())
• 字串指向的指標容量 (size_t string::capacity())

寫成程式就是這樣：

1struct string {
2	char *data;
3	size_t size;
4	size_t capacity;
5};

在 64-bit 系統中，這應該是用掉 24 bytes，到底怎麼會跑出 24 或是 8 bytes？這是因為 g++ stl 實做中的效能都經過了大量的優化，兩種大小對應到不同的優化實做，本文接著討論兩種（簡化過的）實做的不同。

g++ 5 之後的 std::string

長這樣：

1struct string {
2	char *data;
3	size_t size;
4	union {
5		size_t capacity;
6		char small_buffer[16];
7	};
8};

可以看到 capacity 跟 16 bytes 的 buffer 共用一個空間，這個空間可以給小於 16 bytes 的字串使用，也就是說對於長度是 15 以下的字串，data 直接指向這個位置：

1string::string(const size_t n) {
2	data = n < 16 ? this->small_buffer : new char[n+1];
3}

而要知道 capacity() 就必須先判斷 data 到底是指向 small_buffer 還是其他地方：

1size_t string::capacity() {
2	return data == this->small_buffer ? 16 : this->capacity;
3}

因為一般程式裡面很多 string 都很短，用這個小小的 buffer 可以避免大量的 new/delete。至於為什麼 buffer size 是選 16 呢，我猜可能是因為 32 bytes 在很多 CPU 裡面都有單一指令（x86 lea 或是 ARM barrel shifter）可以快速計算。

g++ 5 之前的 std::string

8 bytes 的結構長這樣：

1struct string {
2	struct SizeAndCapacity {
3		size_t size;
4		size_t capacity;
5	}
6	char *data;
7};

等等，為什麼一個 string 只需要存 data 呢？這樣要怎麼知道字串大小？答案就是把他藏在 data 指向的空間的前面

1string::string(const size_t n) {
2	data = new char[sizeof(SizeAndCapacity)+n] + sizeof(SizeAndCapacity);
3}

這樣當我們需要 size 或是 capacity 的時候，只要去前面挖就好，在 stl 裡面的寫法也蠻簡潔的：

1size_t string::size() {
2	return reinterpret_cast<SizeAndCapacity*>(data)[-1].size;
3}

但是這樣每次要拿 size 的時候，都需要 dereference，而且也沒辦法消除小字串造成的 new/delete，所以這個作法就慢慢消失了。

補充

g++ 5 之前的 string 其實有實做 copy-on-write 機制，但是因為我發現在文章中不討論這個好像也不太會怎樣，而且 C++11 之後明文禁止 copy-on-write 實做了，所以就沒有在本文提到。