Изглежда, че всеки път, когато добавите нов елемент към std::vector
, ако няма празни елементи, броят на разпределените елементи се удвоява (поне в GCC 4.9). Мисля, че това се прави, за да се постигне амортизирана постоянна времева сложност.
Например след стартиране на този код:
v.push_back (1);
v.push_back (2);
v.push_back (3);
v.push_back (4);
v.push_back (5);
v.shrink_to_fit(); // capacity is 5 now
v.push_back (6);
std::cout << v.capacity () << std::endl;
Резултатът е 10.
В системите с ограничена памет има ли начин да се предотврати това поведение, дори ако е с цената на наказание за производителност?
Освен това, би ли било възможно да се посочи, че трябва да разпределя само фиксиран брой елементи, вместо да го удвоява?
Знам, че мога да извикам std::vector::reserve()
преди да добавя нови елементи, но изглежда бъркотия в моя случай... извикването на std::vector::shrink_to_fit()
е друг подход, но също неудобен.
shrink_to_fit
? - person juanchopanza   schedule 08.09.2014v.reserve(v.size() + 1)
, последвано отpush_back
. - person dlf   schedule 08.09.2014factor > 1
за увеличаване на размера на вектора, по-често срещаните стойности са1.5
и2
. Но не мислете, чеstd::vector
ще ви позволи да промените това (напр.: увеличаване на 5 елемента при нарастване), защото ще противоречи на стандартното време за сложност. - person NetVipeC   schedule 08.09.2014fixed number of elements
, разбирам, че се увеличава всеки път в N елемент (където N имат някаква постоянна стойност при изпълнението). Можете да използватеstd::list
. - person NetVipeC   schedule 08.09.2014std::vector
амортизира разпределението на паметта при добавяне на елементи. Както спомена @NetVipeC, коефициентите за увеличаване на размера обикновено са 1,5 или 2 (gcc). Без това имате добавяне на линейни елементи на сложност поради копия. Технически трябва да вземете предвид и сложността на разпределението на купчината. Може би имате нужда от различна структура на данните? - person Jason   schedule 08.09.2014v.reserve(v.size() + 1)
ще доведе до това, чеv.capacity()
ще бъде понеv.size() + 1
, а не < i>точно (което изглежда, че OP иска. - person Cornstalks   schedule 08.09.2014shrink_to_fit
е 5. - person jbgs   schedule 08.09.2014