Кажется, что каждый раз, когда вы добавляете новый элемент в 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>точно (это то, чего, похоже, хочет ОП. - person Cornstalks   schedule 08.09.2014shrink_to_fit
равна 5. - person jbgs   schedule 08.09.2014