Как реализуется класс StringBuilder? Внутренне ли он создает новые строковые объекты каждый раз, когда мы добавляем?

Question

Как реализуется класс StringBuilder? Внутренне ли он создает новые строковые объекты каждый раз, когда мы добавляем?

Answer 1

В .NET 2.0 он использует String класс внутренне. String является только неизменным за пределами пространства имен System, поэтому StringBuilder может это сделать.

В .NET 4.0 String было изменено, чтобы использовать char[].

В 2,0 StringBuilder выглядел как этот

public sealed class StringBuilder : ISerializable 
{ 
    // Fields 
    private const string CapacityField = "Capacity"; 
    internal const int DefaultCapacity = 0x10; 
    internal IntPtr m_currentThread; 
    internal int m_MaxCapacity; 
    internal volatile string m_StringValue; // HERE ---------------------- 
    private const string MaxCapacityField = "m_MaxCapacity"; 
    private const string StringValueField = "m_StringValue"; 
    private const string ThreadIDField = "m_currentThread"; 

Но в 4.0 это выглядит следующим образом:

public sealed class StringBuilder : ISerializable 
{ 
    // Fields 
    private const string CapacityField = "Capacity"; 
    internal const int DefaultCapacity = 0x10; 
    internal char[] m_ChunkChars; // HERE -------------------------------- 
    internal int m_ChunkLength; 
    internal int m_ChunkOffset; 
    internal StringBuilder m_ChunkPrevious; 
    internal int m_MaxCapacity; 
    private const string MaxCapacityField = "m_MaxCapacity"; 
    internal const int MaxChunkSize = 0x1f40; 
    private const string StringValueField = "m_StringValue"; 
    private const string ThreadIDField = "m_currentThread"; 

Так, очевидно, это было изменено с помощью string с помощью char[].

EDIT: Обновлен ответ, чтобы отразить изменения в .NET 4 (что я только что открыл).

Answer 2

Не совсем - он использует внутренний буфер символов. Только когда емкость буфера будет исчерпана, он будет выделять новый буфер. Операция добавления будет просто добавлена ​​в этот буфер, строковый объект будет создан, когда на него вызывается метод ToString(). В дальнейшем его рекомендуется для многих конкатенаций строк, поскольку каждая традиционная строка concat op создаст новую строку. Вы также можете указать начальную емкость строкового построителя, если у вас есть приблизительное представление об этом, чтобы избежать множественных распределений.

Редактировать: Люди указывают, что мое понимание неверно. Игнорируйте ответ (я, а не удалить его - он будет стоять как доказательство моего невежества :-)

Answer 3

Если я смотрю на .NET Reflector на .NET 2, то я нахожу это:

public StringBuilder Append(string value) 
{ 
    if (value != null) 
    { 
     string stringValue = this.m_StringValue; 
     IntPtr currentThread = Thread.InternalGetCurrentThread(); 
     if (this.m_currentThread != currentThread) 
     { 
      stringValue = string.GetStringForStringBuilder(stringValue, stringValue.Capacity); 
     } 
     int length = stringValue.Length; 
     int requiredLength = length + value.Length; 
     if (this.NeedsAllocation(stringValue, requiredLength)) 
     { 
      string newString = this.GetNewString(stringValue, requiredLength); 
      newString.AppendInPlace(value, length); 
      this.ReplaceString(currentThread, newString); 
     } 
     else 
     { 
      stringValue.AppendInPlace(value, length); 
      this.ReplaceString(currentThread, stringValue); 
     } 
    } 
    return this; 
} 

Таким образом, это экземпляр мутировали строка ...

EDIT За исключением .NET 4 это a char[]

Answer 4

Если вы хотите увидеть одну из возможных реализаций (это похоже на ту, что поставляется с реализацией microsoft до версии 3.5), вы можете увидеть the source of the Mono one на github.

Answer 5

Я сделал небольшой пример, чтобы продемонстрировать, как StringBuilder работает в .NET 4. Договор

public interface ISimpleStringBuilder 
{ 
    ISimpleStringBuilder Append(string value); 
    ISimpleStringBuilder Clear(); 
    int Lenght { get; } 
    int Capacity { get; } 
} 

И это очень простая реализация

public class SimpleStringBuilder : ISimpleStringBuilder 
{ 
    public const int DefaultCapacity = 32; 

    private char[] _internalBuffer; 

    public int Lenght { get; private set; } 
    public int Capacity { get; private set; } 

    public SimpleStringBuilder(int capacity) 
    { 
     Capacity = capacity; 
     _internalBuffer = new char[capacity]; 
     Lenght = 0; 
    } 

    public SimpleStringBuilder() : this(DefaultCapacity) { } 

    public ISimpleStringBuilder Append(string value) 
    { 
     char[] data = value.ToCharArray(); 

     //check if space is available for additional data 
     InternalEnsureCapacity(data.Length); 

     foreach (char t in data) 
     { 
      _internalBuffer[Lenght] = t; 
      Lenght++; 
     } 

     return this; 
    } 

    public ISimpleStringBuilder Clear() 
    { 
     _internalBuffer = new char[Capacity]; 
     Lenght = 0; 
     return this; 
    } 

    public override string ToString() 
    { 
     //use only non-null ('\0') characters 
     var tmp = new char[Lenght]; 
     for (int i = 0; i < Lenght; i++) 
     { 
      tmp[i] = _internalBuffer[i]; 
     } 
     return new string(tmp); 
    } 

    private void InternalExpandBuffer() 
    { 
     //double capacity by default 
     Capacity *= 2; 

     //copy to new array 
     var tmpBuffer = new char[Capacity]; 
     for (int i = 0; i < _internalBuffer.Length; i++) 
     { 
      char c = _internalBuffer[i]; 
      tmpBuffer[i] = c; 
     } 
     _internalBuffer = tmpBuffer; 
    } 

    private void InternalEnsureCapacity(int additionalLenghtRequired) 
    { 
     while (Lenght + additionalLenghtRequired > Capacity) 
     { 
      //not enough space in the current buffer  
      //double capacity 
      InternalExpandBuffer(); 
     } 
    } 
} 

Этот код не резьбовое безопасно, не делает никакой проверки ввода и не использует внутреннюю (небезопасную) магию System.String. Однако он демонстрирует идею класса StringBuilder.

Некоторые модульные тесты и полный образец кода можно найти по адресу github.

Answer 6

Принятый ответ пропускает отметку на милю.Значительное изменение на StringBuilder в 4.0 не является изменением от небезопасного string до char[] - это факт, что StringBuilder is теперь фактически связанный список StringBuilder экземпляров.

---

Причина этого изменения должны быть очевидны: теперь никогда не нужно перераспределять буфер (дорогостоящая операция, так как, наряду с выделения больше памяти, вы должны скопировать все содержимое из старый буфер к новому).

Это означает, что вызов ToString() теперь немного медленнее, так как конечная строка должна быть вычислена, но делать большое количество Append() операций теперь значительно быстрее. Это соответствует типичному прецеденту для StringBuilder: много звонков на Append(), за которым следует один звонок до ToString().

---

Вы можете найти контрольные отметки here. Вывод? Новый связанный список StringBuilder использует немного больше памяти, но значительно быстрее для типичного прецедента.