О векторах роста

Question

Прочитал Книгу: Учебник по С ++, третье издание. Стэнли Б. Липпман, Жозе Ладжои

Обнаружил 1 ошибку до сих пор.... В программе, приведенной в статье 6.3 «Как растет сам вектор», эта программа пропускает знак «<»!Данная программа: </p>

#include <vector>
#include <iostream>

int main(){
vector< int > ivec;
cout < "ivec: size: " < ivec.size()
< " capacity: "  < ivec.capacity() < endl;

for ( int ix = 0; ix < 24; ++ix ) {
ivec.push_back( ix );
cout < "ivec: size: " < ivec.size()
< " capacity: "  < ivec.capacity() < endl;
}    
}

Теперь я исправил проблему.Позже в этой статье книга говорит следующее: «При реализации Rogue Wave размер и емкость ivec после его определения равны 0. Однако при вставке первого элемента емкость ivec равна 256, а его размер равен 1».

Но, исправляя и выполняя код, я получаю следующий вывод:

---

ivec: size: 0 capacity: 0
ivec[0]=0 ivec: size: 1 capacity: 1
ivec[1]=1 ivec: size: 2 capacity: 2
ivec[2]=2 ivec: size: 3 capacity: 4
ivec[3]=3 ivec: size: 4 capacity: 4
ivec[4]=4 ivec: size: 5 capacity: 8
ivec[5]=5 ivec: size: 6 capacity: 8
ivec[6]=6 ivec: size: 7 capacity: 8
ivec[7]=7 ivec: size: 8 capacity: 8
ivec[8]=8 ivec: size: 9 capacity: 16
ivec[9]=9 ivec: size: 10 capacity: 16
ivec[10]=10 ivec: size: 11 capacity: 16
ivec[11]=11 ivec: size: 12 capacity: 16
ivec[12]=12 ivec: size: 13 capacity: 16
ivec[13]=13 ivec: size: 14 capacity: 16
ivec[14]=14 ivec: size: 15 capacity: 16
ivec[15]=15 ivec: size: 16 capacity: 16
ivec[16]=16 ivec: size: 17 capacity: 32
ivec[17]=17 ivec: size: 18 capacity: 32
ivec[18]=18 ivec: size: 19 capacity: 32
ivec[19]=19 ivec: size: 20 capacity: 32
ivec[20]=20 ivec: size: 21 capacity: 32
ivec[21]=21 ivec: size: 22 capacity: 32
ivec[22]=22 ivec: size: 23 capacity: 32
ivec[23]=23 ivec: size: 24 capacity: 32

---

Следовательно, начальная емкость увеличивается с формулой 2 ^ N неэто ?? Где N - начальная емкость.Пожалуйста, объясните.

Answer 1

Скорость роста емкости вектора зависит от реализации.Реализации почти всегда выбирают экспоненциальный рост, чтобы удовлетворить требование амортизированное постоянное время для операции push_back.Что означает амортизированное постоянное время и как экспоненциальный рост достигает этого, интересно.

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

Это, вероятно, кажется немного странным,поэтому позвольте мне объяснить вам, как это работает ...

• размер: 1 емкость 1 - элементы не были скопированы, стоимость одного элемента для копий равна 0.
• размер:2 емкость 2 - Когда емкость вектора была увеличена до 2, первый элемент должен был быть скопирован.Среднее количество копий на элемент составляет 0,5
• размер: 3 емкости 4 - Когда емкость вектора была увеличена до 4, первые два элемента пришлось скопировать.Среднее количество копий на элемент составляет (2 + 1 + 0) / 3 = 1.
• размер: 4 емкости 4 - Среднее количество копий на элемент составляет (2 + 1 + 0 + 0) / 4 = 3/4 =0,75.
• размер: 5 емкостей 8 - Среднее количество копий на элемент составляет (3 + 2 + 1 + 1 + 0) / 5 = 7/5 = 1,4
• ...
• размер: 8 емкостей 8 - Среднее количество копий на элемент (3 + 2 + 1 + 1 + 0 + 0 + 0 + 0) / 8 = 7/8 = 0,875
• размер: 9 емкостей 16- Среднее количество копий на элемент составляет (4 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 0) / 9 = 15/9 = 1,67
• ...
• размер 16емкость 16 - среднее количество копий на элемент равно 15/16 = 0,938
• размер 17 емкость 32 - среднее количество копий на элемент составляет 31/17 = 1,82

Как видно, каждый раземкость увеличивается, количество копий увеличивается на предыдущий размер массива.Но поскольку размер массива должен удвоиться, прежде чем емкость снова увеличится, количество копий на элемент всегда остается меньше 2.

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

Я подозреваю, что реализация выберет 1,5 вместо 2, чтобы сэкономить немногопространства, но и потому, что 1,5 ближе к золотое сечение .У меня есть интуиция (которая в настоящее время не подкреплена какими-либо достоверными данными), что скорость роста в соответствии с золотым сечением (из-за его связи с последовательностью Фибоначчи) окажется наиболее эффективной скоростью роста для реальных нагрузок.с точки зрения минимизации как используемого дополнительного пространства, так и времени.

Answer 2

Чтобы быть в состоянии обеспечить амортизированное постоянное время вставок в конце std::vector, реализация должна увеличивать размер вектора (при необходимости) на коэффициент K>1 (*), так что при попытке добавить к полному вектору размера N вектор увеличивается до K*N.

В разных реализациях используются разные константы K, которые предоставляют разные преимущества, в частности, большинство реализаций используют либо K = 2, либо K = 1.5. Чем выше K, тем быстрее, так как для этого потребуется меньше , увеличивается , но в то же время он будет оказывать большее влияние на память. Например, в gcc K = 2, а в VS (Dinkumware) K = 1.5.

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

Answer 3

Просто добавим математическое доказательство сложности времени на vector::push_back, скажем, размер вектора равен n, нас интересует количество копий, скажем, y, обратите внимание на копию происходит каждый раз, когда вы выращиваете вектор.

Рост в K

раза

  y = K^1 + K^2 + K^3 ... K^log(K, n)
K*y =     + K^2 + K^3 ... K^log(K, n) + K*K^log(K, n)

K*y-y = K*K^log(K, n) - K
y = K(n-1)/(K-1) = (K/(K-1))(n-1)

T(n) = y/n = (K/(K-1)) * (n-1)/n < K/(K-1) = O(1)

K/(K-1) является константой, и видим наиболее распространенные случаи:

• K = 2, T (n) = 2 / (2-1) = 2
• K = 1,5, T (n) = 1,5 / (1,5-1) = 3

и на самом деле есть причина выбора K как 1,5 или 2 в различных реализациях, см. Этот график : при достижении T(n) минимума, когда K составляет около 2, особой выгоды нет при использовании большего K за счет выделения большего объема памяти

Рост на постоянное количество C

y = C + 2*C + 3*C + 4*C +  ... (n/C) * C
  = C(1+2+3+...+n/C), say m = n/C
  = C*(m*(m-1)/2)
  = n(m-1)/2

T(n) = y/n = (n(m-1)/2)/n = (m-1)/2 = n/2C - 1/2 = O(n)

Как мы могли видеть, это лайнер

Answer 4

Используете ли вы реализацию "Rogue Wave"?

Как растет мощность, зависит от реализации.Твое использование 2 ^ N.

Answer 5

Емкость vector полностью зависит от реализации, никто не может сказать, как она растет ..

Answer 6

Да, емкость удваивается при каждом превышении.Это зависит от реализации.