Как StringBuilder решает, насколько большой его потенциал должен быть?

Я знаю, что объект StringBuilder выделяет больше памяти, когда вы используете sb.Append(..), когда sb уже имеет емкость. Но насколько увеличивается эта мощность?

    StringBuilder sb = new StringBuilder(5);
    sb.Append("0123456789");

Теперь какова способность sb и почему? Что такое множитель?

Просто для ясности. Я спрашиваю о емкости, а не о длине.

Спасибо!

Ответы

Ответ 1

Емкость удваивается каждый раз, кроме некоторых особых случаев:

  • Если удвоения недостаточно, емкость увеличивается до требуемой суммы.
  • Существует верхний предел - 0x7fffffff.

Вы можете увидеть алгоритм с помощью .NET Reflector или загрузить исходный источник.

Я не могу опубликовать исходный код для официальной реализации .NET, но вот код для реализации Mono:

// Try double buffer, if that doesn't work, set the length as capacity
if (size > capacity) {

    // The first time a string is appended, we just set _cached_str
    // and _str to it. This allows us to do some optimizations.
    // Below, we take this into account.
    if ((object) _cached_str == (object) _str && capacity < constDefaultCapacity)
        capacity = constDefaultCapacity;

    capacity = capacity << 1;  // This means "capacity *= 2;"

    if (size > capacity)
        capacity = size;

    if (capacity >= Int32.MaxValue || capacity < 0)
        capacity = Int32.MaxValue;

    if (capacity > _maxCapacity && size <= _maxCapacity)
        capacity = _maxCapacity;
}

Я также рекомендовал бы, чтобы вы не писали код, который опирается на этот конкретный алгоритм, поскольку он является деталью реализации, а не тем, что гарантируется интерфейсом.

Ответ 2

Это экспоненциальный рост (в частности, удвоение с каждым перераспределением), чтобы позволить ряду добавок принимать O (N) время вместо O (N²) времени.