C++ - 字符串容量模式

Question

我注意到 C++ 中的字符串容量遵循以下模式：

• 初始字符串大小为 15
• 对于大于特定大小“块”的任何字符串，容量将增加一倍。

以下是长度不超过 500 的字符串的字符串容量：

15
30
60
120
240
480
960

使用以下 C++ 程序找到了容量：

#include <iostream>
#include <vector>

using namespace std;

string getstr(int len) { 
    string s = "";
    for (int i=0; i<len; i++) {
        s.append("1");
    }
    return s;
}

int main() {
    vector<int> capacities;
    int prevcap;
    for (int i=0; i<500; i++) {
        int cap = getstr(i).capacity();
        if (cap > prevcap) {
            capacities.push_back(cap);
            prevcap = cap;
        }
    }
    for (int i : capacities) {
        cout << i << endl;
    }
}

选择这个算法背后的逻辑是什么？这些数字（这里是 15 和 2）有任何意义，还是随机选择的？另外，这个算法是否因编译器而异？（这是在 Ubuntu 16.04 上用 g++ 5.4.0 编译和测试的）任何见解都表示赞赏。

Answer 1

加倍是众所周知的方法。它摊销了重新分配进行push_back恒定时间操作的成本（因为它是必需的）。添加固定大小的“明显”替代方法将进行push_back线性时间操作。不过，其他模式也是可能的，理论上任何乘法增加都是可行的，我曾经读过一篇文章，主张每增加一次容量都应取自斐波那契数列中的下一项。

我想选择 15 的初始大小是考虑到短字符串优化 (SSO)。使用 SSO，字符串数据存储在字符串对象本身中，而不是单独分配的内存中。我想 15 是这个特定实现中可以容纳的最大的短字符串。知道是什么sizeof(std::string)可能会对此有所了解。