увеличение векторной емкости

я просто новичок в с++. В моей программе я использую вектор push_back и прохожу этот процесс много раз. Я также печатаю векторную емкость после использования push_back. вывод показывает, что емкость вектора увеличивается непосредственно с 2 до 4, а затем с 4 до 8. Это так работает или емкость должна увеличиваться на 1 каждый раз. У меня было это сомнение, потому что в одном из уроков, которые я просматривал, вывод авторов показал, что емкость вектора увеличивается на единицу, а не на степень 2.

#include<iostream>
#include<vector>

void printStack(const std::vector<int> &stack)
{
    for (const auto &element : stack)
        std::cout << element << ' ';
    std::cout << "(cap " << stack.capacity() << " size " << stack.size() << ")\n";
}

int main()
{
    std::vector<int> stack;

    printStack(stack);

    stack.push_back(5); // push_back() pushes an element on the stack
    printStack(stack);

    stack.push_back(3);
    printStack(stack);

    stack.push_back(2);
    printStack(stack);

    printStack(stack);

    stack.push_back(5); // push_back() pushes an element on the stack
    printStack(stack);

    stack.push_back(3);
    printStack(stack);

    stack.push_back(2);
    printStack(stack);

    return 0;
}

Вывод: – (колпачок 0, размер 0)

5 (кепка 1 размер 1)

5 3 (крышка 2 размер 2)

5 3 2 (крышка 4 размер 3)

5 3 2 (крышка 4 размер 3)

5 3 2 5 (крышка 4 размер 4)

5 3 2 5 3 (крышка 8 размер 5)

5 3 2 5 3 2 (крышка 8 размер 6)

Заранее спасибо.


person cecil jacob    schedule 18.05.2016    source источник
comment
Это определено реализацией.   -  person 101010    schedule 18.05.2016
comment
Так это обычно и работает (хотя фактор роста определяется реализацией и может быть всего 1 элементом). Идея состоит в том, что если вы push_back() и уже находитесь в capacity(), вектор увеличивает свою емкость на некоторую величину, чтобы избежать другого распределения при следующем вызове push_back(). Фактор роста 2 довольно распространен, хотя меньшие факторы (~ 1,5) могут работать лучше.   -  person Andrew    schedule 18.05.2016
comment
@Andrew По-прежнему амортизируется постоянное время при добавлении коэффициента меньше 2?   -  person Angew is no longer proud of SO    schedule 18.05.2016
comment
@Angew хороший вопрос. Я направлю вас на место, где я читал об этом. Короткий ответ: да.   -  person Andrew    schedule 18.05.2016
comment
@Andrew В этом месте просто утверждается утверждение (любой коэффициент больше 1 гарантирует, что O (1) амортизирует добавочную сложность до бесконечности) без каких-либо подтверждающих доказательств. Это вполне может быть правдой, но намек на доказательство было бы неплохо.   -  person Angew is no longer proud of SO    schedule 18.05.2016
comment
@Angew, да, это позор. Возможно, это больше соответствует тому, что вы искали?   -  person Andrew    schedule 18.05.2016
comment
@ Андрей Да, этот лучше. Спасибо.   -  person Angew is no longer proud of SO    schedule 18.05.2016


Ответы (1)


Предполагается, что емкость увеличится, чтобы вектор мог содержать достаточно элементов. Как это делается в деталях, зависит от реализации.

person 463035818_is_not_a_number    schedule 18.05.2016
comment
Спасибо за помощь. - person cecil jacob; 18.05.2016