std::vector и разпределение на паметта

Изглежда, че всеки път, когато добавите нов елемент към 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() е друг подход, но също неудобен.


person jbgs    schedule 08.09.2014    source източник
comment
Всъщност проверихте ли капацитета след обаждането до shrink_to_fit?   -  person juanchopanza    schedule 08.09.2014
comment
За да избегнете (намалите) бъркотията, можете да напишете своя собствена безплатна функция, която взема вектор и елемент за добавяне и след това прави v.reserve(v.size() + 1), последвано от push_back.   -  person dlf    schedule 08.09.2014
comment
защо не използвате масив в този случай (ако имате нужда от фиксиран размер)   -  person 4pie0    schedule 08.09.2014
comment
@0d0a Мисля, че jbgs иска фиксиран темп на растеж, а не фиксиран размер.   -  person dlf    schedule 08.09.2014
comment
Съгласно стандартното добавяне и елементът към вектора трябва да се амортизира постоянно време, това се получава само, като се използва factor > 1 за увеличаване на размера на вектора, по-често срещаните стойности са 1.5 и 2. Но не мислете, че std::vector ще ви позволи да промените това (напр.: увеличаване на 5 елемента при нарастване), защото ще противоречи на стандартното време за сложност.   -  person NetVipeC    schedule 08.09.2014
comment
@dlf, fixed number of elements, разбирам, че се увеличава всеки път в N елемент (където N имат някаква постоянна стойност при изпълнението). Можете да използвате std::list.   -  person NetVipeC    schedule 08.09.2014
comment
Отговорът на вашия въпрос е много прост. Не и не. Вече знаете решението на проблема си, но не желаете да го използвате, така че няма да си правя труда да го обяснявам.   -  person Benjamin Lindley    schedule 08.09.2014
comment
std::vector амортизира разпределението на паметта при добавяне на елементи. Както спомена @NetVipeC, коефициентите за увеличаване на размера обикновено са 1,5 или 2 (gcc). Без това имате добавяне на линейни елементи на сложност поради копия. Технически трябва да вземете предвид и сложността на разпределението на купчината. Може би имате нужда от различна структура на данните?   -  person Jason    schedule 08.09.2014
comment
Бихте могли да увеличите::static_vector boost.org/doc/libs/1_55_0/doc/html/container/   -  person Adam Kosiorek    schedule 08.09.2014
comment
@dif: v.reserve(v.size() + 1) ще доведе до това, че v.capacity() ще бъде поне v.size() + 1, а не < i>точно (което изглежда, че OP иска.   -  person Cornstalks    schedule 08.09.2014
comment
@juanchopanza: да, капацитетът след обаждане на shrink_to_fit е 5.   -  person jbgs    schedule 08.09.2014
comment
@dlf Cornstalks е прав en.cppreference.com/w/cpp/container/vector /reserve   -  person 4pie0    schedule 08.09.2014
comment
@0d0a Да. Редактирано (но ще оставя неправилния си коментар, за да избегна глупостите от останалите).   -  person dlf    schedule 08.09.2014


Отговори (1)


Не, няма начин.

Единствената ви възможност е да напишете своя собствена векторна структура от данни и по този начин можете да правите каквото искате с нея (или можете просто да копирате имплементация на интернет/c++ библиотеката и да промените това, от което се нуждаете, и да включите този нов вектор във вашата програма) .

Всъщност можете също да използвате масив и командата realloc.

person tomer.z    schedule 08.09.2014
comment
Как използвате масив заедно с realloc? - person ; 09.09.2014