На сколько vector :: resize увеличивает емкость?

Question

Насколько я знаю, стандарт C ++ не определяет, как именно увеличивается емкость вектора, когда vector :: resize требует увеличения. Но есть ли «типичная» реализация?

В частности: я не знаю, насколько большим должен быть мой вектор. Далее элементы приходят в случайном порядке. Итак, для каждого элемента у меня есть это:

if ( index >= vector.size() ) {
    vector.resize ( index + 1 );
}
vector.at ( index ) = element;

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

Answer 1

Стандарт не дает никаких гарантий об асимптотике повторных вызовов на resize(). Вполне возможно, что контейнер просто увеличит емкость до точно требуемого целевого размера. Фактически, это, вероятно, было бы желаемым поведением (то есть наименее расточительным) в большинстве стандартных случаев использования для resize() (например, когда оно просто используется один раз ).

Если вы беспокоитесь, просто реализуйте свой собственный геометрический рост:

if (index + 1 > v.size()
{
    if (v.capacity() < index + 1)
    {
        v.reserve(2 * (index + 1));   // I had 2 * capacity() here first, but
                                      // I think this version is better
    }
    v.resize(index + 1);
}

Answer 2

Как вы упомянули, то, что делает resize, в точности зависит от вашей реализации (и может меняться в разных версиях одной и той же реализации).

На совместимых реализациях push_back заставляет емкость удваиваться при каждом увеличении, и это связано с амортизируемой сложностью серии push_back.Если бы это увеличивало емкость на 1 каждый раз, сложность для N добавлений была бы O(N^2), тогда как если бы push_back удваивала емкость каждый раз, сложность для той же серии дополнений была бы только O(N)- большое дело.

Что касается вашего вопроса - если вы заранее знаете максимальный index, просто заранее выделите.В противном случае, я думаю, вам лучше с std::map:

map<int, T> M;
for (...) {
  M[index] = element;
}

Это будет иметь сложность O(N log N) для N дополнений, но не будет тратить память на индексы, которые не имеют соответствующих element s.