На сколько 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"S. Если бы увеличить емкость на 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.