StringBuilder.ToString() 的复杂度是什么？

Question

在C＃中，StringBuilder.ToString()的复杂度是什么？它是O（1），O（N）还是其他什么？

- yazanpro

---

查看源代码，你就会知道一切所需：http://referencesource.microsoft.com/#mscorlib/system/text/stringbuilder.cs#5a97da49a158a3c9 - MarcinJuraszek

@MarcinJuraszek的代码对我来说非常有趣，根据纯C#代码。那么你认为它是O(N)吗，因为分块？ - Murat Can OĞUZHAN

Answer 1

这取决于框架版本；在旧版本中，StringBuilder 直接在一个 string 上工作，因此在使用 .ToString() 时没有额外的成本： 它直接将数据交给您（这可能意味着过大，但它确实起作用）；因此是O(1)。

在新的框架版本中，它使用一个 char[] 后备缓冲区，因此现在当你使用 .ToString() 时，它可能需要复制 2 x Length 字节，使其为O(N)。

- Marc Gravell

---

有趣。这是什么时候改变的？哪些版本直接使用string？ - MarcinJuraszek

那个改变的原因是什么？ - MarcinJuraszek

它使每个Append更快，因为它推迟了工作直到字符串实际生成。这也意味着内存不需要连续（直到/除非）你生成一个实际的字符串，减少了SB在LOH上的可能性，减少了内存碎片化，并且比仅仅是内存不足而导致的内存碎片化更不容易受到OOM的影响。 - Servy

@MarcGravell 您误解了 SB 所做的复杂性。它*不仅仅是一个大缓冲区的包装器。实际上，它是 char 数组的链表，因为每个 SB 还引用了“前一个”字符串生成器。基本上，当任何给定的缓冲区用尽空间时，它不会创建一个新的缓冲区并复制现有内容（4.0 之前的方法），而是创建一个新的缓冲区 不复制任何内容，然后保留对“前一个”缓冲区的引用。ToString 遍历当前和所有先前的缓冲区，并将它们全部附加到一个大缓冲区中。 - Servy

@yazanpro现在将它放入一个循环中，并考虑不必要的 "footest"、"footesttest" 和 "footesttesttest"。 - Marc Gravell