在类似StringBuilder的C模块中增加多少缓冲区？
在C中，我正在处理一个管理字节缓冲区的“类”，允许将任意数据附加到结尾。 我现在正在考虑自动resize，因为底层数组使用realloc调用填满。 对于曾经使用过Java或C＃ StringBuilder人来说，这应该是有意义的。 我知道如何resize。 但有没有人提出任何建议，提出每个resize增加缓冲区的数量？
显然，在浪费的空间和过多的realloc调用之间需要权衡（这可能导致过度复制）。 我看过一些建议加倍的教程/文章。 如果用户设法提供良好的初始猜测，这似乎是浪费。 是否值得尝试在平台上舍入到两个或多个对齐大小的幂？
有没有人知道Java或C＃在幕后做了什么？
在C＃中，用于增长StringBuilder使用的内部缓冲区的策略随着时间的推移而发生了变化。
解决这个问题有三种基本策略，它们具有不同的性能特征。
第一个基本策略是：
- 制作一个字符数组
- 当你用完房间时，创建一个包含k个字符的新数组，对于某些常数k。
- 将旧数组复制到新数组，并孤立旧数组。
这个策略有很多问题，其中最明显的问题是如果构建的字符串非常大，它的时间是O（n 2 ）。 假设k是一千个字符，最后一个字符串是一百万个字符。 你最终在1000,2000,3000,4000，…重新分配字符串，因此复制1000 + 2000 + 3000 + 4000 + … + 999000字符，总计复制了5000亿字符的顺序！
这种策略具有很好的特性，即“浪费”内存的数量受k的限制。
实际上，由于这个n平方问题，很少使用这种策略。
第二个基本策略是
- 制作一个数组
- 当你用完房间时，创建一个新的数组，其中包含k％多个字符，对于某些常数k。
- 将旧数组复制到新数组，并孤立旧数组。
k％通常为100％; 如果是，那么这被称为“双满时”策略。
该策略具有良好的性质，其摊销成本为O（n）。 再假设最后一个字符串是一百万字符，你从一千开始。 你可以在1000,2000,4000,8000，…复制，最后复制1000 + 2000 + 4000 + 8000 … + 512000个字符，总计复制大约一百万个字符; 好多了。
该策略具有以下特性： 无论您选择多少百分比 ，摊销成本都是线性的。
这种策略有许多缺点， 有时复制操作非常昂贵 ，并且您可能在未使用的内存中浪费高达最终字符串长度的k％ 。
第三种策略是建立一个数组的链表，每个数组大小为k。 当溢出现有数组时，将分配一个新数组并将其附加到列表的末尾。
这种策略具有很好的特性，即没有任何操作特别昂贵，浪费的总内存以k为界，并且您不需要定期在堆中定位大块。 它的缺点是最终将事物变成字符串可能很昂贵，因为链表中的数组可能具有较差的局部性。
.NET框架中的字符串构建器用于使用双倍完整策略; 它现在使用链接列表块策略。
您通常希望保持增长因子略小于黄金均值（~1.6）。 当它小于黄金均值时，丢弃的段将足够大以满足后来的请求，只要它们彼此相邻即可。 如果你的增长因子大于黄金均值，那就不会发生。
我发现将因子减少到1.5仍然可以很好地工作，并且具有易于在整数数学中实现的优点（ size = (size + (size << 1))>>1; – 使用一个不错的编译器您可以将其写为(size * 3)/2 ，它仍应编译为快速代码）。
我好像回忆起几年前在Usenet上的一次谈话，其中Dinkumware的PJ Plauger（或者也许是Pete Becker）说他们的测试比以往任何时候都要广泛得多，并得出了同样的结论（所以，对于例如，在他们的C ++标准库中实现std::vector使用1.5）。
使用扩展和收缩缓冲区时，您需要的关键属性是增大或缩小您的大小的倍数，而不是常数差异。
考虑你有一个16字节数组的情况，增加128字节的大小是过度的; 但是，如果你有一个4096字节的数组并且只增加了128个字节，你最终会复制很多。
我被教导要将数组加倍或减半。 如果你真的没有关于大小或最大值的提示，乘以2可以确保你有很长时间的容量，除非你在资源有限的系统上工作，否则最多分配两倍的空间不是太可怕了。 另外，保持2的幂可以让你使用位移和其他技巧，并且基础分配通常是2的幂。
有没有人知道Java或C＃在幕后做了什么？
查看以下链接，了解它是如何在JDK7的Java StringBuilder中完成的，特别是expandCapacity方法。 http://hg.openjdk.java.net/build-infra/jdk7/jdk/file/0f8da27a3ea3/src/share/classes/java/lang/AbstractStringBuilder.java
根据文档 ，它是特定于实现的 ，但从16开始：
此实现的默认容量为16，默认最大容量为Int32.MaxValue。
当实例的值被放大时，StringBuilder对象可以分配更多的内存来存储字符，并相应地调整容量。 例如，Append，AppendFormat，EnsureCapacity，Insert和Replace方法可以扩大实例的值。
分配的内存量是特定于实现的，如果所需的内存量大于最大容量，则抛出exception（ArgumentOutOfRangeException或OutOfMemoryException）。
基于其他一些.NET框架的东西，我建议每次达到当前容量时将它乘以1.1。 如果需要额外的空间，只需要具有EnsureCapacity的等效EnsureCapacity ，即可手动将其扩展到必要的大小。
把它翻译成C.
我可能会使用List列表。
class StringBuilder { private List> list; public Append(List listOfCharsToAppend) { list.Add(listOfCharsToAppend); } }
这样，您只需维护一个列表并按需分配内存，而不是提前分配内存。
.NET框架中的列表使用此算法：如果指定了初始容量，则会创建此大小的缓冲区，否则在添加第一个项目之前不会分配缓冲区，这会分配等于添加的项目数量的空间，但是当需要更多空间时，它会分配具有2x先前容量的新缓冲区，并将所有项从旧缓冲区复制到新缓冲区。 早期的StringBuilder使用了类似的算法。
在.NET 4中，StringBuilder分配构造函数中指定大小的初始缓冲区（默认大小为16个字符）。 当分配的缓冲区太小时，不进行复制。 相反，它将当前缓冲区填充到rim，然后创建StringBuilder的新实例，它分配大小为* MAX的缓冲区（length_of_remaining_data_to_add，MIN（length_of_all_previous_buffers，8000））*，这样至少所有剩余数据都适合新缓冲区和所有缓冲区的总大小至少加倍。 新的StringBuilder保持对旧StringBuilder的引用，因此各个实例创建缓冲区的链接列表。