固定長度的數據結構很簡單，大家每天都在用。
可變長度數據結構，都可以通過內嵌對象的形式，轉化成固定長度的數據結構，大家每天也都在用，例如：
struct person
{
int id;
string name;
string address;
};
每個 person 對象的長度是固定的，但是，其內嵌的 name 和 address 是變長的。從而，整個對象佔據的總空間也是變長的。
但是，將這樣的的對象平坦化，使之只佔據一塊連續空間，使用的人很少，因為在絕大多數情況下，很少有人思考這個問題，並且，大多數問題已經使用內嵌數據結構解決掉了。
然而，如果內存很緊張，或者需要處理得數據量非常大，這種方式浪費的內存就太多了。假定我們現在創建了一個 map<int, person> ，在gcc4.1 的 64位環境中，按8字節對齊，這個 map 總共會佔用多少內存呢？
1. sizeof(map) = 48
2. sizeof(string) = 8
3. sizeof(person) = 24
4. sizeof(person_node) = alignto(24 + 32(rbtree node overhead), 8) = 56
5. sizeof(string_node) = 8*3(refcount, size_endptr, capacity_endptr)
6. memsizeof(string) = sizeof(string_node) + alignto(strlen + 1, 8)
7. memsizeof(person_node) = sizeof(person_node) + memsizeof(name) + memsizeof(address)如果 avg(name) = 10, avg(address) = 20
實際佔用的空間，大約還要再加上4：avg(name) = 14, avg(address) = 24
那麼 memsizeof(person_node) = 56 + 24*2 + 14 + 24 = 142
那麼該map 實際佔用空間（gcc 的每個 map 還有一個虛結點:32個字節）：
48+32+n*142 = 80+n*142
如果使用一種理想的變長數據結構，再加上紅黑樹的優化(none virtual node, compressed color, no parentptr)，需要多少內存呢？
1. sizeof(map) = 16
2. memsizeof(person_node) = alignto(16(treenode) + 4(id) + 2*1(strlen) + 10(name) + 20(address) = 52, 8) = 56
memsizeof(map) = 16 + 56*n
內存一下節省了 60% 還多，也就是説，如果內存大小已經固定，可以裝入 2.5 倍的數據。
- 如果用來做集羣緩存，可以節省50%的機器（系統也要佔一些內存）。
- 如果有5.6G的內存可用，就可以裝入1億條數據。
- 並且，在節省了60%內存的同時，還有另外一種好處：提高cache命中率，如果3個字段訪問的頻率相同，cpu的 cache miss 會降低3倍。
- 可以預見，因為cache miss降低，map.find 速度會大幅提高。
這個可變數據結構可以這樣設計：
struct person2
{
int id;
unsigned char nName, nAddress;
char data[1];
// not terminated with '/0'
const char* getName() const { return data; }
const char* getAddress() const { return data + nName; }
int getSize() const { return offsetof(person, data) + nName + nAddress; }
};
更復雜的情況：
- 如果nName 和 nAddress 要大於 255 呢？——把 unsigned char 改成 unsigned short, 甚至 unsigned int
- 如果person的字段很多，例如有20個字段：
struct person3
{
int id;
string name;
string address;
string ex1;
string ex2;
string ex3;
string ex4;
string ex5;
// more...
// var data structure:
// unsigned char nName, nAddress, nEx1, nEx2;
// const char* getEx1() const { return data + nName + nAddress; }
// const char* getEx2() const { return data + nName + nAddress + nEx1; }
// const char* getEx3() const { return data + nName + nAddress + nEx1 + nEx2; }
// const char* getEx4() const { return data + nName + nAddress + nEx1 + nEx2 + nEx3; }
// const char* getEx5() const { return data + nName + nAddress + nEx1 + nEx2 + nEx3 + nEx4; }
// more...
};
這就不光是寫代碼的複雜了，運行時字段訪問的性能也成問題！性能問題可以用另外一種方式——使用直接定位——來解決。
struct person4
{
int id;
string name;
string address;
string ex1;
string ex2;
string ex3;
string ex4;
string ex5;
// more...
// var data structure:
// unsigned short pAddress, pEx1, pEx2, pEx3, pEx4, pEor;
// char data[1];
// const char* getName() const { return data + 0; }
// const char* getAddress() const { return data + pAddress; }
// const char* getEx1() const { return data + pEx1; }
// const char* getEx2() const { return data + pEx2; }
// const char* getEx3() const { return data + pEx3; }
// const char* getEx4() const { return data + pEx4; }
// const char* getEx5() const { return data + pEx5; }
// more...
// int sizeEx1() const { return pEx2 - pEx1; }
// int sizeEx2() const { return pEx3 - pEx2; }
// int sizeEx3() const { return pEx4 - pEx3; }
// int sizeEx4() const { return pEx5 - pEx4; }
// int sizeEx5() const { return pEor - pEx5; }
};
如果需要變長數據的數組，怎麼辦？簡單，offset array + data byte array，具體實現方式與 person4 類似，只不過 offset array 元素需要使用更寬的整數。
