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>точно (это то, чего, похоже, хочет ОП.   -  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 /зарезервировать   -  person 4pie0    schedule 08.09.2014
comment
@0d0a Ага. Отредактировано (но я оставлю свой неправильный комментарий, чтобы не делать глупости из остальных).   -  person dlf    schedule 08.09.2014


Ответы (1)


Нет, нет пути.

Ваш единственный вариант - написать свою собственную векторную структуру данных, и таким образом вы можете делать с ней все, что хотите (или вы можете просто скопировать реализацию библиотеки Internet/С++ и изменить то, что вам нужно, и включить этот новый вектор в свою программу) .

На самом деле вы также можете использовать массив и команду realloc.

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