Объем вектора STL с размером инициализации 1000 удваивается после вставки первого объекта

Question

Емкость вектора STL удваивается без видимой причины.

Я создаю вектор с начальным размером 1000, вставляю один элемент. Я ожидаю, что емкость останется 1000.

vector <int> vec(1000);

cout << "vector capacity " << (unsigned int)vec.capacity() << endl;
vec.push_back(11);

cout << "vector capacity " << (unsigned int)vec.capacity() << endl;

Вывод: вектор емкость 1000

векторный объем 2000 -> после вставки одного элемента

Answer 1

Конструктор для std :: vector создает вектор с 1000 элементами, инициализированными со значением по умолчанию, в данном случае 0. Он НЕ создает пустой вектор с пробелом для 1000 элементов, которые будут добавлены позже.

Затем вы добавляете дополнительный элемент, и таким образом size () вектора теперь равен 1001. Поскольку ему необходимо перераспределить, он удваивает выделенную емкость, чтобы амортизировать последние функции push_back ().

Answer 2

Я ожидаю, что емкость останется 1000.

Размер начинается с 1000, поэтому емкость должна быть не менее 1001.

Что касаетсяудвоение, потому что vector - это динамический массив , а удвоение емкости каждый раз, когда появляется угроза size() > capacity(), гарантирует, что вы амортизируете O (1) push_back.Чтобы процитировать Википедию:

Когда вставлено n элементов, емкости образуют геометрическую прогрессию.Расширение массива на любую постоянную пропорцию гарантирует, что для вставки n элементов в целом требуется время O ( n ), что означает, что для каждой вставки требуется постоянное время амортизации.Значение этой пропорции a приводит к пространственно-временному компромиссу: среднее время на одну операцию вставки составляет около a / ( a -1), в то время какколичество потерянных клеток ограничено сверху ( a -1) n .

Answer 3

Прежде всего, не путайте size() и capacity().

• size() дает количество элементов, содержащихся в векторе.
• capacity() дает текущее количество зарезервированных слотов памяти (сколько элементов умещается в памяти, которую вектор зарезервировал). Емкость всегда равна или больше, чем размер.

Теперь vector<int> vec(1000); создает вектор размера 1000, поэтому добавление одного элемента даст вам вектор размером 1001.

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