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)有什么意义吗?还是随机选择的？此外，这个算法是否因编译器而异？(这是在Ubuntu16.04上用g++ 5.4.0编译和测试的)任何见解都是值得赞赏的。

Answer 1

加倍是一种众所周知的方法。它分摊了重新分配的成本，使push_back成为一个固定时间的操作(根据需要)。添加固定大小的“明显”替代将使push_back成为线性时间操作。其他模式是可能的，任何乘性的增加理论上都是可行的，我曾经读过一篇文章，主张每增加一次容量都应该从Fibonacci序列中的下一项开始。

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