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

Question

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

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

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

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

Спасибо!

Answer 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;
}

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

Answer 2

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